باستخدام فهرس طويل مثل ArrayList في Java

Question

أنا أكتب برنامج جافا هذا للعثور على جميع الأعداد الأولية حتى num باستخدام منخل إراتوستينس، ولكن عندما أحاول التجميع، يقول إنه لا يمكنني استخدام var طويل كمؤشر مصفوفة، ويتوقع int var في مكانها.لكنني سأعمل بأعداد كبيرة، لذا لا يمكنني استخدام int.ماذا يمكنني أن أفعل؟

import java.util.*;
import java.lang.*;

public class t3{
    public static void main(String[] args){
        long num = 100;

        //declaring list and filling it with numbers
        ArrayList<Long> numlist = new ArrayList<Long>();
        for(long x=2 ; x<num ; x++){
            numlist.add(new Long(x));
        }

        //sieve or eratosthenes
        for(long x=0 ; x<Math.sqrt(num) ; x++){
            for(long y=x+1 ; y<numlist.size() ; y++){
                if(numlist[y]%numlist[x] == 0){
                    numlist.remove(y);
                }
            }
        }

        //print list
        for(Object item : numlist){
            System.out.println((Long)item);
        }
    }
}

Answer 1

وأنا لست متأكدا من السبب في التعليمات البرمجية من شأنه تجميع لتبدأ.

وأنت ليس من المفترض أن استخدام [] في قائمة مجموعة لأعضاء الوصول. وarraylist هو مجرد القائمة التي يتم تخزينها داخليا في صفيف. لديك لاستخدام العملية القائمة الحصول على (والذي سيظل O (1)). كتابة numlist [المؤشر] يعني أن لديك مجموعة من الكائنات في numlist. لا يمكنك تجاوز [] العملية كما في C ++.

وبالإضافة إلى ذلك، عدد صحيح هو 32 بت في جاوة. وجود مجموعة من طول أكبر من 2 ^ 32 (لذلك كنت في حاجة مؤشرات طويلة) من غير المرجح وأنا لست حتى متأكدا من مواصفات تسمح لها.

Answer 2

أدرك أنه باستخدام فهرس int مُوقع 32 بت إلى فترة طويلة[] فإنك تعالج 16 جيجابايت من ذاكرة الوصول العشوائي.

إذا كنت جادًا حقًا في الحصول على أعداد أولية كبيرة باستخدام المنخل، فلن تفلت من عدة أشياء في المعنى الضمني الحالي الخاص بك:

• ArrayList من الأطوال المعبأة
• باستخدام [] كما يذكر Uri
• لا يتم الترحيل بشكل منهجي إلى القرص

Answer 3

مواصفات جاوة يحد من المصفوفات لفي معظم عناصر Integer.MAX_VALUE. في حين قد تحتوي على List أكثر من العناصر (وهذا صحيح لCollections في عام)، يمكنك فقط إضافة / الحصول على / إزالة / مجموعة لهم باستخدام مؤشر int.

وعلى افتراض أن لديك ذاكرة لذلك العديد من العناصر (من المستبعد جدا على ما أظن)، هل يمكن أن يكتب هيكل البيانات الخاصة بك تتكون من صفائف "متسلسلة". إن أساليب get() وset() تأخذ مؤشر long ومعرفة مجموعة المقابلة ومؤشر int داخل تلك المصفوفة.

وبالإضافة إلى ذلك، أود أن أقترح استخدام القيم المنطقية لتمثيل الدولة من كل عدد، بدلا من تخزين / إزالة كل رقم صراحة. وهذا سيكون أفضل ل(1) القيم المنطقية تأخذ مساحة أقل من صفقات الشراء، و (2) تحويل العناصر (كما هو الحال في ArrayList) خلال إزالة عنصر يمكن أن تكون مكلفة.

Answer 4

وما لا يقل عن الحد الأقصى لحجم النظري صفائف جافا هو Integer.MAX_VALUE. وذلك لأن نوع مؤشر مجموعة هو وفقا لمواصفات عدد صحيح. في واقع الأمر يعتمد على الذاكرة الخاصة بك على الرغم من.

وحتى إذا الخوارزمية الخاصة بك حقا يتوقف على وجود مثل مجموعة كبيرة كنت من الحظ مع صفائف جافا.

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

Answer 5

وكانت هناك مقترحات لإضافة صفائف المفهرسة طويلة إلى جاوة عبر مشروع كوين (<لأ href = "http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html" يختلط = "نوفولو"> http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html ) على الرغم من أن لا شيء قد تم قبول أو المقرر.

Answer 6

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

ولكن نقطة وقد ذكر الآخرين عن مساحة العنوان أيضا نقطة جيدة.

Answer 7

مكتبة jScience ديه ناقلات كبيرة تسمى Float64Vector . في حين لم يسبق لي أن استخدمت هذه الفئة قد تناسب احتياجاتك. لا وعود.

وتحرير: وأشار زاك Scrivena في التعليقات التي وأبعادها وFloat64Vector إلى [إينتس]. أقف تصحيحها.