MrTiger

Hallo Ich habe ein Problem. Und zwar habe ich n Vektoren und möchte nun alle möglichen Kombinationen der Vektoren bis zum Grad 3 erstellen. Ich kann das am besten an einem Beispiel erklären, nehmen wir an ich hätte 2 Vektoren, x und y und ich möchte alle möglichen Kombinationen bis zum Grad 3 erstellen, dann würde ich folgende Monome erhalten: x y x.^2 y.^2 x.^3 y.^3 x*y x*y.^2 x.^2*y Nun habe ich aber n Vektoren und möchte alle möglichen Terme bis zum Grad 3 erstellen. Ich sehe gerade nicht wie ich das rekursiv lösen könnte. Kann mir da jemand helfen?

Hallo Ich habe ein kleines Anliegen bezüglich Objekt orientierten und relationalen (SQL etc.) Datenmodellen. Ich überlege mir gerade ein Beispiel wo das OO Datenmodell besser geeignet ist als das relationale und ein anderes Beispiel wo das relationale besser geeignet ist, aber ich komme irgendwie auf keinen grünen Zweig. Fallen vielleicht jemandem gerade solche Beispiele ein? Die Hauptanwendung von Objekt Datenbanken ist ja, Programmiersprachen persistent zu machen, d.h. Objekte zu konservieren. Was gibt es sonst noch für Anwendungen? Also im Sinne von Generalisierungen.

Ich danke euch. Ich werde das einmal ausprobieren. Kann man damit auch ordered Tests "beleuchten"? Das Problem ist eben, dass ich ordered tests habe, wenn die tests nicht als ordered ausgeführt werden, schlagen viele fehl. Ich muss allerdings die code coverage abliefern.

Hallo Ich habe gerade ein Projekt in C# abgeschlossen. Zum testen habe ich einige ordered unit tests (in Visual Studio) geschrieben. Nun ist es so, dass ich noch die code coverage bestimmen muss. Wenn ich zuerst die ordered tests ausführe und dannach in Visual Studio die code coverage results anzeigen lasse, dann erscheint die Meldung "Cannot find any coverage data (.coverage or .coveragexml) files. Check test run details for possible errors". Gibt es irgendeine Möglichkeit die code coverage anhand von den ordered unit tests zu bestimmen? Ich darf auch ein externes Tool benutzen, allerdings darf ich nichts mehr am code, auch nicht am test code verändern.

Ich habe noch ein kleines zusätzliches Problem. Ich würde gerne einen timestamp für Dateien und Ordner einführen. Man könnte ja einen timestamp wie folgt bekommen. DateTime CurrentDate; CurrentDate = Convert.ToDateTime(DateTime.Now.ToString("yyyyMMddHHmmssffff")); Das Problem ist nun, dass ich die timestamps vergleichen möchte. Müsste ich da dann nach integer konvertieren? Oder wie macht man das?

Ok, langsam ist es klarer. Wie kann ich den Hash über einen Pfad + Datei bilden? Also ich mein jetzt im konkreten Fall von C#. Ist eine etwas blöde Frage, aber ich bin da gerade etwas verwirrt und habe mit Hashes noch nicht so Erfahrungen. Ja, genau das. Wie lässt sich das denn in C# verwirklichen? Eine HashMap wäre ja bereits als Datenstruktur vorhanden.

Ich danke euch. Du meinst ich solle für jedes Blatt einen Hashwert berechnen? Wobei ein Blatt ja ein leerer Ordner oder eine Datei sein kann. Dann muss ich aber ja alle Hashwerte der Blätter des einten Baumes gegen alle Hashwerte der Blätter des anderen Baumes vergleichen. Könnte ich nicht einfach beide Dateisystem rekursiv durchlaufen und vergleichen? Ich möchte die Dateisysteme als Snapshot vergleichen, d.h. feststellen welche Ordner und Dateien im einten Dateisystem vorhanden sind aber nicht im anderen.

