이 프로그래밍 접근 방식의 공식 이름과 연합 및 교차로 계산

StackOverflow https://stackoverflow.com/questions/2010132

문제

나는 노조와 두 세트 (목록으로 저장)의 교차점과 차이를 동시에 계산하고 싶을 때이 [휠]을 분명히 발명했습니다. 초기 코드 (가장 타이트하지 않음) :

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을 사용해야한다는 것을 깨달았습니다.

이것은 32 비트 INT를 사용하여 최대 32 세트로 일반화 될 수 있으며, 비트 아레 또는 문자열을 사용하는 모든 세트로 일반화 될 수 있습니다. 따라서이 사전을 한 번 미리 압축 한 다음 매우 빠른 O (N) 쿼리를 사용하여 관심있는 요소를 추출합니다. 예를 들어, 모든 1은 모든 세트의 교차점을 의미합니다. 모든 0은 특별한 것입니다 - 발생하지 않습니다.

어쨌든, 이것은 내 자신의 경적을 붙이는 것이 아닙니다. 이것은 확실히 전에 발명되었고 이름이 있습니다. 뭐라고 해요? 이 접근법은 데이터베이스 어딘가에 사용됩니까?

도움이 되었습니까?

해결책

예, 때로는 데이터베이스 (예 : PostgreSQL)에서 사용됩니다. Wikipedia의 언급대로 :

영구 비트 맵 인덱스를 제공하지 않는 일부 데이터베이스 시스템은 비트 맵을 내부적으로 사용하여 쿼리 처리 속도를 높입니다. 예를 들어, PostgreSQL 버전 8.1 이상은 단일 테이블의 사용 가능한 색인간에 임의로 복잡한 논리 작업 속도를 높이기 위해 "Bitmap Index Scan"최적화를 구현합니다.

(에서 http://en.wikipedia.org/wiki/bitmap_index)

다른 팁

n 부울을 대표하기 위해 n 비트 정수를 사용하는 것은 완벽한 해시 테이블. 비트에 대해 생각하게 한 아이디어에서 DICT (일반 해시 테이블)를 명시 적으로 사용하고 있습니다. 해시를 사용하여 값을 찾기 때문에 해시 테이블이며 충돌이 없기 때문에 완벽합니다. 특별한 경우는 테이블을 포장하고 저장하는 방식 때문입니다.

해시 함수를 공식화하여 배열과 어떻게 다른지 보여줍니다.

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

통지 Bitset_hash (3)는 0B1000이며, 이는 CINT 및 BitWise 작업을 사용할 때 4 번째 항목 (오프셋/색인 3)에 해당합니다. (스토리지 구현 세부 사항으로 인해 비트 시일 작업은 해시에서 특정 항목을 조작하는 데 사용됩니다.)

세트 작업에 대해 Bitwise 및/-or/-xor를 사용하는 접근 방식을 확장합니다. 흔한, "작업 설정"이외의 특별한 이름이 필요하지 않거나 "이론 설정 이론"이 필요한 경우 "이론 설정".

마지막으로, 여기에 또 다른 예가 프라임 체 (프로젝트 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

정수를 사용하여 작은 정수 세트를 나타내는 것이 매우 일반적입니다. 그것은 종종 a라고 불립니다 비츠 세트 또는 비트 벡터. 여기에서 정수를 사용하여 "이 값을 포함하는 입력 시퀀스 세트"를 나타냅니다.

당신이하고있는 작업은 나에게 상기시켜줍니다 멀티 맵을 뒤집습니다.

귀하의 경우 입력은 목록 목록입니다.

[["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]}

그리고 당신은 비트 벡터를 사용하여 정수 배열을 대표합니다.

원래 데이터 구조 (목록 목록)를 사용하면 주어진 목록의 모든 값을 쉽게 반복 할 수있었습니다. 반전 된 데이터 구조 (목록 사전)를 사용하면 주어진 값이있는 모든 목록을 쉽게 찾을 수 있습니다.

A의 아이디어입니다 비트 필드 무엇을 찾고 있습니까? 당신의 모든 분야의 모든 비트 (더 나은 단어가 없기 때문에)는 깃발을 나타냅니다. 이 경우 깃발은 세트 N의 멤버십입니다.

편집 - 나는 당신이 어떤 아이디어를 언급했는지 오해했다고 생각합니다. 무시?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top