Генератор простых чисел C #, Максимизирующий массив битов
Вопрос
(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 миллиардов - это больше, чем хочет сохранить bitarray.Есть какие-нибудь идеи о том, как это обойти?
Решение
Я бы "поменял местами" части массива на диск.Под этим я подразумеваю, что разделите свой битовый массив на полмиллиарда битовых блоков и сохраните их на диске.
У них есть только несколько фрагментов в памяти в любой момент времени.С помощью C # (или любого другого языка OO) должно быть легко инкапсулировать огромный массив внутри этого разделяющего класса.
Вы заплатите за это более медленным временем генерации, но я не вижу никакого способа обойти это, пока мы не получим большие адресные пространства и 128-битные компиляторы.
Другие советы
Или в качестве альтернативного подхода, предложенного Pax, используйте новые файловые классы с отображением памяти в .NET 4.0 и позвольте операционной системе решать, какие фрагменты должны находиться в памяти в любой момент времени.
Однако обратите внимание, что вам захочется попробовать оптимизировать алгоритм для увеличения локальности, чтобы вам не приходилось без необходимости загружать страницы в память и извлекать их из нее (сложнее, чем звучит в этом предложении).
Используйте несколько битовых массивов, чтобы увеличить максимальный размер.Если число должно быть большим, сдвиньте его на бит и сохраните результат в битовом массиве для хранения битов 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.Цифры.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;
}
Алгоритм сита был бы более эффективным.С помощью этого я мог бы определить все 32-битные простые числа (всего около 105 миллионов) для диапазона int менее чем за 4 минуты.Конечно, возвращать список простых чисел - это совсем другое дело, поскольку потребность в памяти там будет чуть более 400 МБ (1 int = 4 байта).Используя цикл for, числа были напечатаны в файл, а затем импортированы в базу данных для большего удовольствия :) Однако для 64-разрядных простых чисел программе потребуется несколько модификаций и, возможно, потребуется распределенное выполнение на нескольких узлах.Также обратитесь к следующим ссылкам
http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm