Java Android code auf laufzeit optimieren

[Ken Masters]

Hallo Leute,

könnte man den folgenden code optimieren? also auf das laufzeit verhältnis gesehen. ich habe eine imageview programmiert welches die images im drawable ordner mit jedem button klick abwechselnt anzeigt.

hier der code:

ImageView image;
final int[] images = {R.drawable.comp_1, R.drawable.comp_2,...}
.....
.....

refreshbutton.setOnClickListener(new View.OnClickListener() {
         
            @Override
            public void onClick(View arg0) {
                Random rng = new Random();
               
                List<Integer> generated = new ArrayList<Integer>();
                for (int i = 0; i < images.length; i++)
                {
                  while(true)
                  {
                     Integer next = rng.nextInt(images.length) ;
                     if (!generated.contains(next))
                     {
                        generated.add(next);
                        image.setImageResource(images[next]);
                        break;
                     }
                   }
                }
            }
        });

es tut auch was es soll, aber beim emulator dauert das ca 15 sek. bis das bild gewechselt wird. auf meinem galaxy s2 dauert es ca 3 sekunden.
hier ist nochmal die logcat aufzeichnungen beim drücken auf den button

11-29 12:56:26.314: D/dalvikvm(2471): GC_FOR_ALLOC freed 11729K, 27% free 3222K/4384K, paused 105ms, total 108ms
11-29 12:56:26.444: I/dalvikvm-heap(2471): Grow heap (frag case) to 10.604MB for 7680016-byte allocation
11-29 12:56:26.664: D/dalvikvm(2471): GC_CONCURRENT freed <1K, 10% free 10722K/11888K, paused 77ms+23ms, total 222ms
11-29 12:56:27.464: D/dalvikvm(2471): GC_FOR_ALLOC freed <1K, 10% free 10722K/11888K, paused 59ms, total 59ms
11-29 12:56:27.534: I/dalvikvm-heap(2471): Grow heap (frag case) to 14.723MB for 4320016-byte allocation
11-29 12:56:27.814: D/dalvikvm(2471): GC_CONCURRENT freed 0K, 8% free 14941K/16108K, paused 79ms+31ms, total 275ms
11-29 12:56:28.134: D/dalvikvm(2471): GC_FOR_ALLOC freed 11719K, 27% free 3222K/4384K, paused 106ms, total 108ms
11-29 12:56:28.264: I/dalvikvm-heap(2471): Grow heap (frag case) to 10.604MB for 7680016-byte allocation
11-29 12:56:28.504: D/dalvikvm(2471): GC_CONCURRENT freed <1K, 10% free 10722K/11888K, paused 77ms+32ms, total 235ms
11-29 12:56:29.274: D/dalvikvm(2471): GC_FOR_ALLOC freed <1K, 10% free 10722K/11888K, paused 59ms, total 59ms
11-29 12:56:29.354: I/dalvikvm-heap(2471): Grow heap (frag case) to 14.723MB for 4320016-byte allocation
11-29 12:56:29.594: D/dalvikvm(2471): GC_CONCURRENT freed 0K, 8% free 14941K/16108K, paused 77ms+24ms, total 245ms
11-29 12:56:29.944: D/dalvikvm(2471): GC_FOR_ALLOC freed 11719K, 27% free 3222K/4384K, paused 102ms, total 105ms
11-29 12:56:30.074: I/dalvikvm-heap(2471): Grow heap (frag case) to 10.604MB for 7680016-byte allocation
11-29 12:56:30.315: D/dalvikvm(2471): GC_CONCURRENT freed <1K, 10% free 10722K/11888K, paused 77ms+23ms, total 243ms
11-29 12:56:31.104: D/dalvikvm(2471): GC_FOR_ALLOC freed <1K, 10% free 10722K/11888K, paused 58ms, total 58ms
11-29 12:56:31.184: I/dalvikvm-heap(2471): Grow heap (frag case) to 14.723MB for 4320016-byte allocation
11-29 12:56:31.444: D/dalvikvm(2471): GC_CONCURRENT freed 0K, 8% free 14941K/16108K, paused 78ms+36ms, total 257ms
11-29 12:56:31.894: D/dalvikvm(2471): GC_FOR_ALLOC freed 11719K, 27% free 3222K/4384K, paused 104ms, total 238ms
11-29 12:56:32.025: I/dalvikvm-heap(2471): Grow heap (frag case) to 10.604MB for 7680016-byte allocation
11-29 12:56:32.244: D/dalvikvm(2471): GC_CONCURRENT freed <1K, 10% free 10722K/11888K, paused 77ms+21ms, total 214ms
11-29 12:56:33.044: D/dalvikvm(2471): GC_FOR_ALLOC freed <1K, 10% free 10722K/11888K, paused 60ms, total 60ms
11-29 12:56:33.124: I/dalvikvm-heap(2471): Grow heap (frag case) to 14.723MB for 4320016-byte allocation
11-29 12:56:33.384: D/dalvikvm(2471): GC_CONCURRENT freed 0K, 8% free 14941K/16108K, paused 76ms+22ms, total 258ms
11-29 12:56:33.704: D/dalvikvm(2471): GC_FOR_ALLOC freed 11719K, 27% free 3222K/4384K, paused 102ms, total 106ms
11-29 12:56:33.834: I/dalvikvm-heap(2471): Grow heap (frag case) to 10.604MB for 7680016-byte allocation
11-29 12:56:34.074: D/dalvikvm(2471): GC_CONCURRENT freed <1K, 10% free 10722K/11888K, paused 88ms+22ms, total 234ms
11-29 12:56:34.874: D/dalvikvm(2471): GC_FOR_ALLOC freed <1K, 10% free 10722K/11888K, paused 59ms, total 59ms
11-29 12:56:34.976: I/dalvikvm-heap(2471): Grow heap (frag case) to 14.723MB for 4320016-byte allocation
11-29 12:56:35.235: D/dalvikvm(2471): GC_CONCURRENT freed 0K, 8% free 14941K/16108K, paused 78ms+23ms, total 252ms
11-29 12:56:35.814: D/dalvikvm(2471): GC_FOR_ALLOC freed 12672K, 27% free 3223K/4384K, paused 106ms, total 112ms
11-29 12:56:35.954: I/dalvikvm-heap(2471): Grow heap (frag case) to 10.604MB for 7680016-byte allocation
11-29 12:56:36.204: D/dalvikvm(2471): GC_CONCURRENT freed <1K, 10% free 10722K/11888K, paused 77ms+32ms, total 247ms
11-29 12:56:36.974: D/dalvikvm(2471): GC_FOR_ALLOC freed <1K, 10% free 10722K/11888K, paused 67ms, total 67ms
11-29 12:56:37.044: I/dalvikvm-heap(2471): Grow heap (frag case) to 14.723MB for 4320016-byte allocation
11-29 12:56:37.304: D/dalvikvm(2471): GC_CONCURRENT freed 0K, 8% free 14941K/16108K, paused 76ms+37ms, total 254ms
11-29 12:56:37.633: D/dalvikvm(2471): GC_FOR_ALLOC freed 11719K, 27% free 3222K/4384K, paused 104ms, total 110ms
11-29 12:56:37.773: I/dalvikvm-heap(2471): Grow heap (frag case) to 10.604MB for 7680016-byte allocation
11-29 12:56:38.013: D/dalvikvm(2471): GC_CONCURRENT freed <1K, 10% free 10722K/11888K, paused 77ms+42ms, total 233ms
11-29 12:56:38.784: D/dalvikvm(2471): GC_FOR_ALLOC freed <1K, 10% free 10722K/11888K, paused 59ms, total 59ms
11-29 12:56:38.853: I/dalvikvm-heap(2471): Grow heap (frag case) to 14.723MB for 4320016-byte allocation
11-29 12:56:39.124: D/dalvikvm(2471): GC_CONCURRENT freed 0K, 8% free 14941K/16108K, paused 78ms+23ms, total 270ms
11-29 12:56:39.443: D/dalvikvm(2471): GC_FOR_ALLOC freed 11719K, 27% free 3222K/4384K, paused 102ms, total 103ms
11-29 12:56:39.573: I/dalvikvm-heap(2471): Grow heap (frag case) to 10.604MB for 7680016-byte allocation
11-29 12:56:39.813: D/dalvikvm(2471): GC_CONCURRENT freed <1K, 10% free 10722K/11888K, paused 76ms+22ms, total 229ms
11-29 12:56:40.603: D/dalvikvm(2471): GC_FOR_ALLOC freed <1K, 10% free 10722K/11888K, paused 63ms, total 64ms
11-29 12:56:40.683: I/dalvikvm-heap(2471): Grow heap (frag case) to 14.723MB for 4320016-byte allocation
11-29 12:56:40.946: D/dalvikvm(2471): GC_CONCURRENT freed 0K, 8% free 14941K/16108K, paused 78ms+24ms, total 265ms
11-29 12:56:41.274: D/dalvikvm(2471): GC_FOR_ALLOC freed 11719K, 27% free 3222K/4384K, paused 104ms, total 107ms
11-29 12:56:41.293: I/dalvikvm-heap(2471): Grow heap (frag case) to 4.498MB for 1276816-byte allocation
11-29 12:56:41.524: D/dalvikvm(2471): GC_CONCURRENT freed <1K, 21% free 4469K/5632K, paused 77ms+19ms, total 222ms
11-29 12:56:41.714: D/dalvikvm(2471): GC_FOR_ALLOC freed <1K, 21% free 4469K/5632K, paused 63ms, total 63ms
11-29 12:56:41.734: I/dalvikvm-heap(2471): Grow heap (frag case) to 5.182MB for 718216-byte allocation
11-29 12:56:41.935: D/dalvikvm(2471): GC_CONCURRENT freed 0K, 19% free 5170K/6336K, paused 77ms+18ms, total 203ms
11-29 12:56:41.935: D/dalvikvm(2471): WAIT_FOR_CONCURRENT_GC blocked 12ms
11-29 12:56:41.944: I/Choreographer(2471): Skipped 13425 frames!  The application may be doing too much work on its main thread.

