java - 订购另一个人的 Collection

Question

我有两个 ArrayList 集合，我们将它们称为 A 和 B。 A 是 B 的子集，并且 A 的元素少于 B (A大约有 10% 的元素 B)。但是，A 中的元素排序方式与 B 中的元素排序方式不同，而我需要它们的排序方式。

我可以想出一种算法，按照原始集合中的方式对它们进行排序。我要问的是，是否有一些好的方法可以做到这一点，也许是 JDK 的一部分或 Apache Commons 的一部分。

Answer 1

您需要一个比较器，根据较大列表中的索引来比较较小列表中的对象。

当然有多种选择可以实现这一点。

一种非常简单但非常效率低下的方法是创建一个比较器，用largerList.indexOf(element)检查元素的索引。但是，除了最小的列表之外，这对于所有列表来说都会有可怕的运行时间。

更复杂的解决方案是存储从元素到较大列表中索引的映射，以便可以直接查找索引。这将显着更快，但代价是 map 需要一些额外的存储空间。

这两种方法都作为示例实现:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class SameOrderTest
{
    public static void main(String[] args)
    {
        List<String> listA = new ArrayList<String>();
        listA.add("S");
        listA.add("A");
        listA.add("M");
        listA.add("P");
        listA.add("L");
        listA.add("E");
        listA.add("W");
        listA.add("O");
        listA.add("R");
        listA.add("D");

        List<String> listB = new ArrayList<String>();
        listB.add("A");
        listB.add("M");
        listB.add("S");
        listB.add("E");
        listB.add("L");

        List<String> listB0 = new ArrayList<String>(listB);
        Collections.sort(listB0, simpleSameOrderComparator(listA));

        List<String> listB1 = new ArrayList<String>(listB);
        Collections.sort(listB1, efficientSameOrderComparator(listA));

        System.out.println("A : "+listA);
        System.out.println("B0: "+listB0);
        System.out.println("B1: "+listB1);
    }

    // WARNING: Simple but VERY inefficient
    private static <T> Comparator<T> simpleSameOrderComparator(
        final List<T> reference)
    {
        return new Comparator<T>()
        {
            @Override
            public int compare(T t0, T t1)
            {
                return reference.indexOf(t0)-reference.indexOf(t1);
            }
        };
    }

    private static <T> Comparator<T> efficientSameOrderComparator(
        final List<T> reference)
    {
        final Map<T, Integer> map = new LinkedHashMap<T, Integer>();
        for (int i=0; i<reference.size(); i++)
        {
            map.put(reference.get(i), i);
        }
        return new Comparator<T>()
        {
            @Override
            public int compare(T t0, T t1)
            {
                return map.get(t0)-map.get(t1);
            }
        };
    }

}

我很好奇是否有一种解决方案既不影响排序算法的运行时间，又不需要额外的存储空间。如果较小列表的大小仅为 10%，则可以反转查找并仅存储实际包含在较小列表中的元素的索引，但在这种情况下，运行时间将取决于较小列表的大小。列表和大小的比例，而且很难事先判断这是否会得到返回。

<小时/>

编辑:受到 answer of Eugene Kuleshov 的启发(+1)，我创建了一个使用他的方法的测试，但使用的是集合而不是列表:它的运行时间应该为 O(m+n)，其中 m 和 n 是列表的大小。

(EDIT2:根据评论更新)

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class SameOrderTest2
{
    public static void main(String[] args)
    {
        List<String> listA = new ArrayList<String>();
        listA.add("S");
        listA.add("A");
        listA.add("M");
        listA.add("P");
        listA.add("L");
        listA.add("E");
        listA.add("W");
        listA.add("O");
        listA.add("R");
        listA.add("D");

        List<String> listB = new ArrayList<String>();
        listB.add("A");
        listB.add("M");
        listB.add("S");
        listB.add("E");
        listB.add("L");

        List<String> listB0 = sorted(listA, listB);
        System.out.println("A : "+listA);
        System.out.println("B0: "+listB0);
    }

    private static <T> List<T> sorted(List<T> reference, List<T> toSort)
    {
        List<T> referenceList = new ArrayList<T>(reference);
        referenceList.retainAll(new LinkedHashSet<T>(toSort));
        return referenceList;
    }


}

这也需要额外的存储空间，但非常简洁和优雅，如果您可以为第二个列表创建一个新实例，并且不必就地对其进行排序。