Udvide array's

Nej.

Alloker et nyt større og kopier data.

Men langt bedre: brug ArrayList eller en anden dynamisk struktur

Og et array der ikke er nogen referencer til bliver garbage collectet

Han ville ikke bruge et arraylist.... den er jo langsom..

Så som du først sagde.. så bliver han nød til at lave en ny og kopirer data'en derover

glemte at sige det kun kan betale sig at bruge en array hvis du kun har til formål at kopirer dataen over i en større array. Hvis du begynder og lave add, get og alle de funktioner en arraylist har så kan du ligeså godt bruge arraylist!

En ArrayList er da ikke langsom!

Så vidt jeg ved ligger der inde i en ArrayList et array, som indeholder de elementer man gemmer i listen. Og hvis det bliver nødvendigt gør den dette array større ved at oprette et nyt og kopiere data over i. Og den gør brug af System.arraycopy(...) som vist er klart den hurtigste måde at kopiere at array på!!!

Og ArrayList har en metode der hedder trimToSize() - som fjerner tomme pladser i arrayet.

Og hvis han kører Java 5.0 kan han jo bruge generics:

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);


Hvor det er muligt at typebestemme ArrayList'en - og man derigennem slipper for de simple datatypers wrapperklasser.

ArrayList er langsommere end array.

Men jeg tvivler på at forskellen betyder noget i ret mange applikationer.

I 99 ud af 100 programmer så erlangt den største omkostning de timer der
bruges til udvikling og vedligehold. Hardware er billigt. Derfor er det
vigtigste at skrive pæn vedligeholdelses venligt kode. Der er selvfølgelig
undtagelser, men ikke så mange.

tag det rolig mikkelbm og lad være med at komme på tværs... en ArrayList er langsommere end en array! det et FAKTUM!

og min kommentar

Kommentar: kalp
16/11-2004 10:06:53

er ellers meget dækkende.....

der er forskel på om ArrayLister lettere at anvende(hurtigere) og på performance.. hastighed!

Okay. Jeg troede de var lige hurtige (i og med at ArrayList indeholder et array).

Hvad er det der gør, at en ArrayList er langsommere? Hvis man siger get(int) på en ArrayList henter den da elementet fra arrayet...!?

Jeg synes heller ikke jeg kommer på tværs! Jeg underbygger bare Arnes teori om at det i langt de fleste tilfælde bedre ville kunne betale sig at bruge en ArrayList i stedet for at skrive den samme kode selv!

mikkelbm:

du har ret i at en ArrayList er dejlig nem at anvende og i den forstand "hurtig" at bruge.. men selve ArrayList er langsom, at loade. En en almindelig array med fastlagt størrelse loader meget hurtigere... og det er det spørgeren mener angående performance: ) som jeg har forstået det i hvertfald... han udelukker netop ArrayList af denne grund..

og min kommentar 16/11-2004 10:06:53 giver dig ret i at det dumt at skrive det samme funktioner selv... så er man næsten dum:o)

Jeg forstår ikke helt hvad der menes med "loader" i denne sammenhæng.

Den primære grund til at ArrayList er langsommere end arrays er at elementerne
skal konverteres til objekter.

Jeg lavede lige et eksempel.

Kode:

import java.util.*;

