Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

[Java] Viele Vergleiche beschleunigen

Werbeanzeige

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

21

03.01.2012, 17:11

Deine Listen verkleinern sich in dem von Dir gezeigten Code nicht. Du setzt lediglich gewisse Einträge auf null.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Affje

Treue Seele

  • »Affje« ist der Autor dieses Themas

Beiträge: 89

Beruf: Student

  • Private Nachricht senden

22

03.01.2012, 17:17

Zitat von »BlueCobold«

Deine Listen verkleinern sich in dem von Dir gezeigten Code nicht. Du setzt lediglich gewisse Einträge auf null.

Sorry, das ist die ältere Versiond es Codes, bevor ich den retainAll() Mist entfernt habe.

Hier der aktuelle:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    {
        Thread thread = new Thread()
        {
            @Override
            public void run() 
            {
                long start = Calendar.getInstance().getTimeInMillis();
                CompareResult comparison = null;
                for (int i = possibilities.size() - 1; i >= 0; i--)
                {
                    comparison = new CompareResult(possibilities.get(i), last.ReturnGuessAsResult());
                    if (!(comparison.Blacks() == blacks && comparison.Whites() == whites))
                    {
                        possibilities.remove(i);
                    }
                    comparison = null;
                }
                long end = Calendar.getInstance().getTimeInMillis();
                System.out.println((end - start) + " ms - new Size: " + possibilities.size());   
            };    
        };
        thread.start();
    }

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

23

03.01.2012, 17:26

Ist das jetzt eine Arraylist oder eine LinkedList?

Eigentlich wäre beides ineffizient. Du solltest dich unbedingt mal über die Laufzeit bestimmter AUfrufe informierne, zumindest wenn du möchtest, dass es schnell geht.

Wenn du aus einer Arrayliste ein Element löschst, muss eine neue mit der neuen Größe erstellt werden und die alte bis auf das eine Element hineinkopiert werden. Das ist langsam.

Wenn du aus einer LinkedList das i-te Element löschen willst, wird Java vermutlich das i-te Element raussuchen müssen, was wieder lineare Laufzeit hat. Mit Iteratoren könntest du direkt auf das Element zugreifen, und es in konstanter Zeit löschen.

List.size() könnte auch länger brauchen, als man glaubt. Zwar könnte man Größe der Liste zwischenspeichern und immer erhöhen/erniedrigen, wenn Elemente eingefügt/gelöscht werden. Aber LinkedLists haben als Datenstruktur auch die nette Eigenschaft, dass man, wenn sie anhand von verschiedenen Iteratoren zusammenstückeln kann, was ansich auch in konstanter Zeit funktioniert. Nur hat man dann im Allgemeinen keine Ahnung mehr, wie groß die neue Liste ist, weswegen eine von beiden Operationen lineare Laufzeit hat.
Lieber dumm fragen, als dumm bleiben!

Affje

Treue Seele

  • »Affje« ist der Autor dieses Themas

Beiträge: 89

Beruf: Student

  • Private Nachricht senden

24

03.01.2012, 17:37

Zitat von »Jonathan_Klein«

Ist das jetzt eine Arraylist oder eine LinkedList?

Eigentlich wäre beides ineffizient. Du solltest dich unbedingt mal über die Laufzeit bestimmter AUfrufe informierne, zumindest wenn du möchtest, dass es schnell geht.

Wenn du aus einer Arrayliste ein Element löschst, muss eine neue mit der neuen Größe erstellt werden und die alte bis auf das eine Element hineinkopiert werden. Das ist langsam.

Wenn du aus einer LinkedList das i-te Element löschen willst, wird Java vermutlich das i-te Element raussuchen müssen, was wieder lineare Laufzeit hat. Mit Iteratoren könntest du direkt auf das Element zugreifen, und es in konstanter Zeit löschen.

List.size() könnte auch länger brauchen, als man glaubt. Zwar könnte man Größe der Liste zwischenspeichern und immer erhöhen/erniedrigen, wenn Elemente eingefügt/gelöscht werden. Aber LinkedLists haben als Datenstruktur auch die nette Eigenschaft, dass man, wenn sie anhand von verschiedenen Iteratoren zusammenstückeln kann, was ansich auch in konstanter Zeit funktioniert. Nur hat man dann im Allgemeinen keine Ahnung mehr, wie groß die neue Liste ist, weswegen eine von beiden Operationen lineare Laufzeit hat.

Ich habe noch ne ArrayList.

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

25

03.01.2012, 17:43

Dann sollte ein Wechsel zu LinkedLists dein Programm merkbar beschleunigen ;-)
Lieber dumm fragen, als dumm bleiben!

Affje

Treue Seele

  • »Affje« ist der Autor dieses Themas

Beiträge: 89

Beruf: Student

  • Private Nachricht senden

26

03.01.2012, 17:52

Zitat von »Jonathan_Klein«

Dann sollte ein Wechsel zu LinkedLists dein Programm merkbar beschleunigen ;-)


Ich hab bereits zwei mal geschrieben, dass die merkbare "Beschleunigung" zur LinkedList von 900ms auf fast 90 Sekunden hochgeht :P

Später werde ich das ganze nochmals von int auf bytes umstellen. Da es sowieso nur Zahlen von 1-10 sind, wäre das von Anfang an sinnvoll gewesen :wacko:

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

27

03.01.2012, 17:55

Der Code da oben ist aber ganz und gar nicht der des Comparators von dem ich gesprochen habe.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »BlueCobold« (03.01.2012, 18:05)

Affje

Treue Seele

  • »Affje« ist der Autor dieses Themas

Beiträge: 89

Beruf: Student

  • Private Nachricht senden

28

03.01.2012, 18:07

Zitat von »BlueCobold«

Der Code da oben ist aber ganz und gar nicht der des Comparators von dem ich gesprochen habe.
Nein, das ist die Funktion/Schleife, die für jeden verbleibenden Tipp eben den gepostetetn Comparator (=CompareResult) aufruft. In dieser CompareResult Klasse ist die besagte Compare() Methode.

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

29

03.01.2012, 18:11

Und eben jene ist ineffizient und warum Du da unbedingt Listen willst, hast Du auch noch nicht geklärt ;)
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Affje

Treue Seele

  • »Affje« ist der Autor dieses Themas

Beiträge: 89

Beruf: Student

  • Private Nachricht senden

30

03.01.2012, 18:16

Zitat von »BlueCobold«

Und eben jene ist ineffizient und warum Du da unbedingt Listen willst, hast Du auch noch nicht geklärt ;)
Dann haben wir aneinander vorbeigeredet. Ich-will-unbedingt-Listen bezog sich auf die Methode, die in der Schleife den Vergleich aufruft. Beim Compare geb ich dir recht, das ist nicht gut und ich werds ändern ;)

Werbeanzeige

Ähnliche Themen