Frage zu Lambda-Expressions (C#)

[Mr. Lolman]

Was ist besser/performanter?


1. List.RemoveAll(x => x.Any(y => y.object != null && y.object.subobject == criteria);

2. List = List.Where(x => x.All(y => y.object != null && y.object.subobject != criteria).ToList();


Oder ists wurscht?
Oder sollte man das überhaupt ganz anders machen?

(BTW: y.object?.subobject versteht das VS2010 noch nicht;))

[Ectoplasma]

Ohne mich groß damit auszukennen, aber es könnte sein, dass 1. schneller ist und auch weniger Resourcen verbraucht. Bei 2. wird immerhin eine zusätzliche Liste aufgebaut und das Original erst nach der Zuweisung "zerstört". Das sind einige Operationen mehr.

[Monger]

Vielleicht steh ich aufm Schlauch, aber der All und Any Ausdruck sind doch nicht äquivalent?

Ich kenn die Implementierung nicht, aber wenn sie es klever gemacht haben, ist es gleich schnell.
Remove Operationen sind tendentiell teuer, weil du die Liste immer wieder neu zusammenschieben musst. Intern wird die Liste also mindestens einmal frisch aufgebaut, was aber normalerweise extrem schnell geht.

Der Pferdefuß hier ist eher "all". Any hüpft sofort raus, sobald mindestens ein Element die Bedingung erfüllt, All erst wenn alle überprüft wurden. Würde daher einfach den Any Ausdruck für den zweiten Ausdruck negieren.

[Monger]

Das gilt vielleicht nicht für den Fall hier, aber: Die Erfahrung aus funktionalen Sprachen zeigt, wie wertvoll unveränderliche Objekte wie z.B. Readonly Listen sind. Du kannst dann Optimierungen durchführen, die den Overhead durch Instanziierung locker aufwiegen.

List ist daher eher net so gut optimiert. Eierlegende Wollmilchsau halt, die für fast alle Fälle taugt, aber relativ hohen Speicherverbrauch mit mäßiger Performance verbindet.

[registrierter Gast]

Das kommt auf die Implementierung der Liste an.

Als LinkedList ist die erste Variante schneller, weil dann Elemente schnell aus der Liste entfernt werden.
Als ArrayList werden Lücken damit gefüllt, dass die nachfolgenden Elemente nach vorn geschoben werden. Bei n Treffern wird also auch n-mal geschoben werden.
Variante zwei ist als ArrayList schneller.

Generell finde ich Variante 2 wegen dem funktionalen Ansatz schöner.

[PatkIllA]

Ohne mich groß damit auszukennen, aber es könnte sein, dass 1. schneller ist und auch weniger Resourcen verbraucht. Bei 2. wird immerhin eine zusätzliche Liste aufgebaut und das Original erst nach der Zuweisung "zerstört". Das sind einige Operationen mehr.
Oder mit IEnumerable anfreunden.
Meist braucht man gar keine Liste.

Wenn du es performant willst dann fummelst du mit Arrays und count rum (das was List<T> intern macht). Das ist aber oft nervig, schlecht wartbar und fast nie relevant.

[Unfug]

1 ist schneller da bei 2 noch ToList() durchgeführt wird.


Ich empfehle :
a) Niemals Null Objekte in die Liste hinzufügen. Du weißt scheinbar nicht was in deiner Liste ist bzw. welchen Status die einzelnen Objekte haben. Das ist extrem gefährlich. Prüfe vorher die Objekte, bevor du sie in die Liste hinzufügst.

b) Law of Delimiter: Du fragst parent.child.child ab. Zieh das subobject einen höher, wenn Du es brauchst.
c) Arbeite mit ImmutableList. (Jede Änderung erzeugt eine neue Liste).
d) Arbeite mit IEnumerable und wandle erst in List um, wenn Du auch wirklich die Methoden/Funktionen von List benötigst.

Deine Abfrage sollte lauten:
MyList.Where(x=>x.object !=criteria);

[PatkIllA]

d) Arbeite mit IEnumerable und wandle erst in List um, wenn Du auch wirklich die Methoden/Funktionen von List benötigst.Würde ich auch empfehlen. Als Nachtrag noch, dass das dann lazy ist.
Wir hatten schon den Fall, dass das bis zum Datenbank aufmachen durch ging und dann jedes iterieren die an die Datenbank gegangen ist.

