Gegeben ein Objekt von Set , ich möchte durch alle (ungeordneten) Paare davon gehen.
Beispiel: Set = {1, 2, 3}, Paare: (1, 2), (1, 3), (2, 3).
Wenn Sie mit Vector<Integer> arbeiten, können Sie dies mit Hilfe des Index jedes Elements erreichen:
Aber Elemente in Set<Integer> haben keine Indizes.
Die beste Lösung, die ich bis jetzt gefunden habe, besteht darin, die Set in eine Vector umzuwandeln und die obige Lösung zu verwenden.
Gibt es eine effizientere / direkte Lösung?
In Bezug auf die Komplexität für diesen Algorithmus = n (n -1) / 2 , also ist O (n ^ 2) das Beste, was Sie bekommen können (sequenziell).
Obwohl, wenn Ihr Set wirklich groß ist, ein Set, das nur in den RAM passt. Sie können den Algorithmus optimieren, indem Sie das Paar blockweise berechnen, ähnlich wie bei der Matrixmultiplikation mit Kachelblöcken. Auf diese Weise können Sie den Prozentsatz des Cache-Fehltreffers reduzieren und somit die Gesamtleistung erhöhen.
Außerdem können Sie die Parallelisierung einführen und die Arbeit unter den Threads / Prozessen aufteilen, da der Algorithmus peinlich parallel erscheint.