3

给定一个 KeyValuePairs 列表，其中每对都有一个getValue()方法，获得一个List（或Set）唯一值的最快方法是什么？

以下所有内容都会产生可接受的结果。u1似乎比预期的列表大小（大约 1000-2000 KVP）最快

我们可以做得更好（更快）吗？

private static Set<String> u1(List<_KVPair> pairs) {
    Set<String> undefined = new HashSet<String>();

    for (_KVPair pair : pairs) {
        undefined.add(pair.getValue());
    }

    if (undefined.size() == 1) {
        return new HashSet<String>();
    }
    return undefined;
}

private static List<String> u2(List<_KVPair> pairs) {

    List<String> undefined = new ArrayList<String>();
    for (_KVPair pair : pairs) {
        if (!undefined.contains(pair.getValue())) {
            undefined.add(pair.getValue());
        }
    }

    return undefined;
}

private static List<String> u3(List<_KVPair> pairs) {

    List<String> undefined = new LinkedList<String>();

    Iterator<_KVPair> it = pairs.iterator();
    while (it.hasNext()) {
        String value = it.next().getValue();
        if (!undefined.contains(value)) {
            undefined.add(value);
        }
    }
    return undefined;
}

在大约 3600 对时，'u3' 获胜。在大约 1500 对时，'u1' 获胜

4

6 回答 6

7

第一个选项应该更快。您可以通过在使用之前调整集合大小来使其更快。通常，如果您预计会有少量重复：

Set<String> undefined = new HashSet<String>(pairs.size(), 1);

请注意，我使用 1 作为负载因子以防止任何调整大小。

出于好奇，我进行了测试（下面的代码） - 结果是（编译后）：

测试 1（注意：预热需要几分钟）

原始列表的大小 = 3,000，没有重复：
设置：8数组列表
：668
链接列表：1166

测试 2

原始列表的大小 = 30,000 - 所有字符串相同：
设置：25数组列表
：11
链接列表：13

这种说法是有道理的：

  • 当有很多重复时，List#contains将运行得相当快，因为​​会更快地找到重复并且分配大集合的成本+散列算法正在惩罚
  • 当没有重复或重复很少时，该组以很大的优势获胜。
public class TestPerf {

    private static int NUM_RUN;
    private static Random r = new Random(System.currentTimeMillis());
    private static boolean random = false; //toggle to false for no duplicates in original list


    public static void main(String[] args) {

        List<String> list = new ArrayList<>();

        for (int i = 0; i < 30_000; i++) {
            list.add(getRandomString());
        }

        //warm up
        for (int i = 0; i < 10_000; i++) {
            method1(list);
            method2(list);
            method3(list);
        }

        NUM_RUN = 100;
        long sum = 0;
        long start = System.nanoTime();
        for (int i = 0; i < NUM_RUN; i++) {
            sum += method1(list);
        }
        long end = System.nanoTime();
        System.out.println("set: " + (end - start) / 1000000);

        sum = 0;
        start = System.nanoTime();
        for (int i = 0; i < NUM_RUN; i++) {
            sum += method2(list);
        }
        end = System.nanoTime();
        System.out.println("arraylist: " + (end - start) / 1000000);

        sum = 0;
        start = System.nanoTime();
        for (int i = 0; i < NUM_RUN; i++) {
            sum += method3(list);
        }
        end = System.nanoTime();
        System.out.println("linkelist: " + (end - start) / 1000000);

        System.out.println(sum);
    }

    private static int method1(final List<String> list) {
        Set<String> set = new HashSet<>(list.size(), 1);
        for (String s : list) {
            set.add(s);
        }
        return set.size();
    }

    private static int method2(final List<String> list) {
        List<String> undefined = new ArrayList<>();
        for (String s : list) {
            if (!undefined.contains(s)) {
                undefined.add(s);
            }
        }
        return undefined.size();
    }

    private static int method3(final List<String> list) {
        List<String> undefined = new LinkedList<>();

        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String value = it.next();
            if (!undefined.contains(value)) {
                undefined.add(value);
            }
        }
        return undefined.size();
    }

    private static String getRandomString() {
        if (!random) {
            return "skdjhflkjrglajhsdkhkjqwhkdjahkshd";
        }
        int size = r.nextInt(100);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            char c = (char) ('a' + r.nextInt(27));
            sb.append(c);
        }
        System.out.println(sb);
        return sb.toString();
    }
}
于 2012-09-25T14:45:58.683 回答
2

更新：见下面的编辑

当你可以做的时候，迭代列表是没有意义的

return new HashSet<_KVPair>(pairs)

最糟糕的选择是 u2 和 u3，您将第一个列表中的项目添加到第二个列表并调用List.contains(item)循环的每次迭代。此操作方法O(n^2)-List.contains(item)需要将项目与可能的整个列表进行比较。避免需要迭代列表并调用一些也迭代列表的操作的算法。

如果您想要独特的物品，请使用Set. 如果您需要按排序顺序排列这些项目，请使用 a TreeSet，否则 99% 的时间您需要 a HashSet。

编辑：我错过了你想要一套pair.getValue()；但无论如何建议都是一样的 - 使用 Set，不要List.contains()在循环中使用。

于 2012-09-25T14:38:56.863 回答
2

您可以u1通过将第一行更改为：

Set<String> undefined = new HashSet<String>(pairs.size());

否则，当您添加值时，该集合将在内部进行很多调整。

于 2012-09-25T14:44:48.830 回答
1

我敢说选项 1 是最快和最干净的。在检查值是否已经包含在那里方面，很难击败哈希集。

基于列表的解决方案不会像之前的答案中所说的那样扩展

于 2012-09-25T14:44:13.907 回答
1

另一种方法可能是Sort list在一个循环中，如果引用相等，您可以通过保留添加的最后一个元素的引用来消除重复项不要添加到新列表，否则添加

Collections.sort(pairs)//O(n log n)

Loop
if(!lastAdded.equals(pairs.get(i)))
 {
   //Add to list 
   //change lastAdded
 }
于 2012-09-25T14:53:08.630 回答
-1

给出的答案都没有从最终结果中删除重复项，它们只是删除了重复项。因此，如果一个字符串出现两次，它仍然会出现在最终结果中，但只会出现一次。如果那不是必需的，那么是的，我刚刚浪费了五分钟...

 public Map<String, String> countOccurences(List<String> source){
       Map<String, Integer> result =   new HashMap<>(source.size());
        int temp =0;
        for (String value : source) {
            if(result.containsKey(value)){
                temp = result.get(value);
                temp++;
                result.put(value, temp);
                temp = 0;
            }
            else {
                result.put(value, 1);
            }
        }
    }
    public List<String> sublistSingles(Map<String, Integer> results){
        List<String> duplicatesRemoved = new ArrayList<>(results.size());
        for(Map.Entry<String, Integer> result:results.entrySet()){
            if(result.getValue().equals(1)){
              duplicatesRemoved.add(result.getKey());
            }
        }
        return duplicatesRemoved;
    }
于 2012-09-25T15:04:59.490 回答