5

頻繁に変化する N 個の異なる数値の配列があります。変更するたびに、2 つ以上の数値が等しくなる可能性がありますが、それは望ましくありません。数値 N は、可能な最大整数と同じ大きさにすることができます。変更が頻繁に発生することを知っているので、各変更後に各数値を残りの各数値と比較したくありません。

配列に少なくとも 2 つの等しい数値があるかどうかをすばやく確認するにはどうすればよいですか?

4

2 に答える 2

3

他にどのような制約があるかによって異なります。たとえば、次のようになります。

  1. 番号が入ってくる順序を維持する必要がありますか?
  2. 数字は追加されるだけですか、それとも削除されますか?
  3. より一般的な操作は何ですか: 追加/削除または重複のチェック?
  4. 何を保持する必要がありますか? セット (つまり、一意の数) またはマルチセット (多重度を持つ数)?

2 つの基本的なオプションがあります: Binary Search TreeとHash Tableです。

前者はO(log(n))平均して操作を提供し、後者は - O(1); 実際の結果は、使用しているストリームの種類によって異なります (数字はランダムですか? 増加していますか? 奇妙で非自明なパターンに従っていますか?)

BST を選択する場合は、バランスを保つ必要があることを忘れないでください。

例 (未テスト)

(defparameter *my-data-array* (make-array 100000))
;; fill *my-data-array*
(defparameter *my-data-table*
  (let ((ht (make-hash-table)))
    (loop for v across *my-data-array*
        do (incf (gethash v *my-data-table* 0)))
    ht))
(defun modify-data-array (pos new-value)
  (let* ((old-value (aref *my-data-array* pos))
         (old-count (decf (gethash old-value *my-data-table*)))
         (new-count (incf (gethash new-value *my-data-table* 0))))
    (setf (aref *my-data-array* pos) new-value)
    (case old-count
      (0 ; old-value is now not in the array
       ...)
      (1 ; old-value is now unique
       ...)
      (t ; old-value is still not unique
       ...))
     (case new-count
      (1 ; new-value was not in the array before
       ...)
      (2 ; new-value was unique before, but not anymore
       ...)
      (t ; new-value was not unique
       ...))))
于 2013-06-17T19:05:08.047 に答える
0

バリアントとして、Bloom filterを使用できます。指定された番号がすでに追加されているかどうかをテストできます。ただし、誤検知エラーが発生する可能性があります。一方、ブルームフィルターはスペース効率が高く高速であり、配列を保持できます。ブルーム フィルター アルゴリズムは、反復する数値をめったに使用しない場合に役立ちます。そうでない場合は、線形時間で数値を頻繁に再テストする必要があります。

于 2013-06-18T05:46:42.120 に答える