ArrayList vs. Vector

Jeg har kigget en del her på siden. Men jeg synes ikke rigtig at få noget ud af det. Men jeg har da fundet ud af Disky og CarstenKnudsen ikke er helt enige på dette område.

proev at laese http://java.sun.com/docs/books/tutorial/collections/index.html igennem.

Begge dele er en del af Collections frameworket, som også indeholder Set, List og Map.

Se evt. http://java.sun.com/docs/books/tutorial/collections

Funktionaliteten er den samme.

ArrayList er unsychronized.
Vector er synchronized.

ArrayList er J2SE 1.2+.
Vector er J2SE 1.0+.

Det betyder ikke så meget om du bruger det ene eller det andet.

Jeg tror de fleste bruger ArrayList idag.

Enig med Arne - Ja, Vector er Thread safe og det er ArrayList ikke.
Se http://www.onjava.com/pub/a/onjava/2001/05/30/optimization.html for en sammenligning.

Der er i dag kun en ubetydelig teoretisk performance forskel.

Evt. http://www.javaworld.com/javaworld/javaqa/2001-06/03-qa-0622-vector.html

Jeg vil altid mene at man skal bruge ArrayList de stedet for der er ikke er fare for flere tråde der piller ved listen samtidig.

Ser stadig det overhead der er ved at sikre synkronisering giver en performance forringelse der i store applikationer kan mærkes.

Det kommer helt an på opgavens art og størrelse. I baggrunden er både ArrayList og Vector implementeret som et Object[]. Ellers kan man overveje at bruge HashTable, (Hash)Map, LinkedList osv..

import java.util.ArrayList;
import java.util.Vector;

public class ArrayListVersusVector {
    private final static int NELM = 1000000;
    private final static int RWFACTOR = 10;
    private final static int REPEAT = 10;
    public static void main(String[] args) {
        testArrayList();
        testVector();
    }
    private static void testArrayList() {
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < REPEAT; i++) {
            ArrayList al = new ArrayList();
            for (int j = 0; j < NELM; j++) {
                al.add(new Integer(j));
            }
            for (int k = 0; k < RWFACTOR; k++) {
                for (int j = 0; j < NELM; j++) {
                    Integer iobj = (Integer) al.get(j);
                    if (iobj.intValue() != j) {
                        System.out.println("Error " + iobj.intValue() + " <> " + j);
                        System.exit(1);
                    }
                }

            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("ArrayList : " + (t2 - t1));
        return;
    }
    private static void testVector() {
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < REPEAT; i++) {
            Vector v = new Vector();
            for (int j = 0; j < NELM; j++) {
                v.add(new Integer(j));
            }
            for (int k = 0; k < RWFACTOR; k++) {
                for (int j = 0; j < NELM; j++) {
                    Integer iobj = (Integer) v.get(j);
                    if (iobj.intValue() != j) {
                        System.out.println("Error " + iobj.intValue() + " <> " + j);
                        System.exit(1);
                    }
                }

            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("ArrayList : " + (t2 - t1));
        return;
    }
}

giver følgende tider:

JVM                ArrayList        Vector

SUN 1.3.1            9.8 s          8.7 s
SUN 1.4.1            9.1 s          9.1 s
IBM 1.3.0            7.8 s          7.2 s
BEA 8.0 (=1.4.1)      8.6 s          8.4 s

Min konklusion:
* forskellen er under 10% på nyere JVM's
* forskellen er ligegyldig i langt de fleste situationer
  (en forskel på 1 sekund for 10 millioner adds og
  100 millioners gets er ikke ret meget)

Ja, men skal der ikke stå System.out.println("Vector: " + (t2 - t1)); og ikke System.out.println("ArrayList : " + (t2 - t1)); nederst i din kode? Bare en bemærkning.

Jo. Den linie er bare kopieret. Den skulel selvfølgelig også have haft rettet
teksten.

:-)

Forrygende :)
Så har man også lige lært lidt idag :o)

Hvad betyder det at Vector er Thread safe?

Det betyder at hvis du har 2 tråde som skal opdatere samtidigt, så
kan du med en Vector bare lade dem gøre det og det vil altid
virke korrekt, mens med en ArrayList skal du selv synchronize
adgangen eller vil det en gang imellem gå galt.

Se evt. http://whatis.techtarget.com/definition/0,,sid9_gci331590,00.html

--> Arne
Okey, men det kræver så et multiprocessor eller hyper-thread system. Tror bare jeg forsætter med arraylister så :o)

Nej.

Du kan sagtens lave threaded applikationer på en ganske normal
1 CPU maskine.

Og alle problemerne med threadede applikationer eksisterer også
for 1 CPU maskiner.

Fler CPU maskiner adskiller sig kun ved at flere tråde kan køre
samtidigt på hver sin CPU (OK - sandsyneligheden for tråd-problemer
vokser også).

Ok det troede jeg ikke. Er det i forbindelse med context skift dette problem kan opstå så?

Det jeg mener er at du kan jo ikke på præcis samme tid opdater to tråde på en alm. maskine. Så der må ligesom være en eller anden grund til at det kan opstå. Kunne så forestille mig at det var i forbindelse med context skift... eller?

Nej problemet opstår i forbindelse med ikke atomiske operationer.

Hvis jeg må have lov til at komme med et lidt andet eksempel, som vi
har "hygget" os en del med i det firma jeg arbejder for.

ObjectOutputStream og writeObject !

Den er heller ikke thread safe. Og hvis man kører multi threaded
(også på en 1 CPU maskine) så skal man selv synchronize på
den ObjectOutputStream socket. Ellers går det galt.

Problemet er at writeObject ikke er atomisk.

Der der kan ske er:

tråd 1:
  oos.writeObject(a);

tråd 2:
  oos.writeObject(b);

fordi writeObject ikke er atomisk, så kan der ske det at
JVM'en faktisk gør følgende:

tråd 1 udskriver første halvdel af object a bytene
tråd 2 udskriver første halvdel af object b bytene
tråd 1 udskriver sidste halvdel af object a bytene
tråd 2 udskriver sidste halvdel af object b bytene

Og jeg kan afsløre at en ObjectInputStream readObject ikke
kan finde ud af det !

:-)

Derfor skal man bruge:

tråd 1:
  synchronized (oos) {
      oos.writeObject(a);
  }

tråd 2:
  synchronized (oos) {
    oos.writeObject(b);
  }

Og tilsvarende er det heller ikke atomisk at sætte et Object
ind i en ArrayList eller en Vector.

Men Vector laver selv en synchronized der garderer mod
problemer.

Okey så er jeg med :o)
Tak for en forrygende forklaring! Tror lige jeg smider noget synchronized ind, bare for en sikkerhedsskyld :o)

Det er som sagt kun et problem with multithreaded apps.

Jeps.
Har dog pt. kun et par tråde. Men det er jo ikke til at vide hvad der kommer af udbygninger. Det kan godt være at det er at tage sorgerne på forskud, men synchronized er jo nem at bruge. Det ville være surt hvis man løber ind i problemet og sidder og vrider hovedet med hvad det kunne være, når det er så let at forebygge :o)