Elegante Lösung gesucht: Verschiedene konsekutive Elemente gesucht.
Ich möchte aus einer Sequence mehrfach hintereinander vorkommende gleiche Elemente streichen. Also 1,2,3,3,2 soll zu 1,2,3,2 werden.
Gesucht ist eine möglichst elegante Lösung.
Bisher habe ich:
public static IEnumerable<T> SelectDistinctConsecutive1<T>(this IEnumerable<T> items) {
using (IEnumerator<T> enumerator = items.GetEnumerator()) {
T lastValue = default(T);
if (enumerator.MoveNext()) {
lastValue = enumerator.Current;
yield return lastValue;
}
while (enumerator.MoveNext()) {
if (!enumerator.Current.Equals(lastValue)) {
lastValue = enumerator.Current;
yield return lastValue;
}
}
}
}
public static IEnumerable<T> SelectDistinctConsecutive2<T>(this IEnumerable<T> items) {
bool isFirst = true;
T lastValue = default(T);
foreach (T item in items) {
if (isFirst || !item.Equals(lastValue)) {
isFirst = false;
lastValue = item;
yield return item;
}
}
}
public static void Main() {
int[] arr = { 1, 2, 2, 3, 3, 3, 3, 2, 3, 3, 1 };
foreach (int i in arr.SelectDistinctConsecutive1()) {
Console.Write(i);
}
Console.WriteLine();
foreach (int i in arr.SelectDistinctConsecutive2()) {
Console.Write(i);
}
Console.WriteLine();
}
An Lösung 1 gefällt mir nicht, dass an zwei Stellen MoveNext aufgerufen wird.
An Lösung 2 gefällt mir der Flag "isFirst" nicht.
Irgendwie muss für das erste Element immer eine Sonderbehandlung her....
Kennt jemand eine Elegante Lösung?
Viele Grüße,
Uwe
PS: Mir ist schon klar, dass das dann in einer Methode verschwindet und nie wieder angefasst wird. Aber irgendwie hab ich das Gefühl "Das muss doch schöner gehen".
Hallo Uwe81,
wenn es kein Element gibt, das sicher nicht (als erstes Element) in der Liste vorkommt und das du deshalb zur Initialisierung von lastValue verwenden kannst, ohne dass dadurch fälschlich das erste Element gelöscht wird wird, wirst du wohl einen der beiden Tode sterben müssen. Um eine Sonderbehandlung für das erste Element kommst du dann m.E. nicht herum.
EDIT: Etwas einfacher geht es ab .NET 3.5 allerdings doch noch:
public static IEnumerable<T> SelectDistinctConsecutive1<T>(this IEnumerable<T> items) {
T lastValue = items.FirstOrDefault ();
yield return lastValue;
foreach (T item in items) {
if (!item.Equals(lastValue)) {
lastValue = item;
yield return item;
}
}
}
}
BTW: Beachte, dass es bei knallt, wenn einer der items null ist.
EDIT: Nee, die Lösung ist es auch noch nicht ganz, weil dann bei einer leeren Enummeration trotzdem ein Element zurückgegeben werden würde. Man müsste also noch mit IEnumerable<T>Any fragen, ob es überhaupt Elemente gibt und wenn nicht yield break aufrufen. Dann sind aber die Einsparungen schon wieder zunichte.
herbivore
Naja, konzeptionell etwas schöner aber auch nicht wirklich gut finde ich mittlerweile folgende Idee:
- Gehe auf das erste Element (wenn existent)
- Gebe den Aktuellen wert zurück
- Überspringe gleiche werte, wenn weiteres Element dann beginne bei 2, sonst Ende.
In Code gegossen ist das
public static IEnumerable<T> SelectDistinctConsecutive<T>(this IEnumerable<T> items) {
using (IEnumerator<T> enumerator = items.GetEnumerator()) {
if (enumerator.MoveNext()){
do {
yield return enumerator.Current;
} while (SkipEqualToCurrent<T>(enumerator));
}
}
}
public static bool SkipEqualToCurrent<T>(this IEnumerator<T> enumerator) {
T value = enumerator.Current;
while (enumerator.MoveNext()) {
if (!enumerator.Current.Equals(value)) {
return true;
}
}
return false;
}
Hallo Uwe81,
wie wäre es mit:
public static IEnumerable<T> SelectDistinctConsecutive<T>(this IEnumerable<T> items) {
using (IEnumerator<T> enumerator = items.GetEnumerator()) {
bool furtherValues = enumerator.MoveNext();
while (furtherValues) {
T lastValue = enumerator.Current;
yield return lastValue;
do {
furtherValues = enumerator.MoveNext();
} while (furtherValues && enumerator.Current.Equals(lastValue));
}
}
}
Zwar werden sowohl MoveNext als auch Current an je zwei Stellen benutzt, aber das ist bei deinem letzte Vorschlag nicht anders. Dafür ist mein Code um einiges kürzer und es werden netterweise keine Methoden mit Seiteneffekt in if- oder while-Bedingungen verwendet. 😃
BTW: In deinen beiden Versionen tut es ein einfaches break. Es ist nicht erforderlich, yield break zu verwenden. natürlich kann man darüber streiten, was von beidem günstiger ist.
herbivore
Hallo,
herbivores letzte Version ist tatsächlich ziemlich kurz. Einige Details sind aber nicht optimal: z.B. wird furtherValues bei jedem Schleifendurchlauf 2x hintereinander geprüft, obwohl sich der Wert dazwischen nicht ändern kann: einmal im letzten while(...) und direkt danach (falls die Werte ungleich sind) im ersten while(furtherValues). Auch finde ich die geschachtelte Schleife etwas kompliziert zu verstehen.
Die erste Version von Uwe81 finde ich sehr leicht zu verstehen, wobei das if auch den while-Block umschließen könnte, da die Bedingung im while nie wahr wird, wenn das erste MoveNext() false zurückgibt.
Man kann natürlich auch die Schachtelung reduzieren und dadurch die verschiedenen Fälle (leere Enumeration, erstes Element, Rest) auch noch explizit in der Struktur wiedergeben:
public static IEnumerable<T> DistinctConsecutive<T>(this IEnumerable<T> items)
{
using (var enumerator = items.GetEnumerator())
{
// leere Enumeration abhandeln
if (!enumerator.MoveNext())
{
yield break;
}
// erstes Element abhandeln
var previous = enumerator.Current;
yield return previous;
// Rest
while (enumerator.MoveNext())
{
var current = enumerator.Current;
if (!current.Equals(previous))
{
yield return current;
previous = current;
}
}
}
}
Nicht, dass das notgedrungen besser ist als die Version von Uwe81, es wird nur einiges expliziter gemacht.
Und hier noch eine Version, die NICHT das erste Element speziell behandelt (zumindest nicht explizit):
public static IEnumerable<T> DistinctConsecutive<T>(this IEnumerable<T> items)
{
using (var enumerator = items.GetEnumerator())
{
var returnCurrent = enumerator.MoveNext();
var lastReturnedValue = default(T);
while(true)
{
if (returnCurrent)
{
lastReturnedValue = enumerator.Current;
yield return lastReturnedValue;
}
if (!enumerator.MoveNext())
{
yield break;
}
returnCurrent = !lastReturnedValue.Equals(enumerator.Current);
}
}
}
Einziger Wermutstropfen hier: MoveNext wird für leere Enumerationen 2x hintereinander aufgerufen, beide mit false als Ergebnis. Das ist zwar erlaubt, aber nicht 100% elegant.
Aber wie gesagt, die erste Version von Uwe81 finde ich gut.
Grüße,
Andre
edit: aus do{}while(true) while(true){} gemacht.
Hallo VizOne,
z.B. wird furtherValues bei jedem Schleifendurchlauf 2x hintereinander geprüft, obwohl sich der Wert dazwischen nicht ändern kann
es werden zwei verschiedene Bedingungen geprüft. Einmal nur furtherValues und einmal furtherValues und die Gleichheit zweier aufeinanderfolgender Elemente. Insofern ist es keine doppelte Prüfung, sondern eben genau die Unterscheidung, ob die innere Schleife wegen der einen oder der anderen Bedingung verlassen wurde. Ich finde das unter den schwierigen Rahmenbedingungen ziemlich elegant.
Auch finde ich die geschachtelte Schleife etwas kompliziert zu verstehen.
Hm, die beiden Schleifen haben doch jeweils eine klar erkennbare Aufgabe. Die äußerere Schleife durchläuft alle unterschiedlichen Elemente und die innere die nicht unterschiedlichen. Das ist doch alles andere als kompliziert.
herbivore
es werden zwei verschiedene Bedingungen geprüft. Einmal nur furtherValues und einmal furtherValues und die Gleichheit zweier aufeinanderfolgender Elemente.
Beide Prüfungen werden direkt nacheinander ausgeführt, falls furtherValues false wird oder sobald das aktuelle Element ungleich des vorherigen ist. In beiden Prüfungen wird der Wahrheitsgehalt von furtherValues überprüft, auch wenn sich dieser zwischen den beiden Prüfungen nicht ändern kann. Ich sage ja nicht, dass das dramatisch ist und ein System zur Laufzeit zu Fall bringt, es ist nur nicht optimal.
Hallo VizOne,
das es nicht optimal ist, bedeutet ja, dass es eine bessere Möglichkeit geben muss. Wie würdest du denn in meiner Programmstruktur die doppelte Prüfung vermeiden?
herbivore
Zunächst einmal gilt ja folgende Überlegung: wenn MoveNext() false zurückgibt, kann die gesamte Enumeration abgebrochen werden, also:
public static IEnumerable<T> SelectDistinctConsecutive<T>(this IEnumerable<T> items)
{
using (IEnumerator<T> enumerator = items.GetEnumerator())
{
bool furtherValues = enumerator.MoveNext();
while (furtherValues)
{
T lastValue = enumerator.Current;
yield return lastValue;
do
{
furtherValues = enumerator.MoveNext();
// neu:
if(!furtherValues)
{
yield break;
}
} while (enumerator.Current.Equals(lastValue));
}
}
}
Jetzt besteht das Problem, dass das erste while(furtherValues) ab dem zweiten Durchlauf nicht mehr false sein kann, da sonst die Enumeration bereits beendet worden wäre. Also probieren wir:
public static IEnumerable<T> SelectDistinctConsecutive<T>(this IEnumerable<T> items)
{
using (IEnumerator<T> enumerator = items.GetEnumerator())
{
bool furtherValues = enumerator.MoveNext();
while (true)
{
T lastValue = enumerator.Current;
yield return lastValue;
do
{
furtherValues = enumerator.MoveNext();
if(!furtherValues)
{
yield break;
}
} while (enumerator.Current.Equals(lastValue));
}
}
}
Das kann allerdings nicht mit leeren Enumerationen umgehen, also prüfen wir, dass zumindest ein Element verfügbar ist:
public static IEnumerable<T> SelectDistinctConsecutive<T>(this IEnumerable<T> items)
{
using (IEnumerator<T> enumerator = items.GetEnumerator())
{
bool furtherValues = enumerator.MoveNext();
if (furtherValues)
{
while (true)
{
T lastValue = enumerator.Current;
yield return lastValue;
do
{
furtherValues = enumerator.MoveNext();
if (!furtherValues)
{
yield break;
}
}
while (enumerator.Current.Equals(lastValue));
}
}
}
}
Jetzt läuft es wieder, aber die Verwendung der furtherValues Variable hat kaum noch Sinn, also wird sie geinlined:
public static IEnumerable<T> SelectDistinctConsecutive<T>(this IEnumerable<T> items)
{
using (IEnumerator<T> enumerator = items.GetEnumerator())
{
if (enumerator.MoveNext())
{
while (true)
{
T lastValue = enumerator.Current;
yield return lastValue;
do
{
if (!enumerator.MoveNext())
{
yield break;
}
}
while (enumerator.Current.Equals(lastValue));
}
}
}
}
Das ganze ist jetzt leider durch die doppelte Schleife stark geschachtelt, weswegen ich wieder auf meinen Vorschlag mit der einfachen Schleife verweise. Die Idee dahinter: entscheide pro Element, ob es zurückgegeben wird. Die Kondition für das erste Element ist der erfolgreiche Aufruf von MoveNext, die Kondition für alle weiteren ist die Ungleichheit zum Vorgänger. Prüfe nach jedem Element, ob es weitere gibt, ansonsten beende die Enumeration.
Hallo VizOne,
basierend auf deinem letzten Vorschlag, könnte ich mit folgendem gut leben:
public static IEnumerable<T> SelectDistinctConsecutive<T>(this IEnumerable<T> items) {
using (IEnumerator<T> enumerator = items.GetEnumerator()) {
if (!enumerator.MoveNext()) { yield break; }
for (;;) {
T lastValue = enumerator.Current;
yield return lastValue;
do {
if (!enumerator.MoveNext()) { yield break; }
} while (enumerator.Current.Equals(lastValue));
}
}
}
Das ist sogar noch eine Zeile kürzer als mein Code oben und an keiner Stelle tiefer geschachtelt (gemeint sind die Einrückungsebenen). Wobei dann wieder die Funktionen mit Nebeneffekt direkt in den Bedingungen stehen. Ich fand ja bei meinem vorigen Vorschlag gerade so schön, dass das dort nicht der Fall ist.
Wobei es ohnehin eine ziemlich akademisch abgehobene Diskussion ist. 😃 Das ist zwar nicht produktiv, macht aber Spaß!
herbivore