Hallo Ich habe zwei Dateisystem, welche jeweils Order und Dateien enthalten. Ich möchte nun beide Dateisysteme als Bäume darstellen damit ich dann die Differenz bilden kann und somit feststellen kann welche Dateien und Ordner unterschiedlich sind bzw. im einen Dateisystem vorhanden sind aber nicht im anderen. Ich habe das Dateisystem selber entworfen, hier ist es nur von Bedeutung, dass wir eine hierarichsche Struktur von Ordner und Dateien haben, welche jeweils einen Namen haben. Was für einen Baum würdet ihr da verwenden? Einen normalen n-ary tree? Wie kann solch ein Baum aufgebaut werden, so dass er dann die Ordner- und Filestruktur widerspiegelt? Also wie das theoretisch bei einem n-ary tree geht weiss ich, also die inneren Knoten sind Ordner, der jeweilige Inhalt des Ordners sind dann Kinder etc., ich habe aber mit der Implementation etwas Mühe. Wenn ich nun beide Bäume habe dann könnte ich ja einen normalen tree Diff Algorithmus anwenden. Ich habe bereits früher einmal einen Diff Algorithmus für Bäume implementiert (Zhang & Shasha’s Algorithmus), allerdings sind diese Algorithmen für grosse Bäume sehr langsam. Da ein Dateisystem aber sehr viele Ordner und Dateien enthalten kann und somit die Bäume sehr gross werden können und die Differenz allerdings trotzdem schnell berechnet werden muss, wäre dies vielleicht nicht so geeignet. Was könnte man denn sonst noch anwenden um die Differenz zu bestimmen oder sollte ich gar keinen Baum verwenden? Ich werde es übrigens in C# implementieren, wenn da vielleicht jemand direkt eine library oder code kennt, den ich verwenden oder als Inspiration brauchen könnte, wäre mir sehr gehollfen. Vielen Dank.

Also wenn ich ja eine höhere Order für den B-Tree wähle, z.B. 100, dann reduziert sich ja die Tiefe und jeder Knoten hält eine grössere Anzahl keys. Trifft es zu, dass bei vielen files im virtual file system die order eher höher gewählt werden sollte und bei wenigen files eher eine kleinere order? Es wird jeder filename indexiert. Und was ist genau eine höhere order? Z.B. 100? By the way, die order eines B-Baums beschreibt die minimale Anzahl keys in einem Knoten.

So ich konnte den B-Baum jetzt implementieren, sogar auch die Delete Methode. Nun bin ich mir aber unschlüssig welche Ordnung ich für den Baum wählen soll. Die Ordnung gibt ja die minimale Anzahl keys in einem Knoten an. Was für eine Ordnung würdet ihr da wählen wenn der B-Baum als Index für ein virtual file system gebraucht wird? Vielleicht 2 oder 3 oder doch höher?

Ich brauche v.a. Code oder Pesudocode für die delete methode inklusive Rotatonen etc. des B-Baums. Den Rest sollte ich hinbekommen.

So ich habe mich jetzt entschieden einen B-Baum zu implementieren. Ich habe nun Code gesucht, welcher einen B-Baum oder B+-Baum implementiert. Am besten in C# aber auch Java ist ok. Ich habe bei Google einige Implementationen gefunden, z.B. http://wwwiti.cs.uni-magdeburg.de/iti_db/algoj/code/algoj/kap14/BTree.java BTree.java - my-alogorithm-implementation - my-algorithm-implementation - Google Project Hosting BTree.java Sowas stelle ich mir etwa vor, also keine ganze extrem umfangreiche library, sondern einfach ein kurzes Stück Code, welches einen B-tree repräsentiert, also die Nodes, Operationen wie Einfügen, Löschen, Rebalancieren, Suchen etc. Bei den obigen code snippets fehlt eine delete Methode, das wäre noch wichtig. Kann mir da vielleicht jemand weiterhelfen bzw. kennt so ein code snippet? Ich würde so ein code snippet gerne als Vorlage bzw. Anregung benutzen.

