Speicherverbrauch Rekursion

Hallo Leute,

ich mach gerade bisschen Memoryprofiler mit VS2012:)
Und da is mir aufgefallen, dass folgende Rekursion rel. viel speicher frist:

public IEnumerable<object> GetFlatChildrenOfType(Type type)
		{
			return _children
				.Where(it => type.IsAssignableFrom(it.GetType()))
				.Cast<object>()
				.Concat(_children
					.SelectMany(it => it.GetFlatChildrenOfType(type)));
		}

Jetzt mal allg. gefragt, wie könnte ich diese LINQ anweisung speichersparender machen? geht das überhaupt

Grüße

Rekursives SelectMany() sollte man immer vermeiden, das hat miserable Speicher- und Performancecharakteristik. Vgl. die Erörterung in [1] (da gehts um rekursive Iteratoren, aber das Problem ist dasselbe, weil SelectMany() mit Iteratoren implementiert ist).

Du kannst dir eine Hilfsfunktion wie folgt bauen:

public static class EnumerableHelper
{
    public static IEnumerable<T> FlattenRecursive<T>(T item, Func<T, IEnumerable<T>> subitemSelector)
    {
        return Flatten(new[] { item }, subitemSelector);
    }
    public static IEnumerable<T> FlattenRecursive<T>(IEnumerable<T> items, Func<T, IEnumerable<T>> subitemSelector)
    {
        // TODO: implement
    }
}

Das wäre eine prima Übung für eine Einstiegsvorlesung in Algorithmen und Datenstrukturen Bonuspunkte gibt es, wenn man die gewünschte Rekursionsabfolge wählen kann:

public enum TreeRecursionMode
{
    DepthFirst,
    BreadthFirst
}

Am leichtesten ist die Implementation übrigens in F#, weil du da yield! benutzen kannst, was dir genau diese Arbeit abnimmt. In C# mußt du von Hand einen Stack von Enumeratoren verwalten.

Wenn du über FlattenRecursive() verfügst, kannst du deine Funktion so implementieren:

public IEnumerable<object> GetFlatChildrenOfType(Type type)
{
    return EnumerableHelper.FlattenRecursive(this,
        obj => obj._children.Where(child => type.IsAssignableFrom(child.GetType()));
}

Wie du übrigens siehst, ist das Cast<object>() ist überflüssig, weil IEnumerable<T> kovariant in T ist. Überhaupt wird deine Funktion viel schöner, wenn du sie generisch machst:

public IEnumerable<T> GetFlatChildrenOfType<T>()
{
    return EnumerableHelper.FlattenRecursive(this, obj => obj._children.OfType<T>());
}

[1] http://blogs.msdn.com/b/ericlippert/archive/2007/12/19/immutability-in-c-part-seven-more-on-binary-trees.aspx

Danke für deine erleuterungen,

die Funktion würde ich gerne generisch machen, aber die schnittstelle sieht leider die variatne mit dem Typ argument vor!

In C# kanst du doch auch "yield return" machen!?

Dannn profile ich mal deine implementation:)

NullBockException schrieb:

In C# kanst du doch auch "yield return" machen!?

Ja. Und?

NullBockException schrieb:

Dannn profile ich mal deine implementation:)

Meine Implementation kennst du doch gar nicht.

Meine Implementation kennst du doch gar nicht.

Deinen Helper!

Ja. Und?

weil du von F# geredet hast..

audacia

NullBockException schrieb:

Meine Implementation kennst du doch gar nicht.

Deinen Helper!

Dir ist nicht aufgefallen, daß da "TODO: implement" vermerkt ist?

Die Funktion ist nicht ganz trivial, aber wenn du ein bißchen nachdenkst, kommst du bestimmt selbst drauf, wie man die baut. Den entscheidenden Hinweis (Enumerator-Stack) habe ich dir schon gegeben.

NullBockException schrieb:

Ja. Und?

weil du von F# geredet hast..

Achso. yield return in C# entspricht yield in F#, aber yield! ist ein bißchen anders, das entspricht dem hypothetischen yield foreach [1], das es in C# leider noch nicht gibt.

[1] http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx

Dir ist nicht aufgefallen, daß da "TODO: implement" vermerkt ist?

Die Funktion ist nicht ganz trivial, aber wenn du ein bißchen nachdenkst, kommst du bestimmt selbst drauf, wie man die baut. Den entscheidenden Hinweis (Enumerator-Stack) habe ich dir schon gegeben.

Dein Pattern .. ja hab ich bemerkt:)

Bist du Mathematiker??

Im dichten Nebel verliert ein Ballonfahrer die Orientierung. Er lässt seinen Ballon langsam ab, bis er am Boden einen Menschen sieht, und ruft herab: "Wo bin ich hier?" Daraufhin grübelt der Passant eine Weile und antwortet: "Im Ballon!"

Er überlegt lange.
Seine Antwort ist absolut korrekt.
Seine Aussage ist zu nichts zu gebrauchen.

:p kleiner scherz

Selber Schuld wenn du C# verwendest (auch ein kleiner Scherz).

ich denke das problem hat nix mit der sprache zu tun^^