e ribuondi

ehilà

Hola

salve a tutti!

Ehilà

Buondì!

Mi sono cimentato in un lazy sort-all. Data una lista di collections gia' ordinate, ritornarle concatenate e in ordine. L'idea e' che non occorre scorrere tutti gli elementi di tutte le colls se voglio solo i primi 10, mi basta guardare i primi di ogni coll ad ogni iterazione. Se qualcuno ha qualche idea migliore... 🙂

(def colls (map sort [[4 3 6] [9 5 8] [1 4 2 0 0]]))

(defn sort-all [colls]
  (lazy-seq
    (if (some identity (map first colls))
      (let [[[winner & losers] & others] (sort-by first colls)]
        (cons winner (sort-all (if losers (conj others losers) others)))))))

(take 10 (sort-all colls))
;; (0 0 1 2 3 4 4 5 6 8)

ho un'implementazione che usa un approccio simile ma non e` lazy e usa priority queue per essere ottimamente efficente

(defn merge-events [events total-events]
    (if (empty? events)
      []
      (let [heap (doto (PriorityQueue. (count events) comparator)
                   (.addAll (mapv (fn [[k events]] [k (first events)]) events)))]
        (loop [ret (transient []) events (transient events)]
          (if (or (= total-events (count ret))
                  (.isEmpty heap))
            (persistent! ret)
            (let [[k val] (.poll heap)
                  event (rest (get events k))
                  events (assoc! events k event)]
              (when-let [val (first event)]
                (.add heap [k val]))
              (recur (conj! ret val) events)))))))

(assume che ogni sub-collection sia gia` stata sortata, e` solo la parte merging questa)

chiaramente la tua soluzione e` molto piu` concisa ed elegante, posto questa solo per esempio di una possibile ottimizzazione dell'implementazione, in caso (come nel mio) sia necessario

interessante!

2 impl da tenere nella toolbox. non ho pensato minimamente all'efficienza, quindi direi che uno prende una o l'altra in relazione a che ci deve fa'

nel mio caso, il constraint e' non portare l'intero data set in memoria (che non ci starebbe)

esatto, la tua soluzione e` memory efficient, la mia e` time efficient

anche se, sei sicuro non tenga l'intero data set in memoria? per sortare le collezioni interne mi sembra richiesto

quelle sono su file e sono ordinate in chunks

capisco

senno' andrebbe in memoria il tutto

Ho aggiunto il resto a monte del merge e creato un gist https://gist.github.com/reborg/3056a50af4f977b280b9b6f526670add