Sortieren ist bestimmt eine gute Idee. PHP sortiert mit Quicksort, d.h. du kannst dabei von einer Laufzeit im Bereich O(n log(n)) ausgehen. Natürlich ist es auch so, dass man Laufzeitkomplexität nicht mit realer Laufzeit vergleichen darf, so dass Du also ein n haben wirst, unterhalb dessen deine brute force Schleife schneller fertig ist als die Sortierlösung. Wenn Du tatsächlich mit riesigen Punktewolken arbeiten willst, könntest Du noch einen Bucketizer vorschalten: Du erzeugst einen Punkt und hängst ihn je nach Wert von ['x'] in eins von beispielsweise 4 Teil-Arrays. Damit viertelst Du (asymptotisch) die Laufzeit des Sort, viertelst die Laufzeit des Kollisionstests UND du reduzierst die Größe des Speicherblocks, den das Array beansprucht, was PHPs Speicherverwaltung sicherlich gut gefallen wird. Die Grenzwerte, nach denen ein Punkt verteilt wird, musst Du entsprechend deiner Wertebereiche festlegen, um eine in etwa gleichmäßige Verteilung zu erreichen. Das Bucketizing hat natürlich auch Laufzeit, aber lineare Komplexität. Je mehr Buckets, desto langsamer; es ist also ein Balanceakt und im Zweifelsfall musst Du mit den für Dich relevanten Datenmengen ausprobieren, was lohnt und was nicht. Wenn Deine Koordinaten gleichmäßig um Null herum verteilt sind, könntest Du vier Eimer nach Quadranten in der XY-Ebene bilden, oder acht Eimer gemäß der Raum-Oktanten. Dann brauchst Du nur die Koordinaten auf "<0" testen, d.h. kannst mit 2 Tests auf 4 Eimer verteilen oder mit 3 Tests auf 8 Eimer. Wichtig ist auch, dass Du nicht nach jeder Kollision von vorn beginnst. Damit wiederholst Du viel zu oft Prüfungen, deren Ergebnis Du bereits kennst. Statt dessen sortiere einmal und gehe dann, wie von Sven beschrieben, einmal linear durch. Erkannte Kollisionen markierst Du lediglich (mit einer hinreichend schlauen Methode, da fällt Dir bestimmt was ein). Wenn Du am Ende N kollidierende Punkte gefunden hast, dann erzeugst Du N neue, prüfst die erst einmal untereinander auf Kollisionsfreiheit und dann auf Kollision mit dem Rest der Punktewolke. Diesen Kollisionstest sollst Du NICHT so durchführen, dass Du die neuen Punkte an Dein Array anhängst, einen usort() darauf machst und dann den Kollisionstest erneut durchführst. Grund: Du erwartest nur sehr wenige Kollisionen. Deshalb ist es besser, wenn Du für jede Ersatzzahl eine einfache foreach-Schleife durch das Array mit den bestehenden Punkten laufen lässt (bei Einsatz eines Bucketizers natürlich im richtigen Teil-Array). Wenn das Punktearray sortiert ist, kannst Du dieses Suchen durch eine binäre Suche von O(n) auf O(log n) beschleunigen. Und vielleicht ist die Kollisionsbeseitigung auch viel einfacher, wenn Du gleich zu Anfang ein paar Punkte mehr erzeugst als Du nachher brauchst. Bei der Doublettensuche markierst Du die doppelten Punkte nur und reduzierst das Array dann auf die nicht markierten Punkte. Es ist auch die Frage, ob du für deinen Anwendungsfall unbedingt genau N Punkte brauchst. Wenn Du bei N erzeugten Punkten einen Doublettenanteil von 0,01% hast - kannst Du die nicht einfach wegwerfen und dann mit 99.99% von N weitermachen statt die fehlenden Punkte aufwändig nachzugenerieren? Gruß Rolf

Sortieren ist bestimmt eine gute Idee. PHP sortiert mit Quicksort, d.h. du kannst dabei von einer Laufzeit im Bereich O(n log(n)) ausgehen. Natürlich ist es auch so, dass man Laufzeitkomplexität nicht mit realer Laufzeit vergleichen darf, so dass Du also ein n haben wirst, unterhalb dessen deine brute force Schleife schneller fertig ist als die Sortierlösung. Wenn Du tatsächlich mit riesigen Punktewolken arbeiten willst, könntest Du noch einen Bucketizer vorschalten: Du erzeugst einen Punkt und hängst ihn je nach Wert von ['x'] in eins von beispielsweise 4 Teil-Arrays. Damit viertelst Du (asymptotisch) die Laufzeit des Sort, viertelst die Laufzeit des Kollisionstests UND du reduzierst die Größe des Speicherblocks, den das Array beansprucht, was PHPs Speicherverwaltung sicherlich gut gefallen wird. Die Grenzwerte, nach denen ein Punkt verteilt wird, musst Du entsprechend deiner Wertebereiche festlegen, um eine in etwa gleichmäßige Verteilung zu erreichen. Das Bucketizing hat natürlich auch Laufzeit, aber lineare Komplexität. Je mehr Buckets, desto langsamer; es ist also ein Balanceakt und im Zweifelsfall musst Du mit den für Dich relevanten Datenmengen ausprobieren, was lohnt und was nicht. Wenn Deine Koordinaten gleichmäßig um Null herum verteilt sind, könntest Du vier Eimer nach Quadranten in der XY-Ebene bilden, oder acht Eimer gemäß der Raum-Oktanten. Dann brauchst Du nur die Koordinaten auf "<0" testen, d.h. kannst mit 2 Tests auf 4 Eimer verteilen oder mit 3 Tests auf 8 Eimer. Wichtig ist auch, dass Du nicht nach jeder Kollision von vorn beginnst. Damit wiederholst Du viel zu oft Prüfungen, deren Ergebnis Du bereits kennst. Lass den Kollisionstest komplett durchlaufen und merke Dir die Keys der kollidierenden Punkte in einer separaten Liste. Wenn Du am Ende N kollidierende Punkte gefunden hast, dann erzeugst Du N neue, prüfst die erst einmal untereinander auf Kollisionsfreiheit und dann auf Kollision mit dem Rest der Punktewolke. Diesen Kollisionstest sollst Du NICHT so durchführen, dass Du die neuen Punkte an Dein Array anhängst, einen usort() darauf machst und dann den Kollisionstest erneut durchführst. Grund: Du erwartest nur sehr wenige Kollisionen. Deshalb ist es besser, wenn Du für jede Ersatzzahl eine einfache foreach-Schleife durch das Array mit den bestehenden Punkten laufen lässt (bei Einsatz eines Bucketizers natürlich im richtigen Teil-Array). Wenn das Punktearray sortiert ist, kannst Du dieses Suchen durch eine binäre Suche von O(n) auf O(log n) beschleunigen. Und vielleicht ist die Kollisionsbeseitigung auch viel einfacher, wenn Du gleich zu Anfang ein paar Punkte mehr erzeugst als Du nachher brauchst. Bei der Doublettensuche markierst Du die doppelten Punkte nur und reduzierst das Array dann auf die nicht markierten Punkte. Es ist auch die Frage, ob du für deinen Anwendungsfall unbedingt genau N Punkte brauchst. Wenn Du bei N erzeugten Punkten einen Doublettenanteil von 0,01% hast - kannst Du die nicht einfach wegwerfen und dann mit 99.99% von N weitermachen statt die fehlenden Punkte aufwändig nachzugenerieren? Gruß Rolf