أسرع طريقة لحساب الأعداد الأولية في C#؟

Question

لدي بالفعل إجابة لسؤالي ولكنها ليست متوازية لذا فأنا مهتم بطرق تحسين الخوارزمية.على أية حال قد يكون من المفيد كما هو لبعض الناس.

int Until = 20000000;
BitArray PrimeBits = new BitArray(Until, true);

/*
 * Sieve of Eratosthenes
 * PrimeBits is a simple BitArray where all bit is an integer
 * and we mark composite numbers as false
 */

PrimeBits.Set(0, false); // You don't actually need this, just
PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime

for (int P = 2; P < (int)Math.Sqrt(Until) + 1; P++)
    if (PrimeBits.Get(P))
        // These are going to be the multiples of P if it is a prime
        for (int PMultiply = P * 2; PMultiply < Until; PMultiply += P)
            PrimeBits.Set(PMultiply, false);

// We use this to store the actual prime numbers
List<int> Primes = new List<int>();

for (int i = 2; i < Until; i++)
    if (PrimeBits.Get(i))
        Primes.Add(i);

ربما يمكنني استخدام متعددة BitArrayرمل BitArray.And() معا؟

Answer 1

يمكنك توفير بعض الوقت من خلال الإسناد الترافقي لمصفوفة البت الخاصة بك مع قائمة مرتبطة بشكل مزدوج، حتى تتمكن من التقدم بسرعة أكبر إلى العدد الأولي التالي.

أيضًا، عند إزالة المركبات اللاحقة بمجرد وصولك إلى p أولي جديد للمرة الأولى - فإن أول مضاعف مركب لـ p المتبقي سيكون p*p، نظرًا لأن كل شيء قبل ذلك قد تم حذفه بالفعل.في الواقع، ما عليك سوى ضرب p بكل الأعداد الأولية المحتملة المتبقية بعده في القائمة، والتوقف بمجرد أن يكون منتجك خارج النطاق (أكبر من حتى).

هناك أيضًا بعض الخوارزميات الاحتمالية الجيدة، مثل اختبار ميلر رابين. صفحة ويكيبيديا هي مقدمة جيدة.

Answer 2

وبغض النظر عن التوازي، فأنت لا تريد حساب sqrt(Until) في كل تكرار.يمكنك أيضًا افتراض مضاعفات 2 و3 و5 وحساب N%6 فقط في {1,5} أو N%30 في {1,7,11,13,17,19,23,29}.

يجب أن تكون قادرًا على موازاة خوارزمية التحليل بسهولة تامة، نظرًا لأن المرحلة N تعتمد فقط على النتيجة sqrt(n)th، لذلك لن يكون هناك أي تعارضات بعد فترة.لكن هذه ليست خوارزمية جيدة، لأنها تتطلب الكثير من القسمة.

يجب أن تكون أيضًا قادرًا على موازنة خوارزميات الغربال، إذا كان لديك حزم عمل الكاتب التي يضمن اكتمالها قبل القراءة.في الغالب، لا ينبغي للكتاب أن يتعارضوا مع القارئ - على الأقل بمجرد الانتهاء من بعض الإدخالات، يجب أن يعملوا على الأقل N فوق القارئ، لذلك تحتاج فقط إلى قراءة متزامنة في بعض الأحيان إلى حد ما (عندما يتجاوز N آخر قراءة متزامنة قيمة).لا يجب أن تحتاج إلى مزامنة مصفوفة منطقية عبر أي عدد من سلاسل عمليات الكاتب، حيث لا تنشأ تعارضات في الكتابة (في أسوأ الأحوال، سيكتب أكثر من سلسلة رسائل صحيحًا في نفس المكان).

ستكون المشكلة الرئيسية هي التأكد من اكتمال أي عامل يتم انتظاره للكتابة.في C++، يمكنك استخدام المقارنة والتعيين للتبديل إلى العامل الذي يتم انتظاره في أي وقت.أنا لست من مستخدمي C#، لذا لا أعرف كيفية القيام بذلك بهذه اللغة، ولكن يجب أن تكون وظيفة Win32 InterlockedCompareExchange متاحة.

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

في كلتا الحالتين، عليك التأكد من أن جميع العمال قد تجاوزوا الإدخال N قبل قراءته، وتكلفة القيام بذلك هي حيث يتم إجراء المفاضلة بين المتوازي والتسلسلي.

Answer 3

بدون التنميط لا يمكننا معرفة أي جزء من البرنامج يحتاج إلى التحسين.

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

إن إنشاء ملف تعريف لحلقة تحتوي على أكثر من اثنتي عشرة تعليمات في العادة لا يستحق كل هذا العناء - فالعبء الزائد لملف التعريف كبير مقارنة بجسم الحلقة، والطريقة الوحيدة لتحسين حلقة صغيرة بهذا الحجم هي تغيير الخوارزمية للقيام بتكرارات أقل .لذلك، بمجرد التخلص من أي وظائف باهظة الثمن والحصول على هدف معروف يتمثل في بضعة أسطر من التعليمات البرمجية البسيطة، فمن الأفضل تغيير الخوارزمية وتوقيت التشغيل الشامل بدلاً من محاولة تحسين التعليمات البرمجية حسب مستوى التعليمات. التنميط.