kann man da was rausholen? eventuell habe ich mir gedacht, dass man das feld images nacheinander und nicht random ausgibt.

danke im voraus

 

[SymA]

Standard Tipps zur Optimierung von Java Quellcode angucken. Ansonsten mit einem Profilier laufen lassen und somit deine kritischen Bereiche ausfindig machen und dort optimieren.
Zum Thema Emulator : Gleiches verhalten hast du bei einer VM - das Teil ist nunmal langsamer weil du wesentlich mehr Schichten durchwanderst als auf einem nativen Gerät.
Random - Funktionen sind immer ganz mies, da werden so viele Fälle geprüft bevor du da einen Wert rausbekommst, eventuell eigene Random Funktion bauen?

 

[sasdensas]

Dauert es auf dem S2 3sec. wenn du in der IDE das Programm übertragen lässt um es auf dem S2 zu starten, oder wenn Du die App direkt auf dem S2 aufrufst?
Läuft es über die IDE, dann dauert es halt bissl mit der APK-Erstellung, Übertragung und der Start. Zudem muss die App auch die Debug-Informationen vorbereiten, um es an die IDE, bzw. logcat senden zu können.

 

[vincez]

2 Sachen, die dir helfen:

A)
4mb pro Bild erscheint mir etwas hoch. Das macht das ganze sehr langsam. Daher wichtig:
Immer mit herunterskalierten Versionen deiner Bitmaps arbeiten wenn möglich. Ein 3000x2000 Bild
braucht auf einem 800x400 Pixel Gerät auch nur mit 800x400 Präzision geladen werden.
how to:
http://developer.android.com/training/displaying-bitmaps/load-bitmap.html
(Ladevorgänge nicht auf dem UI Thread durchführen. (e.g. AsyncTask))

