Hot News:

Mit Unterstützung durch:

  Foren auf CAD.de (alle Foren)
  Lisp
  Suche nach: Funktionen zur Listenbearbeitung...

Antwort erstellen  Neues Thema erstellen
CAD.de Login | Logout | Profil | Profil bearbeiten | Registrieren | Voreinstellungen | Hilfe | Suchen

Anzeige:

Darstellung des Themas zum Ausdrucken. Bitte dann die Druckfunktion des Browsers verwenden. | Suche nach Beiträgen nächster neuer Beitrag | nächster älterer Beitrag
  
Gut zu wissen: Hilfreiche Tipps und Tricks aus der Praxis prägnant, und auf den Punkt gebracht für Autodesk Produkte
Autor Thema:  Suche nach: Funktionen zur Listenbearbeitung... (3129 mal gelesen)
marc.scherer
Ehrenmitglied V.I.P. h.c.
CAD-Administrator



Sehen Sie sich das Profil von marc.scherer an!   Senden Sie eine Private Message an marc.scherer  Schreiben Sie einen Gästebucheintrag für marc.scherer

Beiträge: 2490
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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities

Hi,
ich suche zwei Funtionen zur Listenbearbeitung wie sie hier: http://www.n-a-n-o.com/lisp/cmucl-tutorials/LISP-tutorial-24.html
erläutert sind.
intersection
und
set-difference

Hat da schon jemand was fertiges?
Oder kennt 'ne Ressource wo so etwas für AutoLisp umgesetzt wurde?

------------------
Ciao,
Marc

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

Jan1
Mitglied
CAD Consultant


Sehen Sie sich das Profil von Jan1 an!   Senden Sie eine Private Message an Jan1  Schreiben Sie einen Gästebucheintrag für Jan1

Beiträge: 17
Registriert: 12.05.2004

erstellt am: 11. Aug. 2005 14:12    Editieren oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

(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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

Vorsicht, diese Funktionen machen ihrem Namen keine Ehre, sie funktionieren nämlich nicht:

Code:

(intersection '(a b c nil (a) (b c)) '(a c nil (b c)))  =>  (A C (B C))

Es sollte aber (A C nil (B C)) dabei rauskommen, da nil in beiden Listen als Element enthalten ist.

Bei aller Liebe zu mapcar - das ist hier völlig fehl am Platze.

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



Sehen Sie sich das Profil von marc.scherer an!   Senden Sie eine Private Message an marc.scherer  Schreiben Sie einen Gästebucheintrag für marc.scherer

Beiträge: 2490
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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities

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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von marc.scherer an!   Senden Sie eine Private Message an marc.scherer  Schreiben Sie einen Gästebucheintrag für marc.scherer

Beiträge: 2490
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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities

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



Sehen Sie sich das Profil von Dabrunz an!   Senden Sie eine Private Message an Dabrunz  Schreiben Sie einen Gästebucheintrag für Dabrunz

Beiträge: 127
Registriert: 28.05.2003

erstellt am: 12. Aug. 2005 17:46    Editieren oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich


beispiel-listen.rar.txt

 
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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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


Sehen Sie sich das Profil von Apply2CAD an!   Senden Sie eine Private Message an Apply2CAD  Schreiben Sie einen Gästebucheintrag für Apply2CAD

Beiträge: 9
Registriert: 05.04.2005

erstellt am: 14. Aug. 2005 19:47    Editieren oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von marc.scherer an!   Senden Sie eine Private Message an marc.scherer  Schreiben Sie einen Gästebucheintrag für marc.scherer

Beiträge: 2490
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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities

@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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

Zitat:
Original erstellt von marc.scherer:
... wollte es aber auch noch verstehen

Als Achim mir sagte, er schreibe grade an einer Antwort mit binären Bäumen und so, habe ich spontan geantwortet, er soll's gleich so verfassen, dass man ein neues Kapitel für meine advanced-Seiten draus machen kann. Das kommt also, und zwar mit etwas mehr Erläuterung!

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



Sehen Sie sich das Profil von Dabrunz an!   Senden Sie eine Private Message an Dabrunz  Schreiben Sie einen Gästebucheintrag für Dabrunz

Beiträge: 127
Registriert: 28.05.2003

erstellt am: 15. Aug. 2005 11:09    Editieren oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von marc.scherer an!   Senden Sie eine Private Message an marc.scherer  Schreiben Sie einen Gästebucheintrag für marc.scherer

Beiträge: 2490
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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities


methods-properties-history.lsp.txt

 
Wofür brauchte ich die Funktionen? http://ww3.cad.de/foren/ubb/Forum145/HTML/001313.shtml#000000

[Diese Nachricht wurde von marc.scherer am 15. Aug. 2005 editiert.]

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

Dabrunz
Mitglied



Sehen Sie sich das Profil von Dabrunz an!   Senden Sie eine Private Message an Dabrunz  Schreiben Sie einen Gästebucheintrag für Dabrunz

Beiträge: 127
Registriert: 28.05.2003

erstellt am: 18. Aug. 2005 10:57    Editieren oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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


Sehen Sie sich das Profil von Apply2CAD an!   Senden Sie eine Private Message an Apply2CAD  Schreiben Sie einen Gästebucheintrag für Apply2CAD

Beiträge: 9
Registriert: 05.04.2005

erstellt am: 18. Aug. 2005 12:02    Editieren oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich


0192_174.doc.txt


0192_174.zip.txt

 
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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von Dabrunz an!   Senden Sie eine Private Message an Dabrunz  Schreiben Sie einen Gästebucheintrag für Dabrunz

Beiträge: 127
Registriert: 28.05.2003

erstellt am: 19. Aug. 2005 15:42    Editieren oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von mapcar an!   Senden Sie eine Private Message an mapcar  Schreiben Sie einen Gästebucheintrag für mapcar

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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities Nur für marc.scherer 10 Unities + Antwort hilfreich

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



Sehen Sie sich das Profil von marc.scherer an!   Senden Sie eine Private Message an marc.scherer  Schreiben Sie einen Gästebucheintrag für marc.scherer

Beiträge: 2490
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 oder löschen Sie diesen Beitrag!  <-- editieren / zitieren -->   Antwort mit Zitat in Fett Antwort mit kursivem Zitat    Unities abgeben: 1 Unity (wenig hilfreich, aber dennoch)2 Unities3 Unities4 Unities5 Unities6 Unities7 Unities8 Unities9 Unities10 Unities

@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 >>)

Darstellung des Themas zum Ausdrucken. Bitte dann die Druckfunktion des Browsers verwenden. | Suche nach Beiträgen

nächster neuerer Beitrag | nächster älterer Beitrag
Antwort erstellen


Diesen Beitrag mit Lesezeichen versehen ... | Nach anderen Beiträgen suchen | CAD.de-Newsletter

Administrative Optionen: Beitrag schliessen | Archivieren/Bewegen | Beitrag melden!

Fragen und Anregungen: Kritik-Forum | Neues aus der Community: Community-Forum

(c)2023 CAD.de | Impressum | Datenschutz