Außerdem halten die Lambdas oder IEnumerable<T> mit yield return oft Objekte fest, die dann auch nicht vom GarbageCollector weggeräumt werden können.

Und dann gibt es noch das dämliche Pattern.

if (enumerable.Any())
{
foreach (var item in enumerable)
{
..
}
}

oder noch schlimmer
if (enumerable.Count() > 0)
{
foreach (var item in enumerable)
{
..
}
}

[Monger]

b) Law of Delimiter: Du fragst parent.child.child ab. Zieh das subobject einen höher, wenn Du es brauchst.

https://en.wikipedia.org/wiki/Law_of_Demeter

[Ectoplasma]

Remove Operationen sind tendentiell teuer, weil du die Liste immer wieder neu zusammenschieben musst.

Du meinst einen Vector? Remove Operationen in einer verlinkten Liste sind extrem billig. Leider steht da ja nicht, wie die Liste implementiert ist.

@PatkIllA, ich glaube du hast dem falschen geantwortet, oder? Der TS wollte eigentlich eine Antwort, ich hingegen habe nur ein Vermutung geäußert, die von Unfug im Prinzip allerdings bestätigt wurde.

[Mr. Lolman]

Besten Dank für die zum Teil sehr aufschlussreichen Antworten.

Die Liste ist eine normale List<T> wobei T als nested Object von einem Webservice retourniert wird. Die Liste selbst hat den Zweck eines lokalen Caches, der ggf aktualisiert werden muss (dh. Elemente hinten angefügt oder innerhalb der Liste Elemente entfernt werden).

T ist ein weakly typed Object, es werden anscheinend willkürlich Null Werte oder leere Strings retouniert. Diverse children von T liegen als T[] vor , welche dann zum Teil wieder T[] als weiteres Kindelement haben.


EDIT:

Und dann gibt es noch das dämliche Pattern.

Stimmt. Ich greif mir bei meinem eigenen alten Source aber auch regelmäßg an den Kopf. zB var z = T.Where(x => x.child == y).FirstOrDefault() ;)
ad Law of Demeter: Unabhängig davon was meine kommende Frage in dem Zusammenhang alles impliziert - kann man folgenden Ausdruck noch einfacher schreiben? :redface: :confused:

new Func<bool>(() => { a = b; return true})()

[robobimbo]

wat? return a==b;

bzw. bei lambda-ausdrücken brauchst gar kein return, imho

[Monger]

Du meinst einen Vector? Remove Operationen in einer verlinkten Liste sind extrem billig. Leider steht da ja nicht, wie die Liste implementiert ist.

List<T> ist intern ein Array, plus Hashtable. Ergo, optimiert darauf schnell zu prüfen ob die Liste ein bestimmtes Element enthält.

[Trap]

List<T> ist intern ein Array, plus Hashtable. Ergo, optimiert darauf schnell zu prüfen ob die Liste ein bestimmtes Element enthält.
Ich sehe hier keine Hashtable https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,cf7f4095e4de7646

