C# Prime Generator, Maxxing 비트 배열

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

  •  13-09-2019
  •  | 
  •  

문제

(C#, Prime Generator)는 친구에게 일부 코드를하고 다음을 찌르고있었습니다.

public List<int> GetListToTop(int top)
{            
    top++;
    List<int> result = new List<int>();
    BitArray primes = new BitArray(top / 2);
    int root = (int)Math.Sqrt(top);
    for (int i = 3, count = 3; i <= root; i += 2, count++)
    {
        int n = i - count;
        if (!primes[n])
            for (int j = n + i; j < top / 2; j += i)
            {
                primes[j] = true;
            }
    }
    if (top >= 2)
        result.Add(2);            
    for (int i = 0, count = 3; i < primes.Length; i++, count++)
    {
        if (!primes[i])
        {
            int n = i + count;
            result.Add(n);
        }
    }

    return result;
}

내 Dorky AMD X64 1800+ (듀얼 코어), 34546.875ms에서 10 억 미만의 모든 프라임에 대해. 문제는 비트 어레이에 더 많이 저장하는 것 같습니다. ~ 20 억 개 이상을 크랭크하려고하는 것은 Bitarray가 보관하고자하는 것보다 더 많습니다. 그 점을 해결하는 방법에 대한 아이디어가 있습니까?

도움이 되었습니까?

해결책

배열의 일부를 디스크로 "스왑"할 것입니다. 즉, 비트 어레이를 50 억 비트 덩어리로 나누고 디스크에 보관하십시오.

한 번에 메모리에 덩어리가 몇 개 밖에 없습니다. C# (또는 다른 OO 언어)을 사용하면이 청크 클래스 내에서 거대한 배열을 쉽게 캡슐화 할 수 있어야합니다.

생성 시간이 느리게 지불하지만 더 큰 주소 공간과 128 비트 컴파일러를 얻을 때까지 그 주위에는 아무런 방법이 없습니다.

다른 팁

또는 PAX가 제안한 대체 접근 방식으로 .NET 4.0에서 새 메모리 매핑 된 파일 클래스를 사용하고 OS가 주어진 시간에 메모리에 필요한 청크를 결정하게하십시오.

그러나 알고리즘을 늘리기 위해 알고리즘을 최적화하려고 시도하고 최적화하여 메모리 안팎으로 페이지를 교환하지 않도록하십시오 (이 문장보다 까다 롭게하면 소리가 들립니다).

여러 비트 토레이를 사용하여 최대 크기를 늘리십시오. 숫자가 비트 시프트하고 비트 33-64를 저장하기위한 비트 어레이를 저장하는 경우.

BitArray second = new BitArray(int.MaxValue);
long num = 23958923589;
if (num > int.MaxValue)
{
    int shifted = (int)num >> 32;
    second[shifted] = true;
}

long request = 0902305023;
if (request > int.MaxValue)
{
    int shifted = (int)request >> 32;
    return second[shifted];
}
else return first[request];

물론 BitArray가 System.numerics.biginteger까지 크기를 지원한다면 좋을 것입니다.
디스크로 바꾸면 코드가 실제로 느려집니다.
64 비트 OS가 있으며 BitArray도 32 비트로 제한됩니다.

추신 : 소수 계산이 더 넓어 보이며, 내 것 같습니다.

for (int i = 2; i <= number; i++)
    if (primes[i])
        for (int scalar = i + i; scalar <= number; scalar += i)
        {
            primes[scalar] = false;
            yield return scalar;
        }

체 알고리즘이 더 잘 수행 될 것입니다. 4 분 이내에 INT 범위의 32 비트 프라임 (총 약 1 억 5 천 5 백만)을 모두 결정할 수 있습니다. 물론 프라임 목록을 반환하는 것은 메모리 요구 사항이 400MB (1 int = 4 바이트)가 조금 넘기 때문에 다른 것입니다. for 루프를 사용하여 숫자를 파일에 인쇄 한 다음 더 재미있게 DB로 가져 왔습니다. :) 그러나 64 비트 프라임의 경우 프로그램에는 몇 가지 수정이 필요하며 여러 노드에 대한 분산 실행이 필요할 수 있습니다. 또한 다음 링크를 참조하십시오

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

http://en.wikipedia.org/wiki/prime-counting_function

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