Du hast natürlich recht, da habe ich wohl etwas durcheinander gebracht. Könntest du vielleicht ein kleines Beispiel machen für einen B-Baum Index auf files? Ich habe gerade keine Ahnung wie ich das machen soll bzw. was die Knoten für Werte halten sollen. Es soll nur nach den Namen von Dateien gesucht werden, also z.B. "foo.txt" oder eventuell auch partielle Namen also nur "fo" oder "foo". Eventuell soll auch noch nach Verzeichnisnamen gesucht werden. Ist sowas auch im gleichen Baum möglich oder bräuchte ich da einen separaten Baum für die Verzeichnisnamen? Ja, sowas in der Art ist in Form eines streams vorhanden.

Es geht um ein virtual file system, wobei eine virtual disk ein .zip file umfasst. In einer virtual disk, d.h. in dem .zip file, können dann vom Host Dateien importiert werden oder auch neue Dateien erzeugt werden etc. Das .zip File ist in sich hierarchisch organisiert, mit Verzeichnissen, Unterverzeichnissen, Dateien etc., so wie das host file system. Nun möchte ich für jede virtaul disk, d.h. für jedes .zip file einen Index erstellen. Da kommen entweder ein B-Baum oder eine sortedList oder Dictionary in Frage. Bei einem B-Baum würde ich den Index wie folgt sehen. Die inneren Knoten speichern Verzeichnissnamen bzw. Links zu Verzeichnissen und die Blätter Filenamen bzw. Links zu Files. Ich stelle mir das so vor: Wenn man eine Datei mit folgendem Pfad im .zip file hat C:\folder1\file1 dann hat man einen root Knoten mit label "C", der auf das C Verzeichnis zeigt, dann hat man einen Kindknoten mit Label "folder1" und dieser hat einen Kindknoten mit Label "file1". Oder sehe ich das falsch? Eine SortedList bzw. Dictionary ist ja nicht hierarschisch und dann würde das obige Verfahren nicht gehen. Richtig? Weiterhin brauche ich von den Indexes ja irgendeinen Link in das .zip File, d.h. in die virtual Disk. D.h. das obige Beispiel C:\folder1\file1 ist ja im .zip file hierarchisch vorhanden. Die Indexeintrage "C", "folger1" und "file1" sollten ja dann an die entsprechenden Stellen im .zip file zeigen. Wie kann ich das realisieren? der B-Baum soll nicht dazu da sein um die Daten zu speichern, sondern als Verweis auf die Daten, also für effizientes Suchen z.B. Die Datenmengen sind nicht so gross, d.h. die einzelnen virtual disks werden nicht allzu gross. Das ganze soll einfach als programming experience sein. Klar könnte man auch ein Verzeichnis nehmen, allerdings ist ja ein Zip z.B. schon kompromiert, d.h. man spart Speicherplatz.

Es geht um ein virtual file system (ein rudimentäres) wobei eine virtual disk einem .zip file entspricht. D.h. in dem .zip file sind dann die ganzen Verzeichniss und Ordner hierarchisch gespeichert. Für jede virtual disk möchte ich nun einen Index erstellen. Es sollen damit dann Verzeichniss und Files gesucht werden und wenn man natürlich ein neues File vom host file system in die virtual disk importiert muss der Index aktualisiert werden. Ebenso beim löschen eines Files oder Verzeichnisses aus der virtual disk. Wenn ich nun in den Knoten die Verzeichnisse und Files speichern würde, wäre das ja redundant zum .zip file, d.h. ich brauche doch in den Knoten zwar die Namen der Verzeichnisse und Files, aber dann auch irgendeinen Link in das .zip File. Oder sehe ich das falsch?

