5,100만 개의 소수가 있는 데이터 구조를 빠르게 반복

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

  •  22-08-2019
  •  | 
  •  

문제

5,100만 개의 소수를 로드하고 이를 반복하는 작업에 가장 적합한 데이터 구조(Java)는 무엇입니까?

예를 들어, 1000000000과 같은 숫자에서 100000을 뺀 숫자 사이에 있는 소수를 알아야 합니다.

도움이 되었습니까?

해결책

Primes의 상반기가 마지막 절반보다 서로 더 가까워지기 때문에이 데이터에 이진 검색은 훌륭하지 않을 것입니다.

당신은 알면서 검색을 향상시킬 수 있습니다. x 아래에 얼마나 많은 프라임이 있는지. 어쩌면 링크에 언급 된 근사치를 사용하여 컷을 왜곡시킬 수 있습니다.

나의 첫 번째 시도는 이것입니다. 나는 두 개의 배열이있을 것입니다.

  1. 모든 프라임의 배열.
  2. 첫 번째 배열에서 1000*n 이상의 첫 번째 프라임이 어디에 있는지 알려주는 배열. 따라서 값이 5000 이상인 첫 번째 프라임을 찾고 싶다면 SecondArray [5000/1000-1]를 살펴 보겠습니다.

배열 1로 무엇이든하기 전에 배열 2로 거친 위치를 얻었습니다.

다른 팁

왜 지도에 저장하나요?주어진 숫자가 소수인지 빠르게 조회할 수 있도록 하기 위한 것인가요?그것은 의미가 있고 빠른 액세스를 제공합니다.TreeMap의 초기 용량을 설정하면 추가 비용을 완화할 수 있지만 제거할 수는 없습니다.그러나 이로 인해 트리 재조정 비용이 여전히 발생합니다.

대체 저장소는 간단히 정렬하여 배열에 넣는 것일 수 있습니다.이렇게 하면 이분법 검색으로 O(log n) 조회가 제공되지만 범위를 얻는 것이 간단해집니다.당신이 사용할 수있는 배열.바이너리검색().

모든 프라임을 사전 계산할 수 있으며 (Nosredna와 다른 사람들이 언급 한 소수 정리에 따라) 얼마나 많은 사람들이 있을지 알고 있으므로 고정 구조 (int [])와 일회성 사고 삽입을 사용할 수 있습니다. 비용은 걱정되지 않아야합니다.

바이너리 검색 (배열로 .BinarySearch ())가 너무 빠르면 최적화를 고려할 필요가 없습니다. 그러나 Nth Prime이 대략적으로 범위의 종말점을 더 빨리 찾는 곳에 대한 소수 정리의 예측을 사용할 수도 있습니다.

다르기 위해,이 척도에서 프라임을 큰 비트 필드에 세트 비트로 저장할 수 있습니다. 여기서 n이 프라임 인 경우 비트 #N은 1으로 설정됩니다. int [] - 10 억 비트는 ~ 110mib이고 5,100 만 개의 int는 ~ 200mib입니다. 클래스 비트 세트를 참조하십시오. 인덱스조차 없기 때문에 Bitset에 전달되기 전에 모든 인덱스 및 절반/이중 값에 대한 사소한 답변을 제공하여 Bitset을 서브 클래스 또는 랩 세트하여 ~ 55mib에 전체 필드를 저장할 수 있습니다.

이러한 구조로 프라임을 테스트하는 것은 O (1)이지만 모든 세트 비트 (프라임)를 반복하는 것은 타겟팅 한 범위의 프라임 밀도에 따라 다릅니다. 그래도 여전히 빠르야합니다.

