पूर्णांक अधिकतम

Question

से अधिक आकार की सरणी कैसे बनाएं I 600851475143 से पहले सभी प्राइम्स प्राप्त करने का प्रयास कर रहा था। मैं इसके लिए इरेटोस्टेनेस की चाकू का उपयोग कर रहा था। इसके लिए मुझे उस विशाल आकार की एक बूलियन सरणी बनाने की आवश्यकता है। बुरा विचार, आप स्मृति से बाहर हो सकते हैं। कोई अन्य तरीका। मैंने सही या गलत प्रतिनिधित्व करने के लिए मान1 के साथ प्रत्येक इंडेक्स का उपयोग करके स्ट्रिंग का उपयोग करने का प्रयास किया। लेकिन indexOf विधि भी int देता है।

अगला मैं अपनी समस्या के लिए 2 डी सरणी का उपयोग कर रहा हूं। ऐसी विशाल सरणी को स्टोर करने का कोई और बेहतर तरीका?

Answer 1

BitSet का उपयोग करें। फिर आप किसी भी इंडेक्स तत्व को सेट कर सकते हैं। 600851475143 2^39 है इस प्रकार आंतरिक रूप से केवल 39 बिट्स लेते हैं (असल में वास्तव में यह 64 बिट्स पर कब्जा करेगा क्योंकि यह लंबे समय तक उपयोग करता है)।

आप कर सकते हैं 2^63 तक वास्तव में इस कदम का सबसे प्रयोजनों

Answer 2

के लिए बड़े पैमाने पर है मैं एक ऐसी ही समस्या थी और मैं एक सा सेट का इस्तेमाल किया (मूल रूप से 1 या 0 के लिए निर्धारित क्रम में ऑफसेट वांछित) और मैं इसे EWAHCompressedBitmap उपयोग करने की अनुशंसा भी अपने बिट

संपादित

सेट के रूप में एलन ने कहा BitSet स्मृति के 70GB को घेरता है सेक होगा लेकिन आप एक और बात कर सकते हैं: ताकि आप निरपेक्ष स्थिति की गणना कर सकते कई BitSets (लगातार लोगों के लिए) और मेमोरी में लोड करें बस बिटकसेट जिसे आपको उस पल में आलसी लोड की तरह कुछ चाहिए, इस मामले में आपके पास इस्तेमाल की गई स्मृति का नियंत्रण होगा।

Answer 3

600851475143 बूलियन के लिए स्मृति आवश्यकता सर्वोत्तम 70 जीबी है। यह व्यवहार्य नहीं है। स्टीफन द्वारा सुझाए गए अनुसार आपको संपीड़न का उपयोग करने की आवश्यकता है, या प्राइम्स की गणना के लिए एक अलग एल्गोरिदम खोजना होगा।

Answer 4

यह प्रत्येक नंबर के लिए याद रखना वास्तव में व्यावहारिक नहीं है यदि यह एक प्रमुख था या इतनी बड़ी राशि के लिए नहीं (चलनी सामान्य रूप से बड़ी संख्या में धीमी गति है)।

इस link से आप एक विचार है कि कितने अभाज्य संख्या वहाँ एक्स की तुलना में छोटे उम्मीद की जा करने के लिए अपने 600 बिलियन रेंज आप मोटे तौर पर 20 अरब का अभाज्य उस सीमा के भीतर मौजूद हैं की उम्मीद कर सकते हैं के लिए मिलता है। उन्हें लंबे समय तक भंडारित करना [] को लगभग 160 जीबी मेमोरी की आवश्यकता होगी ... जो कि प्रत्येक संख्या के लिए एक बिट को स्टोर करने के लिए सुझाए गए 70 जीबी से अधिक है, आधा अगर आप संख्याओं को भी बाहर करते हैं (2 केवल एकमात्र प्रधान है)।

डेस्कटॉप कंप्यूटर के लिए 35 जीबी मेमोरी में थोड़ा सा हो सकता है, लेकिन एक अच्छा वर्कस्टेशन में इतना रैम हो सकता है। मैं थोड़ा स्थानांतरण/मास्किंग के साथ एक द्वि-आयामी सरणी कोशिश करता हूँ।

मैं अब भी आपके चलनी कोड को चलाने के लिए समय (कुछ दिनों से कुछ) चलाने की अपेक्षा करता हूं। मेरा सुझाव है कि आप चलनी की तुलना में अधिक उन्नत प्राइम डिटेक्शन विधियों की जांच करें।

Answer 5

आप हॉटस्पॉट के आंतरिक sun.misc.Unsafe API का उपयोग बड़े सरणी को आवंटित करने के लिए कर सकते हैं। I wrote a blogpost how to simulate an array with it हालांकि, यह एक आधिकारिक जावा एपीआई नहीं है, इसलिए यह एक हैक के रूप में योग्यता प्राप्त करता है।