Ich muss zählen, wie oft bestimmte Ganzzahlpaare in einem bestimmten Prozess vorkommen (eine Heuristik, die ähnliche Bilder unter Verwendung von ortsabhängigem Hashing erkennt - Ganzzahlen stellen Bilder dar und die "Nachbarn" unten sind Bilder, die denselben Hashwert haben, daher gibt die Anzahl an Wie viele verschiedene Hashes verbinden das Bildpaar?

Die Zählungen werden als eine Karte von (geordneten) Paaren zu Zählungen gespeichert (matches unten).

Die Eingabe (nbrs-list unten) ist eine Liste mit ganzen Zahlen, die als Nachbarn betrachtet werden, wobei jedes einzelne (geordnete) Paar in der inneren Liste ("die Nachbarn") gezählt werden sollte. Also zum Beispiel, wennnbrs-list ist[[1,2,3],[10,8,9]] dann sind die Paare[1,2],[1,3],[2,3],[8,9],[8,10],[9,10].

Die Routinecollect wird mehrfach aufgerufen; dasmatches Parameter akkumuliert Ergebnisse und dienbrs-list ist bei jedem Anruf neu. Die kleinste Anzahl von Nachbarn (Größe der inneren Liste) ist 1 und die größte ~ 1000. Jede ganze Zahl innbrs-list tritt nur einmal bei jedem aufruf aufcollect (Dies bedeutet, dass bei jedem Aufruf kein Paar mehr als einmal vorkommt) und die ganzen Zahlen decken den Bereich 0 - 1.000.000 (also die Größe vonnbrs-list ist kleiner als 1.000.000 (da jeder Wert nur einmal vorkommt und manchmal in Gruppen vorkommt - aber normalerweise größer als 100.000 - da die meisten Bilder keine Nachbarn haben).

Ich habe die Routinen aus einem größeren Teil des Codes herausgezogen, so dass sie möglicherweise kleine Bearbeitungsfehler enthalten, sorry.

(defn- flatten-1
  [list]
  (apply concat list))

(defn- pairs
  ([nbrs]
    (let [nbrs (seq nbrs)]
      (if nbrs (pairs (rest nbrs) (first nbrs) (rest nbrs)))))
  ([nbrs a bs]
    (lazy-seq
      (let [bs (seq bs)]
        (if bs
          (let [b (first bs)]
            (cons (if (> a b) [[b a] 1] [[a b] 1]) (pairs nbrs a (rest bs))))
          (pairs nbrs))))))

(defn- pairs-map
  [nbrs]
  (println (count nbrs))
  (let [pairs-list (flatten-1 (pairs nbrs))]
    (apply hash-map pairs-list)))

(defn- collect
  [matches nbrs-list]
  (let [to-add (map pairs-map nbrs-list)]
    (merge-with + matches (apply (partial merge-with +) to-add))))

Der obige Code erweitert also jede Gruppe von Nachbarn zu geordneten Paaren. Erstellt eine Karte von Paaren zu1; Kombiniert dann die Karten durch Hinzufügen von Werten.

Ich möchte, dass das schneller läuft. Ich weiß nicht, wie ich die O (n ^ 2) -Erweiterung von Paaren vermeiden kann, aber ich stelle mir vor, ich kann den konstanten Overhead zumindest reduzieren, indem ich so viele Zwischenstrukturen vermeide. Gleichzeitig möchte ich, dass der Code ziemlich kompakt und lesbar ist ...

Oh, und jetzt überschreite ich das "GC-Overhead-Limit". Daher hat die Reduzierung des Speicherverbrauchs / der Abwanderung ebenfalls Priorität: o)

[Vielleicht ist das zu spezifisch? Ich hoffe, dass die Lektionen allgemein gehalten sind und nicht viele Beiträge über die Optimierung von "echtem" Clojure-Code erscheinen. Außerdem kann ich Profile usw. erstellen, aber mein Code scheint so hässlich zu sein, dass ich hoffe, dass es einen offensichtlichen, saubereren Ansatz gibt - insbesondere für die Erweiterung der Paare.]