9

アイテムのソースがあり、キー関数の同じ値を持つアイテムの実行を個別に処理したいと考えています。Python では、これは次のようになります。

for key_val, part in itertools.groupby(src, key_fn):
  process(key_val, part)

このソリューションは完全に怠惰です。つまりprocess、全体の内容を保存しようとしない場合part、コードはO(1)メモリ内で実行されます。

Clojure ソリューション

(doseq [part (partition-by key-fn src)]
  (process part))

怠惰ではありません。各部分を完全に実現します。問題は、src同じ値を持つアイテムが非常に長く続く可能性があり、key-fnそれらを認識すると OOM につながる可能性があることです。

次の関数（投稿内の名前の一貫性のためにわずかに変更されています）が十分に怠惰であると主張されているこの議論を見つけました

(defn lazy-partition-by [key-fn coll]
  (lazy-seq
    (when-let [s (seq coll)]
      (let [fst (first s)
            fv (key-fn fst)
            part (lazy-seq (cons fst (take-while #(= fv (key-fn %)) (next s))))]
        (cons part (lazy-partition-by key-fn (drop-while #(= fv (key-fn %)) s)))))))

ただし、OOM に悩まされない理由がわかりません。コンス セルの両方の部分が への参照を保持しているsため、 をprocess消費partしている間sは実現されていますが、ガベージ コレクションは行われていません。drop-whileトラバース時のみGC対象となりますpart。

だから、私の質問は次のとおりです。

  1. lazy-partition-by怠け者ではないというのは正しいですか？
  2. 次のものを実現し始めるpartition-byまでに前のものへの参照を保持していなければ、メモリ要件が保証された実装はありますか?part

編集: これは Haskell での十分に怠惰な実装です:

lazyPartitionBy :: Eq b => (a -> b) -> [a] -> [[a]]
lazyPartitionBy _ [] = []
lazyPartitionBy keyFn xl@(x:_) = let
  fv = keyFn x
  (part, rest) = span ((== fv) . keyFn) xl
  in part : lazyPartitionBy keyFn rest

span実装からわかるようにpart、rest暗黙的に状態を共有します。このメソッドを Clojure に翻訳できないかと考えています。

4

3 に答える 3

8

これらのシナリオ (つまり、1 つの入力シーケンスで複数の出力シーケンスを生成する必要があるシナリオ) で使用する経験則では、次の 3 つの望ましいプロパティのうち、一般的には 2 つしか持つことができません。

  1. 効率（入力シーケンスを 1 回だけトラバースするため、頭を保持しない）
  2. 怠惰 (オンデマンドでのみ要素を生成する)
  3. 共有可変状態なし

clojure.core のバージョンは (1,3) を選択しますが、パーティション全体を一度に作成することで (2) をあきらめます。Python と Haskell はどちらも (1,2) を選択しますが、すぐにはわかりません: Haskell には変更可能な状態がまったくないのではないでしょうか? まあ、すべての (シーケンスだけでなく) の遅延評価は、すべての式がthunksであることを意味します。これは、空白のスレートとして始まり、値が必要な場合にのみ書き込まれます。あなたが言うように、の実装は両方の出力シーケンスでspan同じサンクを共有するspan p xs'ため、最初にそれを必要とする方が他のシーケンスの結果にそれを「送信」し、保存するために必要な距離でアクションを実行しますその他の素晴らしいプロパティ。

あなたが指摘したように、あなたがリンクした代替Clojure実装は（2,3）を選択します。

問題は、 (1)またはpartition-by(2)のいずれかを拒否することは、入力または出力のいずれかのシーケンスの先頭を保持していることを意味することです。したがって、任意に大きな入力の任意に大きなパーティションを処理できるソリューションが必要な場合は、(1,2) を選択する必要があります。Clojure でこれを行う方法はいくつかあります。

  1. Python のアプローチをとってください: seq よりもイテレータに似たものを返します。 1 つのイテレータからアイテムを消費すると、他のイテレータを自由に変更または無効化できます。これにより、消費が順番に行われ、メモリを解放できることが保証されます。
  2. Haskell のアプローチを採用します。手動ですべてをサンクし、大量の への呼び出しをdelay行い、データを取得するためにクライアントがforce必要なだけ呼び出す必要があります。これは Clojure ではかなり醜くなり、スタックの深さが大幅に増加します (重要な入力でこれを使用すると、おそらくスタックが壊れます) が、理論的には可能です。
  3. 出力 seq 間で調整され、いずれかから何かが要求されたときに必要に応じてそれぞれが更新されるいくつかの変更可能なデータ オブジェクトを使用することにより、Clojure 風に (しかしまだ非常に珍しい) 何かを記述します。

これら 3 つのアプローチのいずれかが可能であると確信していますが、正直なところ、どれも非常に難しく、まったく自然ではありません。Clojure のシーケンスの抽象化では、希望するデータ構造を簡単に作成することはできません。私のアドバイスは、このようなものが必要で、パーティションが大きすぎて快適に収まらない場合は、わずかに異なる形式を受け入れて、自分でもう少し簿記を行うことです。すべての出力シーケンス!

したがって((2 4 6 8) (1 3 5) (10 12) (7))、 のような出力形式の代わりに(partition-by even? [2 4 6 8 1 3 5 10 12 7])、少し醜い形式を受け入れることができます([::key true] 2 4 6 8 [::key false] 1 3 5 [::key true] 10 12 [::key false] 7)。これは作成するのも消費するのも難しくありませんが、書き出すのは少し長く退屈です。

プロデュース関数の合理的な実装の 1 つを次に示します。

(defn lazy-partition-by [f coll]
  (lazy-seq
    (when (seq coll)
      (let [x (first coll)
            k (f x)]
        (list* [::key k] x
         ((fn part [k xs]
            (lazy-seq
              (when (seq xs)
                (let [x (first xs)
                      k' (f x)]
                  (if (= k k')
                    (cons x (part k (rest xs)))
                    (list* [::key k'] x (part k' (rest xs))))))))
          k (rest coll)))))))

reduce-groupedこれを使用する方法は次のとおりです。最初にグループ化形式の詳細を非表示にするジェネリックを定義し、次に、count-partition-sizesシーケンスをメモリに保持せずに各パーティションのキーとサイズを出力する関数の例を示します。

(defn reduce-grouped [f init groups]
  (loop [k nil, acc init, coll groups]
    (if (empty? coll)
      acc
      (if (and (coll? (first coll)) (= ::key (ffirst coll)))
        (recur (second (first coll)) acc (rest coll))
        (recur k (f k acc (first coll)) (rest coll))))))

(defn count-partition-sizes [f coll]
  (reduce-grouped (fn [k acc _]
                    (if (and (seq acc) (= k (first (peek acc))))
                      (conj (pop acc) (update-in (peek acc) [1] inc))
                      (conj acc [k 1])))
                  [] (lazy-partition-by f coll)))

user> (lazy-partition-by even? [2 4 6 8 1 3 5 10 12 7])
([:user/key true] 2 4 6 8 [:user/key false] 1 3 5 [:user/key true] 10 12 [:user/key false] 7)
user> (count-partition-sizes even? [2 4 6 8 1 3 5 10 12 7])
[[true 4] [false 3] [true 2] [false 1]]

編集：もう一度見てみると、キーがいつ変更されるかを明確に示すことができないため、 myreduce-groupedが よりもはるかに便利であるとは確信し(reduce f init (map g xs))ていません。lazy-partition-byしたがって、グループがいつ変更されるかを知る必要がある場合は、よりスマートな抽象化が必要になるか、 「巧妙な」ラッピングを何もせずに私のオリジナルを使用する必要があります。

于 2014-07-14T20:40:29.260 に答える