Ich danke euch vielmals. Ich muss das jetzt vielleicht etwas spezifizieren. Es geht um ein virtual file system und ich möchte dazu eine Indexstruktur erstellen. D.h. die Dateien im file system sollen indiziert werden. Ich sehe da jetzt zwei Möglichkeiten: 1. Einen B-Baum verwenden. Da ist dann halt das Problem, dass ich solche B-Bäume eben nur auf dem Papier kenne und nur auf dem Papier mit ihnen gearbeitet habe. Implementiert habe ich noch nie einen, daher bin ich mir über die Klassenstruktur und die Implementationsdetails unsicher. Gibt es für B-Bäume keine library? Oder gibt es vielleicht einen example code in C# welches einen B-Baum zeigt? V.a. das einfügen eines neuen Elementes in einen B-Baum stelle ich mir noch schwer zu implementieren vor wegen rebalancing etc. Was würden die inneren Knoten und die Blätter des B-Baums genau speichern? Also würden dann die inneren Knoten einfach die directory Namen speichern und diese auf den entsprechenden Ort mappen und die Blätter würden die Filenamen halten? 2. Eine SortedList oder einen Dictionary verwenden. Das wäre ja dann einfach und das einfügen, suchen etc. bereits vorhanden. Funktioniert das aber für einen Index auf einem file system? Es ist ja möglich, dass zwei Files mit dem gleichen Namen aber in unterschiedlichen directories existieren und das könnte man ja dann nicht in einer SortedList oder Dictionary speichern, da ja da keys nur einmal vorkommen dürfen. Oder würde man einfach als Indexelement direkt den ganzen Pfad speichern? Dann wüde man aber die Hierarchie verlieren. 3. Der Index soll noch persistent gemacht werden, d.h. wenn das Programm beendet wird soll der Index weiterbestehen, d.h. muss in eine Datei geschrieben werden. Wie macht man das? Könnte man z.B. das Objekt einfach serialisieren und in eine Datei schreiben und bei Gebrauch des Indexes einfach wieder deserialisieren? WPF. D.h. eine Klasse node welches ein Array von nodes hält, welches die Kindknoten repräsentiert. Dann vielleicht eine Klasse Indexer, welches das root objekt hält und zudem die Operationen. Ist das so richtig?

Hi Ich habe eine kleine Frage. Und zwar möchte ich in C# eine B-Baum Indexstruktur auf Files erstellen (also z.B. eine Liste von Filenamen). Diese Indexstruktur soll dann z.B. zum effizienten Suchen von Filenamen verwendet werden. Wie würde man so etwas in C# realisieren? Habe da leider gerade gar keine Idee. Habe nämlich noch fast keine Erfahrung in C#. Ich habe daran gedacht, die Indexstruktur in ein separates .db files zu speichern, aber wen man das so machen würde, wie würde man dises File kreeiren, verwalten etc.? Wie B-Bäume funktioneiren weiss ich, allerdings nur in der Theorie.

Hallo Ich habe hier XML Files, welche den Abstract Syntax Tree von Code darstellen. Die XML files habe ich erfolgreich in einen DOM-tree geparsed und kann diesen auch traversieren. Hier ist eine solche XML Datei: http://img217.imageshack.us/img217/8365/xmlv.jpg Diese XML Datei repräsentiert den folgenden Code (Eiffel): prune_first (n: INTEGER) do prune (n, l) end Nun möchte ich zuerst das XML File wieder in Code zurückverwandeln. Das möchte ich machen, indem ich den Baum traversiere. Zudem gibt es noch eine Visitor Klasse (Visitor Pattern), bei der man Funktionen selber impelementieren kann, die man dann bei jedem Knoten aufrufen kann. Mir ist nun aber nicht ganz klar, wie ich am besten vorgehen soll. Wie man im Beispiel sieht, sind alle Codestücke nur in Textelementen des XML Files vorhanden, ich könnte also alle Textelemente ausgeben, allerdings hätte ich da dann z.B. mit der Klammer () Probleme, da die Ausgabe dann prune()n,l anstatt von prune(n,l) wäre und zudem hätte ich dann alles auf einer Zeile und keine Einrückungen etc. Wie würdet ihr da vorgehen? Die XML files werde ich übrigens später noch kürzen, so dass wirklich nur die wichtigen Nodes übrig bleiben. Weiterhin würde ich auch gerne eine Transformation in die andere Richtung machen, also von Code (Feature = Methode oder Klasse) zu einem XML File. Man könnte da wohl einen parser generator verwenden. Wie würdet ihr das aber ohne parser generator machen oder ist das zu aufwendig? Die erste Fragen oben (Umwandlung von XML nach Code) hat jetzt hier aber gerade Priorität.

