In Clojure, wie kann man mehrere Teilfolgen aus einer großen verzögerten Folge berechnen?

Question

In Clojure möchte ich mehrere Teilmengen aus einer großen trägen Sequenz berechnen (vielleicht eine unendliche). Der naive Weg wäre, die trägen Sequenz in einen Vektor umzuwandeln und dann die Teilmengen zu berechnen. Aber dabei verliere ich die Trägheit.

Ich habe eine große Sequenz big-sequence und positions, eine Liste von Start- und Endpositionen. Ich möchte die folgende Berechnung jedoch träge durchführen:

(let [positions '((5 7) (8 12) (18 27) (28 37) (44 47))
      big-sequence-in-vec (vec big-sequence)]
    (map #(subvec big-sequence-in-vec (first %) (second %)) positions))
; ([5 6] [8 9 10 11] [18 19 20 21 22 23 24 25 26] [28 29 30 31 32 33 34 35 36] [44 45 46])

Ist das machbar?

Bemerkung: Wenn big-sequence unendlich ist, wird vec niemals zurückkehren!

Answer 1

Sie fragen nach einer Lazy-Sequenz von Teilvektoren einer Lazy-Sequenz. Wir können sie Schicht für Schicht entwickeln wie folgt.

(defn sub-vektoren [spans c]
  (let [starts (map first spans)                 ; die Startsequenz der Bereiche
        finishes (map second spans)              ; die Endsequenz der Bereiche

        drops (map - starts (cons 0 starts))                    ; die inkrementellen Zahlen, die abgeworfen werden
        takes (map - finishes starts)                           ; die Zahlen zum Nehmen

        tails (next (reductions (fn [s n] (drop n s)) c drops)) ; die Teilsequenzen, aus denen die Teilvektoren am Anfang entnommen werden
        slices (map (comp vec take) takes tails)]               ; die Teilvektoren
    slices))

Zum Beispiel, gegeben

(def positionen '((5 7) (8 12) (18 27) (28 37) (44 47)))

haben wir

(sub-vektoren positionen (range))
; ([5 6] [8 9 10 11] [18 19 20 21 22 23 24 25 26] [28 29 30 31 32 33 34 35 36] [44 45 46])

Sowohl die Bereiche als auch die Grundsequenz werden lazy behandelt. Beide können unendlich sein.

Zum Beispiel,

(take 10 (sub-vektoren (partition 2 (range)) (range)))
; ([0] [2] [4] [6] [8] [10] [12] [14] [16] [18])

Answer 2

Das funktioniert @schauho's Vorschlag in einer Form, die schneller ist als @alfredx's Lösung, sogar nach der Verbesserung durch OP. Im Gegensatz zu meiner vorherigen Lösung geht es nicht davon aus, dass die erforderlichen Teilvektoren sortiert sind.

Das grundlegende Werkzeug ist eine fleißige Version von split-at:

(defn splitv-at [n v tail]
  (if (and (pos? n) (seq tail))
    (recur (dec n) (conj v (first tail)) (rest tail))
    [v tail]))

Dies entfernt die ersten n Elemente von tail, hängt sie an den Vektor v an und gibt den neuen v und tail als Vektor zurück. Wir verwenden dies, um genau so viel mehr der großen Sequenz im Vektor zu erfassen, wie erforderlich ist, um jeden Teilvektor zu liefern, wenn er entsteht.

(defn sub-spans [spans coll]
  (letfn [(sss [spans [v tail]]
               (lazy-seq
                (when-let [[[von bis] & spans-] (seq spans)]
                  (let [[v- tail- :as paar] (splitv-at (- bis (count v)) v tail)]
                    (cons (subvec v- von bis) (sss spans- paar))))))]
    (sss spans [[] coll])))

Zum Beispiel

(def positions '((8 12) (5 7) (18 27) (28 37) (44 47)))

(sub-spans positions (range))
; ([8 9 10 11] [5 6] [18 19 20 21 22 23 24 25 26] [28 29 30 31 32 33 34 35 36] [44 45 46])

• Da subvec in kurzer konstanter Zeit arbeitet, dauert es linear Zeit in Bezug auf die Menge der konsumierten großen Sequenz.
• Im Gegensatz zu meiner vorherigen Lösung vergisst es nicht seinen Anfang: Es behält die gesamte beobachtete große Sequenz im Speicher.

Answer 3

Sie könnten take auf der großen Sequenz mit dem Maximum der Positionen verwenden. Sie müssen die Werte bis zu diesem Punkt ohnehin berechnen, um die Teilverektoren zu berechnen, also verlieren Sie nicht wirklich etwas.

Answer 4

(defn pos-pair-to-vec [[start end] big-sequence] 
  (vec (for [idx (range start end)]
            (nth big-sequence idx))))

(let [positions '((5 7) (8 12) (18 27) (28 37) (44 47))
      big-seq (range)]
  (map #(pos-pair-to-vec % big-seq) positions))

Answer 5

Der Trick besteht darin, eine faule Version von subvec unter Verwendung von take und drop zu schreiben:

(defn subsequence [coll start end]
  (->> (drop start coll)
       (take (- end start))))

(let [positions '((5 7) (8 12) (18 27) (28 37) (44 47))
      big-sequence (range)]
  (map (fn [[start end]]  (subsequence big-sequence start end)) positions))
;((5 6) (8 9 10 11) (18 19 20 21 22 23 24 25 26) (28 29 30 31 32 33 34 35 36) (44 45 46))