Заказ коллекции другой

Question

У меня есть две коллекции ArrayList, назовем их A и B. A является подмножеством B и A имеет меньше элементов, чем B (A имеет около 10% элементов B). Однако элементы в A не упорядочены так же, как и в B, и мне они нужны.

Я могу придумать алгоритм, который будет их заказывать, как в оригинальной коллекции. Я прошу, если есть хороший способ сделать это, возможно, часть JDK или часть Apache Commons.

Answer 1

Вам нужен компаратор, который сравнивает объекты в меньшем списке в соответствии с их индексом в большем списке.

Существует несколько вариантов реализации этого.

A очень простой, но очень неэффективен один было бы создать компаратор, который проверяет индексы элементов с largerList.indexOf(element). Но это было бы horrible время работы для всех, кроме наименьших списков.

Более сложным решением было бы хранить отображение от элементов к их индексу в большем списке, чтобы индексы могли быть просмотрены напрямую. Это будет значительно быстрее, за дополнительную плату для 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%, можно отменить поиск и сохранить индексы элементов, которые действительно содержатся в меньшем списке, но в этом случае время выполнения будет зависеть от размеров списки и соотношение размеров, и трудно сказать заранее, будет ли это окупаться.

---

EDIT: Вдохновленный answer of Eugene Kuleshov (+1), я создал тест, который использует свой подход, но с набором вместо списка: Он должен иметь время работы O (т + п), где 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; 
    } 


} 

Это также требует дополнительного хранения, но очень сжато и элегантный, если вы можете создать новый экземпляр для второго списка, и Дон» t должен сортировать его на месте.

Answer 2

Вы можете скопировать большую коллекцию, а затем вызвать retainAll() метод удаления недостающих элементов, сохраняя порядок:

ArrayList result = new ArrayList(B).retainAll(A); 

Эффективно это будет вызывать на вашей коллекции A, так и для больших коллекций, Set будет выполнять лучше, чем и ArrayList.