Die folgende Funktion:
%Vor% Ordnet jeden Punkt P einer Liste einer Liste von Punkten zu, die nach ihrer Entfernung zu P geordnet sind. So ist beispielsweise sortByDist [a, b, c, d] Map.! b die Liste [b, a, c, d], wenn a der nächste Punkt ist zu b, c ist die zweitnächste, d ist die dritte.
Da es eine n * log n sort für jedes Element ausführt, ist die Komplexität n^2 * log n . Dies stimmt mit den Benchmarks der Zeit überein, die benötigt wird, um eine Liste von N Punkten zu sortieren:
Wie viel kann das theoretisch verbessert werden? Ist es möglich, es auf N * log N herunter zu bekommen?
Als luqui kommentierte , mit Hilfe eines Quadtree oder ähnlichem wird es wahrscheinlich helfen. Der Aufbau des Baumes sollte O (n log n) nehmen: log n überschreitet, jeder von ihnen O (n) Auswahl und Partition. Sobald Sie den Baum haben, können Sie ihn durchqueren, um die Listen zu erstellen. Der Unterschied zwischen den Listen für einen Knoten und seine Kinder sollte im Allgemeinen klein sein, und wenn einige groß sind, sollte dies dazu neigen, andere dazu zu zwingen, klein zu sein. Die Verwendung einer adaptiven Sortierung (z. B. adaptive Mischsortierung oder adaptive Spreizung) sollte daher eine gute Leistung ergeben, aber die Analyse der Komplexität wird nicht einfach sein. Wenn Sie versuchen möchten, eine Freigabe zu erhalten, müssen Sie die Listen mit einem Sequenztyp (z. B. Data.Sequence ) darstellen und dann versuchen, Beziehungen zwischen Quadraten in verschiedenen Maßstäben herauszufinden. Ich habe ernsthafte Zweifel über das Potenzial eines solchen Ansatzes zur Reduzierung der zeitlichen Komplexität.
Tags und Links algorithm haskell data-structures sorting