Randomly Select Object from a Set Performance

I mentioned in my last post that there were two ways to randomly select an object from a set in Java.

Option 1 - cycling through the set until we reached a randomly selected position
OR
Option 2 - converting the set to a list and directly grabbing a randomly selected position

Option 2 seems the fastest of the two options, but only when the set is large.  If we are randomly selecting an object the average position selection will be the middle value.

Notice here that randomly selecting a number between 1 and 10 a million times yields an average number of 5.498191.

int total = 0;
        for (int i = 0; i < 1000000; i++) {
            int num = randomGenerator.nextInt(10) + 1;
            total += num;
        }
       
        double avgNum = (total * 1.0)/1000000.0;
        System.out.println("Avg Random Number from 1 - 10: " + avgNum);

Thus I wrote a method that predicts at what set size we should abandon Option 1 and start using Option 2.  This size, of course, depends on different OS specifications, JVM initialization parameters, and machine hardware.

    public long getRecommendedSetSizeLimit() {
        long recommendation = -1;

        long accuracy = DEFAULT_SET_SIZE_ACCURACY;
        if (ApplicationLoader.INSTANCE.doesApplicationPropertyExist(SET_SIZE_ACCURACY_PROPERTY_NAME)) {
            final String property = ApplicationLoader.INSTANCE.getApplicationProperty(SET_SIZE_ACCURACY_PROPERTY_NAME);
            if (property != null && !property.isEmpty()) {
                try {
                    accuracy = Long.parseLong(property);
                } catch (Exception e) {
                    LOGGER.warn("unable to parse property " + SET_SIZE_ACCURACY_PROPERTY_NAME + " ()", e);
                }
            }
        }

        long acceptanceMilliseconds = DEFAULT_METHOD_ACCEPTANCE_DIFFERENCE_MILLISECONDS;
        if (ApplicationLoader.INSTANCE.doesApplicationPropertyExist(METHOD_ACCEPTANCE_DIFFERENCE_PROPERTY_NAME)) {
            final String property = ApplicationLoader.INSTANCE.getApplicationProperty(METHOD_ACCEPTANCE_DIFFERENCE_PROPERTY_NAME);
            if (property != null && !property.isEmpty()) {
                try {
                    acceptanceMilliseconds = Long.parseLong(property);
                } catch (Exception e) {
                    LOGGER.warn("unable to parse property " + METHOD_ACCEPTANCE_DIFFERENCE_PROPERTY_NAME + " ()", e);
                }
            }
        }

        long setSize = 10000;

        do {
            final Set<Object> hugeSetOObjects = this.createSetOfRandomObjects(setSize);

            final int sizeOfSet = hugeSetOObjects.size();
            final int halfSizeOfSet = sizeOfSet / 2;

            LOGGER.info("Size of set being evaluated: " + sizeOfSet);

            final Date start1 = new Date();
            for (int i = 0; i < 500; i++) {
                this.selectMiddleObjectInSet(hugeSetOObjects, halfSizeOfSet);
            }
            final Date end1 = new Date();
            final long diff1 = end1.getTime() - start1.getTime();
            LOGGER.info("Time to Execute (set process): " + diff1);

            final Date start2 = new Date();
            for (int i = 0; i < 500; i++) {
                this.convertSetToListAndSelectMiddleInList(hugeSetOObjects, halfSizeOfSet);
            }
            final Date end2 = new Date();
            final long diff2 = end2.getTime() - start2.getTime();
            LOGGER.info("Time to execute (list process): " + diff2);

            long diff = diff1 - diff2;
            if (diff < 0) {
                diff = diff * -1;
            }

            if (diff1 > diff2) {
                LOGGER.warn("Difference between methods: " + diff);
                LOGGER.warn("Consider lowering the application property (acceptanceDiffMilliseconds)");
            }

            if (diff > acceptanceMilliseconds && diff1 > diff2) {
                recommendation = hugeSetOObjects.size();
                break;
            } else if (setSize >= 1000000) {
                recommendation = 1000000;
                break;
            } else {
                setSize += accuracy;
            }

        } while (true);

        return recommendation;
    }

    private Set<Object> createSetOfRandomObjects(final long size) {
        final Set<Object> hugeSetOObjects = new HashSet<>();

        for (int i = 0; i < size; i++) {
            final UUID id = UUID.randomUUID();
            hugeSetOObjects.add(id);
        }

        return hugeSetOObjects;
    }

    private Object selectMiddleObjectInSet(final Set<Object> setOfObjects,
            final int half) {

        int pos = 0;
        for (Object obj : setOfObjects) {
            if (pos == half) {
                return obj;
            } else {
                pos++;
            }
        }

        return null;
    }

    private Object convertSetToListAndSelectMiddleInList(final Set<Object> setOfObjects,
            final int half) {

        final List<Object> listCopy = new ArrayList<>();
        listCopy.addAll(setOfObjects);
        return listCopy.get(half);
    }

In my next post I will reveal the stats from different machines, operating systems, and JVM options.

Randomly Select an Object from a Set

I've seen many posts about how to randomly select an object from a set.  In Java there are only two ways to do this that make sense.

Option 1:  Select from a set by picking a random number ranging from 0 to the set's size and cycle through the set until you get to that position and return that object.

public Object randomlySelectObjectFromSetByPositionNumber(final Set<?> objects) {
        if (objects != null && !objects.isEmpty()) {
            final Random random = new Random();
            final int position = random.nextInt(objects.size());
            int pos = 0;
            for (Object tmpString : objects) {
                if (pos == position) {
                    return tmpString;
                } else {
                    pos++;
                }
            }

            LOGGER.warn("unable to select randomly from set - set exhausted");
            return null;
        } else {
            return null;
        }
    }


Options 2:  Convert the set to a list first, then pick a random number ranging from 0 to the list's size and get the object at the position.

public Object randomlySelectObjectFromList(final Set<?> objects) {
        if (objects != null && !objects.isEmpty()) {

            final List<Object> listCopy = new ArrayList<>();
            listCopy.addAll(objects);

            final Random random = new Random();
            final int position = random.nextInt(listCopy.size());
            return listCopy.get(position);
        } else {
            return null;
        }
    }


The question that should really be asked is, "Which of these is faster?"  I will investigate and explain soon...

Log4j

Most java coders are familiar with log4j setup, but in case you need an example here is one.

This log4j properties file is placed in the classpath of the application.  For a maven setup, which I prefer, place the log4j.properties file in src/main/resources directory of your java project.

# log4j properties file
log4j.rootLogger=DEBUG, file
log4j.appender.file=org.apache.log4j.RollingFileAppender
log4j.appender.file.File=${user.home}/application.log
log4j.appender.file.MaxFileSize=50MB
log4j.appender.file.MaxBackupIndex=10
log4j.appender.file.layout=org.apache.log4j.PatternLayout
log4j.appender.file.layout.ConversionPattern=%-5p %d{yyyy-MM-dd HH:mm:ss:SSS} %m%n

This specific setup will write to a log file located in the user's home directory.  I like this solution because it is operating system independent and file system structure independent.

For maven setup you will need to add the log4j dependency to your pom.xml.

<dependency>
            <groupId>log4j</groupId>
            <artifactId>log4j</artifactId>
            <version>1.2.17</version>
</dependency>

Then create the logger class object in your java class that you want to add logging to.  Make sure this is the first line in your class, right after you define the class name.

public class ApplicationLoader {
  
    private final static Logger LOGGER = Logger.getLogger(ApplicationLoader.class);


To log something just do this:

LOGGER.info(ApplicationLoader.class.getName() + " [ApplicationLoader] : begin");