Performance HashMap<=>Array

[siriuswhite]

Hi ich hoffe das is im richtigen Unterforum wenn nicht bitte verschieben

Mich würd mal interessieren wie der Performanceunterschied ist ob man eine HashMap oder einen Array benutzt
Array is schneller,das weiß ich aber wieviel schneller?

Sollte es die Frage schon geben dann sorry aber ich hab nix gefunden über die suche

Siriuswhite

 

[Landei]

Array und HashMap sind ganz unterschiedliche Datenstrukturen. Array ist statisch und HashMap dynamisch. HashMap unterstützt keine Primitive, d.h. es kommt auch darauf an, ob ich int oder String speichern will, denn bei int kommen noch "Verpackungskosten" dazu. Wieviel Daten willst du speichern? Geht es um die durchschnittliche oder "worst case"-Performance? Und geht es um Lesen, Schreiben oder Löschen?

Ich kann dir nur den Tipp geben, einfach die Datenstruktur zu benutzen, die am besten zu deinem Problem "passt", und Performance-Fragen erst mal komplett zu ignorieren. Wenn du ein Performance-Problem hast - und erst dann - denke über Optimierungen nach.

 

[Ark]

Mich würd mal interessieren wie der Performanceunterschied ist ob man eine HashMap oder einen Array benutzt
Array is schneller,das weiß ich aber wieviel schneller?

Ein Array ist eine endliche und unmittelbare Aneinanderreihung gleichartiger Elemente. Eine HashMap ist eine Schlüssel-Wert-Zuordnung, bei der der Hashwert des Schlüssels den Index ausmacht, der zum direkten Zugriff benutzt wird.

Wie du siehst und schon angedeutet wurde, arbeiten diese beiden Strukturen auf völlig verschiedenen Ebenen. Was auf einer Ebene mit O(1) abläuft, kann auf niedrigerer Ebene O(n) bedeuten.

Der Hinweis also, wie er ebenfalls bereits genannt wurde: Nimm die Struktur, die dein Problem am besten beschreibt.

Ark

 

[bygones]

rein zugriffsperformance betrachtet haben beide konstante zeit.

aber natuerlich - siehe oben

 

[siriuswhite]

Neee ihr habt mich falsch verstanden xD
Natürlich nehm ich die die zum Problem am besten passt
ABer eine HasMap arbeitet ja auch intern mit nem Array und nimmt als Index halt den HashWert des Schlüssels modulo 77 glaub ich
Es interessiert mich nur wie groß der unterschied ist

 

[Marco13]

Der kann gigantisch sein...

class MyStupidObject
{
    @Override
    public int hashCode()
    {
        try
        {
            Thread.sleep(10000);
        }
        catch (Exception e)
        {
        }
        return 0;
    }
}

Aber mal im ernst: Da kann man kaum was "präzises" dazu sagen... :bahnhof:

 

[siriuswhite]

Klar wenn amn die Hash-Methode selber implementiert und dann sowas macht xD
Es geht nur darum wenn die standard hashMethode verwendet wird um wie viel schneller(ungefähr) der array is
Ich probier das jetzt mit nem testprogramm aus und werd dann das ergebnis hier posten

 

[siriuswhite]

So der Test ist vorbei
Hier erst mal der Code

static final int RUNS=200000;
static HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
  static int[] array=new int[RUNS];
  static long arrayTime=0,mapTime=0;

  public static void main(String[] args) {
    arrayTime=System.currentTimeMillis();
    for(int i=0;i<RUNS;i++)
    array[i]=i;
    
    for(int i=0;i<RUNS;i++)
    System.out.println(array[i]);
    arrayTime=System.currentTimeMillis()-arrayTime;
    
    
    mapTime=System.currentTimeMillis();
    for(int i=0;i<RUNS;i++)
    map.put(i,i);
    
    for(int i=0;i<RUNS;i++)
    System.out.println(map.get(i));
    mapTime=System.currentTimeMillis()-mapTime;
    
    System.out.println("Map "+mapTime+"    Array: "+arrayTime);
  }

Also das Ergebnis war so:
Beide sind immer ungefähr gleichschnell (der Unterschied ist Messgenauigkeit)
Also wär mein Problem gelöst, beide sind ungefähr gleich schnell
NAtürlich ist das kein richtiger test ,er zählt ja nur Integer durch und die Ausgabe kostet Zeit...
Aber ich denk ungefähr kann mans mal sagen

 

[SlaterB]

na das Programm sagt wenig aus, der Unterschied ist hier nicht Messgenauigkeit, sondern die Ausgabe per Stream, die kann die 10fache oder 100fache Zeit benötigen, kann man nicht sagen,
zudem vielleicht noch vom parallelen Zugriff externer Programme abhängig, die die Ergebnisse abholen,

zudem ist es etwas unfair, dass zuerst das Array befüllt wird, da muss der Speicher erstmal reserviert werden, das Programm ist in der Startphase,
bei der Map hast du die Größe nicht angegebenen, die muss dann während der Füllung ständig korrigiert werden,
viele Faktoren zu bedenken,
vor allem auch zu entscheiden, was du drin haben willst und was nicht,
wenn man nur 1x einfügt und 100x herausliest, ist eine Map vielleicht sparsamer als bei 1x einfügen + 1x auslesen

