Performance der Durchschnittsberechnung bei Java Collection

Vor einigen Tagen bin ich über einen Optimierungsversuch bei der Bestimmung von Durchschnitten von Listen in Java gestolpert, der mich neugierig gemacht hat. Anstatt die Methode retainAll zu benutzen, wurde dort eine scheinbar verbesserte Version implementiert, die zunächst die längere der beiden Listen bestimmt, diese dann sortiert und danach jedes Element der kleineren Liste mit binärer Suche in der größeren sucht:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private List<Long> intersectListsBySorting( List<Long> l1, List<Long> l2 )
{
   List<Long> smaller, bigger;
 
   if ( l1.size( ) >= l2.size( ) )
   {
      smaller = l2;
      bigger = l1;
   }
   else
   {
      smaller = l1;
      bigger = l2;
   }
 
   Collections.sort( bigger );
   final Iterator<Long> iteratorOverSmaller = smaller.iterator( );
   while ( iteratorOverSmaller.hasNext( ) )
   {
      final Long e = iteratorOverSmaller.next( );
 
      if ( Collections.binarySearch( bigger, e ) < 0 )
      {
         iteratorOverSmaller.remove( );
      }
   }
 
   return smaller;
}

Um die Motivation dahinter zu verstehen, schaut man sich die Implementierung der Methode retainAll in der Klasse AbstractCollection an. Dort findet man eine Schleife über alle Elemente der Collection, innerhalb der mit der Methode contains geprüft wird, ob dieses Element in der zweiten Collection vorhanden ist. Wenn nein, wird es aus der ersten Collection entfernt. Die Methode contains ist wiederum als Schleife über alle Elemente implementiert. Jetzt könnte man tatsächlich auf die Idee kommen, dass ein Sortieren der Liste helfen könnte, um von einem linearen Aufwand für das Suchen zu einem logarithmischen Aufwand zu kommen. Allerdings braucht natürlich das Sortieren wiederum Zeit. Bei kleineren Collections mit nur wenigen hundert Elementen, war die Variante mit dem Sortieren langsamer und erst bei Collections mit vielen tausend Elementen um Faktor 2-3 schneller.

Wenn man statt Listen nun Sets nimmt, umgeht man das Problem der linearen Suche in der Methode contains. Ein Set wird als Map gespeichert, so dass ein Zugriff auf ein Element ohne Suche möglich ist. Ein Vergleich der Performance von retainAll zwischen Listen und Sets zeigt auch, dass die Implementierung für Sets unabhängig von der Größe ca. 10-20 mal schneller ist.

Interessant ist nun folgendes: wenn man als Ausgangspunkt Listen hat, dann ist bei einer Größe von mehreren Tausend Elementen selbst das Kopieren der Listen in Sets und das anschließende Arbeiten mit Sets schneller als das Arbeiten mit Listen.