public class ArrayVersusArrayList {
    private final static int N1 = 100;
    private final static int N2 = 50000;
    private final static int N3 = 10;
    private static void test(String s, WrapperFactory wf) {
        long t1 = System.currentTimeMillis();
        for(int i = 0; i < N1; i++) {
            Wrapper w = wf.getWrapper();
            for(int j = 0; j < N2; j++) {
                w.set(j, j);
            }
            for(int k = 0; k < N3; k++) {
                for(int j = 0; j < N2; j++) {
                    if(w.get(j) != j) {
                        throw new RuntimeException("Ooops");
                    }
                }
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println(s + ": " + (t2 - t1));
    }
    private static void testSimpeltArrayInline() {
        long t1 = System.currentTimeMillis();
        for(int i = 0; i < N1; i++) {
            int[] a = new int[1000];
            for(int j = 0; j < N2; j++) {
                if(j >= a.length) {
                    int[] tmp = a;
                    a = new int[tmp.length + 1000];
                    System.arraycopy(tmp, 0, a, 0, tmp.length);
                }
                a[j] = j;
            }
            for(int k = 0; k < N3; k++) {
                for(int j = 0; j < N2; j++) {
                    if(a[j] != j) {
                        throw new RuntimeException("Ooops");
                    }
                }
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("simpelt array inline: " + (t2 - t1));
    }
    private static void testObjectArrayInline() {
        long t1 = System.currentTimeMillis();
        for(int i = 0; i < N1; i++) {
            Integer[] a = new Integer[1000];
            for(int j = 0; j < N2; j++) {
                if(j >= a.length) {
                    Integer[] tmp = a;
                    a = new Integer[tmp.length + 1000];
                    System.arraycopy(tmp, 0, a, 0, tmp.length);
                }
                a[j] = new Integer(j);
            }
            for(int k = 0; k < N3; k++) {
                for(int j = 0; j < N2; j++) {
                    if(a[j].intValue() != j) {
                        throw new RuntimeException("Ooops");
                    }
                }
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("object array inline: " + (t2 - t1));
    }
    private static void testArrayListInline() {
        long t1 = System.currentTimeMillis();
        for(int i = 0; i < N1; i++) {
            ArrayList list = new ArrayList();
            for(int j = 0; j < N2; j++) {
                list.add(j, new Integer(j));
            }
            for(int k = 0; k < N3; k++) {
                for(int j = 0; j < N2; j++) {
                    if(((Integer)list.get(j)).intValue() != j) {
                        throw new RuntimeException("Ooops");
                    }
                }
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("ArrayList inline: " + (t2 - t1));
    }
    public static void main(String[] args) {
        test("simpelt array", new SimpleArrayWrapperFactory());
        test("object array", new ObjectArrayWrapperFactory());
        test("ArrayList", new ArrayListWrapperFactory());
        testSimpeltArrayInline();
        testObjectArrayInline();
        testArrayListInline();
    }
}

interface WrapperFactory {
    public Wrapper getWrapper();
}

class SimpleArrayWrapperFactory implements WrapperFactory {
    public Wrapper getWrapper() {
        return new SimpleArrayWrapper();
    }
}

class ObjectArrayWrapperFactory implements WrapperFactory {
    public Wrapper getWrapper() {
        return new ObjectArrayWrapper();
    }
}

class ArrayListWrapperFactory implements WrapperFactory {
    public Wrapper getWrapper() {
        return new ArrayListWrapper();
    }
}

interface Wrapper {
    public void set(int ix, int v);
    public int get(int ix);
}

class SimpleArrayWrapper implements Wrapper{
    private int[] a;
    public SimpleArrayWrapper() {
        a = new int[1000];
    }
    public void set(int ix, int v) {
        if(ix >= a.length) {
            int[] tmp = a;
            a = new int[tmp.length + 1000];
            System.arraycopy(tmp, 0, a, 0, tmp.length);
        }
        a[ix] = v;
    }
    public int get(int ix) {
        return a[ix];
    }
}

class ObjectArrayWrapper implements Wrapper{
    private Integer[] a;
    public ObjectArrayWrapper() {
        a = new Integer[1000];
    }
    public void set(int ix, int v) {
        if(ix >= a.length) {
            Integer[] tmp = a;
            a = new Integer[tmp.length + 1000];
            System.arraycopy(tmp, 0, a, 0, tmp.length);
        }
        a[ix] = new Integer(v);
    }
    public int get(int ix) {
        return a[ix].intValue();
    }
}

class ArrayListWrapper implements Wrapper {
    private ArrayList list;
    public ArrayListWrapper() {
        list = new ArrayList();
    }
    public void set(int ix, int v) {
        list.add(ix, new Integer(v));
    }
    public int get(int ix) {
        return ((Integer)list.get(ix)).intValue();
    }
}

Output:

simpelt array: 2405
object array: 4858
ArrayList: 4258
simpelt array inline: 1433
object array inline: 4167
ArrayList inline: 3767

Det ses klart at det er simpel data type versus objekt som gør forskellen
ikke array versus ArrayList i sig selv.

Jeg er med på, at det er performance der er tale om. Men... Når man skriver:
ArrayList list = new ArrayList();

Allokerer den en array inde i ArrayList med plads til 10 elementer. Og det at det er et array der ligger inde i ArrayListen, vil jeg mene øger performance i forhold til andre Collection-klasser. Efterhånden som de 10 pladser bliver fyldt ud fordobler den
(så vidt jeg husker) arrayet - hvilket vel kan være den eneste hage ved det!???

Ahh - selvfølgelig, Arne. Jeg havde det ikke lige i mente, at det var objekter vs. simple datatyper.

Og man kan se at en ArrayList kan klare over 10 millioner get's i sekundet.

Og jeg mener stadig at de færreste har brug for det.

jesper>

Udover den meget interessante diskussion om hvad der performer bedst, så
kan du også se i koden ovenfor hvordan man bruger System.arraycopy !

Array = "Besværlig" - men hurtig
ArrayList = Let anvendlig - men langsom

læs evt. på hvad der er negativt ved en array og hastighed vil være det som bliver belyst.

ved loader mener jeg at initialisere arrayet...

uden at diskutere videre (for skal ud nu..måske i aften igen:)) vil jeg holde mig til min mening... de to første linier i denne kommentar... det er hvad jeg har lært af erfaring og læst mig frem til i de forskellige lærebøger om faget.

jeg vil studere dit eksempel i aften arne hehe

Så lad mig selv bidrage lidt til diskussionen.

Arrays af simple typer er hurtigere end ArrayList's, men ArrayList's er ikke bare ArrayList's. Når man fylder en ArrayList med objekter, som blot er simple typer wrap'et ind i et objekt, kan man enten anvende en wrapper-klasse på elementet eller gemme i et array med plads til netop ét element, idet dette også er et objekt (!). Det sidste er betragteligt hurtigere men ikke så hurtigt som et array af simpel type.

Videre har "oprydning" en del betydning for hastigheden, hvilket man kan prøve af ved at fjerne "null"-referencerne.

Eks.:

import java.util.*;
public class Arrayspeed {
   
    public static void main(String[] args) {
        long antal, starttid, sluttid;
        int arraysize=1000000;
       
        //Array af simpel type
        starttid = System.currentTimeMillis();
        double[] d=new double[arraysize];
        antal=0;
        for (int i=0;i<arraysize;i++) {
            d[i]=Math.random();
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("Array af simpel type,  Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        d=null;
       
        //ArrayList med wrapper
        starttid = System.currentTimeMillis();
        ArrayList al1=new ArrayList();
        antal=0;
        for (int i=0;i<arraysize;i++) {
            al1.add(new Double(Math.random()));
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("ArrayList med wrapper, Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        al1=null;
       
        //ArrayList med array[1]
        starttid = System.currentTimeMillis();
        ArrayList al2=new ArrayList();
        double[] d2=new double[1];
        antal=0;
        for (int i=0;i<arraysize;i++) {
            d2[0]=Math.random();
            al2.add(d2);
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("ArrayList med array,  Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        al2=null;
    }   
}

- giver flg. resultat:

Array af simpel type,  Antal: 1000000 Tid 0.261 sek.
ArrayList med wrapper, Antal: 1000000 Tid 1.762 sek.
ArrayList med array,  Antal: 1000000 Tid 0.541 sek.

Nogle kommentarer til dette?

Den terdie er hurtigere end den anden. Men prøv lige at check indholdet !  :-)

Den tredie er ...

Prøv lige at lave din linje:

d2[0]=Math.random();
om til :
d2 = new double[]{Math.random()};

Så nærmer tiderne sig hinanden.

Som Arne også påpeger!

->mikkelbm: Ja, det er sandt, men så er det omtrent også samme tankegang i 2) og 3)
->arne_v: Ja, det kan jeg godt se..indholdet er ikke selve tallet, som jeg troede :-)

Det var ikke kun det. Man kan nemt kliste [0] på det man getter.

Men prøv og kør:

import java.util.*;

public class X {
    public static void main(String[] args) {
        double[] d = new double[1];
        ArrayList list = new ArrayList();
        d[0] = 1;
        list.add(d);
        d[0] = 2;
        list.add(d);
        System.out.println(((double[])list.get(0))[0] + " " + ((double[])list.get(1))[0]);
    }
}

->arne_v: Ja, det går galt, fordi der ikke løbende oprettes nye array-objekter - det er samme reference i begge tilfælde nemlig svarende til den sidste værdi. Indskyder man linien "d = new double[1];" efter den første "list.add(d)", går det godt, men det koster også på tiden!

I mit eks. bliver det noget med:

        //ArrayList med array[1]
        starttid = System.currentTimeMillis();
        ArrayList al2=new ArrayList();
        double[] d2;
        antal=0;
        for (int i=0;i<arraysize;i++) {
            d2=new double[1];
            d2[0]=Math.random();
            al2.add(d2);
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("ArrayList med array,  Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        System.out.println(((double[])al2.get(0))[0]);
        al2=null;

- og så går det vist godt, omend det går hårdt ud over tiden.

Med denne rettelse får jeg nu:
Array af simpel type,  Antal: 1000000 Tid 0.271 sek.
ArrayList med wrapper, Antal: 1000000 Tid 1.932 sek.
ArrayList med array,  Antal: 1000000 Tid 1.592 sek.

- altså stadig lidt hurtigere i 3) end 2) forudsat der ikke er fejl :-)

Hvis dette holder, er det da lidt interessant.

import java.util.*;

public class ArrayVersusArrayList {
    private final static int N1 = 100;
    private final static int N2 = 50000;
    private final static int N3 = 10;
    private static void test(String s, WrapperFactory wf) {
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < N1; i++) {
            Wrapper w = wf.getWrapper();
            for (int j = 0; j < N2; j++) {
                w.set(j, j);
            }
            for (int k = 0; k < N3; k++) {
                for (int j = 0; j < N2; j++) {
                    if (w.get(j) != j) {
                        throw new RuntimeException("Ooops");
                    }
                }
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println(s + ": " + (t2 - t1));
    }
    private static void testSimpeltArrayInline() {
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < N1; i++) {
            int[] a = new int[1000];
            for (int j = 0; j < N2; j++) {
                if (j >= a.length) {
                    int[] tmp = a;
                    a = new int[tmp.length + 1000];
                    System.arraycopy(tmp, 0, a, 0, tmp.length);
                }
                a[j] = j;
            }
            for (int k = 0; k < N3; k++) {
                for (int j = 0; j < N2; j++) {
                    if (a[j] != j) {
                        throw new RuntimeException("Ooops");
                    }
                }
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("simpelt array inline: " + (t2 - t1));
    }
    private static void testObjectArrayInline() {
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < N1; i++) {
            Integer[] a = new Integer[1000];
            for (int j = 0; j < N2; j++) {
                if (j >= a.length) {
                    Integer[] tmp = a;
                    a = new Integer[tmp.length + 1000];
                    System.arraycopy(tmp, 0, a, 0, tmp.length);
                }
                a[j] = new Integer(j);
            }
            for (int k = 0; k < N3; k++) {
                for (int j = 0; j < N2; j++) {
                    if (a[j].intValue() != j) {
                        throw new RuntimeException("Ooops");
                    }
                }
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("object array inline: " + (t2 - t1));
    }
    private static void testArrayListInline() {
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < N1; i++) {
            ArrayList list = new ArrayList();
            for (int j = 0; j < N2; j++) {
                list.add(j, new Integer(j));
            }
            for (int k = 0; k < N3; k++) {
                for (int j = 0; j < N2; j++) {
                    if (((Integer) list.get(j)).intValue() != j) {
                        throw new RuntimeException("Ooops");
                    }
                }
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("ArrayList inline: " + (t2 - t1));
    }
    private static void testArrayListArrayInline() {
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < N1; i++) {
            ArrayList list = new ArrayList();
            for (int j = 0; j < N2; j++) {
                int[] v2 = new int[1];
                v2[0] = j;
                list.add(j, v2);
            }
            for (int k = 0; k < N3; k++) {
                for (int j = 0; j < N2; j++) {
                    if (((int[]) list.get(j))[0] != j) {
                        throw new RuntimeException("Ooops");
                    }
                }
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("ArrayList array inline: " + (t2 - t1));
    }
    public static void main(String[] args) {
        test("simpelt array", new SimpleArrayWrapperFactory());
        test("object array", new ObjectArrayWrapperFactory());
        test("ArrayList", new ArrayListWrapperFactory());
        test("ArrayList array", new ArrayListArrayWrapperFactory());
        testSimpeltArrayInline();
        testObjectArrayInline();
        testArrayListInline();
        testArrayListArrayInline();
    }
}

interface WrapperFactory {
    public Wrapper getWrapper();
}

class SimpleArrayWrapperFactory implements WrapperFactory {
    public Wrapper getWrapper() {
        return new SimpleArrayWrapper();
    }
}

class ObjectArrayWrapperFactory implements WrapperFactory {
    public Wrapper getWrapper() {
        return new ObjectArrayWrapper();
    }
}

class ArrayListWrapperFactory implements WrapperFactory {
    public Wrapper getWrapper() {
        return new ArrayListWrapper();
    }
}

class ArrayListArrayWrapperFactory implements WrapperFactory {
    public Wrapper getWrapper() {
        return new ArrayListArrayWrapper();
    }
}

interface Wrapper {
    public void set(int ix, int v);
    public int get(int ix);
}

class SimpleArrayWrapper implements Wrapper {
    private int[] a;
    public SimpleArrayWrapper() {
        a = new int[1000];
    }
    public void set(int ix, int v) {
        if (ix >= a.length) {
            int[] tmp = a;
            a = new int[tmp.length + 1000];
            System.arraycopy(tmp, 0, a, 0, tmp.length);
        }
        a[ix] = v;
    }
    public int get(int ix) {
        return a[ix];
    }
}

class ObjectArrayWrapper implements Wrapper {
    private Integer[] a;
    public ObjectArrayWrapper() {
        a = new Integer[1000];
    }
    public void set(int ix, int v) {
        if (ix >= a.length) {
            Integer[] tmp = a;
            a = new Integer[tmp.length + 1000];
            System.arraycopy(tmp, 0, a, 0, tmp.length);
        }
        a[ix] = new Integer(v);
    }
    public int get(int ix) {
        return a[ix].intValue();
    }
}

class ArrayListWrapper implements Wrapper {
    private ArrayList list;
    public ArrayListWrapper() {
        list = new ArrayList();
    }
    public void set(int ix, int v) {
        list.add(ix, new Integer(v));
    }
    public int get(int ix) {
        return ((Integer) list.get(ix)).intValue();
    }
}

class ArrayListArrayWrapper implements Wrapper {
    private ArrayList list;
    public ArrayListArrayWrapper() {
        list = new ArrayList();
    }
    public void set(int ix, int v) {
        int[] v2 = new int[1];
        v2[0] = v;
        list.add(ix, v2);
    }
    public int get(int ix) {
        return ((int[]) list.get(ix))[0];
    }
}

simpelt array: 5657
object array: 11609
ArrayList: 6453
ArrayList array: 7047
simpelt array inline: 4875
object array inline: 11922
ArrayList inline: 6765
ArrayList array inline: 6969

Det bekræfter ikke din hypotese.

Det kan der være flere grunde til bl.a. har jeg et forhold mellem add og get på 1:10.

[I skal ikke sammenligne tallene med sidste kørsel - Java 1.5.0 på Athlon XP 2000+
og Java 1.4.2 på Pentium M 1.6]

kalp>

Med hensyn til bøger:

Effective Java / Joshua Bloch - Item 30 : for brug af libraries & nævner explicit collections som givende både mindre kode og bedre performance

Java Performance Tuning / Jack Schirazi - Chapter 3 : nævner problemet med at
Vector har et pænt overhead når den bruges til simple data typer

Java Performance Tuning / Jack Schirazi - Chapter 11 : siger at arrays er hurtigere
end collections men at de ikke er så gode for det objektorienterede design, siger
også at ArrayList og Vector har glimrende performance og konkluderer at man skal
overveje arrays eller special klasser

Det vil jeg tolke som 60-40 i favør af ArrayList.

->arne_v: Hvad får du, hvis du kører mit (tilrettede) simple eks.?

import java.util.*;
public class Arrayspeed {
   
    public static void main(String[] args) {
        long antal, starttid, sluttid;
        int arraysize=1000000;
       
        //Array af simpel type
        starttid = System.currentTimeMillis();
        double[] d=new double[arraysize];
        antal=0;
        for (int i=0;i<arraysize;i++) {
            d[i]=Math.random();
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("Array af simpel type,  Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        d=null;
       
        //ArrayList med wrapper
        starttid = System.currentTimeMillis();
        ArrayList al1=new ArrayList();
        antal=0;
        for (int i=0;i<arraysize;i++) {
            al1.add(new Double(Math.random()));
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("ArrayList med wrapper, Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        al1=null;
       
        //ArrayList med array[1]
        starttid = System.currentTimeMillis();
        ArrayList al2=new ArrayList();
        double[] d2;
        antal=0;
        for (int i=0;i<arraysize;i++) {
            d2=new double[1];
            d2[0]=Math.random();
            al2.add(d2);
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("ArrayList med array,  Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        al2=null;
    }   
}

Jeg får stadig, at 3) kører hurtigere end 2). Men garbage collection er åbenbart vigtig. Hvis ikke der ryddes op, kører 3) langsommere end 2).

Afvikler jeg de forskellige test i dit program enkeltvis, får jeg andre resultater end ved én samlet kørsel af dit program.

Array af simpel type,  Antal: 1000000 Tid 0.188 sek.
ArrayList med wrapper, Antal: 1000000 Tid 1.203 sek.
ArrayList med array,  Antal: 1000000 Tid 1.031 sek.

Prøv iøvrigt at kør det med:

java -server  Arrayspeed

(det ændrer lidt)

Man burde nok sætte N1 lidt op i mit program for at få mere stabile resultater, men
det tager jo lang tid så ...

Kommentar: arne_v
16/11-2004 21:58:26

Jeg følger med i jeres tests.... men uanset hvad der er lettest og hurtigst... så er forskellen ikke så stor. Men vil stadig mene, at en simpel array er hurtigere end en ArrayList.

Dermed er det heller ikke sagt, at ArrayList kører på skildpadde niveau...

Bil A har en vægt på 100kg og en max hastighed på 220km i timen
Bil B har en vægt på 130kg og en max hastighed på 220km i timen

begge er hurtigere... men hvem kommer først op i omdrejninger?

skulle man virkelig være ivrig efter at anvende en arraylist, men man af en eller anden grund pludselig synes en array er mere passende i en given situation skulle man vist også kunne gøre dette

myArrayList.ToArray();

og så få en array ud af det.

kiggede lidt på nogen devoloper sites.. og præcis dette emne finder i her

http://www.developersdex.com/asp/message.asp?p=2912&r=4699959

array vs arraylist

Nu er det altså C# og ikke Java ...

Og selvfølgelig er de grundliggende problem stillinger helt de samme, men
performance metrics behøver ikke være det.

Jeg er ret overbevist om at overhead ved ArrayList er større jo ældre JVM man
kører det på.

Et lille trick:

Object[] a = list.toArray();

er ubrugelig men:

X[] a = (X[])list.toArray(new X[list.size()]);

er praktisk.

Den foreløbige korte konklusion er vel, at simple arrays er betydelig hurtigere end Arrayobjekter. Hertil kan komme problemstillingen omkring memory-forbrug, som vi ikke har diskuteret.

Ved behandling af meget store datamængder kan såvel tid som memory-forbrug være helt afgørende (hvis man så vidt muligt vil undgå at skrive til en ekstern fil, som virkelig er en "tidsrøver"), og man kan så overveje, hvordan man designmæssigt bør bære sig ad, hvis man vælger at bruge simple arrays og ikke skal løbe ind i memory-problemer.

Jeg ville faktisk konkludere anderledes.

Der er reelt intet overhead ved ArrayList fremfor array for objekter.

Der er noget overhead ved ArrayList fremfor array for simple data typer.

Hvis forskellen skal have målbar indflydelse på den samlede applikations
performance skal man op over 1 million gange tilgang i sekundet.

ArrayList giver den simpleste kode som er billigst at vedligeholde.

I de fleste tilfælde vil det gøre ArrayList til det bedste valg.

Men selvfølgelig kan der eksistere undtagelser.

Og et lidt anderledes resultat fra kørsel på IBM JVM 1.3.1:

simpelt array: 5500
object array: 6079
ArrayList: 3609
ArrayList array: 3812
simpelt array inline: 2969
object array inline: 5110
ArrayList inline: 2296
ArrayList array inline: 3235

Man kunne godt få en mistanke om at de har lavet et eller andet snedigt med
ArrayList !

->arne_v: Kan der yderligere være noget omkring "initialCapacity" i konstruktøren af ArrayList, som påvirker resultaterne?

Ja.

Jo færre gange ArrayList'en skal udvide sig selv eller et array skal
udvides manuelt jo bedre performance.

->arne_v: Jeg har stadig svært ved at sammenligne dine og mine resultater. I mit eks. er det så dramatisk bedre (i hvert fald relativt tiderne imellem) at anvende simple arrays. Kan der være noget galt?

Der er ingen grund til at dine og mine resulatter skulle være de samme.

Du tester 100% add.

Jeg tester 10% add og 90% get.

Derudover spiller valg af JVM og settings også en rolle.

SUN JVM, SUN JVM med -server og IBM JVM giver vidt forskellige resultater.

->arne_v: Prøver lige at kombinere 2) og 3) i en 4) i mit eks.:

import java.util.*;
public class Arrayspeed {
   
    public static void main(String[] args) {
        long antal, starttid, sluttid;
        int arraysize=1000000;
       
        //Array af simpel type
        starttid = System.currentTimeMillis();
        double[] d=new double[arraysize];
        antal=0;
        for (int i=0;i<arraysize;i++) {
            d[i]=Math.random();
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("(1) Array af simpel type,  Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        d=null;
       
        //ArrayList med wrapper
        starttid = System.currentTimeMillis();
        ArrayList al1=new ArrayList();
        antal=0;
        for (int i=0;i<arraysize;i++) {
            al1.add(new Double(Math.random()));
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("(2) ArrayList med wrapper, Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        al1=null;
       
        //ArrayList med array[1]
        starttid = System.currentTimeMillis();
        ArrayList al2=new ArrayList();
        double[] d2;
        antal=0;
        for (int i=0;i<arraysize;i++) {
            d2=new double[1];
            d2[0]=Math.random();
            al2.add(d2);
            antal++;
        }
        sluttid = System.currentTimeMillis();
        System.out.println("(3) ArrayList med array,  Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        al2=null;
       
        //Kombination af array af simpel type og ArrayList
        int[] chunks={1000000,10000,100,1};
        int arraysize2;
        double[] d3;
        ArrayList al3;
        for (int c=0;c<chunks.length;c++) {
            starttid = System.currentTimeMillis();
            arraysize2=(int)arraysize/chunks[c];
            al3=new ArrayList();
            antal=0;
            for (int i=0;i<chunks[c];i++) {
                d3=new double[arraysize2];
                for (int j=0;j<arraysize2;j++) {
                    d3[j]=Math.random();
                    antal++;
                }
                al3.add(d3);
            }
            sluttid = System.currentTimeMillis();
            System.out.println("(4."+c+") Kombination, Chunks: "+chunks[c]+" Arraysize: "+arraysize2+" Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
            al3=null;           
        }       
    }   
}

- hvilket giver flg. resultater:
(1) Array af simpel type,  Antal: 1000000 Tid 0.27 sek.
(2) ArrayList med wrapper, Antal: 1000000 Tid 1.773 sek.
(3) ArrayList med array,  Antal: 1000000 Tid 1.552 sek.
(4.0) Kombination, Chunks: 1000000 Arraysize: 1 Antal: 1000000 Tid 1.512 sek.
(4.1) Kombination, Chunks: 10000 Arraysize: 100 Antal: 1000000 Tid 0.421 sek.
(4.2) Kombination, Chunks: 100 Arraysize: 10000 Antal: 1000000 Tid 0.27 sek.
(4.3) Kombination, Chunks: 1 Arraysize: 1000000 Antal: 1000000 Tid 0.231 sek.

Kørslerne (3) og (4.0) bør give nogenlunde samme resultater, og det samme bør være  tilfældet med (1) og (4.3).

Kørslerne (4.1-3) kører altså væsentligt hurtigere end f.eks. (2), som er den simpleste ArrayList. Og kørslerne (4.1-3) giver den dynamik, som man kan have brug for i forbindelse med løbende udvidelse af arrays samtidig med, at den bevarer den høje hastighed fra simple arrays.

Du bør nok også teste på get fremfor kun på add.

Du skal huske at hvis array size ikke går op i det totale antal, så får du
et ikke helt udfyldt array i det sidste element i ArrayList'en.

->arne_v: Prøver lige..

import java.util.*;
public class Arrayspeed {
   
    public static void main(String[] args) {
        long starttid, sluttid;
        int antal;
        double x;
        int arraysize=1000000;
       
        //Array af simpel type
        starttid = System.currentTimeMillis();
        double[] d=new double[arraysize];
        antal=0;
        // Gemmer data
        for (int i=0;i<arraysize;i++) {
            d[i]=Math.random();
            antal++;
        }
        // Henter data igen
        for (int i=0;i<arraysize;i++) {
            x=d[i];
        }
        sluttid = System.currentTimeMillis();
        System.out.println("(1) Array af simpel type,  Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        d=null;
       
        //ArrayList med wrapper
        starttid = System.currentTimeMillis();
        ArrayList al1=new ArrayList();
        antal=0;
        // Gemmer data
        for (int i=0;i<arraysize;i++) {
            al1.add(new Double(Math.random()));
            antal++;
        }
        // Henter data igen
        for (int i=0;i<arraysize;i++) {
            x=((Double)al1.get(i)).doubleValue();
        }
        sluttid = System.currentTimeMillis();
        System.out.println("(2) ArrayList med wrapper, Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        al1=null;
       
        //ArrayList med array[1]
        starttid = System.currentTimeMillis();
        ArrayList al2=new ArrayList();
        double[] d2;
        antal=0;
        // Gemmer data
        for (int i=0;i<arraysize;i++) {
            d2=new double[1];
            d2[0]=Math.random();
            al2.add(d2);
            antal++;
        }
        // Henter data igen
        for (int i=0;i<arraysize;i++) {
            x=((double[])al2.get(i))[0];
        }
        sluttid = System.currentTimeMillis();
        System.out.println("(3) ArrayList med array,  Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
        al2=null;
       
        //Kombination af array af simpel type og ArrayList
        int[] chunks={1000000,10000,100,1};
        int arraysize2;
        double[] d3;
        ArrayList al3;
        // Prøver med forskelige "chunks"
        for (int c=0;c<chunks.length;c++) {
            starttid = System.currentTimeMillis();
            arraysize2=Math.round(arraysize/chunks[c]);
            al3=new ArrayList();
            antal=0;
            // Gemmer data
            for (int i=0;i<chunks[c];i++) {
                d3=new double[arraysize2];
                for (int j=0;j<arraysize2;j++) {
                    d3[j]=Math.random();
                    antal++;
                }
                al3.add(d3);
            }
            // Henter data igen
            for (int i=0;i<chunks[c];i++) {
                for (int j=0;j<arraysize2;j++) {
                    x=((double[])al3.get(i))[j];                   
                }
            }
            sluttid = System.currentTimeMillis();
            System.out.println("(4."+c+") Kombination, Chunks: "+chunks[c]+" Arraysize: "+arraysize2+" Antal: "+antal+" Tid "+ (sluttid-starttid)*0.001 +" sek.");
            al3=null;           
        }       
    }   
}

- med flg. resultater:
(1) Array af simpel type,  Antal: 1000000 Tid 0.29 sek.
(2) ArrayList med wrapper, Antal: 1000000 Tid 1.863 sek.
(3) ArrayList med array,  Antal: 1000000 Tid 1.582 sek.
(4.0) Kombination, Chunks: 1000000 Arraysize: 1 Antal: 1000000 Tid 1.563 sek.
(4.1) Kombination, Chunks: 10000 Arraysize: 100 Antal: 1000000 Tid 0.471 sek.
(4.2) Kombination, Chunks: 100 Arraysize: 10000 Antal: 1000000 Tid 0.32 sek.
(4.3) Kombination, Chunks: 1 Arraysize: 1000000 Antal: 1000000 Tid 0.29 sek.

Samme billede som ovenfor.

Jo men er det umagen værd ?

Du laver noget kompleks kode som tilmed har nogle potentielle problemer
hvis antal elementer ikke er et multipla af chunk size.

For at spare 1.5 CPU sekund på 1 million add og get.

->arne_v: Ja, det er umiddelbart sandt.

Et par bemærkninger:

Øvelsen her med arraysize2=Math.round(arraysize/chunks[c]) er selvfølgelig lidt noget programmeringsmæssigt juks, som du påpeger. Konstruktionen er her bare valgt fordi den var nem og for at få nøjagtig samme antal (1000000) i alle test-kørsler. Ellers skal man jo holde sig strengt til integers ved løkker - enig!

Men konklusionen er vel fortsat, at der er fornuft i at sammensætte klumper af simple arrays performance-mæssigt (denne sammensætning kan man så pakke ind i sin egen klasse, så den lidt komplicerede kode er gemt af vejen).

Hvis anvendelsen er indlæsning af meget store datamængder med en del talgymnastik i halen på indlæsningen, ganger alle tidsforbrugene formentlig op, og så tror jeg, det svarer sig at bruge krudt på en smidig indlæsning og enkel repræsentation i simple (array-)typer snarere end (Array-)objekter.

Men bortset fra denne anvendelse er jeg 100% enig med dig. Jeg har kodet meget i APL for år tilbage, og det er fantastisk kompakt men fuldstændig ulæseligt (læses i øvrigt fra højre mod venstre!)- selv for programmøren efterfølgende!

Hvad iøvrigt med memory-forbrug: Objekter vs. simple typer? Her er nok en del "fedt" på objekterne i forhold til de simple typer.

->arne_v: Smid lige et svar

svar

En lidt underlig diskussion :-))

grunden til at arraylist er langsommere er vel netop at der i en arraylist er taget hensyn til ønsker om at udvide/krympe listen.

Så når vi udvider et simpelt array med kode til at tage den slags hensyn vil der også komme mindre god performance der.

Tilbage er så spørgsmålet om hvor effektivet koden er implementeret og det kan vi nok regne med at SUN's professionelle implementering nok er bedre end hvad vi kan flikke sammen på 5 minutter. Og de kan endda optimere helt ned på bytecode niveau.

Men belastningsmønsteret betyder også noget ( 90% add/delete : 10% get ) vil give en anden karateristik end ( 10% add/delete : 90% get ). Det kan vi tage hensyn til i vor egen kode, imens SUN's kode nødvendigvis må være optimeret henimod et gennemsnit.

Der skal en meget ekstrem situation til før jeg ikke vælger den der arraylist.

mvh JakobA

->jakoba: Hmm.. :-)

Valg af løsning afhænger selvfølgelig i høj grad af anvendelsen i forhold til kodens kompleksitet. I mit tilfælde interesserer jeg mig for læsning og efterbehandling af ret store datamængder som det primære, så i det lys er performance afgørende.

Videre har jeg den holdning, at kompleks kode ikke er problematisk for så vidt koden kan indkapsles på fornuftig vis i en afgrænset klasse. Sortering er et godt eksempel herpå. Resultatet af en sortering er udefra banal, men de forskellige sorteringsalgoritmer kan være temmelig komplekse under "motorhjelmen". Læsning og skrivning af data er et andet eksempel.

Hvis ellers mine egne resultater er valide, er der markant forskel på at anvende simple datatyper i forhold til objekter. Ved dog f.eks. at anvende en kombinationsløsning, hvor man fylder en ArrayList med arrays af simpel type opnår man både hurtig performance og den nødvendige dynamik, som jeg ser det. Herudover kan memory-forbrug være en faktor, hvilket vi slet ikke har diskuteret endnu.

Din kommentar omkring SUN er jeg nok ikke enig i. En af erkendelserne omkring Java IO var vel, at (bl.a.) performance var for dårlig, hvorfor Java NIO tilbyder en mere "low-level" adgang til data. Der er også andre eksempler på klasser (f.eks. behandling af String's), som performer dårligt, men som nok også snarere er designet med henblik på generalitet og brugervenlighed.

Math-pakken er så vidt jeg ved også skrevet om til "BigDecimal" og er derved blevet langsommere end i tidligere JDK-versioner.

Har du lavet nogen analyse af hvor flaskehalsen ligger performance mæssigt ?

Kompleks kode er ikke problematisk design mæssigt, men kan være det
udfra en simpel omkostnings betragtning.

Det koster at vedligeholde kompleks kode.

I langt de fleste tilfælde er er det billigere at købe mere hardware end
at vedligeholde kompleks kode.

Det er meget diskuteret hvorvidt NIO faktisk har givet de helt store
besparelser.

Den fordel som alle anerkender er at man nemmere (som i med mindre
kompleks kode) kan understøtte N connections med M threads hvor M < N.

Og String performer excellent.

Hvis man bruger den til det den er beregnet til (fjernsyn er ganske gode
til at følge med i nyheder med, men de er elendige til at klaske fluer med).

->arne_v: Flaskehalsen er efter min mening objekter vs. simple typer. Jeg vil derfor så vidt muligt holde mig til simple typer under selve ind- og udlæsningen

Mht. String er det vel relevant at diskutere brug af char arrays i stedet? Videre kan man måske i specielle tilfælde have glæde af at bruge 8-bit i stedet for 16-bit karaktersæt.

Helt overordnet forstår jeg ikke - og det skyldes måske manglende kendskab (!) - hvorfor man ikke på lige fod med String, som er 16-bit, har en 8-bit udgave med samme funktionalitet. Man har jo tilsvarende (int, long) og (float, double). Hvorfor så ikke en 8-bit String-udgave?