나에게 간단한 배열 (또는 작업하기가 더 쉽기 때문에 Arraylist)은 괜찮을 것 같습니다. 요소를 추가하는 것은 O (1)이며 첫 번째 프라임> = X를 바이너리 검색하여 X와 Y 사이의 모든 프라임을 얻을 수 있습니다 (참조 http://java.sun.com/j2se/1.5.0/docs/api/java/util/collections.html#binarysearch%28java.util.list,%20T%29 ), 그런 다음 프라임에 도달 할 때까지 목록을 통과하십시오.

(나는 Cletus가 나를이기는 것을 알고 있지만, 추가 세부 사항이 어느 정도 사용되기를 바랍니다.)

N'th Prime에 관한 것입니다 p(n) ~ n ln(n), 즉

p(51E6) ~ 905114146 < 2147483647 = Integer.MAX_VALUE

이것은 처음 5 천 5 백만 프라임을 저장하는 가장 효율적인 방법을 의미합니다. int[].

그것은 정확히 운영의 균형과 사용에 따라 다릅니다. 간단한 분류 배열은 프라임을 저장하는 데 가장 적합합니다.

이제 성능이 실제로 프리미엄이되고 메모리 비용이 중요하지 않은 경우 지수 지수로이를 보강 할 수 있습니다. 예를 들어

int MAX_NUM_PRIMES =    ...   // the maximum number of primes to be stored
int MAX_PRIME = ....          // the largest prime to be stored
int primes[MAX_NUM_PRIMES]    // array of prime numbers, sorted
int nextPrime[MAX_PRIME]      // nextPrime[i] is the index of the next prime >= i

where nextPrime[i] is the starting point in the array primes for the first prime > i.

then, to iterate over e.g.   2000 primes from   3456, you would do

int j = nextPrime[3456]
for (i = j; i < j + 2000; i++) {
    int x = prime[i];
    ... do whatever with x ...
}

예를 들어, 1000000000 사이의 프라임과 동일한 숫자를 뺀 100000을 알아야합니다.

그런 다음 관심있는 숫자에 대한 체를 구축하십시오. 아래의 모든 프라임을 계산하는 것은 99900000 미만의 프라임이 정확히 있는지 정확히 알고 싶지 않다면 폐기물입니다.

이 크기의 숫자에 대한 좋은 데이터 구조는 약간 설정됩니다. 21 숫자 중 약 1 명이 프라임이므로 숫자를 명시 적으로 저장하는 것보다 메모리가 줄어들고 범위를 통과하기에 충분히 빠릅니다.

편집하다: 콘크리트가 되려면, 자바의 내 노트북에서 전체 범위를 가리키는 데 1 분이 조금 걸리면 지난 100000 명을 약 30 밀리 초 정도 할 수 있습니다.

X와 Y 사이의 프라임 수를 빠르게 찾기 위해 최상의 데이터 구조를 원한다면 (예에서와 같이) 이진 색인 트리.

좋은 설명이 있습니다 여기.

이 Java 애플릿은 상당히 빠른 것 같습니다 : 1 ~ 1,000 000 000의 프라임 테이블 http://www.walter-fendt.de/m14e/primes.htm (그래도 출처는 없지만 저자를 시도 할 수 있습니다)

숫자 배열은 아마도 잘 될 것입니다 :)

문제가 배열을 생성하는 것일 수 있습니까? 이 경우 배열이 포함 된 객체를 만들어 채우고 (생성하거나 프라임 목록에서 읽음) 완료되면 디스크로 직렬화하여 프로그램이 향후 바이너리 스트림을 빠르게 읽어 배열을로드 할 수 있습니다.

프라임 배열을 생성하는 방법에 대한 변형은이 질문을 참조하십시오. 소수 계산 재미

요구 사항에 따라 Eratosthenes의 세그먼트 된 체를 사용해야합니다. 많은 양의 기억이 필요하지 않습니다 ..

999900000의 제곱근까지 모든 프라임을 찾으십시오. (~ 31,621) 배열에 쉽게 저장할 수 있습니다.

이제 100000 길이의 배열에서 체 공정을 수행하십시오. 이 소수로.

많은 수의 경우 매우 효율적입니다.

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