hätte jetzt fast ein anderes Programm gepostet, aber mir fiel kaum was sinnvolles zur Verarbeitung ein,
System.out.println in jedem Schleifendurchlauf ist mächtig langsam, aber praktisch jede Verarbeitung dürfte bedeutend langsamer als der simple Zugriff auf die Map/ das Array sein

 

[Marco13]

Das Programm sagt gar nichts aus. Interessant wäre die Frage, was es aussagen soll. Wenn es um den Zugriff (und nicht das Füllen) geht, kann ich ggf. mal einen aussagekräftigeREn (aber wie immer mit Vorsicht zu genießenden) Microbenchmark basteln...

 

[siriuswhite]

Hab doch gesagt es ist nicht aussagekräftig aber es geht darum dass es nicht so is dass einer wirklich schneller is
Wenn jetzt als ergebnis rausgekommen wär dass der array viel schneller is oder so dann hätt ich vielleicht nochmal geprüft aber ich denk das speicher reservieren und das größe ständig anpassen gleicht sich in etwa aus und die Werte haben sich auch bei jedem Durchlauf geändert(System.out.println-Problematik!) aber sie sind beide ungefähr gleich
Wenn es jemand genau wissen will kann man ja ein genaues Messprogramm schreiben aber hier gings nur um den ungefähren unterschied(viel oder wenig)

 

[Marco13]

Nur ein Microbenchmark - dass dort genaugenommen nur Unfug gemessen werden kann, weil alleine die Schleife und die Addition wohl etwa so viel Rechenzeit verbrät, wie der Arrayzugriff, ist klar, aber zumindest ist eine Tendenz erkennbar...

// For [url]http://www.java-forum.org/java-basics-anfaenger-themen/89461-performance-hashmap-array.html#post566159[/url]

import java.util.*;

class ArrayHashMapSpeedTest
{
    public static void main(String args[])
    {
        for (int size=100000; size<=1000000; size+=100000)
        {
            Integer array[] = createArray(size);
            Map<Integer, Integer> map = createMap(size);

            for (int runs=100; runs<=1000; runs+=100)
            {
                long before = 0;
                long after = 0;
                int result = 0;

                before = System.nanoTime();
                result = test(array, runs);
                after = System.nanoTime();
                System.out.println("size "+size+" runs "+runs+" result "+result+" time array "+((after-before)/1000000));

                before = System.nanoTime();
                result = test(map, runs);
                after = System.nanoTime();
                System.out.println("size "+size+" runs "+runs+" result "+result+" time map   "+((after-before)/1000000));
            }
        }
    }

    private static Integer[] createArray(int size)
    {
        Integer result[] = new Integer[size];
        for (int i=0; i<size; i++)
        {
            result[i] = 1;
        }
        return result;
    }

    private static Map<Integer, Integer> createMap(int size)
    {
        Map<Integer, Integer> result = new HashMap<Integer, Integer>();
        for (int i=0; i<size; i++)
        {
            result.put(i, 1);
        }
        return result;
    }

    private static int test(Integer array[], int runs)
    {
        int result = 0;
        int n = array.length;
        for (int j=0; j<runs; j++)
        {
            for (int i=0; i<n; i++)
            {
                result += array[i];
            }
        }
        return result;
    }

    private static int test(Map<Integer, Integer> map, int runs)
    {
        int result = 0;
        int n = map.size();
        for (int j=0; j<runs; j++)
        {
            for (int i=0; i<n; i++)
            {
                result += map.get(i);
            }
        }
        return result;
    }

}

 

[bygones]

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."

 

[Marco13]

Ich find'
"More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity."
- W.A. Wulf
eigentlich schöner. Schließlich könnte man sich beim anderen noch auf die 3% berufen

 

[SlaterB]

billige Sprüche,
warum nur hat Java die Map die überhaupt im Angebot, eine Liste reicht nach der Einstellung doch völlig

 

[bygones]

billige Sprüche,
warum nur hat Java die Map die überhaupt im Angebot, eine Liste reicht nach der Einstellung doch völlig

weil ich zu faul bin in eine liste eine key-value struktur selbst zu machen und dann noch ne suche in der liste für nen key... zu faul, faul faul faul.

ausserdem liste - pfff - array reicht

 

[siriuswhite]

Es ist ja nicht so dass ich in meinem Code zwanghaft versucht hätte HashMaps zu vermeiden ich hatte halt nur ne DIskussion mit einem freund der auch Java programmiert und weil wir keine Lösung gefunden haben wollte ich aus Interesse wissen wies jetzt ist
Dieser Freund hat nämlich gesagt(sinngemäß) wieso ich unnötigerweise HashMaps benutzen würde da würd ich besser arrays benutzen weil die HashMaps unnötig Performance verbrauchen würden
Es ging wie gesagt nur ums Interesse nicht um praktische Anwendung
Weil sonst könnt man auch sagen wieso Java programmieren wir gleich in MAschinencode xD

 

[Marco13]

Wie schon zu Anfang gesagt wurde: Es kommt auf den Anwendungsfall an.

Eine HashMap<Integer, Something> ist sinnlos genau dann, wenn diese "Integers" von 0 bis n reichen, und für jeden Integer ein entsprechendes Something existiert. Dann sollte man einen Array verwenden.

Umgekehrt wäre es blöd, wenn man einen Array "Something something[]" anlegen würde, wenn man bei jedem Zugriff darauf den ganzen Array durchsuchen müßte, um das Something zu finden, das zu einem bestimmten Index passt.