So Preorder habe ich erfolgreich hinbekommen. Das sieht bei mir wie folgt aus. Der Durchlauf ist iterativ mit einem Stack und nicht rekursiv, da mit der next Methode immer nur der nächste Knoten zurückgegeben werden soll. Nun möchte ich das genau gleiche auch noch für Postorder machen, aber das krieg ich irgendwie nicht hin. Das Problem ist halt, dass nicht immer zuerst der Vater Knoten besucht wird, wie bei Preorder, da ist es dann mit dem Stack ja ganz leicht. Könnte mir vielleicht kurz jemand den obigen Code in Postorder umwandeln? Wäre sehr lieb.

So ich habe mich jetzt in die tree-based diff algorithmen eingelesen und möchte nun den Algorithmus aus dem Paper 'The Tree-to-Tree Correction Problem' von Tai implementieren. S. 431 (bzw. S 10 im PDF) step (1), step(2) und step(3). http://www.techfak.uni-bielefeld.de/ags/pi/lehre/PatTreesWS11/tree-to-tree_tai.pdf Leider ist der nicht so ganz einfach und ich habe ziemliche Probleme. Es sind zwei Bäume vorhanden, welche in Preorder nummeriert sind (wie im Algorithmus gefordert). Zur Zeit hänge ich gerade im Step(1) des Algorithmus fest. Und zwar geht es da um folgenden Code. Wichtig ist hier noch, dass s <= u < i und t <= v < j. Es gilt preorder Nummerierung. T1 und T2 sind die zwei Bäume die "gedifft" werden sollen. |T1| und |T2| ist die Anzahl der Knoten in den Bäumen. r(...) bedeutet eine edit operaton, also das löschen, hinzufügen oder verändern eines Knotens. Der Pesudocode ist ja nun ziemlich abstrakt und nicht so leicht zu implementieren. Ich möchte zudem nicht nur die edit distance, wie im Algorithmus berechnet wird, sondern auch gleich noch das edit script dazu. Hat da vielleicht jemand einen Tipp wie ich den Algorithmus am besten umsetzen könnte? Wie gesagt, die Baumstruktur ist schon vorhanden. Insbesondere habe ich ein Problem mit Datenstruktur für E[s u i, t v j]. E[s u i, t v j] muss man doch fast als 6D Array speichern oder wie würdet ihr das machen? Das Array wäre dann leider ziemlich gross, also |T1| x |T1| x |T1| x |T2| x |T2| x |T2|. Für grössere Bäume ist die Laufzeit sehr schlecht. Die einfachste Möglichkeit wäre natürlich das Mapping auf ein 1D Array zu machen, das wäre auch sehr schnell, aber da habe ich dann das Problem dass es out of memory läuft.

Vielen Dank. Werde es mal probieren.

Hallo Ich habe ein kleines Problem mit der Baumtraversierung. Und zwar ist ein Baum vorhanden (ein DOM Tree). Alle Knoten des Baumes sind vom selben Typ XML_NODE. Der root des Baumes ist durch root: XML_NODE referenziert (Eiffel Syntax), d.h. 'root' vom Typ XML_NODE zeigt auf den root node. Die Kinder sind durch die Methode elements abrufbar, welches eine Liste mit den Kindern zurückgibt. Also z.B. root.elements. Nun möchte ich zwei Funktion 'next_preorder' und 'next_postorder' implementieren, die mir bei jedem Aufruf das nächste Element in preorder bzw. postorder Reihenfolge zurückgibt. Ich habe zwar bereits Algorithmen gefunden, die einen Baum in postorder bzw. preorder Reihenfolge durchlaufen, aber da wird eben gerade der ganze Baum durchlaufen (ich möchte nur das jeweils nächste Element) und zudem sind diese Algorithmen meisten für 2 Kinder, ich habe aber eine Liste von Kindern. Könnte da vielleicht kurz jemand mit Pseudocode (oder in Java) zu Hilfe eilen? Ich danke vielmals.

