Laufzeitverhalten

[lilith2k3]

Hi Leute,

habe hier ein etwas kniffelges Problemchen ...

Zum Rahmen:

Ich beziehe zwei Listen an Daten aus einer Datenbank. In der ersten Liste befinden sich eine nicht näher bezifferte Anzahl an Projekten. In der Zweiten Liste befinden sich dazugehörige Waren(hier "Typen" genannt).

Was ich gern für die Ausgabe erreichen würde, wäre eine Verknüpfung der Projekte mit den dazugehörigen Typen.

Was ich mir überlegt habe:

List<Project> ProjectsList;  // enthält eine sortierte Liste der Projekte (wichtig für die Ausgabe


List<Type> TypesList;


Dictionary<ProjectID, List<Type>> ProjectTypes;

So, daß ich nachher bei der Ausgabe nur noch ein

foreach(Projects item in ProjectsList)

abarbeiten lassen müsste und (Dank Dictionary) per ProjectID als Schlüssel erhielte ich dann die Liste der Types als value zurückgegeben. Mein Problem: Um allerdings zu wissen, welche Typen welchen Projekten zugeordnet sind, muß ich zum einen über alle Projekte iterieren und zum anderen über alle Typen. Möglichkeit 1:

foreach (Project item in ProjectsList)

{

    foreach (Type item in TypesList)

    {}

}

Wenig Code, leicht verständlich, aber "langsam". Schneller wäre in meinen Augen ... Möglichkeit 2: Die äußere foreach-Schleife bleibt bestehen, allerdings lösche ich nach jeder Übereinstimmung ein Element aus der TypesList - erhalte dann aber ein Problem, daß foreach das nicht mag. Das ließe sich mit einer while-Schleife

while(TypesList.Count>0)

{

   ...

}

innerhalb derer dann jeweils die TypesList in ein Array umgewandelt wird, das ich dann mit einer For-Schleife durchlaufen könnte. Innerhalb der For-Schleife würden bei Übereinstimmung ("Type gehört zu Projekt") dann die Typen aus der Liste gelöscht.

Führt aber zu mindestens doppelt so langem Code und die Frage ist, ob das Laufzeitverhalten dadurch wirklich verbessert werden würde.

(Falls jemand noch eine andere Idee zur Umsetzung haben sollte, wäre ich ebenfalls aufgeschlossen)

Vielen Dank für die Hilfe/Vorschläge :]

Bearbeitet 31. März 2010 von lilith2k3

[flashpixx]

Wäre nicht der Ansatz in der Datenbank sinnvoller?

D.h. Du lässt Dir die Verknüpfung der Daten z.B. als Join direkt von der DB liefern

Egal welchen der beiden Algorithmen Du verwendest, es bleibt ein O(cn^2) Algorithmus, da Du zwei geschachtelte Schleifen hast, die über die Daten iterieren. Du veränderst lediglich den konstanten Faktor c. Es bleibt aber immer noch ein Algorithmus mit quadratischer Laufzeit.

[lilith2k3]

Du veränderst lediglich den konstanten Faktor c

Was ja schonmal etwas wäre

Das Problem ist, daß ich nicht per SQL direkt auf die Daten zugreifen kann...

[flashpixx]

Was ja schonmal etwas wäre

O(cn^2) bei 10 Datensätzen hast Du ne Laufzeit von 100 Zeitschritten, bei 100 => 10000 usw.

Das Problem ist, daß ich nicht per SQL direkt auf die Daten zugreifen kann...

Der Ansatz ist aber die Datenbank, denn dafür ist sie ja gemacht, dass sie so etwas effizient durchführt. Du wirst mit dem iterativen Vorgehen immer schlechte Laufzeiten haben.

[lilith2k3]

Schon klar, daß die Konstante nur eine marginale Rolle spielt, wenn n->oo geht :]

Mal gucken, wie ich das anders gemanaged bekomme. Zumindest schonmal vielen Dank!

[flashpixx]

Kannst Du die Daten vorsortieren, also HashMap, Baum oder sortierte Liste usw. Damit hast Du zwar bei der Einfügenoperation etwas mehr Aufwand, aber Du musst dann nie die komplette Liste durchlaufen.

[TDM]

Wenn es eine 1:m-Beziehung ist, kannst du auch Artikel aus der Type-List raushauen, sobald du sie einmal in einem Projekt gefunden hast.

Würde sicher auch bissl Performance bringen.

[lilith2k3]

Wenn es eine 1:m-Beziehung ist, kannst du auch Artikel aus der Type-List raushauen, sobald du sie einmal in einem Projekt gefunden hast.

Würde sicher auch bissl Performance bringen.

Ja, es ist eine 1:n Beziehung (1 Projekt : n Typen). Und genau das ist ja mein zweites Verfahren *g* das eine ist halt eben (Projekte * Typen) als Laufzeit und das andere eben nur (.5*(Typen^2 + Typen)) als Laufzeit. Und das kann schon Unterschiede mit sich bringen ... :]

Tja, eleganter wäre das Ganze natürlich, wenn ich das datenbankseitig erledigen könnte. Aber da liegt (derzeit) mein grundlegendes Problem ...

Ich arbeite mit Microsoft CRM und mir sind nur Abfragen per Webservice gestattet; als ReturnType erhalte ich eine sog. BusinessEntityCollection. Über die kann ich bequem per foreach iterieren und caste dann eine BusinessEntity in eine DynamicEntity, die ich dann mit DynamicEntity.Contains() nach den entsprechenden Attributen abfragen kann; bzw. mit DynamicEntity[iNDEXER] den Wert des entsprechenden Attributs erhalte.

Soweit so gut, wenn ich die Abfrage auf eine Entity beschränkt habe.

Wie man allerdings einen Join per Webservice realisieren kann, bzw. wie ich dann mit der Ergebnismenge weiterverfahren kann, weiß ich nicht.

Ich muß mir wohl das SDK ein wenig näher zu Gemüte führen...

[lilith2k3]

Falls jemand ähnliche Probleme haben sollte: die Lösung ist "Fetch-XML". Damit hat man ein wenig mehr Freiheiten.

[TDM]

Da man ja im Alkoholrausch bekanntlich am Kreativsten ist:

Hat Type eigentlich eine Property namens ProjectID bzw. Project eine Property namens ID?

Theoretisch könnte man nämlich flashpixx' Idee:

Der Ansatz ist aber die Datenbank, denn dafür ist sie ja gemacht, dass sie so etwas effizient durchführt.

nachbilden. Ich sag nur Linq usw. :beagolisc