Главный генератор C #, Maxxing Out Bit Array - PullRequest
Новая
       21

Главный генератор C #, Maxxing Out Bit Array

1 голос
/ 10 июня 2009

(C #, простой генератор) Вот какой-то код, который мы с другом ковыряли: 

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;
}

На моем дорогом AMD x64 1800+ (двухъядерный), для всех простых чисел менее 1 миллиарда в 34546,875 мс. Проблема, кажется, хранит больше в битовом массиве. Попытка получить более 2 миллиардов - это больше, чем хочет сохранить битаррай. Любые идеи о том, как обойти это?

Ответы [ 4 ]

0 голосов
/ 21 мая 2010

Алгоритм сита будет лучше работать. С этим я смог определить все 32-битные простые числа (всего около 105 миллионов) для диапазона int менее чем за 4 минуты. Конечно, возвращение списка простых чисел - это другое дело, так как требования к памяти будут чуть более 400 МБ (1 int = 4 байта). Используя цикл for, числа были напечатаны в файл, а затем импортированы в БД для большего удовольствия :) Однако для 64-битных простых чисел программе потребуется несколько модификаций и, возможно, потребуется распределенное выполнение по нескольким узлам. Также обратитесь к следующим ссылкам

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

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

0 голосов
/ 10 июня 2009

Или в качестве альтернативы подходу, предложенному Pax, используйте новые классы Memory-Mapped File в .NET 4.0 и позвольте ОС решать, какие куски должны быть в памяти в любой момент времени.

Обратите внимание, однако, что вы захотите попробовать и оптимизировать алгоритм для увеличения локальности, чтобы вам не пришлось без необходимости обмениваться страницами в памяти и из нее (хитрее, чем это одно предложение делает его звучащим).

0 голосов
/ 04 мая 2010

Используйте несколько BitArrays, чтобы увеличить максимальный размер. Если число слишком велико, сдвиньте его и сохраните результат в битовом массиве для хранения битов 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-разрядная ОС, и мой BitArray также ограничен 32-разрядными.

PS: ваши вычисления простых чисел выглядят странно, мои выглядят так: 

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;
        }
0 голосов
/ 10 июня 2009

Я бы "поменял" части массива на диск. Под этим я подразумеваю разделить ваш битовый массив на полмиллиарда битовых кусков и сохранить их на диске.

В памяти одновременно может быть только несколько фрагментов. С C # (или любым другим языком OO) должно быть легко инкапсулировать огромный массив внутри этого класса чанкинга.

Вы заплатите за это с более медленным временем генерации, но я не вижу никакого пути к этому, пока мы не получим большие адресные пространства и 128-битные компиляторы.

...