B)
Caching von Bitmaps:
http://developer.android.com/training/displaying-bitmaps/cache-bitmap.html

ggf. ImageAdapter
http://developer.android.com/training/displaying-bitmaps/display-bitmap.html

LG
~vincezz

 

[Ken Masters]

danke für die schnellen antworten.

@sasdensas: die apk ist auf dem galaxy installiert und dauert ca. 3 sek.

@SymA und vincez:

danke. werde es gleich probieren.

 

[Dese]

also eine sache, die vermutlich recht teuer bei dir ist läßt sich mit keinem der oben genannten tips beseitigen:
du benutzt eine arraylist um dir zu merken welche bilder du bereits "generiert" hast und rufst dann
generated.contains()
auf.

was du da gerade machst ist sehr teuer und unnötig.

besser du benutzt eine Hashset statt der ArrayList. die beantwortet dir diese frage in konstanter zeit statt in Theta(n).

Und dann kommt noch eine sache hinzu, die gerade wenn du viele bilder generieren willst, hochwahrscheinlich sehr teuer ausfallen wird:
dein vorgehen ist
- wähle zufällig aus einer menge von bilder
- schaue ob du das schon hast
-> wenn nein, nimms auf
-> wenn ja ingoriere es.

nun, warum ist das ganz schlecht?
wenn du die meisten bilder schon hast, dann wirst du bei den meisten würfen ein bild treffen, dass du bereits hast und damit sehr lange darauf warten müssen, bis du ein freies erwischt.

