1

要するに、Clojureでは、私が書いたカスタムシーケンスタイプで標準シーケンスAPI（ISeq、IndexedSeqなどのインターフェイスでは定義されていない）から関数を再定義する方法はありますか？

1.巨大なデータファイル

次の形式の大きなファイルがあります。

  • nエントリ数を含むlong（8バイト）
  • nエントリ。各エントリは3つのlong（つまり、24バイト）で構成されます。

2.カスタムシーケンス

これらのエントリにシーケンスが必要です。通常、すべてのデータを一度にメモリに保持することはできず、高速シーケンシャルアクセスが必要なため、次のようなクラスを作成しました。

(deftype DataSeq [id
                  ^long cnt
                  ^long i
                  cached-seq]
  clojure.lang.IndexedSeq

  (index [_]     i)
  (count [_]     (- cnt i))
  (seq   [this]  this)
  (first [_]     (first cached-seq))
  (more  [this]  (if-let [s (next this)] s '()))

  (next [_] (if (not= (inc i) cnt)
              (if (next cached-seq)
                (DataSeq. id cnt (inc i) (next cached-seq))
                (DataSeq. id cnt (inc i)
                          (with-open [f (open-data-file id)]
                             ; open a memory mapped byte array on the file
                             ; seek to the exact position to begin reading
                             ; decide on an optimal amount of data to read
                             ; eagerly read and return that amount of data
                          ))))))

主なアイデアは、リスト内の一連のエントリを先読みして、そのリストから消費することです。キャッシュが完全に消費されるたびに、エントリが残っている場合は、新しいキャッシュリストのファイルから読み取られます。そのような単純な。

このようなシーケンスのインスタンスを作成するには、次のような非常に単純な関数を使用します。

(defn ^DataSeq load-data [id]
  (next (DataSeq. id (count-entries id) -1 [])))
; count-entries is a trivial "open file and read a long" memoized

ご覧のとおり、データの形式により、count非常に簡単かつ効率的に実装できました。

3. dropO（1）である可能性があります

同じ精神で、再実装したいと思いdropます。これらのデータファイルの形式により、次のdropように、（標準のO（n）ではなく）O（1）で再実装できます。

  • 残りのキャッシュされたアイテムよりも少ない量をドロップする場合は、キャッシュから同じ量をドロップして完了します。

  • を超える値を削除した場合cntは、空のリストを返します。

  • それ以外の場合は、データファイル内の位置を把握し、その位置にジャンプして、そこからデータを読み取ります。

私の難しさは、、、などdropと同じ方法で実装されていないcountことです。後者の関数は、同様の名前の静的メソッドを呼び出します。このメソッドは、上記の実装を呼び出しますが、前者は、のインスタンスが呼び出されているシーケンスは、カスタム実装を提供します。firstseqRTdrop

もちろん、私は何でも名前の付いた関数を提供できますが、dropそれは私が望むことを正確に実行しますが、それは他の人（私の将来の自己を含む）にdrop毎回ではなくそれを使用することを忘れないようにします。

したがって、問題は次のとおりです。デフォルトの動作をオーバーライドすることは可能dropですか？

4.回避策（私は嫌いです）

この質問を書いている間、私は考えられる回避策を見つけました：読書をさらに怠惰にします。カスタムシーケンスは、インデックスを保持し、読み取り操作を延期します。これは、firstが呼び出された場合にのみ発生します。問題は、可変状態が必要にfirstなることです。最初の呼び出しでデータがキャッシュに読み込まれ、その後のすべての呼び出しでこのキャッシュからデータが返されます。同様のロジックがありますnext：キャッシュがある場合は、nextそれだけです。それ以外の場合は、わざわざデータを入力しないでくださいfirst。再度呼び出されたときに実行されます。

これにより、不要なディスク読み取りを回避できます。ただし、これはまだ最適ではありません。それでもO（n）であり、簡単にO（1）になる可能性があります。

とにかく、私はこの回避策が好きではありません、そして私の質問はまだ開いています。何かご意見は？

ありがとう。

4

1 に答える 1

1

とりあえず、上記の回避策を実行しました。これは、読み取りをへの最初の呼び出しに延期することによって機能します。これにより(first)、データはローカルの可変キャッシュに格納されます。

このバージョンでは、unsynchronized-mutable（へのすべての呼び出しでvolatile-readsを回避しfirst、nextへmoreの最初の呼び出しでvolatile-writeを回避するために）を使用することに注意してくださいfirst。言い換えれば、スレッド間で共有しないでください。スレッドセーフにするには、volatile-mutable代わりに使用します（これによりパフォーマンスがわずかに低下します）。それでも、異なるスレッドによる同じデータの複数の読み取りが発生する可能性があります。これを回避するには、に戻って、フィールドからの読み取りまたはフィールドへの書き込み時unsynchronized-mutableに必ず使用してください。(locking this ...)cache

編集：いくつかの（厳密ではない）テストの後、によって導入されたオーバーヘッド(locking this ...)は、ディスクからの不要な読み取りによって導入されたオーバーヘッドと同様のようです（データの一部をすでにキャッシュしている可能性がある高速SSDから読み取っていることに注意してください） 。したがって、現時点で（そして私の特定のハードウェアにとって）最良のスレッドセーフソリューションは、揮発性キャッシュを使用することです。

(deftype DataSeq [id
                  ^long cnt
                  ^long i
                  ^{:unsynchronized-mutable true} cache]
  clojure.lang.IndexedSeq

  (index [_]    i)
  (count [_]    (- cnt i))
  (seq   [this] this)
  (more  [this] (if-let [s (.next this)] s '()))
  (next  [_]    (if (not= (inc i) cnt)
                  (DataSeq. id cnt (inc i) (next cache))))
  (first [_]
    (when-not (seq cache)
      (set! cache
            (with-open [f (open-data-file id)]
              ; open a memory mapped byte array on the file
              ; seek to the exact position to begin reading
              ; decide on an optimal amount of data to read
              ; eagerly read and return that amount of data
            )))
    (first cache)))

それでも気にdropなるのは、ディスクからの読み取りを停止する（つまり、「出て行って、役に立たないデータ」）ためだけに可変状態を使用する必要があることです。

于 2012-10-13T09:27:39.633 に答える