轮盘选择，无需排序即可找到口袋

Question

我目前正在尝试实现java轮盘赌选择（参见http://en.wikipedia.org/wiki/ Fitness_proportionate_selection）。

我的问题是在找到我的人口中每个人的相对适合度之后出现的。

例如，假设我创建了一个概率轮盘，例如：

个体 a : 0 - 0.3 个体b：0.3-0.5 个人 c ： 0.5 - 1

如果我旋转这个轮盘赌，个人 a 的被选择率有 30% 的变化，b 有 20%，c 有 50% 的被选择率。

我的问题是，维基百科文章提到“请注意，通过使用二分搜索而不是线性搜索来找到正确的口袋，可以实现性能提升。”这意味着在生成随机数后，我必须对我的口袋完成线性或二分搜索才能找到已选择的数字。

问题是，从性能的角度来看，这种每次都找到正确口袋的二分搜索似乎是不必要的，难道不可能简单地拥有某种 HashMap，而表中的每个条目都链接到如图所示的范围上面并使用该范围内的键拉动将在线性时间内拉出关联的个体，而不需要二分搜索。

我查看了树形图，但树形图必须首先对口袋进行排序，这是不行的，不能排序。

Answer 1

对于 n=1.000 个人并选择其中 k=100，您可以进行

• 100 次二分搜索，O(k logn)
• 或 1.000 次放入树、HashMap 或其他数据结构中，O(n+k)

只有测试才能知道什么更快，性能取决于 n、k 和实现。

Answer 2

好吧，也许这段 Java 中的轮盘赌选择代码可以让您入门
获得所有你能得到的这里的染色体类

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 3

HashMap 允许仅通过键的精确值查找元素。您的算法需要按范围查找值。因此，使用二分搜索或 TreeMap 会给您带来 O(log(n)) 复杂度。我认为不可能有更好的复杂性。

我不明白你在说什么。看起来你是说线性搜索比 TreeMap 或二分搜索具有更好的性能。这是错误的。