Holen Sie sich eine Unterliste aus einer Arraylist effizient

Mein ProblemHolen Sie sich eine Unterliste aus einer Arraylist effizient

Ich habe eine feste Größe Arraylist, die benutzerdefinierten Variablen enthält. Obwohl die ArrayList eine feste Größe hat, werden viele von ihnen tatsächlich null sein. Die Sache ist, dass ich die ArrayList ohne die Nullvariablen innerhalb es zurückgeben muss. Eine wichtige Sache zu beachten:die ArrayList wird alle Nicht-Null-Elemente zuerst haben, und dann alle Nullen unter ihnen, z. B. die Elemente sind nicht gemischt. Beispiel: [nicht-null, nicht null, .... null, null, null]

Meine Abhilfe

ich aber von einer for-Schleife erstellen, die (von den letzten geprüft zum ersten Index) jedes der Elemente innerhalb der ArrayList, um festzustellen, ob es null ist oder nicht. Wenn null ist, dann würde ich diesen Code nennen:

for (i = size-1; i >=0 ; i--) { 
    groupList = new ArrayList<>(groupList.subList(0, i)); 
}

Meine Frage

Wenn die Arraylist zu groß ist, ist diese Methode könnte ich besonders langsam (oder nicht?). Ich habe mich gefragt, ob es eine bessere, leistungsfähigere Lösung gibt. AFAIK die .subList-Methode ist teuer.

Quelle

2015-08-25 Jose Lopez

Die Methode '.subList' ist O (1). Es kopiert nicht; es ist _super super billig._ –

Dies zeigt ein ernsthaftes Designproblem.Was ist der Punkt, der eine Liste fester Größe macht und Nullen in der Liste speichert, wenn das, was Sie wirklich wollen, eine Liste variabler Größe ist, die keine Nullen enthält? Warum speichern Sie nicht zumindest den Index des ersten Nullwertes in einer Variablen? –

@Rainbolt Ich reagierte hauptsächlich auf den letzten Satz der OP-Frage, die behauptete, "die .subList-Methode ist teuer". –

Sie können eine Variante von binary search haben, wo Ihre benutzerdefinierten Komparator ist:

Beide Elemente sind null/nicht null? Sie sind gleich
Nur ein Element ist null? Die none null ist "kleiner".

Sie suchen nach dem ersten Nullelement.

Dies dauert O (logn) Zeit, wobei n die Größe des Arrays ist.

Allerdings ist die Unterliste der ArrayList, die keine Null ist (vorausgesetzt, Sie werden es in ein neues Listenobjekt kopieren), wird linear Zeit der Elemente kopiert werden, da Sie jedes von "berühren" müssen Sie.

Dies ergibt eine Gesamtzeitkomplexität von O(logn + k), wobei k die Anzahl der Nicht-Null-Elemente und n die Größe des Arrays ist.

Quelle

2015-08-25 19:04:04 amit

nur ändern, wo das Array endet, ohne es zu kopieren/verschieben ist O (1) - das sollte in einigen Sprachen/mit einigen Implementierungen möglich sein. Also dann O (logn)? – Brendan

@brendan Ja, aber AFAIK, speziell in Java wird es erforderlich sein, eine benutzerdefinierte Implementierung zu erstellen. Vielleicht unterstützt ['ArrayList.removeRange()'] (http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#removeRange (int,% 20int)) dieses Verhalten effizient (wahrscheinlich), aber es ist eine geschützte Methode. – amit

Ja, das klingt nach Java ... haha – Brendan

Nach all Ihren ausstehenden Ratschlägen habe ich die ursprüngliche Methode so geändert, dass ich die letzte (erste) Nullpositionsposition nehmen und die .subList-Methode nur einmal aufrufen kann. Und hier ist sie:

int lastNullIndex = size - 1; 

for (i = lastNullIndex; i >= 0; i--) { 
    if (null == groupList.get(i)) { 
     lastNullIndex = i; 
    } else { 
     break; 
    } 
} 

groupList = new ArrayList<>(groupList.subList(0, lastNullIndex)); 
return groupList;

Wenn Sie denken, es kann weiter modifiziert werden, um für eine bessere Leistung zu ermöglichen, lassen Sie es uns wissen.

Quelle

2015-08-25 19:24:45

Holen Sie sich eine Unterliste aus einer Arraylist effizient

Antwort

Verwandte Themen