Jak efektywnie uzyskać wszystkie pary zestawów?

Question

Biorąc pod uwagę obiekt Set, chcę przejść przez wszystkie (nieuporządkowane) pary tego.

Przykład: Ustaw = {1, 2, 3}, Pary: (1, 2), (1, 3), (2, 3).

Gdy mamy do czynienia z Vector<Integer>, można to osiągnąć przy pomocy indeksu każdego elementu:

for (int i = 0; i < vector.size(); i++) 
    for (int j = i + 1; j < vector.size(); j++) 
    // Do something with vector.get(i) and vector.get(j) 

Ale elementy w Set<Integer> mają żadnych indeksów.

Najlepsze rozwiązanie, jakie dotychczas znalazłem, to przekonwertować Set na Vector i skorzystać z powyższego rozwiązania.

Czy istnieje bardziej wydajne/bezpośrednie rozwiązanie?

Answer 1

List<Integer> list = new ArrayList<Integer>(mySet); 
for (int i = 0; i < list .size(); i++) 
    for (int j = i + 1; j < list .size(); j++) 
     // Do something with vector.get(i) and vector.get(j) 

Answer 2

Pod względem złożoności dla tego algorytmu = n (n -1)/2, więc O (n^2) jest najlepszy można dostać (sekwencyjna).

Chociaż zestaw jest naprawdę duży, zestaw pasuje tylko do pamięci RAM. Możesz zoptymalizować algorytm, obliczając parę w sposób podobny do tego, co robi się w mnożeniu macierzy za pomocą bloków kafli. W ten sposób można zmniejszyć% braków pamięci podręcznej, a tym samym zwiększyć ogólną wydajność.

Oprócz tego można wprowadzić równoległość i podzielić pracę między wątkami/procesami, ponieważ algorytm wydaje się zawstydzająco równoległy.