Performance ArrayList#remove

[The_S]

Guten Morgen,

ich habe leider momentan keine Möglichkeit das selbst zu testen, deshalb die Frage an euch:

Ich habe eine ArrayList, aus der bestimmte Werte entfernt werden sollen. Diese Werte habe ich in einem Array stehen. Ich gehe also das komplette Array durch und entferne jedes Element aus der ArrayList, welches auch im Array steht. Soweit kein Problem, aber: Ich weiß, dass ca. die Hälfte der Werte in dem Array immer gleich ist, und dass diese Werte garantiert nicht in der ArrayList vorkommen (das Array hat eine Länge von ca. 5-15).

Was ist jetzt performanter? Einfach jedes Element (egal ob ich weiß, dass es u. U. gar nicht vorkommen kann) entfernen, oder vorher überprüfen, ob es sich um ein Element handelt, bei dem ich ein vorkommen in der ArrayList sicher ausschließen kann?

Um das festzustellen benötige ich keine equals Methode, sondern kann mit == überprüfen.

Bsp.:

private void remove(ArrayList<Integer> list, int[] values) {
  for (int i = 0; i < values.length; i++) {
    if (values[i] != 0) { // Performanter???
      list.remove(values[i]);
    }
  }
}

Danke!

 

[Grasstampfer]

die idee so wie du es schreibst geht so und so nicht...
die methode remove benoetigt den Index welches element geloescht wird.

so wie du es beschreibst stehen im array die werte die geloescht werden sollen, also rufst du remove mit einem wert nicht mit einem index auf.

du muesstest wissen an welcher stelle der Wert X, der im array steht und somit geloescht werden soll, in der liste vorkommt.

es gibt die methode remove(Object o) aus der liste, aber da du ein int[] benutzt nimmt er die remove(int index) methode...

ansonsten glaub ich nicht dass du viel zeit damit gewinnst... das remove laeuft einmal ueber die liste drueber und prueft mit equals auf gleichheit. selbst bei einer liste von 10000 elementen ist das ne sache von millisekunden.

ich persoenliche finde es aber besser dass, wenn du schon werte ausschliessen kannst, die nicht in der liste vorkommen, dass dann auch nicht geloescht werden muss, ergo wuerde ich die abfrage vorher machen.

 

[SlaterB]

1.
selber testen?

2.
in dem Bereich doch hoffentlich ohne jede Performance-Relevanz
oder löschst du milliardenfach Elemente aus Listen?

3.
LinkedList statt ArrayList könnte allein schon wegen des Löschens performanter sein?

4.
wenn sowas schon wichtig ist, dann schreib doch lieber ne eigene Klasse, die gleich die Werte irgendwie indexiert,
oder zumindest mitzählt, wieviel von welcher Sorte vorhanden ist

 

[The_S]

@Grasstampfer

Die Idee geht, ich hab nur beim Beispielcode vergessen einen Integer zu erstellen .

Dieser Vorgang muss seeeeeeeeeeeeeehr oft auf einem seeeeeeeeeeehr langsamen PC wiederholt werden. Deshalb die Performance-Frage.

@Slater

1. geht nicht, s. o.
2. siehe Antwort an Grasstampfer
3. hab mich noch nicht mit den Perfromance Unterschieden zwiscnen LL und AL auseinander gesetzt. Werde ich mal tun ...
4. hab ich auch schon überlegt, geht mir aber primär um die oben genannte Fragen und nicht um Alternativen

Danke

 

[Marco13]

Beim "remove" mit einem Element, das nicht in der Liste enthalten ist, tritt der worst case ein: Die Liste muss komplett durchsucht werden, nur um festzustellen, dass das Element nicht enthalten ist. Wenn man das vorher schnell testen kann, sollte man das vermutlich tun ...

 

[Leroy42]

Ich würde vom worst-case beim Löschen aus einer Array-List
eher dann sprechen, wenn das 1. Element gelöscht werden soll! :shock:

Auch mein Vorschlag: Umstellung auf eine LinkedList

 

[The_S]

Also ich werd wohl nicht drum rum kommen das zu testen. Mach ich mal sobald ich die Möglichkeit habe. Danke für eure Tipps!

 

[Marco13]

OK, das was Leroy42 erwähnt hat stimmt zwar, ist aber nur ein Implementierungsdetail der List. Wenn dort irgendeine List verwendet wird, dann ist das Löschen eines nicht enthaltenen Elements der worst case. Wenn die konkrete Implementierung eine ArrayList ist, ist ein Löschen des ersten Elements zwar "noch schlechter", aber das könnte man ja durch Verwendung einer LinkedList umgehen :wink:

 

[SlaterB]

ich empfinde das Durchlaufen der ganzen Liste eher als Normalfall,

hier bisher kaum direkt thematisiert: remove() löscht nur das erste Vorkommen,
wenn es das erste Element der Liste ist, dann wird 99% der Liste gar nicht durchlaufen,

wenn man weiß, dass ein Element nur maximal einmal vorhanden sein kann, dann mag das reichen,
ansonsten muss man doch eh noch ein remove hinterherschicken