Und in der Dokumentation (https://msdn.microsoft.com/en-us/library/bhkz42b3(v=vs.110).aspx) steht auch nicht, dass Contains schnell sein soll:
This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.

[Mr. Lolman]

wat? return a==b;

bzw. bei lambda-ausdrücken brauchst gar kein return, imho

Nä a = b ist eine Zuweisung und return true, damit ich das als verkettete Lambda Expression im x.ten Subobjekt ausführen kann :eek:

[Monger]

Ich sehe hier keine Hashtable https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,cf7f4095e4de7646

Und in der Dokumentation (https://msdn.microsoft.com/en-us/library/bhkz42b3(v=vs.110).aspx) steht auch nicht, dass Contains schnell sein soll:
Okay, komisch, ich war mir so sicher... Die List ist ja dann wirklich nix anderes als ein Array. Hatte gedacht das wäre komplexer.

[][immy]

Was ist besser/performanter?


1. List.RemoveAll(x => x.Any(y => y.object != null && y.object.subobject == criteria);

2. List = List.Where(x => x.All(y => y.object != null && y.object.subobject != criteria).ToList();


Oder ists wurscht?
Oder sollte man das überhaupt ganz anders machen?

(BTW: y.object?.subobject versteht das VS2010 noch nicht;))

es dürfte schneller sein, eine neue Liste zu erstellen, als elemente aus einer bestehenden zu entfernen. Aber kann gut sein, das Linq das schon für einen erledigt, aber generell ist es niemals gut aus einem Array oder einer Liste Elemente zu entfernen.
Besonders der Garbage Collector freut sich ansonsten das bei jedem entfernten Element ein neues Array im Hintergrund erstellt wird. Aber wie geschrieben, gut möglich das Linq das schon von sich aus so macht.

Wirklich schlecht wäre es allerdings wenn Linq intern die Liste nicht in der passenden Größe vorinitialisiert, dann würde der Garbagecollector einiges zu tun bekommen.
Kann also auch gut sein, das am ende beides genau so schnell ist. Müsste man dementsprechend einfach mal testen. Um sicher zu gehen die schnellste Methode zu haben würde ich aber Option 2 wählen.

@Monger
Da is nix mit Hashtable. Hab schon oft gesehen das Hashtables deutlich schneller darin sind etwas zu finden. Ist allerdings nicht so schön lesbar. ... Gibt es eigentlich keine typisierte Hashtable? Das wäre für viele Dinge gut.

@Unfug
das .ToList() sorgt nur dafür das die Lambda Expression auch tatsächlich komplett ausgeführt wird. Als Enumerable würde ich es nur lassen, wenn du noch vor hast weitere Linq-Befehle daran zu reihen. Dann optimiert sich das Intern eventuell noch. Das RemoveAll wird hingegen direkt ausgeführt und nicht erst beim ersten zugriff auf die Liste.

Ohne mich groß damit auszukennen, aber es könnte sein, dass 1. schneller ist und auch weniger Resourcen verbraucht. Bei 2. wird immerhin eine zusätzliche Liste aufgebaut und das Original erst nach der Zuweisung "zerstört". Das sind einige Operationen mehr.
Das ist leider nicht so. Jedes mal wenn du aus einem Array (eine Liste ist letztlich nichts anderes als ein erweitertes array) etwas entfernst, wird ein neues Array erzeugt und alles übrige hineinkopiert (sind ja nur Referenzen). Aber das alte Array wird dem GC vorgeworfen und der hat was zu tun. Daher wäre die Frage ob Linq jetzt erst mal guckt wie groß das Array am ende wird, oder wirklich jeden Wert einzeln rausschmeißt (worst case).
Wenn Linq allerdings beim zusammenbauen ebenfalls die Elemente einzeln der Liste hinzufügen würde, hätte der GC auch wieder was zu tun. Aber eigentlich sollte Linq soweit optimiert sein, das das nicht passiert.

[PatkIllA]

[immy;11670328']es dürfte schneller sein, eine neue Liste zu erstellen, als elemente aus einer bestehenden zu entfernen. Aber kann gut sein, das Linq das schon für einen erledigt, aber generell ist es niemals gut aus einem Array oder einer Liste Elemente zu entfernen.
Besonders der Garbage Collector freut sich ansonsten das bei jedem entfernten Element ein neues Array im Hintergrund erstellt wird. Aber wie geschrieben, gut möglich das Linq das schon von sich aus so macht.
Wirklich schlecht wäre es allerdings wenn Linq intern die Liste nicht in der passenden Größe vorinitialisiert, dann würde der Garbagecollector einiges zu tun bekommen.
Bei Linq werden meistens nur neue IEnumerables und IEnumerator und delegate objekte erstellt. Davon jede Menge.
Beim Entfernen in der Liste wird "nur" umkopiert. Da braucht man kein neues Array. Die neue Liste wird allerdings schrittweise vergrößert.
[immy;11670328']Kann also auch gut sein, das am ende beides genau so schnell ist. Müsste man dementsprechend einfach mal testen. Um sicher zu gehen die schnellste Methode zu haben würde ich aber Option 2 wählen.Deswegen bencht man ja und wenn man wirklich Performance braucht setzt man Linq nur sehr sparsam ein.
[immy;11670328']@Monger
Da is nix mit Hashtable. Hab schon oft gesehen das Hashtables deutlich schneller darin sind etwas zu finden. Ist allerdings nicht so schön lesbar. ... Gibt es eigentlich keine typisierte Hashtable? Das wäre für viele Dinge gut.IDictionary<TKey, TValue> die muss man allerdings auch erstmal erstellen, indizieren usw. Außerdem geht dann die Reihenfolge verloren. Und man hat nur nach der einen Eigenschaft indiziert.
[immy;11670328']Das ist leider nicht so. Jedes mal wenn du aus einem Array (eine Liste ist letztlich nichts anderes als ein erweitertes array) etwas entfernst, wird ein neues Array erzeugt und alles übrige hineinkopiert (sind ja nur Referenzen). Aber das alte Array wird dem GC vorgeworfen und der hat was zu tun. Daher wäre die Frage ob Linq jetzt erst mal guckt wie groß das Array am ende wird, oder wirklich jeden Wert einzeln rausschmeißt (worst case).Da wird nichts neuerstellt sondern nur umkopiert. Der Quelltext ist doch einsehbar.
[immy;11670328']Wenn Linq allerdings beim zusammenbauen ebenfalls die Elemente einzeln der Liste hinzufügen würde, hätte der GC auch wieder was zu tun. Aber eigentlich sollte Linq soweit optimiert sein, das das nicht passiert.Es gibt ein paar Shortcuts für IEnumerable<T> die auch ICollection<T> sind. Beim Where ist das allerdins nicht mehr vorhanden. Da wird das Array immer dann verdoppelt wenn die Kapazität nicht ausreicht.

[Monger]

[immy;11670328']
@Monger
Da is nix mit Hashtable. Hab schon oft gesehen das Hashtables deutlich schneller darin sind etwas zu finden. Ist allerdings nicht so schön lesbar. ... Gibt es eigentlich keine typisierte Hashtable? Das wäre für viele Dinge gut.

Dictionary<Key,Value> ?
Das ist doch nix anderes als ne Hashtable

[][immy]

Dictionary<Key,Value> ?
Das ist doch nix anderes als ne Hashtable
gefühlt aber um einiges langsamer, deshalb hab ich jetzt auch nicht an das Dictionary gedacht ^^


Da wird nichts neuerstellt sondern nur umkopiert. Der Quelltext ist doch einsehbar.


Kann sein (in den Quelltext hab ich nicht geschaut), mein Wissen kam da eher von dem Verhalten von Arrays, aber Generische Listen können da natürlich noch mal Logik drum herum bauen. Schnell hab ich es allerdings nie in Erinnerung wenn ich etwas massenweise aus einer Liste entferne.
Das mit den Enumerable-Objekten ist mir durchaus klar, aber das hat ja eigentlich nur mit Lazyloading zu tun. Die Operation wird spätestens dann ausgeführt wenn du sie Objekte daraus anforderst. Im Falle von LinqToSql kann ich dann immer nur empfehlen .ToList() zu nutzen, weil ansonsten massig Verbindungen geöffnet und geschlossen werden wenn man mal da durch geht.

Linq ist allgemein für mich eher ein schneller weg ein Ziel zu erreichen. Häufig kommen auch Optimierungen etc darin zum tragen, die man ansonsten nicht hätte. Allerdings geht es meist mit "klassischem" Code dann doch noch flotter. Aber eben nicht flotter zu schreiben.

[Demirug]

[immy;11671226']Kann sein (in den Quelltext hab ich nicht geschaut), mein Wissen kam da eher von dem Verhalten von Arrays, aber Generische Listen können da natürlich noch mal Logik drum herum bauen. Schnell hab ich es allerdings nie in Erinnerung wenn ich etwas massenweise aus einer Liste entferne.

Wiederholtes RemoveAt ist langsam weil dabei jedesmal alles was nach dem gelöschten Element kommt verschoben wird.

RemoveAll ist optimiert. Im schlimmsten Fall wird jedes Element das in der Liste bleiben soll einmal kopiert egal wie viele Elemente entfernt werden.