besser ist das:
- erzeuge ne NEUE liste
- füge alle bilder da rein
- würfle ein bild aus (index), entferne es aus der liste und füge es in eine zweite ergebnisliste ein oder wo auch immer.

da du den index / das bild nur aus der menge der in der liste vorhandenen auswürfelst hast du immer einen treffer.

edit: die in den anderen posts angesprochenen optimierungen sind sogenannte micro-optimierungen. die werden deine laufzeit nur um konstante faktoren verbessern, wenn überhaupt. deine vorgehensweise hat aber bereits algorithmisch ne schelchte laufzeit, die man deutlich verbessern kann.

das ist nicht als vorwurf gemeint. eine rein objektive feststellung.

 

[Ken Masters]

jo, danke dese. werde deinen ratschlag beherzigen und testen.

 

[Dese]

da mein post sehr informel geschrieben wurde bin ich nicht ganz sicher ob klar wurde, dass das eigentlich zwei verschiedene ansätze sind. der erste vorschlag verbessert dein vorhandenes verfahren (billigere contains abfrage).

der zweite vorschlag macht es halt ganz anders. das ist der bessere im übrigen.

 

[Hancock]

@Dese:
Bitte nicht persönlich nehmen, aber wenn die ArrayList nicht gerade >10000 Elemente enthält, dann sollte der Ansatz kaum Zeit kosten.
@Ken Masters:
Das Problem ist der Algo an sich, gegen Ende hast du einfach zu viele Versuche, bis was passiert.
Meine Idee: Schreib ne Liste, in die du zuerst alle Bilder reinkopierst, dann ne Liste, die leer ist, jetzt entfernst du immer ein Element zufällig aus der ersten Liste und fügst es in die zweite ein. Dadurch hast du eine lineare Anzahl an Zufallszahlen und ne Worst-Case-Kompexität von O(n²) (wenn man Arrays für die Listen verwendet).

 

[Shagg]

wieso packst du die bilder eigentlich wenn sie angezeigt wurden in eine liste? ist das damit ein bild nicht zweimal angezeigt wird?

 

