比较两个数组列表以保留它们之间的增量的有效方法

Question

这是我遇到的问题：

我需要比较两个 ArrayList 和 return 如果它们相同或不同，return 来自其中之一的新元素，可以说是枢轴。

这是数据集的行为：

这两个 ArrayList 由字符串组成
它们来自同一来源，因此大部分时间都相同
已排序（在附加到它们的自定义逻辑的意义上）
永远不会有任何空字符串
所有字符串都具有相同的长度，总是
无重复

我想要的：

以最快的方式实现我的两个目标，无论哪种情况
仅使用 Java 1.6 标准库功能，我不想实现一个混合 class 来模拟 List 中的内容，然后再设置。

示例：

A: [ 'a', 'b', 'c', 'd']   

B: [ 'a', 'c', 'd']

结果：列表不同，return元素'b'； A将是'work'List，我们将根据这个ArrayList中的新内容进行比较，因为B永远不会改变。

感谢您的回复和意见。

Answer 1

你的尽可能快的要求让我很困扰——我非常反对优化——我通常认为早期优化是最糟糕的编程实践之一。

如果你真的想这样做，只需按顺序遍历两个列表即可。

如果第一个条目匹配，则将那个条目放入 "Same" 堆中并递增两个索引。如果它们不同，将第一个 (lower/less-than) 个放入 "Different" 堆中并递增列出索引。以这种方式循环，直到你到达一个列表的末尾（另一个列表中的任何剩余显然都进入 "Different" 集合。

那应该给你 "close" 最快的方法。如果你想要绝对最快，那么你必须从使用数组开始，而不是列表，然后非常注意你在每一步中还做了什么——但算法应该仍然非常接近最优。

作为次优但更具可读性的示例，您可以使用一些集合操作。

Set set1=new HashSet(list1)
Set set2=new HashSet(list2)
Set same=set1.retainAll(set2) // I forget if retainAll modifies set1--if so you need to copy it first
set1.removeAll(list2)
set2.removeAll(list1)
Set different=set1.addAll(set2)

// at this point same contains all the similar values and different contains the ones that don't match.  Done.

本文简短易读，可能比您想象的更高效。如果这样的东西运行良好（比如，在速度不太重要的 GUI 代码中），那么自己编写代码将是一种不好的做法。

Answer 2

非常简单（假设列表按升序排列，可以很容易地更改为降序）：

ArrayList<String> delta(ArrayList<String> a , ArrayList<String> b , Comparator<String> comp){
    if(a.isEmpty())
        return new ArrayList(b);
    if(b.isEmpty())
        return new ArrayList(a);

    Iterator<String> it_a = a.iterator();
    Iterator<String> it_b = b.iterator();

    ArrayList<String> delta = new ArrayList<>();

    String a_s = it_a.next() , b_s = it_b.next();
    boolean onechecked = false;

    while(!onechecked){
        int comp_v = comp.compare(a_s , b_s);

        if(comp_v == 0){
            //strings are equal -> ommit them
            if(it_a.hasNext())
                a_s = it_a.next();
            else
                onechecked = true;

            if(it_b.hasNext())
                b_s = it_b.next();
            else
                onechecked = true;
        }else if(comp_v < 0){
            //a_s is not part of b
            delta.add(a_s);
            if(it_a.hasNext())
                a_s = it_a.next();
            else
                onechecked = true;
        }else{
            //b_s is not part of a
            delta.add(b_s);
            if(it_b.hasNext())
                b_s = it_b.next();
            else
                onechecked = true;
        }
    }

    //add remaining items
    delta.add(it_a.hasNext() ? a_s : b_s);

    for(Iterator<String> it = (it_a.hasNext() ? it_a : it_b) ; it.hasNext();)
        delta.add(it.next());

    return delta;
}

抱歉没有添加任何解释，但代码必须说明一切，因为我不知道如何解释它。

比较两个数组列表以保留它们之间的增量的有效方法

Efficient way of comparing two arraylists in order to retain a delta between them

java

algorithm

arraylist

set

data-structures