Ich habe mich jetzt schon ein wenig eingelesen und die Aufgabenstellung wurde klarer, da ich mit dem Assi gesprochen habe. Als Input für den line-based Algorithmus sollen XML files und String Objekte möglich sein, d.h. der Algorithmus kann eigentlich auf jedes Dokument angewendet werden. Der tree-based Algorithmus akzeptiert nur XML files als Input. Es soll zuerst ein DOM tree erstellt werden (in wie fern hängt der mit dem AST zusammen?), wobei Der Algorithmus dann auf diesen DOM tree anwendet werden soll. Ich wäre froh, wenn ihr mir vielleicht Literatur (insbesondere Papers) zu tree-based Algorithmen (auf der Basis von der DOM Struktur) empfehlen könnt. Die Papers sollten nicht zu umfangreich sein und nicht zu kompliziert, wenn sie gerade noch Code Beispiele enthalten würden, wäre das natürlich toll. Falls jemand noch Literatur über DOM bzw. AST hätte, würde ich das auch dankend annehmen (wobei natürlich Literatur über tree-based Algorithmen Priorität haben). Beim line-based Algorithmus habe ich schon einige Papers gefunden, falls jemand aber noch zusätzliche empfehlen könnte (z.B. über Levensthein, Diff von Unix etc.), wäre das nicht schlecht (aber wie gesagt tree-based hat Priorität, da ich da noch praktisch keine Papers gefunden habe). ------------------------- By the way, Eine kleine kurze Frage habe ich noch. Vielleicht könnt ihr mir da helfen. Nehmen wir an, dass wir zwei Dokumente A und B hätten, wobei A = abbba und B = abbab Mit dem line-based Algorithmus, den ich implementieren könnte, würde man ein edit script bekommen mit dem man vom ersten Dokument (A) aufs zweite Dokument ( kommt. D.h. es würde beschrieben werden, welche Elemente in A gelöscht und welche eingefügt werden müssten. Also z.B. für das obige Beispiel würden wir das 4. Element von A löschen und das 3. b aus B nach der 5. Stelle von A einfügen. Somit würden wir aus A B bekommen. Wenn ich nun die Differenzen graphisch darstelle, wäre es dann ok, wenn ich im Dokument A einfach alle Elemente, die gelöscht wurden markiere (also das 4. Element von A) und in Dokument B einfach alle Elemente markiere, die in A eingefügt wurden (also das 3. Element von ? ich danke vielmals.

Ich muss keinen Algorithmus erfinden, sondern nur bestehende implementieren. Und bei einer Arbeit geht es ja auch nicht darum, dass man alles problemlos abarbeiten kann, sondern das man die Probleme gut löst. Das Thema ist das beste, das ich gefunden habe bzw. das Thema, womit ich am wenigsten Probleme haben sollte.

Vielen Dank metux. Meinst du Git? Habe Git Sources noch nie benutzt. Ist da nicht eher so ein Programm, wo man Projekte koordinieren kann? Ich muss hier wohl noch etwas klar stellen, ich bin da ein bisschen falsch verstanden worden. Es geht mir nicht darum, dass jemand für mich die Arbeit schreibt und ich werde auch selber nach Literatur etc. suchen. Es geht mir nur um Vorschläge für einen Baum-basierten und Zeilenbasierten Algorithmus, ich brauche nur etwas Starthilfe. Ich habe übrigens jetzt auch schon ein Weile gesucht und nicht wirklich etwas brauchbares zu dem Thema gefunden.