Roulette wheel selection, finding pocket without sorting

Question

I am currently attempting to implement a java roulette wheel selection (see http://en.wikipedia.org/wiki/Fitness_proportionate_selection).

My problem comes after finding the relative fitness for each individual of my population.

For example, Say I create a probalistic roulette such as :

individual a : 0 - 0.3 individual b : 0.3 - 0.5 individual c : 0.5 - 1

Whereas individual a has a 30% change of being selected, b has 20% and c has 50% of being selected was I to spin this roulette.

My problem is, the wikipedia article mention "Note performance gains can be achieved by using a binary search rather than a linear search to find the right pocket." implying that after generating my random number, I have to complete a linear or binary search of my pockets to find which one has been selected.

The thing is, from a performance point of view this binary search to find the right pocket at each turn seems unnecessary, wouldn't it be possible to simply have some kind of HashMap whereas each entry in the table is linked to the range as shown above and pulling using a key within that range would pull out the associated individual in linear time instead of requiring a binarysearch.

Ive looked at the treemap, but the treemap has to initialy sort the pockets which is a no go, no sorting.

Answer 1

Well maybe this code of Roulette wheel selection in java can ghet you started to get all you can get Chromosome class here

import java.util.*; // Random, Arrays, Vector, List
import java.io.*;   // BufferedWriter, FileWriter


/**
 * <code>Evolution</code> implements the genetic algorithm.
 *
 * This is an executable class that uses the <code>Chromosome<code>
 * class to implement the genetic algorithm.  It can be run with the
 * following command line calls:
 * <UL>
 * <LI>java Evolution ones population_size chromosome_size generations crossover_rate mutation_rate logfile
 * <LI>java Evolution binary population_size chromosome_size generations crossover_rate mutation_rate logfile binary_number
 * </UL>
 * <P>
 * Where the parameters are:
 * <UL>
 * <LI><B>ones</B>: use the number of ones in the gene sequence as the
 * fitness function
 * <LI><B>binary</B>: measure the closeness of the gene sequence to a binary
 * number for the fitness function
 * <LI><B>chromosome_size</B>: an int number of genes in each chromosome
 * <LI><B>generations</B>: an int number of generations to produce
 * <LI><B>crossover_rate</B>: a double gene crossover rate between 0 and 1
 * <LI><B>mutation_rate</B>: a double gene mutation rate between 0 and 1
 * <LI><B>logfile</B>: a String name for the log file
 * <LI><B>binary_number</B>: an int to be used as the binary number for
 * the binary number fitness function
 * </UL>
 * <P>
 * Some example command line calls:
 * <UL>
 * <LI>java Evolution ones 100 20 100 0.7 0.001 ones.log
 * <LI>java Evolution binary 100 20 100 0.7 0.001 binary.log 3755865
 * </UL>
 * <P>
 * This class implements a "roulette wheel" selection method, based on each
 * chromosome's fitness value.  The genetic operators are single-point
 * crossover and point-mutation.  To boost the selectiveness of each
 * generation, the <code>threshold</code> value in the <code>selection</code>
 * method can be set to an arbitrary fitness value, or to the average
 * fitness value, etc.
 * <P>
     */
public class Evolution
    {


    /**
     * holds the best fitness value of a population for a particular
     * generation
     */
    private int best_fit = 0;


    /**
     * holds the sum of the fitness values of the population for a particular
     * generation
     */
    private int total_fit = 0;


    /**
     * holds the population
     */
    private Vector population = null;


    /**
     * holds the "roulette odds" for each individual in a generation.  Each
     * index corresponds to an individual in the population, and each value
     * represents the sum of the fitness values for that individual and all
     * the prior ones in the population.  The "roulette wheel" algorithm is
     * performed by choosing a random number between zero and
     * <code>total_fit</code> (inclusive).  This number is then searched for
     * in the <code>roulette</code> array.  The index which contains the
     * random number or the next higher number is the individual chosen for
     * that "spin of the roulette wheel."
     *
     * @see #selection(double)
     */
    private int roulette[] = null;


    /**
     * holds onto a <code>Random</code> object
     *
     * @see java.util.Random
     */
    private Random rand = null;


    /**
     * a double between 0 and 1 (inclusive) that represents the rate at which
     * crossover occurs in selected individuals
     */
    private double crossover_rate = 0;


    /**
     * a double between 0 and 1 (inclusive) that represents the rate at which
     * mutation occurs in selected individuals
     */
    private double mutation_rate  = 0;



    /**
     * Constructor for <code>Evolution</code> that use the total number of
     * ones in a <code>Chromosome</code>'s gene sequence as its fitness
     * function.
     *
     * @param pop_size   a positive <code>int</code> number of
     *                   chromosomes in the population for each generation
     * @param chrom_size a positive <code>int</code> number of genes in each
     *                   <code>Chromosome</code> object's gene sequence
     * @param pc         the crossover rate; this should be a
     *                   <code>double</code> value between zero and one
     *                   (inclusive)
     * @param pc         the mutation rate; this should be a
     *                   <code>double</code> value between zero and one
     *                   (inclusive)
     *
     * @see #crossover_rate
     * @see #mutation_rate
     * @see Chromosome#Chromosome(int, java.util.Random)
     */
    public Evolution(int pop_size, int chrom_size, double pc, double pm)
        {
        Chromosome c   = null;
        total_fit      = 0;
        best_fit       = 0;
        crossover_rate = pc;
        mutation_rate  = pm;

        // make population and roulette mapping
        population = new Vector(pop_size);
        roulette   = new int[pop_size];

        // seed the random number generator
        rand = new Random(System.currentTimeMillis());

        // make population
        for (int i = 0; i < pop_size; i++)
            {
            c = new Chromosome(chrom_size, rand);

            // update fitness information
            total_fit = total_fit + c.get_fit();
            best_fit = Math.max(best_fit, c.get_fit());

            // add chromosome to population and roulette wheel
            population.add(c);
            roulette[i] = total_fit;
            }
        }



    /**
     * Constructor for <code>Evolution</code> that use the proximity of
     * a <code>Chromosome</code>'s gene sequence to a <code>target</code>
     * sequence as the fitness function.
     *
     * The <code>Chromosome</code>s made in this <code>Evolution</code> have
     * gene sequences equal to <code>target.length</code>.  The fitness
     * function walks through the indexes of <code>target</code> and the
     * given chromosome's gene sequence, and adds one to that chromosome's
     * fitness for each gene that has the same value as <code>target</code>.
     *
     * @param pop_size   a positive <code>int</code> number of
     *                   chromosomes in the population for each generation
     * @param target     a <code>boolean</code> array whose length will be
     *                   used as the length for all <code>Chromosome</code>s
     *                   made by this <code>Evolution</code>; this parameter's
     *                   value will be used by the <code>Chromosome</code>s'
     *                   fitness functions
     * @param pc         the crossover rate; this should be a
     *                   <code>double</code> value between zero and one
     *                   (inclusive)
     * @param pc         the mutation rate; this should be a
     *                   <code>double</code> value between zero and one
     *                   (inclusive)
     *
     * @see #crossover_rate
     * @see #mutation_rate
     * @see Chromosome#Chromosome(boolean[], java.util.Random)
     */
    public Evolution(int pop_size, boolean[] target, double pc, double pm)
        {
        Chromosome c   = null;
        total_fit      = 0;
        best_fit       = 0;
        crossover_rate = pc;
        mutation_rate  = pm;

        // make population
        population = new Vector(pop_size);
        roulette   = new int[pop_size];

        // seed the random number generator
        rand = new Random(System.currentTimeMillis());

        // make population
        for (int i = 0; i < pop_size; i++)
            {
            c = new Chromosome(target, rand);

            // update fitness information
            total_fit = total_fit + c.get_fit();
            best_fit = Math.max(best_fit, c.get_fit());

            // add chromosome to population and roulette wheel
            population.add(c);
            roulette[i] = total_fit;
            }
        }



    /**
     * Probablistically selects <code>Chromosome</code>s from this
     * <code>Evolution</code>'s <code>population</code> using the
     * code "roulette wheel" algorithm.
     *
     * This method returns a new <code>List</code> of individuals from the
     * previous population who have been probabalistically selected based
     * on their fitness.  To do this, this method randomly picks a value
     * between zero and <code>total_fit</code> (inclusive).  It then
     * searches for this value in <code>roulette</code>, which is an
     * <code>int</code> array the same length as the number of individuals
     * in <code>population</code>.  Each index in <code>roulette</code>
     * corresponds to an individual in the population, and each value in
     * the array is the sum of the the fitness values of all the
     * individuals before it, plus the fitness value of the current
     * individual.  A search is done on <code>roulette</code> for the
     * randomly generated number.  If the number is equal to or less than a
     * value in the array, but greater than the value in the previous index,
     * that index is selected, and the individual that corresponds to that
     * index is added to the selected population.
     * <P>
     * Often, this function is not "selective" enough.  For that reason, one
     * can set the <code>threshold</code> parameter.  No individual with a
     * fitness function less than the threshold will be added to the new
     * population.  For the simple roulette behavior described above, the
     * <code>threshold</code> should be set to zero. Else, it could be
     * set to the average fitness, or any other arbitrary value.  If it is
     * set higher than the fitness of the most fit individual in this
     * population, the method will enter an infinite loop.
     *
     * @param threshold  a <code>double</code> fitness value; individuals
     *                   fitness values below this value are guaranteed not
     *                   to added to the <code>List</code> of selected
     *                   individuals.  This value must be less than or equal
     *                   to the fitness of the most fit individual in the
     *                   population, or this method will enter an infinite
     *                   loop.
     *
     * @return           a <code>List</code> of length equal to the size of
     *                   the current <code>population</code> composed of
     *                   individuals probabalistically selected from the
     *                   current <code>population</code>
     */
    public List selection(double threshold)
        {
        int        index        = 0;
        int        random_int   = 0;
        int        size         = population.size();
        Vector     selected_pop = new Vector(size);
        Chromosome selected     = null;

        // make population
        for (int i = 0; i < size; i++)
            {

            // roulette wheel selection
            random_int = rand.nextInt(total_fit + 1);
            index = Arrays.binarySearch(roulette, random_int);
            if (index < 0)
                {
                index = Math.abs(index + 1);
                }

            // get selected chromosome
            selected = (Chromosome)(population.get(index));

            // ignore if chromosome doesn't meet fitness threshold
            if (selected.get_fit() < threshold)
                {
                i--;
                }

            // else add chromosome to new selected population
            else
                {
                selected_pop.add(selected.getCopy());
                }
            }

        return selected_pop;
        }



    /**
     * Accepts a <code>List</code> of <code>Chromosomes</code>, performs
     * crossover and mutation operations on them with some probability,
     * recomputes each <code>Chromosome</code>'s fitness value,
     * recomputes the <code>total_fit</code>, <code>best_fit</code>, and
     * </code>roulette</code>, and then sets the <code>population</code>
     * to this <code>List</code> of new <code>Chromosome</code>.
     *
     * This method performs two basic functions: crossover and mutation.
     * It first clears <code>total_fit</code> and <code>best_fit</code>.
     * In the crossover step, the first and second <code>Chromosome</code>
     * are selected for crossover, the third and fourth, etc.  If there is
     * an odd number in the list, the last <code>Chromosome</code> is not
     * crossed.  Crossover occurs only with the probability given by the
     * <code>crossover_rate</code>.  This method assumes that the
     * elements in the input <code>List</code> were already selected
     * randomly, and thus makes no effort to randomly select individuals
     * from the input <code>List</code> for crossover.
     * <P>
     * Mutation occurs after crossover.  Each element is examined and
     * has a chance of being point-mutated with a probability given by
     * the <code>mutation_rate</code>.  After the<code>Chromosome</code>
     * is or is not mutated, its fitness is recomputed and
     * <code>total_fit</code>, <code>best_fit</code> and
     * <code>roulette</code> are updated accordingly.
     * <P>
     * After the mutation step, the <code>population</code> is given the
     * value of the <code>List</code> of mutated and crossed
     * <code>Chromosome</code>s.
     *
     * @param threshold  a <code>List</code> of <code>Chromosome</code>s to
     *                   be crossed and mutated
     *
     * @see #crossover_rate
     * @see #mutation_rate
     * @see Chromosome#crossover(Chromosome, Chromosome, java.util.Random)
     * @see Chromosome#mutate(Chromosome, java.util.Random)
     */
    public void reproduction(List selected_pop)
        {
        int    size         = selected_pop.size();
        int    half_size    = ((size + 1) / 2);
        Chromosome parent1 = null;
        Chromosome parent2 = null;

        // reset fitness statistics
        best_fit = 0;
        total_fit = 0;

        // crossover
        for (int i = 1; i < half_size; i++)
            {
            if (rand.nextDouble() <= crossover_rate)
                {
                parent1 = (Chromosome)(selected_pop.get(i * 2));
                parent2 = (Chromosome)(selected_pop.get((i * 2) - 1));
                Chromosome.crossover(parent1, parent2, rand);
                }
            }

        // mutation, and update fitness and roulette
        for (int i = 0; i < size; i++)
            {
            parent1 = (Chromosome)(selected_pop.get(i));
            if (rand.nextDouble() <= mutation_rate)
                {
                Chromosome.mutate(parent1, rand);
                }

            // update fitness information
            total_fit = total_fit + parent1.get_fit();
            best_fit = Math.max(best_fit, parent1.get_fit());

            // update roulette
            roulette[i] = total_fit;
            }

        // set the population to this new population
        population = new Vector(selected_pop);
        }



    /**
     * Creates a binary representation <code>boolean</code> array of
     * an input <code>int</code>.
     *
     * This method makes a <code>boolean</code> array of a length
     * specified by the <code>length</code> parameter, with the binary
     * representation of the <code>number</code> parameter, where
     * <code>true</code> represents one, and <code>false</code>
     * represents zero.  The least signifiant bits are at the start of
     * the array, and if the number ends before the end of the array,
     * subsequent bits are zero.  If the length of the array is less
     * than the number of bits needed to represent the input digit,
     * the most significant bits past the length of the array are
     * truncated.
     *
     * @param number   an <code>int</code> to be encoded into binary
     * @param length   the length of the binary array
     *
     * @return         a <code>boolean</code> array representation of
     *                 the <code>number</code> parameter in binary
     */
    public static boolean[] toBinary(int number, int length)
        {
        boolean result[] = new boolean[length];


        for (int i = (length - 1); i >= 0; i--)
            {
            if ((number % 2) == 1)
                {
                result[i] = true;
                }
            else
                {
                result[i] = false;
                }
            number = (number / 2);
            }

        return result;
        }



    /**
     * Evolves this evolution object through the given number of generations,
     * printing the results of each generation to stdout and to a log file.
     *
     * This method is basically a glorified loop, with a lot of string
     * manipulation for the print statements.  Note that you can set the
     * threshold parameter for the <code>selection</code> method in this
     * method.  It will loop and print out the results for the number of
     * generations specifed by the parameter <code>generations</code>.
     *
     * @param generations an <code>int</code> number of generations to
     *                    print results for
     * @param log         a <code>BufferedWriter</code> attached to a
     *                    log file, for writing results to a log
     *
     * @throws IOException thrown if there is an error writing to 
     *                     the log file
     *
     * @see java.io.BufferedWriter
     * @see #selection(double)
     * @see #reproduction(java.util.List)
     */
    public void evolve(int generations, BufferedWriter log) throws IOException
        {
        StringBuffer buffer    = null;
        double       average   = 0;
        double       threshold = 0;

        // print header info to screen and file
        buffer = new StringBuffer();
        buffer.append("Generations: ");
        buffer.append(generations);
        buffer.append("\tPopulation Size: ");
        buffer.append(population.size());
        buffer.append("\tCrossover Rate: ");
        buffer.append(crossover_rate);
        buffer.append("\tMutation Rate: ");
        buffer.append(mutation_rate);
        System.out.println(buffer.toString());
        log.write(buffer.toString() + "\n");

        // make new generations
        for (int i = 0; i <= generations; i++)
            {
            average = total_fit / (double)(population.size());

            // print to screen
            buffer = new StringBuffer();
            buffer.append("Generation: ");
            buffer.append(i);
            buffer.append("\tBest Fitness: ");
            buffer.append(best_fit);
            buffer.append("\tAverage Fitness: ");
            buffer.append(average);
            System.out.println(buffer.toString());

            // log to file
            buffer = new StringBuffer();
            buffer.append(i);
            buffer.append("\t");
            buffer.append(best_fit);
            buffer.append("\t");
            buffer.append(average);
            buffer.append("\n");
            log.write(buffer.toString());

            // create new generation
            threshold = 0;
            reproduction(selection(threshold));
            }
        }



    /**
     * Execute method for <code>Evolution</code>.
     *
     * The syntax for running this method at the command line is included in
     * the class comments for <code>Evolution</code>.  This method takes an
     * array of <code>String</code> arguments and, depending on the
     * arguments, makes a new <code>Evolution</code> that uses either the
     * number-of-ones or the binary number fitness function.  It creates
     * a log file, and then calls <code>evolve</code> to do the work.  Any
     * exception that is thrown in this process is caught, a stack trace is
     * printed, and the program exits.
     *
     * @param args    an array of <code>String</code> parameters from the
     *                command line
     *
     * @see #Evolution
     */
    public static void main(String args[])
        {
        Evolution      evolution       = null;
        int            pop_size        = 0;
        int            chromosome_size = 0;
        int            generations     = 0;
        double         crossover_rate  = 0;
        double         mutation_rate   = 0;
        BufferedWriter log             = null;
        int            number          = 0;
        boolean[]      binary          = null;

        try
            {

            // get command line parameters 
            pop_size        = Integer.parseInt(args[1]);
            chromosome_size = Integer.parseInt(args[2]);
            generations     = Integer.parseInt(args[3]);
            crossover_rate  = Double.parseDouble(args[4]);
            mutation_rate   = Double.parseDouble(args[5]);
            log             = new BufferedWriter(new FileWriter(args[6]));

            if (args[0].equals("ones") && (args.length == 7))
                {
                evolution = new Evolution(pop_size, chromosome_size, crossover_rate, mutation_rate);
                }
            else if (args[0].equals("binary") && (args.length == 8))
                {
                number = Integer.parseInt(args[7]);
                binary = Evolution.toBinary(number, chromosome_size);
                evolution = new Evolution(pop_size, binary, crossover_rate, mutation_rate);
                }
            else
                {
                System.err.println("Usage: java Evolution ones <population_size> <chromosome_size> <generations> <crossover_rate> <mutation_rate> <logfile>");
                System.err.println("Usage: java Evolution binary <population_size> <chromosome_size> <generations> <crossover_rate> <mutation_rate> <logfile> <binary_number>");
                System.exit(1);
                }

            evolution.evolve(generations, log);
            log.flush();
            log.close();
            }
        catch (Exception e)
            {
            e.printStackTrace();
            System.err.println("Usage: java Evolution ones <population_size> <chromosome_size> <generations> <crossover_rate> <mutation_rate> <logfile>");
            System.err.println("Usage: java Evolution binary <population_size> <chromosome_size> <generations> <crossover_rate> <mutation_rate> <logfile> <binary_number>");
            System.exit(1);
            }
        }
    }

Chromosome.java

import java.util.*; // Random


/**
 * <code>Chromosome</code> is a wrapper class for a bit vectory representing
 * an individual in a population for a genetic algorithm.
 *
 * This class has three main functions: First, it holds the "genetic"
 * information for an individual in a genetic algorithm population.  This
 * information takes the form of a bit vector, represented as a boolean
 * array.  Second, it computes and holds the fitness value for the
 * individual represented by a particular instantiation of this class.
 * Currently, there are two fitness functions available, which are described
 * later.  Finally, it provides static functions for the recombination of
 * gene sequences.
    */
public class Chromosome implements Cloneable
    {


    /**
     * the target gene sequence, if the fitness function is
     * <code>binary_number</code>
     */
    private boolean target[];


    /**
     * the bit vector representing the gene sequence
     */
    private boolean genes[];


    /**
     * the fitness value for this <code>Chromosome</code>
     */
    private int fit = 0;



    /**
     * Constructor for <code>Chromosomes</code> that use the
     * <code>number_of_ones</code> fitness function.
     *
     * @param length    the length of the gene sequence this
     *                  <code>Chromosome</code> will contain
     * @param rand      a <code>Random</code> object
     *
     * @see #no_of_ones()
     * @see java.util.Random
     */
    public Chromosome(int length, Random rand)
        {
        genes = new boolean[length];
        rand_sequence(rand);

        // fitness = the number of ones
        target = null;
        fitness();
        }



    /**
     * Constructor for <code>Chromosomes</code> that use the
     * <code>binary_number</code> fitness function.
     *
     * @param in_target the length of the gene sequence this
     *                  <code>Chromosome</code> will contain
     * @param rand      a <code>Random</code> object
     *
     * @see #binary_number()
     * @see java.util.Random
     */
    public Chromosome(boolean[] in_target, Random rand)
        {
        genes = new boolean[in_target.length];
        rand_sequence(rand);

        // fitness = closeness to a binary number
        target = in_target;
        fitness();
        }



    /**
     * Returns a copy of this <code>Chromosome</code> obtained from the
     * <code>clone</code> method in <code>java.lang.Object</code>.
     *
     * @return  a new <code>Chromosome</code> object with exactly the same
     *          values as this <code>Chromosome</code> object
     *
     * @see java.lang.Object#clone()
     */
    public Chromosome getCopy()
        {
        Chromosome copy = null;

        try
            {
            copy = (Chromosome)(this.clone());
            }
        catch (Exception e)
            {
            e.printStackTrace();
            }

        return copy;
        }



    /**
     * Returns the fitness value for this <code>Chromosome</code>.
     *
     * @return  a non-negative <code>int</code> representing the fitness of
     *          this <code>Chromosome</code> object
     *
     * @see #fit
     */
    public int get_fit()
        {
        return fit;
        }



    /**
     * Prints the fitness and gene sequence of this <code>Chromosome</code>
     * to stdout.
     */
    public void print()
        {
        StringBuffer buffer = new StringBuffer();

        // print fitness
        buffer.append("fitness: ");
        buffer.append(fit);
        buffer.append("\t");

        // print gene genes
        buffer.append("[");
        for (int i = 0; i < genes.length; i++)
            {
            if (genes[i])
                {
                buffer.append(1);
                }
            else
                {
                buffer.append(0);
                }
            if (i < (genes.length - 1))
                {
                buffer.append(" ");
                }
            }
        buffer.append("]");

        System.out.println(buffer.toString());
        }



    public static void crossover(Chromosome parent1, Chromosome parent2, Random rand)
        {
        int cross_point = rand.nextInt(parent1.genes.length);
        boolean swap_buff = true;

        for (int i = 0; i <= cross_point; i++)
            {
            swap_buff = parent1.get(i);
            parent1.set(i, parent2.get(i));
            parent2.set(i, swap_buff);
            }

        // update fitness
        parent1.fitness();
        parent2.fitness();
        }




    public static void mutate(Chromosome parent, Random rand)
        {
        int index = rand.nextInt(parent.genes.length);

        // mutate at index
        parent.set(index, !parent.get(index));

        // update fitness
        parent.fitness();
        }



    /**
     * Returns the gene at <code>index</code> in <code>genes</code>.
     *
     * @return  the <code>boolean</code> value of the gene at
     *          <code>index</code> in the <code>genes</code> array.
     *
     * @see #genes
     */
    private boolean get(int index)
        {
        return genes[index];
        }



    /**
     * Sets the gene at <code>index</code> in <code>genes</code>.
     *
     * @see #genes
     */
    private void set(int index, boolean value)
        {
        genes[index] = value;
        }




    private void fitness()
        {

        // choose proper fitness function
        if (target == null)
            {
            no_of_ones();
            }
        else
            {
            binary_number();
            }
        }




    private void rand_sequence(Random rand)
        {
        for (int i = 0; i < genes.length; i++)
            {
            genes[i] = rand.nextBoolean();
            }
        }


    private void binary_number()
        {
        int count = 0;

        // count genes that are the same as the target
        for (int i = 0; i < genes.length; i++)
            {
            if (genes[i] == target[i])
                {
                count++;
                }
            }

        // set fitness
        fit = count;
        }




    private void no_of_ones()
        {
        int count = 0;

        // count genes that are true
        for (int i = 0; i < genes.length; i++)
            {
            if (genes[i])
                {
                count++;
                }
            }

        // set fitness
        fit = count;
        }

    }

Answer 2

With n=1.000 individuals and selecting k=100 of them, you can do

• 100 binary searches, O(k logn)
• or 1.000 puts in a Tree, HashMap or some other data structure, O(n+k)

Only testing will tell what is faster, performance depends on n, k and the implementations.

Answer 3

HashMap allows find elements by exact value of a key only. Your algorithm requires find a value by a range. So, using a binary search or the TreeMap will give you O(log(n)) complexity. I don't think it's possible to have better complexity.

And I don't understand what are you talking about. Looks like you are saying that linear search has better performance than TreeMap or binary search. It's wrong.