파이썬에서 정수에 대해 다른 해시 함수를 생성 하시겠습니까?

Question

minhashing 알고리즘을 구현하기 위해 무작위 해시 함수 (최대한 많은 수의)를 사용하여 시뮬레이션 할 정수의 많은 순열을 만들어야합니다. 현재 내가 형태의 해시 함수를 사용

a와 b가 무작위로 번호를 생성하고, C는 B의 가장 높은 값보다 소수 더 큰

h(x) = (a*x + b) % c 

. 어쨌든 코드는 이 너무 느리며으로 실행되며 합리적인 실행 시간에 15 개 이상의 해시 함수를 사용할 수 없습니다. 누구든지 Python에서 정수에 임의의 해시 함수를 사용하는 다른 방법을 권장 할 수 있습니까? 다른 게시물에서 나는 비트 섞기과 XOR 작업을 제안했지만, 어떻게 이런 식으로 구현해야하는지 완전히 이해하지 못했습니다 (저는 비교적 새로운 Python입니다).

Answer 1

비슷한 질문에 my answer에서 차용하고, 올바른 구문을 추측하려고 파이썬 문서에 잠깐 모습을 가지고 ...

당신이 게시 코드는 OK이지만 아마 이상 정밀도로 계산되는 대상이다 최적이며, 또한 상황을 느리게 만드는 부분이 포함됩니다.

는 2의 거듭 제곱에서 c를 해결할 수 있습니다, 빨리 만들려면, 당신은 바이너리 & (과) 대신이주는 모듈로,로 사용할 수 있습니다

과 동일

h(x) = (a * x + b) & ((1 << 32) - 1) 

:

h(x) = (a * x + b) % 4294967296 

당신이해야합니다과 동일

h(x) = (a * x + b) & (4294967296 - 1) 

a이 홀수 인 지 확인하십시오. c이 2의 거듭 제곱 인 경우 c과 공동 소수로 만드는 데 필요한 모든 것입니다. 이 예제는 출력 범위를 32 비트 정수로 제한합니다. 보시다시피 변경할 수 있습니다. 나는 파이썬의 한계가 무엇인지 모른다.

보다 많은 파라미터 화를 원하거나 결과가 "무작위"가 아니라는 것을 발견하면 (통계 테스트는 매우 빨리 실패하지만 대개 상관 없습니다) 더 많은 연산을 추가 할 수 있습니다. 덧셈과 곱셈의 사슬은 항상 한 쌍의 덧셈과 곱하기로 단순화되므로 여분의 연산으로는 아무 것도 고칠 수 없기 때문에 을 더 추가 할 수 없습니다.

대신 할 수있는 것은 bit shifts and exclusive-or을 사용하여 선형성을 해체하는 것입니다. 좋아요 :

def h(x): 
    x = x^(x >> 16) 
    x = (a * x + b) & ((1 << 32) - 1) 
    x = x^(x >> 16) 
    x = (c * x + d) & ((1 << 32) - 1) 
    x = x^(x >> 16) 
    return x 

원하는 경우 변형 할 수 있습니다. b과 d을 0으로 설정하고 가운데를 16으로 변경하면 MurmurHash3 finalizer 구조가됩니다. 대부분과 c을 선택하면 대부분의 용도에 이상적입니다 (슬프게도 무작위 일 수는 없습니다).