Szybki sposób policzenia, jak często pary pojawiają się w Clojure 1.4

Muszę policzyć, ile razy w niektórych procesach występują określone pary liczb całkowitych (heurystyka wykrywająca podobne obrazy za pomocą mieszania z lokalną czułością - liczby całkowite reprezentują obrazy, a „sąsiedzi” poniżej to obrazy o tej samej wartości mieszania, więc liczba wskazuje ile różnych skrótów łączy daną parę obrazów).

Liczniki są zapisywane jako mapa z (uporządkowanej) pary do zliczenia (matches poniżej).

Wejście (nbrs-list poniżej) jest listą liczb całkowitych, które są uważane za sąsiadów, gdzie każda odrębna (uporządkowana) para na wewnętrznej liście („sąsiedzi”) powinna być policzona. Na przykład, jeślinbrs-list jest[[1,2,3],[10,8,9]] wtedy pary są[1,2],[1,3],[2,3],[8,9],[8,10],[9,10].

Rutynacollect jest nazywany wielokrotnie;matches parametr kumuluje wyniki inbrs-list jest nowy przy każdym połączeniu. Najmniejsza liczba sąsiadów (rozmiar wewnętrznej listy) wynosi 1, a największa ~ 1000. Każda liczba całkowita wnbrs-list pojawia się tylko raz w dowolnym wezwaniucollect (oznacza to, że przy każdym wywołaniu żadna para nie występuje więcej niż raz), a liczby całkowite obejmują zakres 0 - 1 000 000 (czyli wielkośćnbrs-list jest mniejsza niż 1 000 000 - ponieważ każda wartość występuje tylko raz, a czasami występują w grupach - ale zazwyczaj większych niż 100 000 - ponieważ większość obrazów nie ma sąsiadów).

Wyciągnąłem procedury z większego fragmentu kodu, więc mogą zawierać małe błędy edycji, przepraszam.

(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))))

Powyższy kod rozszerza więc każdy zestaw sąsiadów na pary uporządkowane; tworzy mapę z par do1; następnie łączy mapy, dodając wartości.

Chciałbym, żeby to działało szybciej. Nie rozumiem, jak uniknąć ekspansji par O (n ^ 2), ale wyobrażam sobie, że mogę przynajmniej zmniejszyć stały narzut, unikając tylu struktur pośrednich. Jednocześnie chciałbym, aby kod był dość zwarty i czytelny ...

Aha, a teraz przekraczam „górny limit GC”. Tak więc redukcja użycia / odejścia pamięci jest również priorytetem: o)

[Może to jest zbyt szczegółowe? Mam nadzieję, że lekcje są ogólne i nie wydaje mi się, aby wiele wpisów na temat optymalizacji „prawdziwego” kodu clojure. Mogę również profilować itp., Ale mój kod wydaje się tak brzydki Mam nadzieję, że istnieje oczywiste, czystsze podejście - szczególnie w przypadku rozszerzenia par.]

questionAnswers(4)

yourAnswerToTheQuestion