تخزين فعالة من الأعداد الأولية

Question

لمكتبة، ولست بحاجة لتخزين أرقام الأعداد الأولية الأولى تصل إلى حد L. يجب أن يكون هذا جمع لO (1) وقت البحث (للتحقق ما إذا كان العدد هو رئيس أم لا) ويجب أن يكون من السهل، نظرا عدد، للعثور على رئيس الرقم التالي (على افتراض أنه أصغر من L).

وبالنظر إلى أن L هو ثابت، وهو غربال Eratostene لتوليد قائمة على ما يرام. الحق الآن، وأنا استخدم مجموعة منطقية معبأة لتخزين القائمة، التي تحتوي على إدخالات الوحيدة للالأعداد الفردية بين 3 و L (ضمنا). وهذا يأخذ (L-2) / 2 بت من الذاكرة. وأود أن تكون قادرة على زيادة ثابت L دون استخدام المزيد من الذاكرة.

هل هناك بنية البيانات باستخدام ذاكرة أقل مع خصائص مماثلة؟ أو مع الوقت بحث مستمر على الأقل؟ (الأعداد الفردية ويمكن بعد ذلك يتم تعداد حتى نحصل على رئيس الوزراء)

و(لغة كتبت هذا في غير href="http://www.factorcode.org/" عامل لكن هذا السؤال تكون هي نفسها في أي لغة التي لديها مدمج أو برمجة بسهولة صفائف معبأة بت)

Answer 1

ويمكنك التحقق صراحة أرقام أكثر قصوى لإزالة التكرار.

في الوقت الحالي القيام بذلك فقط لمدة سنتين، عن طريق التحقق من القسمة من قبل اثنين من صراحة ومن ثم تخزين فقط عن الأعداد الفردية سواء كانوا من الوزراء.

ل2 و 3 تحصل بقايا 0-5، منها سوى 1 و 5 لا يقبل القسمة على اثنين أو ثلاثة ويمكن أن يؤدي إلى عدد أولي، لذلك كنت وصولا الى 1/3.

ل2 و 3 و 5 تحصل 8 أرقام من أصل 30، وهو لطيف لتخزين في بايت.

وهذا يفسر بمزيد من التفصيل هنا .

Answer 2

وبديل لالنقطية وعجلات معبأة - ولكنها فعالة على قدم المساواة في سياقات معينة - يتم تخزين الخلافات بين يعبي متتالية. إذا تركت من عدد 2 كالمعتاد ثم كل الخلافات، بل هي. تخزين الفرق / 2 يمكنك الحصول على ما يصل إلى 2 ^ 40ish المناطق (قبل 1999066711391) باستخدام المتغيرات بايت الحجم.

وويعبي بنسبة 2 ^ 32 لا تتطلب سوى 194 ميجابايت، مقارنة مع 256 ميجابايت لخلاف فقط نقطية معبأة. بالتكرار عبر يعبي المخزنة دلتا أسرع بكثير من لتخزين العجلات، والتي تشمل عجلة مودولو-2 المعروف باسم نقطية خلاف فقط.

لنطاقات من 1999066711391 فصاعدا، وهناك حاجة أكبر حجم الخلية أو تخزين متغيرة الطول. وهذه الأخيرة يمكن أن تكون فعالة للغاية حتى في حالة استخدام برامج بسيطة جدا (مثل الحفاظ على إضافة حتى بايت <255 تمت إضافة، كما في <لأ href = "http://en.wikipedia.org/wiki/LZ4_٪28compression_algorithm٪29 "> LZ4 على غرار ضغط)، وذلك بسبب التردد المنخفض للغاية من الثغرات أطول من 510/2.

لأجل كفاءة لذلك فمن الأفضل لتقسيم مجموعة إلى أقسام (صفحات) وإدارتها، على غرار B-شجرة.

والانتروبيا الترميز الاختلافات (Huffmann أو الحساب الترميز) خفض متطلبات التخزين الدائمة إلى أقل قليلا من النصف، التي هي قريبة من النظرية الأمثل وأفضل من القوائم أو عجلات مضغوط باستخدام أفضل تعبئة المتاحة.

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

Answer 3

في هذه اللحظة كنت علاج 2 حالة خاصة ومن ثم وجود مجموعة حيث يتم تعيين كل عدد فردي إلى عنصر في مجموعة (مع بعض الأعداد الفردية يجري رئيس الوزراء). هل يمكن تحسين هذا عن طريق علاج 2 و 3 كحالات خاصة الاعتراف بأن بقية الأعداد الأولية هي في 6N شكل + 1 أو 6N-1 (وهذا هو لجميع يعبي ص حيث ص> 3، ص زارة الدفاع 6 = 1 أو 5). وهذا يمكن أن يكون أبعد المعمم - راجع ويكيبيديا . لجميع الأعداد الأولية p> و5، ص زارة الدفاع 30 = 1، 7، 11، 13، 17، 19، 23 أو 29. هل يمكن أن تستمر مع هذا وتقليل الذاكرة المطلوبة على حساب وقت المعالجة (على الرغم من أنه سيظل O (1)، مجرد أبطأ O (1)).

Answer 4

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

وألطاف، فإنها لا تفي O الخاص بك (1) شرط، فهي غاية الذاكرة فعالة لمفاتيح مماثلة (كما معظم أنحاء الأرقام) وسريع جدا للبحث عن مع O (م) (م = رئيسي طول) كحد أقصى.

إذا قمت بالبحث عن رئيس الحكومة في شجرة ولدت قبل، يمكنك المشي الشجرة حتى تجد ذلك أو كنت بالفعل في عقدة وهو بجانب الآنفة الذكر ورئيس الوزراء التالية.

Answer 5

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

وإذا كان هناك حل أفضل، ثم كنت تحمل انها تريد الاستفادة من رئيس عدد نظرية أن يظهر بأنه L يحصل على اكبر، والحد من

وπ (L) / (L / من قانون الجنسية (L)) نهج 1.

ولعل أفضل حل لها حل التعبئة التكيف في بنية بيانات نوع من مثل قائمة <تخطي / أ>.

Answer 6

وماذا عن نوع من جدول التجزئة؟

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

Answer 7

وماذا عن شجرة الفاصل؟ http://www.geeksforgeeks.org/interval-tree/

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

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

Answer 8

إذا يمكنك معرفة تلك التي هي ميرسين أو غيرها من الأعداد الأولية ممثلة بسهولة، ل قد تكون قادرة على انقاذ بضعة بت باستخدام أن التمثيل مع إشارة للأرقام المعمول بها.

وأيضا، عن كيفية تخزين أرقام بالفرق من الرقم السابق؟ ثم ينبغي أن حجم لا ترتفع جدا بالسرعة (ولكن البحث تكون بطيئة). مع الجمع بين النهج أعلاه، هل يمكن تخزين يعبي ميرسين والفرق بينه وبين الماضي ميرسين رئيس الوزراء.

Answer 9

وتحقق من توب كودر البرنامج التعليمي على الأعداد الأولية: http://community.topcoder.com/tc؟module=Static&d1=tutorials&d2=math_for_topcoders