[Dese]

@Dese:
Bitte nicht persönlich nehmen, aber wenn die ArrayList nicht gerade >10000 Elemente enthält, dann sollte der Ansatz kaum Zeit kosten.

nö tue ich nicht

du beziehst dich sicherlich auf da "contains". aber du irrst dich, weil das zu einer laufzeit von n^2 führt. er geht ja das array durch und ruft contains für jedes element auf.

aber du hast insofern recht, als dass wenn es nicht all zu viele element sind, das es dann nicht wirklich spürbar ist. aber 10000 ist schon zu viel.

davon abgesehen, warum sollte er es nicht gleich richtig machen?


ABER, das contains ist nicht der hauptgrund für sein performance-problem. was ihn da wirklich zeit kostet ist, dass wenn er die meisten bilder schon "generiert" hat die suche mit random nach einem noch nicht generiertem bild SEHR lange dauert, weil die wahrscheinlichkeit es auszuwürfeln sehr klein wird.

deswegen schrieb ich ja meinen zweiten ansatz. DAS ist sein hauptproblem.

@Ken Masters:
Das Problem ist der Algo an sich, gegen Ende hast du einfach zu viele Versuche, bis was passiert.
Meine Idee: Schreib ne Liste, in die du zuerst alle Bilder reinkopierst, dann ne Liste, die leer ist, jetzt entfernst du immer ein Element zufällig aus der ersten Liste und fügst es in die zweite ein. Dadurch hast du eine lineare Anzahl an Zufallszahlen und ne Worst-Case-Kompexität von O(n²) (wenn man Arrays für die Listen verwendet).

das hab ich doch oben schon erklärt und gerade in diesem post ein zweites mal

edit: und wenn du das entfernen geschickter machst, dann kannst du ne worst-case-komplexität von n erreichen. soll ich verraten wie?

hsat du meinen ersten post ganz gelesen? (das ist nicht böse gemeint).

 

[Hancock]

OK, eig. bezog ich mich auf die HashSet <-> ArrayList Geschichte.
Das ist auch eine Mikrooptimierung.
Den Algo da haste recht, den hab ich nochmal vorgeschlagen .

Und worst-case Komplexität von n haste nur mit einer idealen Hashmap, welche es nicht gibt (ne Liste hat n²).

Oder aber: n beliebige Vertauschungen auf dem Array (was sogar sehr schnell wäre), was aber eine sehr schlechte Randomisierung aufweißt.

 

[Dese]

Und worst-case Komplexität von n haste nur mit einer idealen Hashmap, welche es nicht gibt (ne Liste hat n²).

Oder aber: n beliebige Vertauschungen auf dem Array (was sogar sehr schnell wäre), was aber eine sehr schlechte Randomisierung aufweißt.

ich nehme mal an, dass soll die antwort auf meine frage sein?

1. du kannst sehr wohl mit einer hashmap garantierte worst case von O(n) erreichen. aber das war gar nicht gemeint in meiner frage

2. die lösung ist ein array zu nehmen. und wenn du ein ausgewürfeltes element entfernen willst, dann kopierst du einfach das letzte element des arrays über das zu entfernende drüber und dekrementierst anschließend den zähler für die anzahl der elemente im array.

damit hast du eine konstante laufzeit für das löschen eines beliebigen elementes im array, gekauft dadurch, dass sich die reihenfolge der elemente verändern kann. das ist aber egal, da du eh nur auswürfelst.

somit bestimmst du n zufällige zahlen in garantiert Theta(n) zeit.

 

[Hancock]

Ja das Löschen geht in konstanter Zeit, aber der Container muss irgendeine Art von entweder Zufallsauswahl oder Nummerierung haben, damit du auch das zu löschende Element findest (und das hängt sehr wohl von der Größe ab).

http://www.codeproject.com/Articles/340797/Number-crunching-Why-you-should-never-ever-EVER-us

