| | | Gut zu wissen: Hilfreiche Tipps und Tricks aus der Praxis prägnant, und auf den Punkt gebracht für Autodesk Produkte | | | | PNY präsentiert die neue NVIDIA RTX A400 und die A1000 Grafikkarte, eine Pressemitteilung
|
Autor
|
Thema: Suche nach: Funktionen zur Listenbearbeitung... (3188 mal gelesen)
|
marc.scherer Ehrenmitglied V.I.P. h.c. CAD-Administrator
Beiträge: 2494 Registriert: 02.11.2001 Windows 10 64bit AutoCAD Architecture 2018/2019 (deu/eng) AEC-Collection 2019 (Revit und Zeugs) Wenn sich's nicht vermeiden läßt: D-A-CH Erweiterung (mies implementierter Schrott)
|
erstellt am: 11. Aug. 2005 12:39 <-- editieren / zitieren --> Unities abgeben:
|
Jan1 Mitglied CAD Consultant
Beiträge: 17 Registriert: 12.05.2004
|
erstellt am: 11. Aug. 2005 14:12 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
(defun intersection (lA lB / x) (vl-remove 'nil (mapcar '(lambda (x) (if (member x lB) x nil)) lA)) ); end defun (defun set-difference (lA lB / lC x) (setq lC (vl-remove 'nil (mapcar '(lambda (x) (if (member x lB) nil x)) lA))) (setq lC (append lC (vl-remove 'nil (mapcar '(lambda (x) (if (member x lA) nil x)) lB)))) ); end defun Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 11. Aug. 2005 16:52 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|
marc.scherer Ehrenmitglied V.I.P. h.c. CAD-Administrator
Beiträge: 2494 Registriert: 02.11.2001 Windows 10 64bit AutoCAD Architecture 2018/2019 (deu/eng) AEC-Collection 2019 (Revit und Zeugs) Wenn sich's nicht vermeiden läßt: D-A-CH Erweiterung (mies implementierter Schrott)
|
erstellt am: 12. Aug. 2005 08:19 <-- editieren / zitieren --> Unities abgeben:
Zitat: Original erstellt von mapcar: Bei aller Liebe zu mapcar
Ich schmeiß mich vor Lachen gleich aus dem Fenster *grins* Na, lieber Axel dann werde ich's wohl selber schreiben müssen. Ich hatte ja auf eine Deiner oder Achims genialen Lösungen gehofft... Aber dann gibt es halt nur eine deutlich weniger geniale und mit zuviel Zeichen geschriebene Version von mir... @jan1 Vielen Dank für Deine Codes, für meinen Zweck haben sie gute Dienste geleistet. Sind zwar nicht universell einsetzbar aber in 'ner Liste von einfachen Strings kam schon das richtige raus. Danke!
------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 12. Aug. 2005 10:07 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Für Kleinkram tut's sicherlich sowas hier: Code:
; ACHTUNG: ungetestet! (defun intersection(l1 l2 / l3) (foreach item l1 (if(member item l2) (setq l3(cons item l3)) ) ) (reverse l3) ); ACHTUNG: ungetestet! (defun difference(l1 l2 / l3 l4) (setq l3(intersection l1 l2)) (foreach item(append l1 l2) (if(not(member item l3)) (setq l4(cons item l4)) ) ) (reverse l4) )
Bei längeren Listen kann das Gemembere allerdings ziemlich auf die Nüsse schlagen. Angebracht wären Funktionen, die zuerst indiziert sortieren. Aber da stellt sich das Problem, dass < bzw. > nicht für alle Datentypen definiert sind, vor allem nicht für Unterlisten. In den Unterlisten darf ja nicht rekursiv sortiert werden, denn dann würde man ja Elemente "fälschen". In der Praxis reicht das oben aber oft aus. Nehmen wir als Beispiel mal ein Checkprogrämmchen, das kontrolliert, ob man auch brav alle seine Variablen lokal gemacht hat. (difference atomfamilie-vorher atomfamilie-nachher) => (myfunc1 myfunc2 i myfunc3). Ups, da wurde irgendwo ein i nicht hinter den Schrägstrich geschrieben, und schon läuft wieder eine Routine Amok, weil sie sich am i eines Vorgesetzten vergreift. Noch ein Wort zu dieser remove-nil-mapcar-irgendwas-Technik: Die kam schon vor Jahren auf und wurde in der Custom-NG immer wieder gepostet. Leider hat es wenig gebracht, dass auf die implizierten Fehler hingewiesen wurde ("Was soll ich denn mit einem nil in meiner Liste, muss doch sowieso raus!"). Tja, und so hat diese kaputte Technik einen regelrechten Siegeszug angetreten. Na ja, ich wünsche fröhliches Debuggen! Gruß, Axel Strube-Zettler ------------------ Meine AutoLisp-Seiten Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
marc.scherer Ehrenmitglied V.I.P. h.c. CAD-Administrator
Beiträge: 2494 Registriert: 02.11.2001 Windows 10 64bit AutoCAD Architecture 2018/2019 (deu/eng) AEC-Collection 2019 (Revit und Zeugs) Wenn sich's nicht vermeiden läßt: D-A-CH Erweiterung (mies implementierter Schrott)
|
erstellt am: 12. Aug. 2005 10:24 <-- editieren / zitieren --> Unities abgeben:
lol, hat mich mal wieder nicht losgelassen die Problemstellung und habe jetzt (wo mal kurz Zeit war...;-)) meine eigene Lösung gebaut. @Axel Das war aber bevor ich Dein Posting gesehen hatte :-(. So here we go:
Code:
(defun DT:LIST-INTERSECTION (X Y / RETVAL) (foreach ELEM X (if (member ELEM Y) (setq RETVAL (cons ELEM RETVAL)) ) ) (reverse RETVAL) )(defun DT:LIST-DIFFERENCE (X Y / RETVAL) (foreach ELEM X (if (not (member ELEM Y)) (setq RETVAL (cons ELEM RETVAL)) (setq Y (vl-remove ELEM Y)) ) ) (DT:LIST-UNION (reverse RETVAL) Y) ) (defun DT:LIST-UNION (X Y) (cond ((null X) Y) ((member (car X) Y) (DT:LIST-UNION (cdr X) Y)) (t (cons (car X) (DT:LIST-UNION (cdr X) Y))) ) ;_ end of cond )
... ------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 12. Aug. 2005 17:46 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Tag zusammen. Zur Zeit ist das Forum einfach zu schnell für mich - oder genauer: ich bin zu langsam für's Forum. Im Kern ist bereits alles Wesentliche gesagt, aber zu Axels Anmerkungen, dass, unter der Voraussetzung der Existenz von Vergleichs-Operatoren < und = für die Elemente innerhalb der Liste, erheblich schnellere Implementierungen möglich seien, möchte ich noch ein Beispiel mit Verwendung von Suche mit binären Bäumen vorstellen. In den Anhängen finden sich 2 Dateien beispiel-liste-0.lsp und beispiel-liste-2.lsp, die sich mittels
Code:
(setq #l0(load"beispiel-liste-0.lsp") #l1(load"beispiel-liste-1.lsp") )
zum Nachvollziehen der Zeitmessung verwenden lasssen. Die Listen enthalten ca. 50'000, bzw. 10'000 INT-Einträge und bringen die Schnittmengen-Bildung ordentlich zum Schwitzen. Nehmen wir also mal Marcs Funktion DT:LIST-INTERSECTION zur Hand (das reverse hab' ich mal raus genommen, weil's meiner Meinung nach für Schnittmengen nicht von Bedeutung ist) und sehen uns an, wie sie mit den beiden Listen umgeht: Code:
(defun dt:list-intersection (list0 list1 / retval) (foreach elem list0 (if (member elem list1) (setq retval (cons elem retval)) ) ) retval )
(dt:list-intersection #l0 #l1) -> 1:28 Minuten *gähn* Axel merkte bereits an, dass die Ursache für die schleppende Verarbeitung in der Verwendung von member zu finden ist. Die Funktion muss nämlich jedes Mal die Liste von vorne durchsuchen, um festzustellen, ob ein Element in ihr enthalten ist. Wenn wir also Glück haben, steht das gesuchte Element ganz am Anfang, häufig ist's aber gar nicht darin enthalten, was dazu führt, dass die gesammte Liste durchlaufen werden muss. Also ein Laufzeitverhalten, das vom Produkt der Länge der Listen #l0 und #l1 abhängt. Das ist Programmier-Selbstmord. Was wir brauchen ist also ein besseres Verfahren als Ersatz für member. Die Suche mit binären Bäumen gibt und genau diesen Ersatz an die Hand: Code:
(defun :l-intersect (list0 list1 / retval) ((lambda (binaer-baum) (foreach elem list1 (if (:bintree-member elem binaer-baum) (setq retval (cons elem retval)) ) ) ) (:bintree-fill list0 nil) ) retval )
Bis auf die neue MEMBER-Funktion und das Füllen des binären Baums bleibt also alles beim alten. Mal schauen, wie sich die Änderung auswirkt: (:l-intersect #l0 #l1) -> 0:07 Minuten *huch* - schon fertig .. Bleibt noch zu erklären, was die Funktionen :bintree-* so tun und was ein binärer Baum eigentlich ist und warum sich in diesen Bäumen so flott suchen lässt. Ich zitiere jetzt mal aus {"Struktur und Interpretation von Computerprogrammen", Abelson, Sussman, Sussman, Springer-Verlag, Seite 161-162}:
Zitat:
[..] An jeder Verzweigungsstelle (jedem "Knoten") des Baums befindet sich eine Element der Menge, genannt Eintrag in dem Knoten, und je ein Verbindungszeiger zu zwei anderen (möglicherweise leeren) Knoten. der "linke" Verbindungszeiger zeigt auf Elemente, die kleiner als dder Eintrag in dem Knoten sind, und der "rechte" Verbindungszeiger zeigt auf Elemente, die größer als der Eintrag in dem Knoten sind. [..]und weiter Der Vorteil der Baumdarstellung ist folgender: Wir wollen feststellen, ob eine Zahl x in einer Menge enthalten ist. Zuerst vergleichen wir x mit dem Eintrag im obersten Knoten. Wenn x kleiner ist, wissen wir, daß wir nur den linken Unterbaum durchsuchen müssen; wenn x größer ist, müssen wir nur den rechten Unterbaum durchsuchen. [..] Da der [zu durchsuchende] Baum nach jedem Schritt nur noch halb so groß ist wie vorher, wird die Anzahl der benötigten Schritte zur Durchsuchung eines Baums [nur] mit der Größe n mit O(log n) wachsen. [..]
Damit hätten wir den Grund für die nette Beschleunigung gefunden: 1000 Elemente ca. 10 Vergleiche, bei 10'000 ca. 14. Wie wird jetzt ein Binärbaum gefüllt? Im Prinzip genauso, wie darin gesucht wird: Vergleichen mit dem Eintrag im obersten Knoten, ist er kleiner, dann wird das Element dem linken Unterbaum zugeschlagen, andernfalls gehört es in den rechten Unterbaum. Eine rekursive Definition lässt sich dann auch auch prima mit einem rekursiven Algorithmus erschlagen: Code:
;** definiert Gleichheits und kleiner-als-Operatoren für die Einträge in den Knoten des Binärbaums (setq :binTree-equal =) (setq :binTree-less < ) ; (defun :binTree-node (#binTree)(car #binTree));** gibt das Element im obersten Knoten zurück (defun :binTree-left (#binTree)(cadr #binTree));** gibt den linken Unterbaum des obersten Knotens zurück (defun :binTree-right(#binTree)(caddr #binTree));** gibt den rechten Unterbaum des obersten Knotens zurück ; ;** erzeugt einen neuen Binärbaum aus obersten Knoten #node, linkem Unterbaum #left und rechtem Unterbaum #right (defun :binTree-make (#node #left #right) (list #node #left #right) ) ; ;** prüft, ob #item als Eintrag in einem Knoten des Binärbaums #binTree enthalten ist (defun :binTree-member (#item #binTree) ((lambda(node) (cond ((or (not node)(:binTree-equal #item node)) node ) ((:binTree-less #item node) (:binTree-member #item(:binTree-left #binTree)) ) ('else (:binTree-member #item(:binTree-right #binTree)) ) ) ) (:binTree-node #binTree) ) ) ; ;** fügt das Element #item in einen Knoten des Binärbaum #binTree ein (defun :binTree-add (#item #binTree) ((lambda(node) (cond ((not node) (:binTree-make #item nil nil));** ist der Zweig nicht belegt, dann wird er jetzt belegt ((:binTree-less #item node) (:binTree-make node (:binTree-add #item(:binTree-left #binTree)) (:binTree-right #binTree) ) ) ('else (:binTree-make node (:binTree-left #binTree) (:binTree-add #item(:binTree-right #binTree)) ) ) ) ) (:binTree-node #binTree) ) ) ; ;** füllt die komplette Liste #list als Einträge in Knoten des Binärbaums #binTree (defun :binTree-fill (#list #binTree / ) (foreach el #list (setq #binTree (:binTree-add el #binTree)) ) #binTree )
Achim Dabrunz ------------------ [Diese Nachricht wurde von Dabrunz am 12. Aug. 2005 editiert.] [Diese Nachricht wurde von Dabrunz am 12. Aug. 2005 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 12. Aug. 2005 23:49 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Zitat: Original erstellt von Dabrunz: das reverse hab' ich mal raus genommen, weil's meiner Meinung nach für Schnittmengen nicht von Bedeutung ist
Ohne jetzt überhaupt auf die Bäume einzugehen: Mit dem reverse hast du natürlich Recht - nicht nur Marc ist darauf reingefallen, sondern auch ich. Das ist einfach Blödsinn. Eine Reihenfolge kann es nicht geben, da ja die Funktion kommutativ sein soll (heisst, es muss egal sein, ob ich (diff l1 l2) oder (diff l2 l1) aufrufe, und entsprechend kann/muss also das Ergebnis keine definierte Reihenfolge haben). Ich führe die Macht der Gewohnheit als Entschuldigungsgrund an;-)
Gruß, Axel Strube-Zettler PS: @cadensäge: Ich finde deine Lösungen übrigen trotz aller Diskussion eleganter als meine, da das "union" gleich noch mit erschlagen ist! ------------------ Meine AutoLisp-Seiten Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze [Diese Nachricht wurde von mapcar am 12. Aug. 2005 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 14. Aug. 2005 01:14 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Tja, Achim, schöne Demo für die Implementation eines unausgeglichenen Binärbaumes, aber ich möchte noch auf einen Aspekt hinweisen, den du unterschlagen hast. Die Sache mit dem Binärbaum krankt daran, dass sie mit *deinen* Daten prima läuft (0:07 statt 1:28), aber mit *meinen* Daten will sie nicht so recht - nach 5 Minuten habe ich abgebrochen;-) Meine Daten braucht man sich nicht runterladen, die kann man sich aus deinen erzeugen: (acad_strlsort(mapcar'itoa(load"bespiel-liste-0"))) ; bzw. Liste 1 Und damit sollte das Problem für alle klar sein: Der binäre Baum in dieser Form ist schön für Daten in normalverteilter Reihenfolge, aber bei bereits sortierten Daten versagt das Verfahren völlig, der Baum wird zur Karikatur einer windgestressten Latschenkiefer. Mein Ansatz mit dem Sortieren macht's aber auch nur etwas besser. Die Universal-Funktion, die immer gleich ein Sortieren anwirft, beschleunigt natürlich auch nicht gerade, wenn sie mit bereits sortierten Daten gefüttert wird. Nur - da hält sich der Schaden in Grenzen! Mag sein, dass die Zeit fürs Sortieren in den Sand gesetzt ist, dafür ist ein Durchkämmen der beiden Listen mit Iteratoren das Schnellste, was man dann implementieren kann. Ich denke, die *universelle* Funktion, die überschaubar ist, bei ganz kurzen Listen (< 100) keinen unnötigen overhead produziert, und bei großen Listen schnell ist, gibt es wohl nicht. Da reicht Marcs Implementierung erstmal, und bei größeren Datenmengen ist einfach das Wissen um die Dinge entscheidend: Man muss wissen, dass man solche Funktionen nicht unbedarft auf ein paar Megabyte loslassen darf, genauso wie append, member und nth. Und man muss wissen, wie man im Bedarfsfall etwas für größere Listen implementiert, z.B. eben das Sortieren/Iterieren, Binäre Bäume einschl. ausgefeilterer Modelle wie Black-Red-Tree, Hashtables und wer-weiss-was. Gruß, Axel Strube-Zettler ------------------ Meine AutoLisp-Seiten Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Apply2CAD Mitglied
Beiträge: 9 Registriert: 05.04.2005
|
erstellt am: 14. Aug. 2005 19:47 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Einen universellen Listen-Sortieralgorithmus gibt es meiner Meinung nach nicht und kann mich nur Axels Meinung anschließen. In einem alten ct-Artikel: ct 4/92 S.264 Bsort - ein gutmütiges Sortierverfahren Uwe Thiemann ist das ganze schön beschrieben, aber auch füllen Lehrbücher komplette Kapitel damit. In Abhängigkeit von den zu "erwarteten" Daten (große/kleine Listen, doppelte Elemente etc.) gibt es passende Sortieralgorithmen mit akzeptablen/performen Laufzeitverhalten. _______________ Ralph Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
marc.scherer Ehrenmitglied V.I.P. h.c. CAD-Administrator
Beiträge: 2494 Registriert: 02.11.2001 Windows 10 64bit AutoCAD Architecture 2018/2019 (deu/eng) AEC-Collection 2019 (Revit und Zeugs) Wenn sich's nicht vermeiden läßt: D-A-CH Erweiterung (mies implementierter Schrott)
|
erstellt am: 15. Aug. 2005 09:09 <-- editieren / zitieren --> Unities abgeben:
@Achim: & Ich hatte ja auf was geniales gehofft, wollte es aber auch noch verstehen ;-) Sehr geiles Beispiel für mich um mal wieder festzustellen, dass ich noch enorm viel zu lernen habe. @mapcar: Zitat: Ich finde deine Lösungen übrigen trotz aller Diskussion eleganter als meine, da das "union" gleich noch mit erschlagen ist!
Das glaube ich Dir gerne, das Union ist ja bis auf den Funktionsnamen von Dir *grins* Und was von einem selbst kommt ist einem ja in der Regel immer symphatisch. (Na ja, vielleicht nicht alles ;-)) Zum Thema reverse oder nicht: Ich habe mit den Funktionen eine Historie der ActiveX Methoden und Eigenschaften von R2000 bis 2006 erarbeitet (den Link dazu stelle ich auch noch hier rein, wenn es denn upgeloaded ist...). Da standen dann immer die in der neuen Version fehlenden Elemente ganz am Ende der Liste. Die wollte ich aber zuerst sehen, deswegen das reverse da drin. Hat aber natürlich in der eigentlichen Routine gar nichts verloren, da stimme ich Euch zu.
Code:
;| Ermittelt die Schnittmenge zweier Listen Die Listen dürfen keine Duplikate enthalten! Beispiel: (DT:LIST-INTERSECTION '(a b c) '(b)) > (b)(DT:LIST-INTERSECTION '(a b c nil (a) (b c)) '(a c nil (b c)) ) > (A C nil (B C)) |; (defun DT:LIST-INTERSECTION (X Y / RETVAL) (foreach ELEM X (if (member ELEM Y) (setq RETVAL (cons ELEM RETVAL)) ) ) RETVAL ) ;| Ermittelt die Differnz zweier Listen Die Listen dürfen keine Duplikate enthalten! Beispiele: (DT:LIST-DIFFERENCE '(a b c) '(b)) > (A C)
(DT:LIST-DIFFERENCE '(a b c nil (a) (b c)) '(a c nil (b c)) ) > (B (A)) |; (defun DT:LIST-DIFFERENCE (X Y / RETVAL) (foreach ELEM X (if (not (member ELEM Y)) (setq RETVAL (cons ELEM RETVAL)) (setq Y (vl-remove ELEM Y)) ) ) (DT:LIST-UNION RETVAL Y) ) ;| Vereinigt zwei Listen miteinander, Duplikate fliegen aber raus!! (DT:LIST-UNION '(a b) '(c)) > (A B C)
(DT:LIST-UNION '(a b) '(a c)) > (B A C) (DT:LIST-UNION '(a b c (b)(d e)) '((f g))) > (A B C (B) (D E) (F G)) |; (defun DT:LIST-UNION (X Y) (cond ((null X) Y) ((member (car X) Y) (DT:LIST-UNION (cdr X) Y)) (t (cons (car X) (DT:LIST-UNION (cdr X) Y))) ) ;_ end of cond )
...------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 15. Aug. 2005 10:36 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 15. Aug. 2005 11:09 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Tag zusammen. @Axel: Ja, ich habe das Konzept der ausgeglichenen Bäume weggelassen und damit unterschlagen. Es stimmt natürlich, dass eingedenk der vielfältigen Möglichkeiten, in denen die Datenlisten zur Verarbeitung vorliegen können das von mir illustrierte Verfahren in der vorliegenden Form nicht in allen Situationen den erhoften Vorteil bringt. Aber, und dasss weißt du sicher auch, es gibt Verfahren, mit denen sich Bäume ausgeleichen lassen (das bedeutet: Alle Zweige im Baum sind ungefähr gleich lang.). Häufig steht der Aufwand in keinem akzeptablen Verhältnis zum Resultat, insbesondere, wenn der Baum immer wieder neu ausgeglichen werden muss. Allerdings gibt es einen Algorithmus für den Aufbau eines ausgeglichenen Binärbaums, er aus einer bereits sortierten Liste aufzubauen ist. Der ist gut, gerade wenn in der sortierten Liste häufig gesucht wird - ich werde ihn hier posten, wenn ich mal wieder in meinen Unterlagen blättern kann, denn ich hab' ihn nicht im Kopf (und auch nicht in Code). Im Wesentlichen wird aber immer das Element aus der "Mitte" zum Eintrag im obersten Knoten (nenn' ich jetzt, wie allgem. üblich auch Wurzel-Knoten) und aus den Teillisten vor und nach dem Mittel-Element werden die Unterbäume (rekursiv) konstruiert - am Mittwoch kann ich's nachschieben, wenn sich jemand dafür interessiert. @Uwe: Ja, du hast recht, wenn du unter universell "immer das beste Laufzeitverhalten unabhängig von der Datenstruktur der zu sortierenden Daten" verstehst. Das tue ich aber nicht. Ich verstehe unter universell: Egal, wie die zu sortierende Liste aussieht, erhalte ich im ungünstigsten Fall noch immer eine Mindest-Performance. Und da gibt's dann doch den einen oder anderen Sortieralgorithmus, der dieses Versprechen einlöst (good old "Mergesort" z.B.). Diese Algos bringen's gerade deshalb, weil ich sie ohne groß nachzudenken erstmal verwenden kann und nur, wenn Performance-Engpässe auftreten, muss ich mir was besseres einfallen lassen. BubbleSort ist ein Kandidat für "meistens schlecht". Allerdings, ist er sehr performant, wenn die Daten bereits weitestgehend sortiert vorliegen. Was aber verlangt, dass ich die zu sortierenden Daten bereits kenne. @Marc: Irgendwie glaube ich, dass du dein Licht ein wenig unter den Scheffel stellst :-) Wenn aber noch was nicht ganz klar ist, dann frag' bitte einfach nach. Achim Dabrunz ------------------ [Diese Nachricht wurde von Dabrunz am 15. Aug. 2005 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 15. Aug. 2005 11:51 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Zitat: Original erstellt von Dabrunz: das Konzept der ausgeglichenen Bäume weggelassen
So meinte ich das gar nicht. Mir fehlte nur der Hinweis, dass der Ansatz eine gewisse Verteilung der Daten veraussetzt, um effektiv zu sein. Und das habe ich ein wenig ausgeführt, damit Leute wie Marc, der Verstehensprobleme äussert, nicht ggf. mit einem Nebensatz abgefertigt werden. Aber nochmal ein Stück weiter zurück: Wie könnte man eine Vrgleichsfunktion implementieren (für das Sortieren bzw. Einordnen in einen Baum), die auf alle Datentypen einschl. Unterlisten anwendbar ist? Das einzige, was mir spontan einfällt, ist a) die Speicheradresse, die wäre eindeutig, aber auf die haben wir in Lisp ja keinen Zugriff, und b) vl-princ-to-string. Noch andere Ideen? Gruß, Axel Strube-Zettler ------------------ Meine AutoLisp-Seiten Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
marc.scherer Ehrenmitglied V.I.P. h.c. CAD-Administrator
Beiträge: 2494 Registriert: 02.11.2001 Windows 10 64bit AutoCAD Architecture 2018/2019 (deu/eng) AEC-Collection 2019 (Revit und Zeugs) Wenn sich's nicht vermeiden läßt: D-A-CH Erweiterung (mies implementierter Schrott)
|
erstellt am: 15. Aug. 2005 14:06 <-- editieren / zitieren --> Unities abgeben:
|
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 18. Aug. 2005 10:57 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Tag zusammen. Wenn auch mit einiger Verzögerung (sorry), so doch noch diese Woche mein versprochener Beitrag zu ausgeglichenen Binärbäumen. Dazu möchte ich erst einmal etwas ausführlicher beleuchten, warum die 'einfache' Implementierung der Funktion (:binTree-fill <Liste> <Baum>) von oben keine guten Bäume produziert, wenn <Liste> sortiert ist. Was passiert, wenn ich die Liste (1 2 3 4 5 6 7) in einen leeren Binärbaum packe? Betrachten wir einige Zwischenergebnisse nach einem :binTree-add mal mit grafischer Aufbereitung: (:binTree-add 1 nil) -> Iter[1] der erste Knoten
Code:
<1>
(:binTree-add 2 Iter[1]) -> Iter[2] der zweiter Eintrag ist größer, er gehört also nach 'rechts' Code:
<1> \ <2>
(:binTree-add 2 Iter[2]) -> der dritte Eintrag ist größer als der 1. Knoten und auch größer als der 2. Knoten-Eintrag, er wird also immer in den 'rechten' Teilbaum einsortiert
Code:
<1> \ <2> \ <3>
Das setzt sich jetzt so fort und am Ende sieht unser Baum gar nicht besonders binär aus:
Code:
<1> \ <2> \ <3> \ <4> \ <5> \ <6> \ <7>
Wenn wir in diesem Baum nach einem Element suchen (z.B. die 12), wird gegenüber member also nix gewonnen, weil wir im Zweifel auch jeden Knoten prüfen müssen. Von den ".. im Schnitt log(n) Vergleichen .." ist also nichts zu sehen. Wir müssen also versuchen, den Baum 'gleichmäßig' zu befüllen. Das soll heißen: In jedem rechten und linken Teibaum eines Knotens liegen ungefähr die gleiche Anzahl Elemente.So kann das bei unserer sortierten Liste aussehen:
Code:
<4> / \ / \ <2> <6> / \ / \ <1><3> <5><7>
Wie sorge ich jetzt dafür, dass die Zahlen auch auf diese Weise in den Baum gefüllt werden? Die Antwort ergibt sich fast aus einer genauen Betrchtung des Beispielbaums hier oben:Teilen wir die sortierte Liste in 3 Teile <links von der Mitte> - <Mitte> - <rechts von der Mitte>, dann müssen wir nur noch (*hüstel*) die beiden Mengen rechts und links des mittleren Elements in (ausgeglichene) Bäume verwandeln und sie als rechten und linken Teilbaum unter den neuen Knoten hängen, der aus dem Mittel-elemnet besteht. Wer den einen oder anderen Beitrag von mir gelesen hat wird schon vermuten worauf das alles hinaus läuft - auf eine rekursive Funktion. Leider ist mir keine wirklich einfache Implementierung eingefallen, die auch flott zur Sache geht und nicht immer wieder auf's neue linke und rechte Teillisten bauen muss - dann ist nämlich unsere tolle Performance wieder zum Teufel. Aber ich habe mal eine Fassung (das Grundgrüst ist, wie so einiges was ich zu diesem Thread beitrage, aus {"Struktur und Interpretation von Computerprogrammen", Abelson, Sussman, Sussman, Springer-Verlag}, diesmal von Seite 166) mit ordentlich vielen SETQs gebastelt, an der vielleicht besser nachzuvollziehen ist, was passiert. Die Hilfsfunktion _binTree-partial erzeugt aus den ersten #n Elementen aus #elements einen ausgewogenen (Teil-)Baum und lässt den Rest (remainder) einfach am Ende der Rückgabeliste 'rumhängen. Code:
(defun :binTree-from-sorted (#sorted-list) (car (_binTree-partial #sorted-list (length #sorted-list))) ) ; (defun _binTree-partial (#elements #n / left-length left-result left-tree right-length right-result right-tree not-left new-knot remainder ) (if (<= #n 0) (cons '() #elements);** dann ist nichts in den Baum zu packen (progn;** ELSE: (setq left-length (/ (1- #n)2));** Anz. der Elemente 'links der Mitte' (setq left-result (_binTree-partial #elements left-length));** das Zwischresultat des linken Teils (setq left-tree (car left-result));** der linke Teilbaum steckt vorn in der Rückgabe der Funktion (setq not-left (cdr left-result));** alle übrigen Elemente im Rest der Rückgabe (setq right-length (- #n (1+ left-length)));** Anz. der Elemente 'rechts der Mitte' (setq new-knot (car not-left));** der erste Eintrag der Reste wird zum aktuellen Knoten (setq right-result (_binTree-partial (cdr not-left) right-length));** aus dem was übrig bleibt, ... (setq right-tree (car right-result));** der rechte Teilbaum zusammengebaut (setq remainder (cdr right-result));** alles was nicht verarbeitet wurde, wird ... (cons;** zur Rückgabeliste der Form: (<Baum> Rest) verarbeitet (:binTree-make new-knot left-tree right-tree) remainder ) ); end ELSE: ) )
Der Vollständigkeit halber noch die Geschwindigkeitsvergleiche mit der neuen Funktion :l-intersect-sort:
Code:
(defun :l-intersect-sorted (list0 list1 / retval) ((lambda (binaer-baum) (foreach elem list1 (if (:bintree-member elem binaer-baum) (setq retval (cons elem retval)) ) ) ) (:binTree-from-sorted list0) ) retval )
Die Listen, wie vom Beitrag oben:
Code:
(setq #l0(load"beispiel-liste-0.lsp") #l1(load"beispiel-liste-1.lsp") )
ergibt dann - unter Berücksichtigung der Tagesform meines Notebooks mit leichten Abweichungen zur letzten Messung:(dt:list-intersection #l0 #l1) -> 1:28 Minuten (:l-intersect #l0 #l1) -> 0:08 Minuten (:l-intersect-sorted (vl-sort #l0':binTree-less) #l1) -> 0:01 Minuten !! inkl. Sortierung !! Yeah - Ausgleichen bringt's Achim Dabrunz ------------------ [Diese Nachricht wurde von Dabrunz am 18. Aug. 2005 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Apply2CAD Mitglied
Beiträge: 9 Registriert: 05.04.2005
|
erstellt am: 18. Aug. 2005 12:02 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hallo Achim, einen kurzen und interessanten Artikel zum Thema binäre Bäume in c't 1/1992 Bäume in Balance Schnelle Datenverwaltung mit dem AVL-Baum Mathias Hermainski Angehängt ist der C-Quellcode mit interessanten Erweiterungen. Das Ganze sollte sich auch in LISP nachbauen lassen. _______________ Ralph Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 18. Aug. 2005 17:56 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hi Achim, auch hier wieder: schöne Funktionen, gute Demo. Trotzdem setze ich dem das iterative Modell entgegen: Code:
(defun iterative-l-intersect(l0 l1 / l2) (setq l0(vl-sort l0'< )l1(vl-sort l1'< )) (while(and l0 l1) (cond ((<(car l0)(car l1))(setq l0(cdr l0))) ((>(car l0)(car l1))(setq l1(cdr l1))) (1(setq l2(cons(car l0)l2)l0(cdr l0)l1(cdr l1))) ) ) l2 ) (length(iterative-l-intersect #l0 #l1)) ; => 7315 in ca 0.3 s, also *dreimal* so schnell wie dein ausgeglichener Baum. Die ganzen Zeiten nochmal im Überblick (alle Angaben ca.!): [code] Sekunden Funktion ------------------------------------------------------------------- >300 unausgeglicher Baum, wenn die Daten sortiert sind 90 Mit (member)-Aufrufen 8 unausgeglicher Baum, wenn die Daten zufällig verteilt sind 1 ausgeglichener Baum (incl. Sortieren) 0.3 iterativ (incl. Sortieren)
Wer hat noch tieferlegende Ideen? Gruß, Axel Strube-Zettler ------------------ Meine AutoLisp-Seiten Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 18. Aug. 2005 23:08 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Immer noch auf der Suche nach der eierlegenden Wollmilchsau, der Funktion, die sowohl schnell ist als auch sämtliche Datentypen verarbeitet. Die Sache hat einen kleinen Haken, bzw. mehrere... Zunächst mal: Die Funktionen (< ...) und (> ...) verarbeiten ausschließlich Zahlen und Zeichenketten, bei allen anderen Datentypen wird ein Error ausgelöst. Anders als bei (= ...) und (equal ...), da gibt es eine Funktion für Zahlen/Zeichenketten und eine für alle Datentypen. Natürlich kann man, wenn man's genau nimmt, auch nicht wirklich sagen, dass der Entityname "myCirleEntity" größer oder kleiner als "myLineEntity" ist. Aber es ist ja völlig unwichtig, ob dieser Vergleich inhaltlich sinnvoll ist oder nicht, er muss nur funktionieren. Letztlich muss man ja auch bei Zeichenketten ein inhaltliches "klener/größer" vom formalen trennen: Eine Gasse ist kleiner als eine Allee, trotzdem gilt (> "Gasse" "Allee") => T. Um beliebige Datentypen zu sortieren, muss man sie also allesamt in Zeichenketten umwandeln - eine andere Möglichkeit sehe ich nicht. Und da bietet sich als Möglichkeit (vl-princ-to-string <expr> ) an. Aber schon haben wir mit dem nächsten Haken zu tun: Diese Funktion hat einen derben Bug, sie produziert nämlich einen Aussetzer, wenn sie mit einer Zeichenkette gefüttert wird. Da hat sich Serge wohl damals gedacht: "Ist doch schon ein String, also warum noch was machen ...?". Tja, dadurch ist die Funktion eben nicht mehr eindeutig. Ein Beispiel:
Code:
(setq fluesse-der-kontinente '("mississippi" "amazonas" "nil" "jangtsekiang" "darling" "wolga" nil) ; in der Antarktis gibt's eben keine Flüsse, da fließt gar nix )(mapcar'vl-princ-to-string fluesse-der-kontinente) => '("mississippi" "amazonas" "nil" "jangtsekiang" "darling" "wolga" "nil")
Das ist einfach Käse, der Nil fließt nicht auch noch durch die Antarktis! Also muss eine Bugfix-Funktion her. Ich umgehe einfach den Fehler, indem ich mit (list ...) jedes Element in eine ein-elementige Liste umwandle:
Code:
(defun princ-to-string-l(arg / ) (vl-princ-to-string(list arg)) )
So kann man nun also mit '< oder '> vergleichen. Aber es kommt schlimmer: Die Umwandlung in eine Zeichenkette kann man nicht rückgängig machen. Ja, sicher, es gibt (read ...). Aber in AutoLisp gibt es Datentypen, die dagegen geschützt sind, dass man sie sich selber bastelt - sie zerfallen bei (read ...), und das mit Absicht:
Code:
(setq myEname(entlast)) => <Entity name: 7ef60f68> (setq myEname(princ-to-string myEname)) "(<Entity name: 7ef60f68> )"(car(read myEname)) => <ENTITY
Aus diesem Grunde ergibt sich eine Einschränkung: Wir können die Zeichenketten zwar für die Vergleiche benutzen, dürfen aber die Daten selbst nicht umwandeln. Zwei Möglichkeiten ergeben sich: Entweder ein indiziertes Sortieren mit einer in Zeichenketten umgewandelten Listen-Kopie, oder die Umwandlung on-the-fly beim Vergleich, auch wenn dadurch jedes Element mehrfach umgewandelt wird.Indiziertes Sortieren halte ich für ein in AutoLisp relativ nutzloses Verfahren, da man anschließend mit (nth) auf die Daten zugreifen muss. (nth) ist genauso schlimm wie member, d.h. der "Anfahrweg" ist exakt der selbe. Indizertes Sortieren macht in meinen Augen nur dann Sinn, wenn man Arrays befüllt, und die sind in AutoLisp nun mal gestrichen worden (in XLisp gab es sie). Ich könnte mir aber vorstellen, dass man hier auf die Kombination "Indiziertes Sortieren/Safearray" setzen könnte. Auch wenn das safearray kein nativer Datentyp ist und einen gewissen COM-Overhead mitbringt, könnte das ein schnellerer Weg sein. Damit wird schon klar: Die Funktion (l-intersect ...), die ich jetzt vorstelle, verarbeitet zwar *ALLE* Datentypen, aber sie ist tierisch langsam. Na ja, immer noch schneller als die anfangs geposteten member-haltigen Codes.
Code:
(defun princ-to-string-l(arg / ) (vl-princ-to-string(list arg)) )(defun compare(e0 e1 / ) (setq e0(princ-to-string-l e0) e1(princ-to-string-l e1) ) (cond((> e0 e1)1)((< e0 e1)1)('T 0)) ) (defun _<(e0 e1 / ) (<(princ-to-string-l e0)(princ-to-string-l e1)) ) ;nur der Vollständigkeit halber (defun _>(e0 e1 / ) (>(princ-to-string-l e0)(princ-to-string-l e1)) ) (defun l-intersect(l0 l1 / cmp l2) (setq l0(vl-sort l0'_< )l1(vl-sort l1'_< )) (while(and l0 l1) (setq cmp(compare(car l0)(car l1))) (cond ( (= cmp -1) (setq l0(cdr l0)) ) ( (= cmp +1) (setq l1(cdr l1)) ) ('T (setq l2(cons(car l0)l2)l0(cdr l0)l1(cdr l1)) ) ) ) l2 )
Für die Verarbeitung von Achims Beispiel-Listen benötigt sie auf meinem Privat-Rechner (einem schlappen, ollen Duron 1200, der genügt mir immer noch) ca. 55 Sekunden. Das ist die eine Seite der Medaille, die andere ist eben, dass sie auch das hier kann:
Code:
(setq bl2 (list 4 3 "a" (entlast)'(1 2)'(3 4)19 37 'mysym1 20 21 '() 22 23 'T set) ) (setq bl3 (list '(3 5)19 3 "a" '(1 2)19 37 'mysym1 20 15 '() 24 23 'T set (entlast)) )(l-intersect bl2 bl3) => ("a" T MYSYM1 <Entity name: 7ef60f68> 37 3 23 20 19 (1 2) #<SUBR @0759c078 SET> )
Kann sie das wirklich? Nö. Wenn man genau hinsieht, dann erkennt man, dass das nil irgendwo verdunstet ist. Die Ursache ist schnell lokalisiert: (vl-sort) tickt nicht richtig, da wird ein nil einfach ignoriert, auch wieder nach dem Motto "steht ja eh nix drin, also kehren wir's unter den Tisch". Tja, irgendwie kann einem die Lust schon vergehen...Das reicht mir jetzt auch wirklich, für heute jedenfalls. Gruß, Axel Strube-Zettler
------------------ Meine AutoLisp-Seiten Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 19. Aug. 2005 11:23 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Neuer Tag, neues Glück. Die rettende Idee kam mir heute morgen: Um a) der vl-sort-Macke aus dem Weg zu gehen, und b) das mehr- bis vielfache Umwandeln in Strings zu umgehen, conse ich einfach den mit princ-to-string erzeugten String und das Original-Element zusammen. Die Vergleichsfunktionen habe ich dahingehend angepasst, dass sie jeweils nur den car des dotted pairs vergleichen, und die Hauptfunktion schiebt den cdr in die Ergebnisliste - im Falle eines nil fehlt der cdr, das gibt uns ein sauberes nil zurück. Durch diesen kleinen Trick haben wir nun eine Funktion, die a) sämtliche Klippen umschifft und mit *allen* Datentypen zurechtkommt, und b) auch noch relativ schnell ist. Zum Tempo: ich habe jetzt keine Messung vorgenommen, schätze aber, dass sie auf Achims Notebook etwa 3 Sekunden benötigt. Das ist zwar um Faktor 10 langsamer als die Nur-Zahlen-oder-Strings-Variante, aber immer noch um den Faktor 30 schneller als die Versionen mit member-Aufrufen. Code:
(defun compare(e0 e1 / ) (cond((>(car e0)(car e1))1)((<(car e0)(car e1))-1)('T 0)) )(defun _<(e0 e1 / ) (<(car e0)(car e1)) ) ; (defun _>(e0 e1 / ) ; (>(car e0)(car e1)) ; ) (defun make-sortable(l / ) (mapcar'(lambda(e /)(cons(princ-to-string-l e)e))l) ) ; gibt die Elemente zurück, die sowohl in A als auch in B enthalten sind ; A AND B (defun l-conjunction(l0 l1 / cmp l2) ; oder auch l-intersection (setq l0(vl-sort(make-sortable l0)'_< )) (setq l1(vl-sort(make-sortable l1)'_< )) (while(and l0 l1) (setq cmp(compare(car l0)(car l1))) (cond ( (= cmp -1) (setq l0(cdr l0)) ) ( (= cmp +1) (setq l1(cdr l1)) ) ('T (setq l2(cons(cdr(car l0))l2)l0(cdr l0)l1(cdr l1)) ) ) ) l2 )
Und da ich nun mal die Probleme für gelöst halt, kann man ja gleich die anderen Fälle mit erschlagen: Code:
; gibt die Elemente zurück, die in A oder B enthalten sind, aber ; nicht in beiden Listen ; A XOR B (defun l-antivalence(l0 l1 / cmp l2) (setq l0(vl-sort(make-sortable l0)'_< )) (setq l1(vl-sort(make-sortable l1)'_< )) (while(and l0 l1) (setq cmp(compare(car l0)(car l1))) (cond ( (= cmp -1) (setq l2(cons(cdar l0)l2)l0(cdr l0)) ) ( (= cmp +1) (setq l2(cons(cdar l1)l2)l1(cdr l1)) ) ('T (setq l0(cdr l0)l1(cdr l1)) ) ) ) (append l2(mapcar'cdr l0)(mapcar'cdr l1)) ); gibt alle Elemente zurück = l-union ; A OR B (defun l-disjunction(l0 l1 / cmp l2) (setq l0(vl-sort(make-sortable l0)'_< )) (setq l1(vl-sort(make-sortable l1)'_< )) (while(and l0 l1) (setq cmp(compare(car l0)(car l1))) (cond ( (= cmp -1) (setq l2(cons(cdar l0)l2)l0(cdr l0)) ) ( (= cmp +1) (setq l2(cons(cdar l1)l2)l1(cdr l1)) ) ('T (setq l2(cons(cdar l0)l2)l0(cdr l0)l1(cdr l1)) ) ) ) (append l2(mapcar'cdr l0)(mapcar'cdr l1)) ) ; gibt die Elemente zurück, die nur in A vorkommen ; A AND ~B (defun l-2ndinhibition(l0 l1 / cmp l2) (setq l0(vl-sort(make-sortable l0)'_< )) (setq l1(vl-sort(make-sortable l1)'_< )) (while(and l0 l1) (setq cmp(compare(car l0)(car l1))) (cond ( (= cmp -1) (setq l2(cons(cdar l0)l2)l0(cdr l0)) ) ( (= cmp +1) (setq l1(cdr l1)) ) ('T (setq l0(cdr l0)l1(cdr l1)) ) ) ) (append l2(mapcar'cdr l0)) ) ; gibt die Elemente zurück, die nur in B vorkommen ; ~A AND B (defun l-1stinhibition(l0 l1 / ) (l-2ndinhibition l1 l0) )
Zu Schluss noch ein kleiner Test mit Achims Listen:
Code:
(princ(strcat "conjunction : "(itoa(length(l-conjunction #l0 #l1)))"\n")) (princ(strcat "antivalence : "(itoa(length(l-antivalence #l0 #l1)))"\n")) (princ(strcat "disjunction : "(itoa(length(l-disjunction #l0 #l1)))"\n")) (princ(strcat "2ndinhibition: "(itoa(length(l-2ndinhibition #l0 #l1)))"\n")) (princ(strcat "1stinhibition: "(itoa(length(l-1stinhibition #l0 #l1)))"\n"))=> conjunction : 7315 antivalence : 45974 disjunction : 53289 2ndinhibition: 44009 1stinhibition: 1965
Konjunktion + Antivalenz == Disjunktion 2.Inhibition + 1.Inhibition == Antivalenz Das lässt schließen, dass alles richtig tickt. Gruß, Axel Strube-Zettler
------------------ Meine AutoLisp-Seiten Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 19. Aug. 2005 15:42 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Bravo: Auf einen key-search wollte ich auch noch hinweisen, aber das hast du mir sozusagen aus der Tastatur genommen. Der bietet sich übrigens häufig an, wenn Speichermenge keine Rolle spielt. Bleiben nur noch ein paar Anmerkungen, die hier noch fehlen: (1) vl-prin1-to-string macht Axels Funktion princ-to-string-l überflüssig. (2) Bei den von mir vorgestellten Funktionen :l-intersect* macht es durchaus einen Unterschied, welche Liste in den Baum gepackt wird. Die Laufzeit verschlechtert sich, wenn die kürzere Liste dazu verwendet wird, was ja nicht überrascht. Bei Axels Ansatz ist das egal. (3) Verallgemeinere bitte niemand die Resultate im Detail hier auf anderere Programmier-Umgebungen oder Sprachen! Wenn eine Sortierfunktion nicht vom Himmel fällt, wie bei uns das vl-sort, so wird man sehen, dass die grundsätzlichen Konzepte hier eben genau dafür benutzt werden können, diese Funktion ersteinmal zu implementieren. (4) Auch, wenn's weiter oben bereits erwähnt wurde sage ich's nochmal: Index-Searchs, bei denen der Vorteil darin zu sehen ist, dass nur Pointer auf Feldinhalte und nicht die Inhalte selbst verändert werden, funktioniert niemals flott in AutoLisp, weil's hier keine Pointer gibt. (5) Das führt zur Anmerkung, dass die bisher vorgestellten Konzepte zwar gut zu gebrauchen sind, wenn fest vorgegebene Mengen (resp. Listen) in einen Binärbaum gepackt werden sollen, aber nichts bieten, wenn sich diese Menge häufig ändert (hier sind die 'automatisch justierenden' AVL-Bäume vorzuziehen - s. Uwes Anhängsel). Insbes. haben wir noch keien Funktion zum Löschen von Elementen aus einem Baum. Achim Dabrunz ------------------ Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 19. Aug. 2005 16:42 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Zitat: Original erstellt von Dabrunz: vl-prin1-to-string macht Axels Funktion princ-to-string-l überflüssig.
Richtig. Da war ich wohl zu faul zum Ausprobieren;-) Zitat:
die 'automatisch justierenden' AVL-Bäume vorzuziehen - s. Uwes Anhängsel
Da steht aber Ralph drunter, oder? Aber zur Sache: Ich habe mir mal Gedanken über die Implementation eines Rot-Schwarz-Baums in AutoLisp Gedanken gemacht, ja sogar schon angefangen. Aber davon habe ich sehr schnell wieder Abstand genommen. Den Grund will ich noch schnell erläutern: Bei solchen "selbstausgleichenden Bäumen" muss man immer wieder Nodes paarweise gegeneinander tauschen. Dazu stellt AutoLisp aber keine Funktionalität bereit! In anderen Lisp-Dialekten gibt es dafür entsprechende destruktive Funktionen, hier wäre vor allem (setf ...) zu nennen. Nehmen wir an, wir haben einen Node in einem Baum, dann wäre das eine Liste mit 2 Unterlisten: ((<linker-ast> )(<rechter-ast> )) Das setzt sich natürlich in den beiden Ästen genauso fort: (((<linker-ast> )(<rechter-ast> ))((<linker-ast> )(<rechter-ast> ))) Wenn wir (um die Bälle flach zu halten, bleibe ich in der obersten Ebene) den linken gegen den rechten Teilbaum austauschen wollen, müssen wir in AutoLisp schreiben: (setq baum(cons(cdr baum)(car baum)) Sieht harmlos aus, zieht aber das volle Panoptikum der Laufzeit-Abscheulichkeiten nach sich - der ganze Baum wird kopiert, hier zuerst der rechte, dann der linke Teilbaum. Das liegt daran, dass AutoLisp immer 'by value' arbeitet, ein 'by reference' kennt AutoLisp nicht (ausser bei Auswahlsätzen - und ssadd ist destruktiv, aber das nur am Rande). Hat jeder Teilbaum 100000 Knoten, dann haben wir es mit mindestens 400000 internen Operationen zu tun, und die gc hat anschließend noch 200000 Nodes wegzukehren. In XLisp (nur als Beispiel, da ging das *selbstverständlich*) würde man die Knoten so austauschen: (setf dummy(car baum)) (setf(car baum)(cdr baum)) (setf(cdr baum)dummy)) Das sind 10 interne Operationen, und fertig. Ich ziehe daraus den Schluss, dass eine Ausgleichsoperation innerhalb eines Baums zur absoluten Katastrophe wird. Das Ganze wird ja noch viel schlimmer, wenn es tiefer in den Baum hineingeht, denn dann muss man ja den korrigierten Node mit subst hineinflicken. Bei Größenordnungen wie die der Beispiellisten sehe ich da Rechenzeiten von Stunden oder Tagen! Also: Ich lasse mich ja gern belehren, aber hier sehe ich die Grenzen von AutoLisp deutlich überschritten. Solange mir keiner gute Argumente für ein Umdenken bringt, lasse ich die Finger davon oder schreibe das in C. Gruß, Axel Strube-Zettler ------------------ Meine AutoLisp-Seiten Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze
[Diese Nachricht wurde von mapcar am 19. Aug. 2005 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
marc.scherer Ehrenmitglied V.I.P. h.c. CAD-Administrator
Beiträge: 2494 Registriert: 02.11.2001 Windows 10 64bit AutoCAD Architecture 2018/2019 (deu/eng) AEC-Collection 2019 (Revit und Zeugs) Wenn sich's nicht vermeiden läßt: D-A-CH Erweiterung (mies implementierter Schrott)
|
erstellt am: 22. Aug. 2005 08:05 <-- editieren / zitieren --> Unities abgeben:
@mapcar Ui, klasse das rockt. Werde ich mir die Tage mal reinziehen und versuchen das im Detail nachzuvollziehen... Danke. @Achim Auch Dir ein herzliches Danke für all die interessanten Kommentare und Anregungen. ------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
| Anzeige.:
Anzeige: (Infos zum Werbeplatz >>)
|