java - 在恒定长度列表中插入对象 - Java

Question

我正在寻找一个好的最佳策略来为以下问题编写代码。

我有一个对象列表。

1. 对象在其他字段中具有字符串“评估”字段。评估字段可能是唯一的，也可能不是唯一的。
2. 该列表的长度是在程序内计算的恒定长度。长度通常在 100 到 500 之间。
3. 对象均根据字符串字段 - 评估在列表中排序
4. 发现或创建新对象时:将字符串字段评估与列表中的现有成员进行比较。
5. 如果比较失败，例如与列表的底部成员，则该对象不会添加到列表中。
6. 如果比较成功并且新对象被添加到列表中 - 在排序标准内；新对象被添加到正确的位置，并且底部成员被从列表中驱逐以保持列表的长度不变。

我正在考虑的一个策略:

1. 不断向列表添加成员 - 直到达到 maxLength
2. 对列表进行排序(例如使用比较器对 Collections.sort 进行排序)
3. 创建新成员时 - 将其与列表底部的成员进行比较。
4. 如果成功 - 更换底部成员，否则继续
5. 重新排序列表 - 如果成功

并继续。

程序循环了百万次甚至更多次迭代，优化比较和运行就成了问题。

有关在 Java 领域内解决此问题的良好策略的任何指导。哪些列表将是最有效的，例如LinkedList 或 ArrayLists 或 Sets 等。哪种排序/插入(标准包)最有效？

Answer 1

考虑这个基于 TreeSet 的示例并通过字符串比较结果。正如您所看到的，经过足够的迭代后，List 中只剩下具有非常大键的元素。在我相当旧的笔记本电脑上，我在不到 50 毫秒的时间内处理了 10.000 个项目 - 因此每百万列表操作需要 5 秒。

public class Valuation {

    public static class Element implements Comparable<Element> {
        String valuation;
        String data;
        Element(String v, String d) {
            valuation = v;
            data = d;
        }
        @Override
        public int compareTo(Element e) {           
            return valuation.compareTo(e.valuation);
        }       
    }

    private TreeSet<Element> ts = new TreeSet<Element>();

    private final static int LISTLENGTH = 500;

    public static void main(String[] args) {
        NumberFormat nf = new DecimalFormat("00000");
        Random r = new Random();
        Valuation v = new Valuation();
        for(long l = 1; l < 150; ++l) {
            long start = System.currentTimeMillis();
            for(int j = 0; j < 10000; ++j) {
                v.pushNew(new Element(nf.format(r.nextInt(50000))
                                , UUID.randomUUID().toString()));
            }
            System.out.println("10.000 finished in " + (System.currentTimeMillis()-start) + "ms. Set contains: " + v.ts.size());
        }
        for(Element e : v.ts) {
            System.out.println("-> " + e.valuation);
        }
    }

    private void pushNew(Element hexString) {
        if(ts.size() < LISTLENGTH) {
            ts.add(hexString);
        } else {
            if(ts.first().compareTo(hexString) < 0) {
                ts.add(hexString);
                if(ts.size() > LISTLENGTH) {
                    ts.remove(ts.first());
                }
            }
        }
    }
}