Da gehts zwar um LinkedList, aber für HashMaps ist das sehr wohl übertragbar.

 

[Dese]

ich glaub du hast mich mißverstanden:

nimm ein array A und ein integer size:

füge deine n werte in das array und setze size = n

jetzt würfelst du eine zahl r zwischen 0 und <size aus.

du nimmst A[r]

dann setzt du A[r] = A[size-1] und anschließend size--
das machst du solange wie size > 0 ist.

damit hast du in genau Theta(n) schritten eine zufällige folge deiner in A ursprünglich gespeicherten werte.

edit: ich hab mir mal deinen link angeschaut. nicht ganz zu ende gelesen, aber ein großteil. die quintessence ist ja durch aus richtig, aber mit der headline suggeriert der artikel was völlig falsches.
natürlich ist neben der asymptotischen laufzeit auch zu beachten was für konstante effekte es noch gibt, wie caching etc.

und sein erstes beispiel ist ja mal ziemlich blöd, angesichts seiner headline. denn da ist nicht der grund, dass die asymptotische laufzeit einem über die konstanten faktoren hinwegtäuscht, sondern dass die suche, welche bereits für linked lists eine schlechtere asymptotische laufzeit hat, die dominante operation ist.

ganz ehrlich, ich find den artikel grausig. klingt so als hätte jemand autodidaktisch die asymtpotischen laufzeiten etdeckt und mangels fundiertem wissen wurde er entäuscht, weil ih nie jemand aufgekl#rt hat wie genau das zu verstehen und abzuschätzen ist. ein ziemllich nifantiler artikel.

Ergänzung (4. Dezember 2012)

http://www.codeproject.com/Articles/340797/Number-crunching-Why-you-should-never-ever-EVER-us

Da gehts zwar um LinkedList, aber für HashMaps ist das sehr wohl übertragbar.

was genau meinst du mit ist auf hashmaps übertragbar? ich hab da bisher nichts erkennen können, was auf hashmaps übertragbar wäre.

 

[Hancock]

OK, die Idee mit dem A[r]=A[A.size-1]; ist gut...
Aber das wird bei ner Hashmap ziemlich blöd (A[A.size-1] geht da nähmlich net), da würd ich echt direkt nen Array nehmen, da haste echtes O(n).

Mit dem Artikel: Immer, wenn man im Internet oder sonstwo was ließt: Hashmap ist das beste Hashmap hier und Hashmap da.
Ich persönlich mag Hashmaps nicht, wenns sortiert ist bin ich immer froh drum und ein Array (std::vector in C++) find ich sehr nett, weil es vor allem Speicher spart. Und wenns jetzt um nicht key-value-Daten geht, dann ersetz oben Hashmap mit LinkedList.

 

[F_GXdx]

Du kannst schon bei einer ArrayList bleiben (oder eben Array). Ich denke, dass die schlechte Performance einfach aus deinem Algorithmus kommt und nicht aus der Datenstruktur.

Ich würde es halt so machen, dass ich eine sortierte Liste erzeuge, also 1, 2 ,3 ,4 ,5 ... n mit einer Schleife, und dann diese durchshufflen und dann entsprechend die Bilder zuweisen, indem du das geshuffelte Array durchgehst.

Shufflen geht mit Collections, und zwar in O(n): Collections.shuffle(arrayList);

Und somit wohl der gesammte Algo in O(n).

 

[Dese]

OK, die Idee mit dem A[r]=A[A.size-1]; ist gut...
Aber das wird bei ner Hashmap ziemlich blöd (A[A.size-1] geht da nähmlich net), da würd ich echt direkt nen Array nehmen, da haste echtes O(n).

ich sag doch die ganze zeit, für die lösung ein array und keine hashmap.

