소수의 효율적인 저장
https://stackoverflow.com/questions/1032427
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
라이브러리의 경우 첫 번째 프라임 번호를 한계 L로 저장해야합니다.이 컬렉션은 O (1) 조회 시간이 있어야합니다 (숫자가 프라임인지 아닌지 확인하려면 숫자가 주어지면 쉬워야합니다. 다음 소수를 찾으려면 (L보다 작다고 가정).
L이 고정되어 있으면 목록을 생성하기위한 에라토스테인 체는 정상입니다. 지금은 포장 된 부울 배열을 사용하여 목록을 저장합니다. 여기에는 3과 L (포함) 사이의 홀수 항목 만 포함되어 있습니다. (L-2)/2 비트의 메모리가 필요합니다. 더 많은 메모리를 사용하지 않고 L을 정적으로 증가시키고 싶습니다.
비슷한 속성을 가진 메모리가 적은 데이터 구조가 있습니까? 아니면 적어도 지속적인 조회 시간으로? (홀수 숫자는 우리가 프라임이 될 때까지 열거 될 수 있습니다)
(내가 이것을 쓴 언어는 IS입니다 요인 그러나이 질문은 내장되거나 쉽게 프로그래밍 가능한 포장 비트 배열이있는 모든 언어에서 동일합니다).
해결책
중복성을 제거하기 위해 더 많은 소수를 명시 적으로 확인할 수 있습니다.
현재 당신은 두 가지만 명시 적으로 분할 성을 확인한 다음 홀수 여부에 관계없이 홀수에 대해서만 저장함으로써 두 가지에 대해서만이 작업을 수행합니다.
2와 3의 경우 나머지 0 ~ 5를 얻을 수 있으며 그 중 1과 5만이 2 ~ 3으로 나눌 수 없으며 소수로 이어질 수 있으므로 1/3로 줄어 듭니다.
2, 3 및 5의 경우 30 개 중 8 개의 숫자를 얻을 수 있습니다. 이는 바이트에 보관하는 것이 좋습니다.
이것은 더 자세히 설명됩니다 여기.
다른 팁
포장 된 비트 맵과 바퀴에 대한 대안 (특정 상황에서 똑같이 효율적인)은 연속 프라임 사이의 차이점을 저장하는 것입니다. 평소와 같이 숫자 2를 제거하면 모든 차이점도 짝수입니다. 차이 저장/2 바이트 크기 변수를 사용하여 최대 2^40ish 지역 (1999066711391 직전)을 얻을 수 있습니다.
Primes Up 2^32는 확률 전용 포장 비트 맵에 대해 256 MBYTE에 비해 194 MBYTE 만 필요합니다. 델타 저장된 프라임 위에 반복하는 것은 휠 스토리지보다 훨씬 빠릅니다. 여기에는 승률 전용 비트 맵으로 알려진 모듈로 -2 휠이 포함됩니다.
1999066711391 이후의 경우 더 큰 셀 크기 또는 가변 길이 저장이 필요합니다. 후자는 매우 간단한 체계가 사용 되더라도 매우 효율적 일 수 있습니다 (예 : 바이트 <255가 추가 될 때까지 계속 추가하십시오. LZ4-스타일 압축), 510/2보다 긴 간격이 매우 낮기 때문입니다.
효율성을 위해 범위를 섹션 (페이지)으로 나누고 B- 트리 스타일을 관리하는 것이 가장 좋습니다.
엔트로피 코딩 차이 (Huffmann 또는 산술 코딩)는 영구적 인 저장 요구 사항을 절반보다 약간 적게 줄입니다. 이는 이론적 최적에 가깝고 최상의 사용 가능한 패커를 사용하여 압축 된 목록 또는 휠보다 더 가깝습니다.
데이터가 압축되지 않은 저장되면 여전히 바이너리 또는 텍스트 번호 파일보다 훨씬 더 작습니다. B-Tree 스타일 인덱스가 제자리에 있으면 필요한만큼 섹션을 메모리에 매핑하고 타오르는 속도로 반복 할 수 있습니다.
현재 2를 특별한 경우로 취급 한 다음 모든 홀수가 배열의 요소에 매핑되는 배열 (일부 홀수 숫자)이있는 배열이 있습니다. 2와 3을 특수한 경우에 취급함으로써이를 개선 할 수 있습니다. 소수의 나머지 부분은 6n+1 또는 6n-1 형식에 있음을 인식합니다 (P> 3, p mod 6 = 1 또는 5). 이것은 더 일반화 될 수 있습니다 - 참조 위키 백과. 모든 Primes P> 5, P Mod 30 = 1, 7, 11, 13, 17, 19, 19, 23 또는 29. 귀하는 계속해서 계속 진행하고 처리 시간을 희생시키면서 필요한 메모리를 줄일 수 있습니다 (여전히 가능합니다. o (1), 단지 느린 O (1)).
어떤 종류의 해시 테이블은 어떻습니까?
아주 좋은 해시 기능이 필요합니다 ( n mod p, 어디 p 어떤 배수가 아닙니다 q 가장 낮은 프라임 - 선택하십시오 q 충돌 횟수를 최소화하기 위해 충분히 높습니다).
인터벌 트리는 어떻습니까? http://www.geeksforgeeks.org/interval-tree/
O (1)은 아니지만 정말 빠릅니다. 아마도 O (log (p (n)))와 마찬가지로 p (n)은 숫자 n까지 프라임 수입니다. 이렇게하면 필요한 메모리는 프라임 수에만 비례하여 메모리 비용을 크게 줄입니다.
예를 들어 P1에서 Prime을 찾은 다음 P2에서 다음을 찾아서 간격 (P1, P2) 등을 삽입하고 해당 범위에서 숫자를 검색 할 때이 간격을 반환하고 P2를 반환 할 수 있다고 가정합니다. 당신의 경우에 대한 답이 될 것입니다.
어떤 것이 있는지 알아낼 수 있다면 Mersenne 또는 다른 쉽게 표현되는 소수는 해당 표현을 해당 숫자와 함께 사용하여 몇 비트를 절약 할 수 있습니다.
또한 숫자를 이전 숫자와의 차이로 저장하는 것은 어떻습니까? 그러면 크기가 빨리 상승해서는 안됩니다 (그러나 조회는 느립니다). 위의 접근 방식과 결합하여 Mersenne Primes와 마지막 Mersenne Prime과의 차이를 저장할 수 있습니다.
소수에 대한 TopCoder 자습서를 확인하십시오.http://community.topcoder.com/tc?module=static&d1=Tutorials&d2=math_for_topcoders
