foreach: Ist die Reihenfolge festgelegt?
Abgeteilt von foreach oder for? was ist schneller?
Zu beachten ist IMHO noch, dass foreach nicht garantiert, in welcher Reihenfolge die Collection durchlaufen wird - for hingegen schon.
Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden
Um einige gesicherte Ergebnisse des Threads schon vorweg zu nehmen:
Die Reihenfolge, in der foreach die Elemente durchläuft, ist auf jeden Fall definiert, denn foreach ist laut Sprachspezifikation 8.8.4 The foreach statement nur eine Abkürzung für(*):
E enumerator = (collection).GetEnumerator(); try { while (enumerator.MoveNext()) { ElementType element = (ElementType)enumerator.Current; statement; } } finally { IDisposable disposable = enumerator as System.IDisposable; if (disposable != null) disposable.Dispose(); }
Insofern wird die Reihenfolge also einzig und alleine durch den Enumerator der Collection festgelegt.
Und zumindest für Arrays die Reihenfolge, in der die Elemente in foreach durchlaufen werden, in der Sprachspezifikation explizit definiert ist, nämlich:
For single-dimensional arrays, elements are traversed in increasing index order, starting with index 0 and ending with index Length – 1.
Welche Schlüsse man daraus für andere Arten von Collections ziehen kann, wird im Thread kontrovers diskutiert.
(*) In C# 5.0 hat sich der genaue Code, der für foreach eingesetzt wird, leicht geändert, was allerdings für das hier behandelte Thema keinen Unterschied macht. Was genau sich geändert hat, steht in Has foreach's use of variables been changed in C# 5?
Hallo Golo Roden,
foreach benutzt ja intern nichts anders als IEnumerator bzw. IEnumerator<T>. Und zu der entscheidenden Methode IEnumerator.MoveNext steht in der Doku:
Nach dem Erstellen eines Enumerators oder nach dem Aufrufen der Reset-Methode wird ein Enumerator zunächst vor dem ersten Element der Auflistung positioniert. Der erste Aufruf der MoveNext-Methode legt den Enumerator auf das erste Element der Auflistung fest. [Ansonsten] setzt [MoveNext] den Enumerator auf das nächste Element der Auflistung.
Natürlich sind "erste" und "nächste" nicht absolut feststehende Begriffe, aber zumindest für Collections, auf die man über eine natürliche Zahl als Index zugreifen kann, sind diese Begriffe schon ziemlich klar definiert. Insofern kann man in aller Regel davon ausgehen, dass die Reihenfolge garantiert und determiniert ist.
Ausnahmen wie IsoIter.Shuffle aus Hilfreiche Iteratoren / Improving Foreach bestätigen die Regel. 🙂
herbivore
Jein. Denn was passiert, wenn Du aus einer Collection einen Eintrag entfernst, und einen neu hinzufügst? Hängt der dann hinten dran? Hängt der zwischendrin? Das kann je nach Implementierung durchaus unterschiedlich sein, und vor allem könnt es in .NET 4.0 (oder in Mono, oder im CF) anders sein ... deswegen sollte man sich hierauf NIE verlassen.
Und wer sagt, wie es sich bei einer eigenimplementierten Collection verhält? Diese kann sich ja ganz anders verhalten ...
Ebenso wenig wie zB dass Eventhandler in einer festgelegten Reihenfolge ausgelöst werden. Auch hier ist es eben NICHT zwingend die Reihenfolge, in der die Handler angemeldet wurden.
Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden
Hallo Golo Roden,
Denn was passiert, wenn Du aus einer Collection einen Eintrag entfernst, und einen neu hinzufügst?
da man Collections während des foreach per Definition nicht ändern darf, spielt dieser Fall bzw. diese Überlegung keine Rolle.
und vor allem könnt es in .NET 4.0 anders sein
Ich würde davon ausgehen, dass alle Iteratoren der Framework-Klassen deterministisch sind und sich die Reihenfolge nie ändern wird. Und damit gilt das Gleiche für foreach.
Ebenso wenig wie zB dass Eventhandler in einer festgelegten Reihenfolge ausgelöst werden.
Dein Vergleich finde ich insofern irreführend, als dass EventHandler auch praktisch in einer anderen als der erwarteten Reihenfolgen aufgerufen werden können. Bei foreach ist das (zumindest für die Standard-Collections) allenfalls theoretisch der Fall.
Und wer sagt, wie es sich bei einer eigenimplementierten Collection verhält? Diese kann sich ja ganz anders verhalten ...
Ich würde zumindest erwarten, dass auch hier eine Reihenfolge definiert ist und deterministisch eingehalten wird. Wenn nicht würde ich das als Implementierungsfehler in der eigenimplementierten Collection ansehen.
herbivore
Und wer sagt, wie es sich bei einer eigenimplementierten Collection verhält? Diese kann sich ja ganz anders verhalten ...
Ich würde zumindest erwarten, dass auch hier eine Reihenfolge definiert ist und deterministisch eingehalten wird. Wenn nicht würde ich das als Implementierungsfehler in der eigenimplementierten Collection ansehen.
ah dein wort in gottes ohr (oder zumindes in dem vom projektleiter....)
ich stimme dir hier komplett zu.
Mich interessiert eure Meinung:
Die Semantik der foreach-Schleife ist ja eher deklarativ als prozedural und besagt lediglich, dass etwas mit allen Elementen getan wird. D.h. die Reihenfolge der Elemente wird nicht explizit festgelegt sondern nur implizit durch die dahinterstehende Implementierung der Iteratoren. Wenn hier nun sooft die Lesbarkeit des Codes als prioritär angegeben wird, ist es dann nicht ein Hohn, eine Abarbeitungsreihenfolge in einer foreach-Schleife (implizit) vorauszusetzen, obwohl dies durch keinerlei Syntax garantiert werden kann?
Hallo,
Und wer sagt, wie es sich bei einer eigenimplementierten Collection verhält? Diese kann sich ja ganz anders verhalten ...
Ich würde zumindest erwarten, dass auch hier eine Reihenfolge definiert ist und deterministisch eingehalten wird. Wenn nicht würde ich das als Implementierungsfehler in der eigenimplementierten Collection ansehen.
Wäre nicht ein Enumerator denkbar und sinnvoll, der die Elemente einer Liste in einer zufälligen Reihenfolge durchläuft?
Wäre nicht ein Enumerator denkbar und sinnvoll, der die Elemente einer Liste in einer zufälligen Reihenfolge durchläuft?
denkbar -> ja
sinnvoll -> WOZU bitte?
Da es komplizierter wäre die Elemente in zufälliger Reihenfolge zu durchlaufen als der Reihe nach denke ich dass kaum jemand seinen Enumerator so programmieren würde. Elemente in zufälliger Reihenfolge wiedergeben ist eigentlich zu speziell für einen Enumerator, der sollte eher allgemein gehalten sein -> also sequenziell
Lg
Preli
Hallo Kartoffel,
Wenn hier nun sooft die Lesbarkeit des Codes als prioritär angegeben wird, ist es dann nicht ein Hohn, eine Abarbeitungsreihenfolge in einer foreach-Schleife (implizit) vorauszusetzen, obwohl dies durch keinerlei Syntax garantiert werden kann?
im Grunde hast du Recht. Rein pragmatisch gesehen spricht aber m.E. nichts gegen diese Annahme (= implizite Voraussetzung). Sie macht das Leben leichter und die Wahrscheinlichkeit, dass sie nicht gilt, ist in meinen Augen wie gesagt nur theoretischer Natur.
Hallo ujr,
Wäre nicht ein Enumerator denkbar und sinnvoll, der die Elemente einer Liste in einer zufälligen Reihenfolge durchläuft?
mehr als denkbar: mit IsoIter.Shuffle (s.o.) habe ich ja sogar so einen Iterator implementiert. Allerdings ist das auch eine bewusste Ausnahme.
Im Allgemeinen sollte die Reihenfolge definiert und deterministisch sein. Sonst bekommt man unnötigerweise Effekte, wie sie bei C mit uninitialisierten Variablen aufgetreten konnten. Das Programm zeigt manchmal (quasi zufällig) Fehler und manchmal nicht. Und da solche Fehler schwer zu finden sind, sollte eben die Reihenfolge definiert und deterministisch sein.
herbivore
Ich sehe das ein bisschen anders:
Da die Reihenfolge eben nicht definiert und nicht deterministisch ist, sollte der Code so geschrieben sein, dass er sich nicht darauf verlässt, dass eine bestimmte Reihenfolge vorliegt.
Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden
Hallo preli,
sinnvoll -> WOZU bitte?
als Beispiel schwebte mir spontan eine zufällig zu durchlaufende Playliste vor, und es gibt sicherlich noch andere nützliche Anwendungen.
Hallo herbivore,
danke für die Erläuterung. IsoIter ist sehr interessant, muss ich mir allerdings nochmal in Ruhe anschauen.
Selbstverständlich ist eine deterministische Reihenfolge zu bevorzugen (schon allein für die Fehlersuche 🙂, und in den allermeisten Fällen ja auch gegeben. Andererseits ist diese deterministische Reihenfolge ja nicht notwendigerweise bekannt (Dictionary), sodass Annahmen u. U. schwer zu treffen sind.
Ähnlich verhält es sich meiner Meinung nach mit den Kind-Knoten eines XML-Knotens - ich habe bisher keine Dokumentation gefunden, die festlegt, dass diese Knoten in der Reihenfolge ihres Auftretens in der XML-Datei durchlaufen werden - egal ob mit for oder foreach.
als Beispiel schwebte mir spontan eine zufällig zu durchlaufende Playliste vor, und es gibt sicherlich noch andere nützliche Anwendungen.
Ja, das wäre ein Beispiel warum man in zufälliger Reihenfolge auf eine Liste zugreifen möchte, aber in meinen Augen kein Beispiel für einen Enumerator der eine Liste zufällig durchläuft. Man will ja sicher die Liste auch der Reihe nach anhören. Wie schon gesagt: "gemischter" Zugriff auf eine Liste -> ja; aber nur als Spezialfall und das würd ich nicht in einem Enumerator implementieren
Lg
Preli
Hallo Golo
Da die Reihenfolge eben nicht definiert und nicht deterministisch ist, sollte der Code so geschrieben sein, dass er sich nicht darauf verlässt, dass eine bestimmte Reihenfolge vorliegt.
Was ja implizieren würde, das in keinem Fall foreach benutzt werden darf, ausser die Reihenfolge ist egal.
Gruss Peter
--
Microsoft MVP - Visual Developer ASP / ASP.NET, Switzerland 2007 - 2011
- https://peterbucher.ch/ - Meine persönliche Seite
- https://fpvspots.net/ - Spots für FPV Dronenflüge
Hallo Golo Roden,
Ich sehe das ein bisschen anders:
das ist dein gutes Recht. 🙂
Da die Reihenfolge eben nicht definiert und nicht deterministisch ist, sollte der Code so geschrieben sein, dass er sich nicht darauf verlässt, dass eine bestimmte Reihenfolge vorliegt.
Woraus leitest du das ab?
Ich habe ja oben geschrieben aus welcher Stelle der Doku ich meine Sichtweise der Definiertheit ableite.
Außerdem habe ich begründet, warum Undeterminiertheit die Fehlersuche unnötig erschweren würde. Wenn man aus den Problemen mit der Undeterminiertheit von uninitialisierten Variablen in C gelernt hat, dass diese unbedingt zu vermeiden sind, dann sollte man den gleichen Schluss auch für Undeterminiertheit von Enumeratoren ziehen.
Sicher, mir ist klar dass bei einem Dictionary einer Hashtable die Reihenfolge der Aufzählung auf der internen Reihenfolge der Buckets basiert und die von außen gesehen chaotisch wirkt und sich zudem durch Hinzufügen weiterer Elemente ändern kann. Trotzdem ist sie determiniert in dem Sinne, dass bei gleicher Einfügereihenfolge von Elementen die Reihenfolge der Auszählung die gleiche ist.
EDIT: In Dictionary sortieren nach Value (möglichst performant) und die Key-Value Beziehung beibehalten habe ich gelernt, dass der Enumerator eines Dictionaries die Einträge - solange zwischendurch nichts gelöscht wird - in der Reihenfolge liefert, in der sie hinzugefügt wurden, also keineswegs so chaotisch aufzählt, wie das bei einer Hashtable der Fall ist.
herbivore
Hallo Golo Roden,,
ich habe mal weiter gesucht und jetzt zumindest für Arrays folgendes in der Sprachspezifikation (8.8.4 The foreach statement) gefunden:
The order in which foreach traverses the elements of an array is as follows: For single-dimensional arrays, elements are traversed in increasing index order, starting with index 0 and ending with index Length – 1.
Damit ist zumindest für Arrays in der Sprachspezifikation festgeschrieben, in welcher Reihenfolge sie mit foreach durchlaufen werden.
Das ist zwar kein Beweis, dass das ich mir meiner Ansicht grundsätzlich richtig liege, aber doch ein starkes Indiz. Natürlich kann die Sprachspezifikation nicht z.B. auf List<T> eingehen, weil List<T> kein Teil der Sprache sondern "nur" des Frameworks ist.
Abgesehen davon ist in der Sprachspezifikation die Übersetzung von foreach in eine while-Schleife unter Verwendung von MoveNext und Current des mit GetEnumerator abgerufenen Enumerators des Collection angegeben. Damit ist die Semantik von foreach definiert. Daher ist kein Raum anzunehmen, dass nicht klar wäre, in welcher Reihenfolge foreach selbst die Elemente durchläuft. foreach durchläuft die Elemente also sicher in der Reihenfolge, die durch den Enumerator vorgegeben ist.
Das einzige was offen ist, ist in welcher Reihenfolge der jeweilige Enumerator die Elemente durchläuft. Wenn also für einen bestimmten Collection-Typ klar ist, in welcher Reihenfolge der zugehörige Enumerator die Elemente der Collection durchläuft (und das ist ja z.B. bei Arrays der Fall), dann ist die Reihenfolge insgesamt definiert und determiniert.
Bleibt also nur noch die Frage, ob es relevante Fälle gibt, in denen Enumeratoren von Collections keine definierte und determinierte Reihenfolge einhalten. Und da greift schon der oben genannte Hinweis, dass die Doku der Schnittstelle IEnumerator durch die Verwendung der Begriffe "erstes Element" und "nächstes Element" zumindest eine bestimmte Ordnung intendiert.
Ich fände es ausgesprochen unpraktisch, wenn ich mich bei
foreach (String strLine in File.ReadAllLines ("bla.txt"))
nicht darauf verlassen könnte, dass die Zeilen in der Reihenfolge abgearbeitet werden, in der sie in der Datei stehen. Zum Glück kann man sich aber darauf verlassen, weil die Reihenfolge von foreach selbst sowie des hier verwendeten Enumerators eines Arrays durch die Sprachspezifikation klar definiert ist.
herbivore
Hallo,
also, zuerst einmal - was das foreach-Statement und dessen interne Umsetzung angeht, gebe ich Dir vollkommen recht: Was foreach an sich macht, ist deterministisch.
Die Frage, ob der zu Grund liegende Enumerator deterministisch ist, ist letztlich also die entscheidende Frage. Und hier gilt doch: Man weiß es nicht, zudem kann dies von Collection zu Collection variieren.
Natürlich ist davon auszugehen, dass eine Textdatei mit ReadAllLines immer von vorne nach hinten abgearbeitet wird, aber worauf ich hinaus will ist, dass eben nirgends explizit steht, dass dies immer und bei jeder Collection der Fall ist - oft genug wird aber so programmiert.
Beispiel Multicastdelegaten: Sofern ein Delegate einen Rückgabewert hat, und mehrere Methoden angehängt wurden, wird nur der Rückgabewert der zuletzt aufgerufenen Methode ausgewertet. Wer sagt mir denn nun, welche dies sein wird? In der Regel geht man davon aus, dass es die ist, die zuletzt angehängt wurde.
Das steht aber nirgends. Es steht auch nirgends, dass - obwohl das in .NET bislang so sein mag - es morgen noch so sein muss, oder dass es auf einer anderen Plattform nicht anders sein könnte.
Ich finde es gefährlich, pauschal davon auszugehen, dass foreach sich immer so verhält, wie es das heute tut - eben weil dies nirgends festgelegt ist, wie ein Enumerator eine Collection zu durchlaufen hat.
Wenn sich Microsoft überlegt, dass aus welchen Gründen auch immer ab .NET 4.0 Enumeratoren genau andersherum laufen, dann widerspricht das nicht dem bisherigen Sprachstandard, trotzdem fallen zig Anwendungen auf die Nase, weil sie eben davon ausgehen, dass das schon immer so sein wird.
Kurzum: Ja, foreach ist deterministisch, sofern der zu Grunde liegende Enumerator deterministisch ist. Aber niemand sagt mir, dass dies immer und unter allen Umständen so sein wird, und das ist auch nicht durch die Sprachspezifikation abgedeckt.
Viele Grüße,
Golo
Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden
Hallo Golo Roden,
Wenn sich Microsoft überlegt, dass aus welchen Gründen auch immer ab .NET 4.0 Enumeratoren genau andersherum laufen, dann widerspricht das nicht dem bisherigen Sprachstandard, trotzdem fallen zig Anwendungen auf die Nase, weil sie eben davon ausgehen, dass das schon immer so sein wird.
genau deshalb wird MS das nie ändern. 🙂 Und genau deshalb würde ich eine bestimmte Enumerationsreihenfolge als für die Zukunft unveränderlich ansehen.
Insofern schlägt insgesamt wieder zu, was ich schon oben zu Kartoffel sagte:
im Grunde hast du Recht. Rein pragmatisch gesehen spricht aber m.E. nichts gegen diese Annahme [dass für eine bestimmte Collection die Aufzählungsreihenfolge definiert, deterministisch und unveränderlich ist]. Sie macht das Leben leichter und die Wahrscheinlichkeit, dass sie nicht gilt, ist in meinen Augen wie gesagt nur theoretischer Natur.
herbivore
Hallo,
ja, pragmatisch gesehen würde ich das auch so stehen lassen - aber eben mit dem Bewusstsein, dass es "nur" pragmatisch ist.
Viele Grüße,
Golo
Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden