8

2 つのセット (リストとして格納されている) の和集合と交差と差分を同時に計算したいときに、この [ホイール] を [確実に再] 発明しました。初期コード (厳密ではない):

dct = {}
for a in lst1:
  dct[a] = 1
for b in lst2:
  if b in dct:
    dct[b] -= 1
  else:
    dct[b] = -1

union = [k for k in dct]
inter = [k for k in dct if dct[k] == 0]
oneminustwo = [k for k in dct if dct[k] ==  1]
twominusone = [k for k in dct if dct[k] ==  -1]

次に、-1、1、0、... の代わりに 00、01、10、および 11 を使用する必要があることに気付きました。したがって、位置 n のビットは、セット n のメンバーであることを示します。

これは、32 ビットの int を使用して最大 32 セットに一般化するか、bitarray または文字列を使用して任意の数のセットに一般化できます。したがって、このディクショナリを 1 回事前計算してから、非常に高速な O(n) クエリを使用して対象の要素を抽出します。たとえば、すべて 1 はすべてのセットの交差を意味します。すべての 0 は特殊なものであり、発生しません。

とにかく、これは自分の角を鳴らすためではありません。これは確かに以前に発明されたもので、名前があります。それはなんと呼ばれていますか？このアプローチはどこかのデータベースで使用されていますか?

4

4 に答える 4

7

N ブール値を表すために N ビット整数を使用することは、完全ハッシュ テーブルとして知られるデータ構造の特殊なケースです。ビットセットについて考えるきっかけとなったアイデアで、dict (一般的なハッシュ テーブル) を明示的に使用していることに注意してください。ハッシュを使用して値を見つけるため、これはハッシュ テーブルであり、衝突がないため完璧です。特殊なケースは、テーブルがどのようにパックされて格納されるかによるものです。

配列との違いを示すハッシュ関数を定式化します。

int bitset_hash(int n) {
  // domain of this function is only non-negative ints
  return 1 << n;
}

bitset_hash(3) が 0b1000 であることに注意してください。これは、C の int およびビット演算を使用する場合の 4 番目の項目 (オフセット/インデックス 3) に対応します。(ストレージ実装の詳細のため、ハッシュから特定のアイテムを操作するためにビット単位の操作も使用されます。)

集合操作に bitwise-and/-or/-xor を使用するアプローチを拡張することは一般的であり、「集合操作」または流行語が必要な場合は「集合理論」以外の特別な名前は必要ありません。

最後に、素ふるいで別の使用例を示します(私は Project Euler ソリューションでこのコードを使用しました)。

class Sieve(object):
  def __init__(self, stop):
    self.stop = stop
    self.data = [0] * (stop // 32 // 2 + 1)
    self.len = 1 if stop >= 2 else 0
    for n in xrange(3, stop, 2):
      if self[n]:
        self.len += 1
        for n2 in xrange(n * 3, stop, n * 2):
          self[n2] = False

  def __getitem__(self, idx):
    assert idx >= 2
    if idx % 2 == 0:
      return idx == 2
    int_n, bit_n = divmod(idx // 2, 32)
    return not bool(self.data[int_n] & (1 << bit_n))

  def __setitem__(self, idx, value):
    assert idx >= 2 and idx % 2 != 0
    assert value is False
    int_n, bit_n = divmod(idx // 2, 32)
    self.data[int_n] |= (1 << bit_n)

  def __len__(self):
    return self.len

  def __iter__(self):
    yield 2
    for n in xrange(3, self.stop, 2):
      if self[n]:
        yield n
于 2010-01-06T01:55:01.237 に答える
4

はい、PostgreSQL などのデータベースで使用されることがあります。ウィキペディアに言及しているように：

永続的なビットマップ インデックスを提供しない一部のデータベース システムでは、内部的にビットマップを使用してクエリ処理を高速化しています。たとえば、PostgreSQL バージョン 8.1 以降では、「ビットマップ インデックス スキャン」最適化が実装されており、単一のテーブルで使用可能なインデックス間の任意の複雑な論理操作が高速化されます。

( http://en.wikipedia.org/wiki/Bitmap_indexから)

于 2010-01-06T02:03:27.977 に答える
2

小さな整数のセットを表すために整数を使用することは非常に一般的です。多くの場合、ビットセットまたはビットベクトルと呼ばれます。ここでは、「この値を含む入力シーケンスのセット」を表すために整数を使用しています。

あなたがしている操作は、マルチマップを逆にすることを思い出させます。

あなたの場合、入力はリストのリストです：

[["a", "b"], ["a", "c", "d"]]

しかし、代わりに、次のように、順序対のバッグと考えることができます。

0, "a"
0, "b"
1, "a"
1, "c"
1, "d"

逆のペアを含むテーブルを作成しているだけです

"a", 0
"b", 0
"a", 1
"c", 1
"d", 1

これは次のようになります：

{"a": [0, 1],
 "b": [0],
 "c": [1],
 "d": [1]}

そして、あなたはたまたまビットベクトルを使ってそれらの整数の配列を表現しているのです。

元のデータ構造（リストのリスト）により、特定のリストのすべての値を簡単に繰り返すことができました。逆のデータ構造（リストの辞書）を使用すると、特定の値を持つすべてのリストを簡単に見つけることができます。

于 2010-01-06T00:27:50.353 に答える
1

ビットフィールドのアイデアはあなたが探しているものですか? ... フィールドのすべてのビット (より適切な言葉がないため) は、フラグを表します。この場合、フラグはセット N のメンバーシップです。

編集 - あなたが言及しているアイデアを誤解したと思います。無視？

于 2010-01-06T00:25:42.260 に答える