C # مولد Prime، Maxxing Out Array

Question

(C #، مولد Prime) هيريس بعض الكود صديق وكنت بدقة في:

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+ (ثنائي النواة)، لجميع الأعداد الأولية أقل من 1 مليار في 34546.875ms. يبدو أن المشكلة تخزن أكثر في صفيف بت. محاولة كرنك أكثر من ~ 2billion هي أكثر من bitarray يريد تخزينها. أي أفكار حول كيفية التجول في ذلك؟

Answer 1

وأود أن "مبادلة" أجزاء من الصفيف خارج القرص. من ذلك، أقصد، قسم صفيف بت إلى قطع نصف مليار بت وتخزينها على القرص.

ليس لديهم سوى عدد قليل من القطع في الذاكرة في أي وقت واحد. مع C # (أو أي لغة OO الأخرى)، يجب أن يكون من السهل تغليف الصفيف الضخم داخل فئة الزاي هذه.

ستدفع ثمنها مع وقت الجيل أبطأ ولكني لا أرى أي طريقة حول ذلك حتى نحصل على مساحات عنوان أكبر ومجمعات محمولة 128 بت.

Answer 2

أو كهدوث نهج بديل واحد اقترحه PAX، الاستفادة من فئات الملفات المعينة الجديدة في الذاكرة في .NET 4.0 واترك نظام التشغيل يقرر أن تكون الأقسام التي تحتاج إلى أن تكون في الذاكرة في أي وقت معين.

ملاحظة سترغب في محاولة تحديد الخوارزمية وتحسين الخوارزمية لزيادة المناطق بحيث لا تنتهي دون داع باختبار صفحات المبادلة داخل وخارج الذاكرة (صعبة من هذه الجملة التي تجعلها صوت).

Answer 3

استخدم Bitarrass متعددة لزيادة الحد الأقصى للحجم. إذا كان هناك عدد من التحول بشكل كبير وتخزين النتيجة في مجموعة بعض الشيء لتخزين البتات 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 بت.

ملاحظة: حسابات الأعداد الأولية الخاصة بك تبدو WierD، يبدو لي مثل هذا:

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

Answer 4

خوارزمية غربال سيكون أداء أفضل. يمكنني تحديد جميع الأعداد الأولية 32 بت (إجمالي حوالي 105 مليون) من أجل المدى الدولي في أقل من 4 دقائق مع ذلك. بالطبع إرجاع قائمة الأعداد الأولية هو شيء مختلف حيث أن هناك متطلبات الذاكرة سيكون هناك ما يزيد قليلا عن 400 ميغابايت (1 INT = 4 بايت). باستخدام A For Loop، تمت طباعة الأرقام إلى ملف ثم استيرادها إلى DB لمزيد من المتعة :) ومع ذلك، فإن البرنامج 64 بت يحتاج البرنامج إلى عدة تعديلات وربما تتطلب التنفيذ الموزع على عقد متعددة. الرجوع أيضا إلى الروابط التالية

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

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