Mit dem Artikel: Immer, wenn man im Internet oder sonstwo was ließt: Hashmap ist das beste Hashmap hier und Hashmap da.
Ich persönlich mag Hashmaps nicht, wenns sortiert ist bin ich immer froh drum und ein Array (std::vector in C++) find ich sehr nett, weil es vor allem Speicher spart. Und wenns jetzt um nicht key-value-Daten geht, dann ersetz oben Hashmap mit LinkedList.

ja der artikel macht genau das gleiche: dies ist gut dies ist schelcht und das ziemlich pauschal durch die gegend gewürfelt.

die datenstruktur hashmap ist eine super datenstruktur für ihren einsatzzweck, genau wie alle anderen auch.
Listen sind SUPER für das wozu sie gedacht sind
Arrays sind SUPER für das wozu sie gedacht sind
HashSets/Maps sind SUPER für das, wozu sie gedacht sind.
etc.

das problem leigt IMMER beim programmierer, wenn er nicht wirklich verstanden hat was genau die verschiedenen datenstrukturen machen, welche operationen sie wie gut unterstützen.

allerdings liegt es manchmal auch an den verwendeten bibliotheken welche diese datenstrukturen teils schlecht implementieren. java ist da leider eine sehr sehr gutes beispiel. die implementierungen mancher datenstrukturen (allen voran listen) ist schlecht. im fallen von listen ne einzige katstrophe.

noch eines zu java:
was eigentlich ein ganz ganz schlechter stil ist und wirklich schwerwiegende folgen haben kann ist allgemein List als rückgabewert zu haben, aber intern immer ArrayListen zu nutzen.

wenn das ein anderer auch nutzt aber mal KEINE arraylist nutzt, man davon ausgehen es wäre so die methode get() benutzt, dann hat man gleich ne teure laufzeit. das kommt leider oft vor, weil java hier einfach zuviel und falsch in interfaces aufgeteilt hat.

aber das führt jetzt einfach zu weit.

Ergänzung (5. Dezember 2012)

Ich würde es halt so machen, dass ich eine sortierte Liste erzeuge, also 1, 2 ,3 ,4 ,5 ... n mit einer Schleife, und dann diese durchshufflen und dann entsprechend die Bilder zuweisen, indem du das geshuffelte Array durchgehst.

Shufflen geht mit Collections, und zwar in O(n): Collections.shuffle(arrayList);

Und somit wohl der gesammte Algo in O(n).

also erstens brauchst du für das erzeugen der sortierten liste schon mal n log n.

edit: zweitens, macht shuffle verm,utlich genau das was ich oben geschrieben habe. wenn nicht, dann kommt ne schlechte randomisierung bei raus, wenn es nur O(n) bracuht. wozu dann überhaupt ne sortierte liste davor erzeugen? wird doch eh gemsicht.

und drittens ist das ganze ziemlich umständlich, vor allem wo ich doch oben eine sehr sehr einfache und dazu sehr sehr effiziente methode erklärt habe.

warum einfach und effizient wenn's auch kompliziert und langsam geht?

Ergänzung (5. Dezember 2012)

nachtrag zum Collection.shuffle
hab mir den source dazu angeschaut. es nutzt vertauschungen in einem einmaligen durchgang. das sollte so keine gleichverteilung erzeugen weil zahlen die früh vertauscht werden öfters von weiteren vertauschungen betroffen seien können als zahlen die erst gegen ende getroffen werden. bin mir da aber nicht ganz sicher.

 

[F_GXdx]

also erstens brauchst du für das erzeugen der sortierten liste schon mal n log n.

Muahahahaha wollen Sie dabei bleiben, Holmes?

 

[Dese]

was hab ich verpasst? legst du die liste von hand an oder was?

edit: ach jetzt verstehe ich was du meinst. du erzeugst ne index-liste, einfach mit den zahlen 1..n. ich dachte du erzeugst aud den daten eine sortierte liste.

naja, diese zu erstellen geht natürlich in genau n schritten. aber wozu??? damit hast du noch ne liste zusätzlich und noch eine for-schleife und und und...