Answer 4

@DrPizza Profiling يساعد فقط في تحسين التنفيذ، ولا يكشف عن فرص للتنفيذ المتوازي، أو يقترح خوارزميات أفضل (ما لم تكن لديك خبرة في خلاف ذلك، وفي هذه الحالة أود حقًا رؤية ملف التعريف الخاص بك).

ليس لدي سوى أجهزة أساسية واحدة في المنزل، ولكني قمت بتشغيل ما يعادل Java لغربال BitArray الخاص بك، وإصدار مترابط واحد من انعكاس الغربال - مع الاحتفاظ بالعلامات الأولية في صفيف، واستخدام عجلة لتقليل مساحة البحث بمقدار خمسة أضعاف، ثم وضع علامة على مجموعة بتات بزيادات العجلة باستخدام كل علامة أولية.كما أنه يقلل من التخزين إلى O(sqrt(N)) بدلاً من O(N)، مما يساعد على حد سواء من حيث أكبر N، والترحيل، وعرض النطاق الترددي.

بالنسبة للقيم المتوسطة لـ N (1e8 إلى 1e12)، يمكن العثور على الأعداد الأولية حتى sqrt(N) بسرعة كبيرة، وبعد ذلك يجب أن تكون قادرًا على موازنة البحث اللاحق على وحدة المعالجة المركزية بسهولة تامة.في جهازي ذو النواة الواحدة، يجد نهج العجلة أعدادًا أولية تصل إلى 1e9 في 28 ثانية، في حين أن الغربال الخاص بك (بعد نقل sqrt خارج الحلقة) يستغرق 86 ثانية - يرجع التحسن إلى العجلة؛يعني الانعكاس أنه يمكنك التعامل مع N أكبر من 2 ^ 32 ولكنه يجعله أبطأ.يمكن العثور على الكود هنا.يمكنك موازنة مخرجات النتائج من المنخل الساذج بعد تجاوز sqrt(N) أيضًا، حيث لا يتم تعديل مصفوفة البت بعد تلك النقطة؛ولكن بمجرد أن تتعامل مع N كبير بما يكفي ليهم، يصبح حجم المصفوفة كبيرًا جدًا بالنسبة إلى ints.

Answer 5

يجب عليك أيضًا أن تفكر في التغيير المحتمل لـ خوارزميات.

ضع في اعتبارك أنه قد يكون من الأرخص إضافة العناصر إلى قائمتك بمجرد العثور عليها.

ربما يؤدي التخصيص المسبق للمساحة لقائمتك إلى جعل عملية البناء/التعبئة أقل تكلفة.

Answer 6

هل تحاول العثور على أعداد أولية جديدة؟قد يبدو هذا غبيًا، لكن قد تكون قادرًا على تحميل نوع ما من بنية البيانات ذات الأعداد الأولية المعروفة.أنا متأكد من أن هناك شخص ما لديه قائمة.قد يكون من الأسهل بكثير العثور على الأرقام الموجودة التي تحسب الأرقام الجديدة.

يمكنك أيضًا إلقاء نظرة على Microsofts مكتبة الفوركس الموازية لجعل التعليمات البرمجية الموجودة لديك متعددة الخيوط للاستفادة من الأنظمة متعددة النواة.مع الحد الأدنى من تغييرات التعليمات البرمجية، يمكنك جعل حلقات for متعددة الخيوط.

Answer 7

هناك مقالة جيدة جدًا عن غربال إراتوستينس: المنخل الحقيقي لإراتوستينس

إنه في بيئة وظيفية، ولكن معظم عمليات التحسين تنطبق أيضًا على التنفيذ الإجرائي في C#.

أهم تحسينين هما البدء بالشطب عند P^2 بدلاً من 2*P واستخدام عجلة للأعداد الأولية التالية.

من أجل التزامن، يمكنك معالجة جميع الأرقام حتى P^2 بالتوازي مع P دون القيام بأي عمل غير ضروري.

Answer 8

    void PrimeNumber(long number)
    {
        bool IsprimeNumber = true;
        long  value = Convert.ToInt32(Math.Sqrt(number));
        if (number % 2 == 0)
        {
            IsprimeNumber = false;
            MessageBox.Show("No It is not a Prime NUmber");
            return;
        }
        for (long i = 3; i <= value; i=i+2)
        {             
           if (number % i == 0)
            {

                MessageBox.Show("It is divisible by" + i);
                IsprimeNumber = false;
                break;
            }

        }
        if (IsprimeNumber)
        {
            MessageBox.Show("Yes Prime NUmber");
        }
        else
        {
            MessageBox.Show("No It is not a Prime NUmber");
        }
    }