| |
| Gut zu wissen: Hilfreiche Tipps und Tricks aus der Praxis prägnant, und auf den Punkt gebracht für Autodesk Produkte |
| |
| PNY WIRD VON NVIDIA ZUM HÄNDLER DES JAHRES GEWÄHLT, eine Pressemitteilung
|
Autor
|
Thema: Doppelte Elemente einer Liste finden... (6553 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: 10. Mai. 2004 11:34 <-- editieren / zitieren --> Unities abgeben:
Hi, habe folgende Funktion zum finden doppelter Elemente einer Liste: Code:
(defun DOUBLES? (LST / RETVAL) (foreach ELEM LST (if (> (- (length LST) (length (vl-remove ELEM LST))) 1) (if (not (member ELEM RETVAL)) (setq RETVAL (cons ELEM RETVAL)) ) ;_ end of if ) ;_ end of if ) ;_ end of foreach RETVAL )
Habt's Ihr da was eleganteres/schnelleres? Ohne vl? ------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Brischke Moderator CAD on demand GmbH
Beiträge: 4187 Registriert: 17.05.2001 AutoCAD 20XX, defun-tools (d-tools.eu)
|
erstellt am: 10. Mai. 2004 11:48 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hallo Marc, wozu ist dies: (if (> (- (length LST) (length (vl-remove ELEM LST))) 1) überhaupt drin? Es ist doch gar nicht notwendig, das Element von der Liste zu entfernen Deshalb dann so
Code:
(defun DOUBLES? (LST / RETVAL) (foreach E LST (if (not (member E RETVAL)) (setq RETVAL (cons E RETVAL)) ) ) (reverse RETVAL) ) ;oder an Stelle der (foreach ..) (mapcar '(lambda (E) (if (not (member E RETVAL)) (setq RETVAL (cons E RETVAL)) ) ) LST )
Grüße Holger ------------------ Holger Brischke (defun - Lisp over night! AutoLISP-Programmierung für AutoCAD Da weiß man, wann man's hat! 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: 10. Mai. 2004 12:11 <-- editieren / zitieren --> Unities abgeben:
Hi Holgähr, ich will nicht die doppelten Elemente aus der Liste raushaben, ich will eine Liste zurückhaben die doppelt vorkommende Elemente rauslöscht. Rufe mal meine Funktion mit: (DOUBLES? '(0 1 2 3 4 5 6 6 7 8 9 6 11)) auf... Und dann Deine. Gecheckt? ------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Brischke Moderator CAD on demand GmbH
Beiträge: 4187 Registriert: 17.05.2001 AutoCAD 20XX, defun-tools (d-tools.eu)
|
erstellt am: 10. Mai. 2004 12:45 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hallo Marc, Ok, habe es nicht getestet, nur überflogen und dann geschrieben. Hier deshalb das ganze ohne (vl-..) und so wie du es benötigst. Ich habe das ganze dann auch so gemacht, dass du mal dies und mal jenes als Ergebnis erhältst.
Code:
(defun DOUBLES? (LST WIE / RETVAL CHECK) ;| WIE - T = Liefert die doppelten Einträge der Liste LST WIE - nil = Liefert die nicht doppelt vorhandenen Einträge der Liste LST BSP: (DOUBLES? '(0 1 2 3 4 5 6 6 7 8 9 6 11) T); -> (6) (DOUBLES? '(0 1 2 3 4 5 6 6 7 8 9 6 11) nil); -> (0 1 2 3 4 5 7 8 9 11) |; (foreach E LST (if (and (if WIE (member E (setq LST (cdr LST))) (not (member E (setq LST (cdr LST)))) ) (not (member E CHECK)) ) (setq RETVAL (cons E RETVAL)) ) (setq CHECK (cons E CHECK)) ) (reverse RETVAL) ) (DOUBLES? '(0 1 2 3 4 5 6 6 7 8 9 6 11) T);_-> (6) (DOUBLES? '(0 1 2 3 4 5 6 6 7 8 9 6 11) nil); -> (0 1 2 3 4 5 7 8 9 11)
Grüße Holger ------------------ Holger Brischke (defun - Lisp over night! AutoLISP-Programmierung für AutoCAD Da weiß man, wann man's hat! 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: 10. Mai. 2004 14:32 <-- editieren / zitieren --> Unities abgeben:
Axel? Deine Meinung? Wie ist's mit diesem Ansatz: Code:
(defun DOUBLES? (LST / VAL) (if LST (progn (if (member (setq VAL (car LST)) (cdr LST)) (if (not (member VAL RETVAL)) (setq RETVAL (cons VAL RETVAL)) ) ;_ end of if ) ;_ end of if (DOUBLES? (cdr LST)) ) ;_ end of progn ) ;_ end of if RETVAL ) ;_ end of defun
.. ------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
fuchsi Mitglied Programmierer c#.net Datawarehouse
Beiträge: 1201 Registriert: 14.10.2003 AutoCad Version 2012 deu/enu <P>Windows 7 64bit
|
erstellt am: 10. Mai. 2004 15:36 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
andere Lösung (dbl (list "1" "1" "2" "3" "1" "3")) -> ("3" "1") (defun dbl (lst / retval)
(foreach n1 lst (setq lst (cdr lst)) (if (and (not (member n1 retval)) (member n1 lst)) (setq retval (cons n1 retval))) ) retval ) ------------------ Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
CADwiesel Moderator CAD4FM UG
Beiträge: 1989 Registriert: 05.09.2000 AutoCAD, Bricscad Wir machen das Mögliche unmöglich
|
erstellt am: 10. Mai. 2004 15:40 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|
CAD-Huebner Ehrenmitglied V.I.P. h.c. Verm.- Ing., ATC-Trainer
Beiträge: 9803 Registriert: 01.12.2003 One AutoCAD 2.5 - 2024, AutoCAD, Civil 3D, Win10/Win11
|
erstellt am: 10. Mai. 2004 16:02 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
; Mein Ansatz - entspricht etwa dem von Holger - ; ist doch gut, ausserdem vermutlich schneller als der erste Code (und ohne VL), da sich die Vergleichsliste ja jedesmal um ein Element verkürzt. ; am Ende noch ein Reverse, damit die Reihenfolge der ursprünglichen Liste wiederhergestellt wird. Eine Rekursion für diese Funktion wird schnell unleserlich. Code:
(DEFUN DOUBLE? (lst / elem retval) (WHILE (SETQ elem (CAR lst)) (IF (MEMBER elem (SETQ lst (CDR lst))) (SETQ retval (CONS elem retval)) ) ) (REVERSE retval) )
Gruß Udo Hübner Nachtrag: While mit dem o. a. Vergleich ist problematisch, falls die Liste NIL-Elemente enthalten könnte. Evt. Foreach (wobei ich ungern die abzuarbeitende Liste aus Foreach zur Laufzeit verändere) oder besser die Abbruchbedingung in While so ändern
Code:
(DEFUN DOUBLE? (lst / elem retval) (WHILE lst (SETQ elem (CAR lst)) (IF (MEMBER elem (SETQ lst (CDR lst))) (SETQ retval (CONS elem retval)) ) ) retval )
[Diese Nachricht wurde von CAD-Huebner am 10. Mai. 2004 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
CADwiesel Moderator CAD4FM UG
Beiträge: 1989 Registriert: 05.09.2000 AutoCAD, Bricscad Wir machen das Mögliche unmöglich
|
erstellt am: 10. Mai. 2004 16:33 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 10. Mai. 2004 16:53 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Tag zusammen. Zwar bin ich nicht Axel, aber ein paar Anmerkungen möchte ich dennoch loswerden: _____________________________________________________________________ (1) Der Member-Ansatz Eine verglw. einfache Implementierung, um doppelte Elemente aus einer Liste zu löschen gelingt so: Code:
(defun removeDups-member (#liste / cleanListe) (foreach eintrag #liste (if (not(member eintrag cleanListe)) (setq cleanListe (cons eintrag cleanListe)) ) ) ;** Rückgabe, wenn's auf Reihenfolge ankommt: (reverse cleanListe);** ansonsten reicht: cleanListe )
Die Vorteile dieser Lösung sind neben der Einfachheit der Implementierung: (a) die Erhaltung der ursprünglichen Elementreihenfolge innerhalb der Liste (wenn alle "später" auftauchenden Duplikate mal falsch sind, also weg müssen UND die Liste nicht sowieso sortiert wurde, sondern die Reihenfolge eher zufällig ist); (b) ihr hervorragendes "Best-Case"-Verhalten, denn wenn die Liste NUR aus Duplikaten besteht, braucht dieser Algorithmus genau N (Anzahl der Listen-Elemnete) Vergleiche - das geht ganz sicher nicht mit wenigeren. Der Nachteil ist allerdings nicht ohne, denn das "Worst-Case"-Verhalten (wenn also die Liste KEINE Duplikate besitzt) ist unbrauchbar, wenn mit größeren Listen gearbeitet wird, denn die Rechenzeit steigt quadratisch mit der Anzahl der Listen-Elemnte (heißt auch: "o(N²)" oder "von quadratischer Ordnung"). Solche Algorithmen gelten als in der Praxis kaum einsetzbar. _____________________________________________________________________ (2) Der Sortiert-Ansatz Wenn die List sowieso sortiert wird (ich gehe jetzt mal davon aus, dass sie es bereits ist), dann bietet sich ein Verfahren an, mit dem ich diese Eigenschaft prima ausnutzen kann: Ich überspringe gleiche Nachbar-Elemente beim Zusammensetzen der bereinigten Liste (jetzt mal rekursiv): Code:
(defun removeDups-sorted (#liste) (if #liste;** nur dann macht es Sinn, weiter zu eliminieren ((lambda (erstesElement cleanListe) ;** hier wird jetzt <erstesElement> angefügt, wenn's noch fehlt ** (if (= erstesElement (car cleanListe)) cleanListe (cons erstesElement cleanListe) ) ) (car #liste);** <erstesElement> (removeDups-sorted (cdr #liste));** den Rest bereinigen ) ) )
Diese Verfahren ist optimal, wenn die Daten bereits sortiert sind, weil es in jedem Fall N Vergleiche benötigt, egal, wieviele Duplikate die Liste enthält. Was aber, wenn die Liste nicht sortiert ist? Sortieren! Ein ordendlicher Sortier-Algorithmus benötigt eine Anzahl von Vergeichen in der Größenordnung N*log(N), was i.d.R. besser ist als N² von oben. Allerdings ist das Verfahren nicht direkt anwendbar, wenn die ursprüngliche Reihenfolge erhalten bleiben soll, denn die geht ja durch die Sortierung flöten .. _____________________________________________________________________ Nun bin ich sicher, dass diese beiden Verfahren nicht alle sind, die es auf diesem weiten Globus gibt, aber sie sind beide noch ganz gut nachzuvollziehen. Vielleicht kennt jemand noch ein weiteres? Würde mich freuen, davon zu hören. Wann soll nun aber welches zum Einsatz kommen? Nun ja, wenn ich weiß, dass die Reihenfolge der Listen-Elemente festgelegt ist, ich aber nicht feststellen kann, nach welcher Methode die wohl sortiert wurden (z.B. wenn der Benutzer ZeichenKetten in einer ihm genehmen Anordnung übergibt), dann bleibt mir nur (1) und die Hoffnung, dass die Liste nicht zu lang ist. Genauso werde ich mich für (1) entscheiden, wenn ich as der Struktur der Liste weiß, dass Duplikate eher die Regel denn die Ausnahme sind (z.B. beim Ermitteln der Blocknamen, zu denen es auch eine BlockReferenz in der Zeichnung gibt). Ist die Liste bereits sortiert, dann geht kaum ein Weg an (2) vorbei - das ist dann kaum zu toppen. Wenn auf der anderen Seite allerdings über die zu bereinigende Liste nicht viel bekannt ist, außer, dass sie ziemlich lang werden kann (z.B. eine Liste aller Endpunkte von Linien innerhalb einer Zeichnung), dann ist (2) die bessere Wahl, auch, wenn eine Sortierung der Elemente erfolgen muss, die eigendlich nicht vorgesehen war. Achim Dabrunz [Diese Nachricht wurde von Dabrunz am 12. Mai. 2004 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
CAD-Huebner Ehrenmitglied V.I.P. h.c. Verm.- Ing., ATC-Trainer
Beiträge: 9803 Registriert: 01.12.2003 One AutoCAD 2.5 - 2024, AutoCAD, Civil 3D, Win10/Win11
|
erstellt am: 10. Mai. 2004 23:26 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Zitat: Original erstellt von CADwiesel: die langsamkeit von While dürfte doch Axel zur genüge erklärt haben
Hallo CADwiesel, deine Anmerkung hab ich zum Anlass genommen, das Problem genauer zu untersuchen. Übrigens die Seiten von Axel (mapcar) sind für mich Kult, allerdings hab ich einen Vergleich von Axel zwischen while und foreach aktuell nicht parat und auch auf die Schnelle bei CAD.de und google.de nichts gefunden. Hier mein Test: Ich hab alle hier geposteten Quelltexte (ausser von Dabruns, da hier die Aufgabenstellung nicht getroffen wurde) genommen und einem Laufzeittest unterzogen. Aufgabenstellung war eine Funktion zum Finden doppelter Elemente: FAZIT: Die Funktion von CADwiesel ist die Schnellste, sie erledigt die Aufgabenstellung jedoch nicht korrekt. Bei dem Code wird jedes Element genau 1x in die Rückgabeliste eingefügt, es sollen aber nur die doppelten Elemente genau 1 x eingefügt werden. Mein Code funktioniert, allerdings nur wenn Elemente höchstens dopppelt Vorkommen, da jedes Element (n-1) mal in der Rückgabeliste aufführt wird. Betrachtet man die Performance, liegt mein Code meistens an 2. Stelle, dabei gibt es keinen signifikanten Unterschied zwischen der FOREACH und der WHILE-Schleife. Die Codes von Marc Scherer, Holger Brischke und Fuchsi erledigen die Aufgabenstellung korrekt, auch bei n-maliger Wiederholung der Elemente. Fuchsis Code ist dabei am schnellsten, dicht gefolgt von Holger und Marcs erster Code ist das Schlußlicht. Marcs zweiter, rekursiver Code hat eine gute Geschwindigkeit, allerdings benutzt er eine globale Variable und schafft die letzte Runde auf meinem Rechner überhaupt nicht. Die Codes hab ich geringfügig angepasst, Marcs globale Variable umbenannt und Holgers Rückgabevariante entfernt. Udo Hübner Der Test erfolgte unter Win XP, AutoCAD 2005 deu und P4 2,0 Ghz Test von verschiedenen DOUBLES Routinen mit 10000 Elementen Test beginnt... 0% Doppelte... (DOUB-CADWIESEL 16.329 sec.) (DOUB-HUEBNER1 18.453 sec.) (DOUB-HUEBNER2 18.328 sec.) (DOUB-BRISCHKE 18.515 sec.) (DOUB-FUCHSI 18.407 sec.) (DOUB-SCHERER1 55.093 sec.) (DOUB-SCHERER2 18.313 sec.) 50% Doppelte... Member findet sofort (DOUB-CADWIESEL 4.031 sec.) (DOUB-HUEBNER1 9.063 sec.) (DOUB-HUEBNER2 9.140 sec.) (DOUB-BRISCHKE 17.485 sec.) (DOUB-FUCHSI 4.109 sec.) (DOUB-SCHERER1 65.109 sec.) (DOUB-SCHERER2 13.782 sec.) 50% Doppelte... Member findet zuletzt (DOUB-CADWIESEL 10.265 sec.) (DOUB-HUEBNER1 17.532 sec.) (DOUB-HUEBNER2 17.265 sec.) (DOUB-BRISCHKE 22.485 sec.) (DOUB-FUCHSI 18.406 sec.) (DOUB-SCHERER1 59.547 sec.) (DOUB-SCHERER2 17.937 sec.) 100% Doppelte... (DOUB-CADWIESEL 0.125 sec.) (DOUB-HUEBNER1 0.156 sec.) (DOUB-HUEBNER2 0.172 sec.) (DOUB-BRISCHKE 0.313 sec.) (DOUB-FUCHSI 0.234 sec.) (DOUB-SCHERER1 349.891 sec.) Schwerer Fehler aufgetreten *** Grenze des internen Stapels erreicht (simuliert)
Code:
(defun DOUB-CADWIESEL (LST / VAL RETVAL) (foreach VAL lst (if (not (member VAL RETVAL)) (setq RETVAL (cons VAL RETVAL)) ) ) RETVAL ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (DEFUN DOUB-HUEBNER1 (lst / elem retval) (WHILE lst (SETQ elem (CAR lst)) (IF (MEMBER elem (SETQ lst (CDR lst))) (SETQ retval (CONS elem retval)) ) ) retval ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (DEFUN DOUB-HUEBNER2 (lst / elem retval) (FOREACH elem lst (IF (MEMBER elem (SETQ lst (CDR lst))) (SETQ retval (CONS elem retval)) ) ) retval ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;(DEFUN DOUB-BRISCHKE (LST / RETVAL CHECK) (FOREACH E LST (IF (AND (MEMBER E (SETQ LST (CDR LST))) (NOT (MEMBER E CHECK)) ) (SETQ RETVAL (CONS E RETVAL)) ) (SETQ CHECK (CONS E CHECK)) ) RETVAL ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun DOUB-SCHERER1 (LST / RETVAL) (foreach ELEM LST (if (> (- (length LST) (length (vl-remove ELEM LST))) 1) (if (not (member ELEM RETVAL)) (setq RETVAL (cons ELEM RETVAL)) ) ) ) RETVAL ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun DOUB-SCHERER2 (LST / VAL) ; benutzt *retval* als globale Variable (if LST (progn (if (member (setq VAL (car LST)) (cdr LST)) (if (not (member VAL *RETVAL*)) (setq *RETVAL* (cons VAL *RETVAL*)) ) ) (DOUB-SCHERER2 (cdr LST)) ) ) *RETVAL* ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun DOUB-FUCHSI (lst / retval) (foreach n1 lst (setq lst (cdr lst)) (if (and (not (member n1 retval)) (member n1 lst)) (setq retval (cons n1 retval))) ) retval ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (DEFUN C OUBTEST ( / i Liste1 Liste2 Liste3 funklist start funklist gesamtliste) (PROMPT "\nTest von verschiedenen DOUBLES Routinen mit 10000 Elementen") ; Erstellen der Testliste (SETQ i 1.0) ; reelle Zahlen (REPEAT 5000 (SETQ Liste1 (CONS i (CONS (1+ i) Liste1)) ; 0% doppelt '(1 2 3 4 5 6 7 8 ...) ; Member findet nie einen Member Liste2 (CONS i (CONS i Liste2)) ; 50% doppelt '(1 1 3 3 5 5 7 7 ...) ; Member findet bei 50% nie einen Member, sonst sofort Liste3 (CONS (- 5000 i) (CONS i Liste3)) ; 50% doppelt '(4999 1 4888 2 ...) ; Member findet bei 50% nie einen Member, sonst zuletzt Liste4 (CONS 1.0 (CONS 1.0 Liste4)) ;100% doppelt '(1 1 1 1 1 1 1 1 ...) ; Member findet immer einem Member i (+ 2 i) ) ) (SETQ gesamtliste (LIST (CONS "0% Doppelte..." liste1)(CONS "50% Doppelte... Member findet sofort" liste2)(CONS "50% Doppelte... Member findet zuletzt" liste3)(CONS "100% Doppelte..." liste4))) (SETQ funklist (LIST 'DOUB-CADWIESEL 'DOUB-HUEBNER1 'DOUB-HUEBNER2 'DOUB-BRISCHKE 'DOUB-FUCHSI 'DOUB-SCHERER1 'DOUB-SCHERER2 )) (PRINC "\nTest beginnt...") (FOREACH liste gesamtliste (SETQ *retval* NIL) ; für DOUB-SCHERER2 (PRINC "\n\n") (PRINC (CAR liste)) (FOREACH funk funklist (SETQ start (GETVAR "DATE")) (APPLY funk (list (CDR liste))) (PRINC "\n") (PRINC (LIST funk "\t" (RTOS (* 86400 (- (GETVAR "DATE") start)) 2 3) " sec.")) ) ) (PRINC "\nTest beendet.") (PRIN1) )
Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
CAD-Huebner Ehrenmitglied V.I.P. h.c. Verm.- Ing., ATC-Trainer
Beiträge: 9803 Registriert: 01.12.2003 One AutoCAD 2.5 - 2024, AutoCAD, Civil 3D, Win10/Win11
|
erstellt am: 11. Mai. 2004 07:58 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hier noch eine Variante, die alles andere in den Schatten stellt, da sie mit den Testdaten etva 100 mal schneller als die anderen Funktionen ist: Es wird vorher sortiert, dann kommt man ohne die Member-Funktion aus. Die Funktion benutzt allerdings vl-sort, welches sich bei Integern ungewöhnlich verhält. Zum Vergleich noch mal eine Gegenüberstellung mit Fuchsis Code. [Nachtrag] Dabruns ist zwar nicht Axel, hat die Funktionsweise der Codeansätze und deren Laufzeitverhalten aber ebenso gut erklärt. Sein Code mit Member entspricht dem Code von Cadwiesel. Dieser Code (Wiederholungen werden entfernt) wird sicherlich häufiger zum Einsatz kommen, als der hier getestete Code (sich wiederholende Elemente werden komplett entfernt inklusive des ersten Vorkommens). Ich verteil jetzt für jeden Code 5 Units und für Dabruns gibts von mir 10. [/Nachtrag] Test von verschiedenen DOUBLES Routinen mit 10000 Elementen Test beginnt... 0% Doppelte... (DOUB-HUEBNER3 0.110 sec.) (DOUB-FUCHSI 18.187 sec.) 50% Doppelte... Member findet sofort (DOUB-HUEBNER3 0.047 sec.) (DOUB-FUCHSI 3.937 sec.) 50% Doppelte... Member findet zuletzt (DOUB-HUEBNER3 0.141 sec.) (DOUB-FUCHSI 17.984 sec.) 100% Doppelte... (DOUB-HUEBNER3 0.141 sec.) (DOUB-FUCHSI 0.219 sec.) Test beendet. Zitat: Original erstellt von marc.scherer: Hi Holgähr, ich will nicht die doppelten Elemente aus der Liste raushaben, ich will eine Liste zurückhaben die doppelt vorkommende Elemente rauslöscht. Rufe mal meine Funktion mit: (DOUBLES? '(0 1 2 3 4 5 6 6 7 8 9 6 11)) auf... Und dann Deine. Gecheckt?
Hoppla, aufgrund Marcs erstem Beitrag und seinem Beispielcode haben es wohl alle (ausser Dabruns und Holger Brischke) nicht gescheckt - ähh falsch verstanden. Hier die Codeänderungen für obige Funktion, damit nur die Liste der einfach vorkommenden Elemente zurückgegeben wird.
Code:
(IF (= cnt 0) (SETQ retval (CONS elem retval)) (SETQ cnt 0) )
[Diese Nachricht wurde von CAD-Huebner am 11. Mai. 2004 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: 11. Mai. 2004 09:00 <-- editieren / zitieren --> Unities abgeben:
Hi, vielen Dank erstmal an alle für die heißen Tipps. @CAD-Huebner: Deine finaler Code gibt bei der Liste '("10" "10") nil zurück. Das ist definitiv falsch. Aber vielen Dank für den Testansatz. Echt prima. @Achim: Ab heute schreib' ich natürlich immer nur noch: "A.? Deine Meinung?" Dann fühlt Ihr Euch beide angesprochen :-) ------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
CAD-Huebner Ehrenmitglied V.I.P. h.c. Verm.- Ing., ATC-Trainer
Beiträge: 9803 Registriert: 01.12.2003 One AutoCAD 2.5 - 2024, AutoCAD, Civil 3D, Win10/Win11
|
erstellt am: 11. Mai. 2004 09:15 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Zitat: Original erstellt von marc.scherer: Hi, vielen Dank erstmal an alle für die heißen Tipps. @CAD-Huebner: Deine finaler Code gibt bei der Liste '("10" "10") nil zurück. Das ist definitiv falsch. Aber vielen Dank für den Testansatz. Echt prima.
Dieser finale Code soll doch nur die einfach vorkommenden Elemente einer Liste zurückgeben, aber wenn "10" doppelt vorkommt und die Liste keine weiteren Elemente enthält muss doch NIL zurückkommen -oder hab ich da wieder etwas missverstanden? Udo Hübner Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
CADwiesel Moderator CAD4FM UG
Beiträge: 1989 Registriert: 05.09.2000 AutoCAD, Bricscad Wir machen das Mögliche unmöglich
|
erstellt am: 11. Mai. 2004 09:49 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
ok, Sorry ich hatte nicht alles gelesen aber wenn ich meine Funktion etwas umbaue (defun DOUBLES? (LST / VAL RETVAL neuval) (foreach VAL lst (if (not(member VAL RETVAL)) (setq RETVAL (cons VAL RETVAL)) (if (not(member VAL neuval))(setq neuval(cons VAL neuval))) ) ) neuval ) ist sie immernoch die schnellste und liefert das Richtige Ergebniss. Komischerweise lassen sich die Lispler hier immer mit solch 'Banalen' Dingen locken und laufen zu Höchstformen auf. :crazy
------------------ Gruß CADwiesel Besucht uns im CHAT
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. Mai. 2004 12:12 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hi, nun melde ich mich etwas verspätet doch noch zu Wort, hab das erst eben gelesen... Ein schöner interessanter Thread, ganz nach meinem Geschmack, und ich sehe, dass meine Seiten bei Udo auf fruchtbaren Boden fallen - geht ja auch ohne mich;-) Schöne Profiler-Funktion, Udo! Ein paar Unklarheiten sind aber noch da: Es geht Marc ja offensichtlich nicht darum, die bereinigte Liste zu kriegen, sondern eine Liste der Duplikate. Nun heisst die Funktion aber doubles?! Natürlich sind die Konventionen nicht bindend, jedenfalls im technischen Sinne. Man _KÖNNTE_ die Funktion auch doubles! oder doubles@ oder #§$%&doubles&%$§# - technisch machts keinen Unterschied. ABER: Jeder, der nicht dem AutoLisp-Sumpf entstiegen ist, würde da eine predicate function erwarten. Wenn ich nur wissen will, ob eine Liste Duplikate enthält, muss ich ja nicht alles testen... Aber es geht wohl doch um alle Duplikate, wobei der Unterschied, ob man eine bereinigte Liste zurückhaben oder nur die Duplikate will, für die Tempo-Überlegungen völlig zweitrangig ist. So schön die Tests auch gemacht sind, haben sie doch einen Mangel: Es wird immer mit n=10000 getestet. Aussagefähiger wären aber Vergleiche mit zwei verschiedenen Werten für n (z.B. noch 20000). Das, was Achim mit der Aussage <zitat> Diese Verfahren ist optimal, wenn die Daten bereits sortiert sind, weil es in jedem Fall N Vergleiche benötigt, egal, wievile Duplikate die Lsiste enthält. Was aber, wenn die Liste nicht sortiert ist? Sortieren! Ein ordendlicher Sortier-Algorithmus benötigt eine Anzahl von Vergeichen in der Größenordnung N*log(N), was i.d.R. besser ist als N² von oben. </zitat> gesagt hat, ist der springende Punkt. Der 'best case' ist also gegeben, wenn ein Kandidat für 20000 Elemente doppelt so lange braucht wie für 10000, der 'worst case' wäre hier, dass sich der Rechner in Schweigen hüllt und bis zum jüngsten Tag weiterrechnet;-) Es könnte also sein, dass die Rangordung bei 2*N oder 10*N plötzlich eine ganz andere ist. Udo, mach doch mal bitte... ;-) Man stelle sich einfach ein kleines Diagramm vor: 2 Messwerte durch eine Gerade verbunden. Es ist nicht so erheblich, wo die Gerade liegt, es kommt nur auf den Winkel an! Die flachste Gerade erkläre ich zum (vorläufigen) Testsieger, selbst wenn sie erstmal der 'Verlierer' ist. Ein 'Sorted'-Ansatz ist nämlich sehr wahrscheinlich bei kleinen Datenmengen immer der Verlierer, die Investition ins Sortieren zahlt sich erst ab einer gewissen Grenze aus. Noch besser würde das Diagramm dann mit 3 Messwerten, dann hätte man schon Kurven. Udo, hab ich Tomaten auf den Augen? Wo ist denn die Version HUEBNER3, die alles in den Schatten stellt? Kann ja sein, dass ich noch etwas unfrisch bin, aber ich finde den Code einfach nicht... Aber da sie 'sorted' arbeitet, wundert mich das Ergebnis überhaupt nicht - es bestätigt offensichtlich das, was Achim gesagt hat. Ach ja - auch hier fiel wieder das Stichwort 'vl-' - siehe http://ww3.cad.de/foren/ubb/Forum145/HTML/000563.shtml Gruß, Axel ------------------ Meine AutoLisp-Seiten Meine private Homepage Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Meine Überzeugung... Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 11. Mai. 2004 15:15 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
3 wichtige Anmerkungen fallen mir noch ein: ___________________________________________________________________ (1) Geschwindigkeit ist durchaus das wesendliche Qualitätsmerkmal hier (dass der Code korrekt arbeitet ist ja eine Minimal-Voraussetztung), deshalb ist's gar nicht so schlecht, einmal vl-position an Stelle von member zu versuchen, das sollte noch einen Vorteil bringen. Hier die überarbeiteten Fassung: Zitat:
[..] ich will nicht die doppelten Elemente aus der Liste raushaben, ich will eine Liste zurückhaben die doppelt vorkommende Elemente rauslöscht. [..]
Das ist doch (beinahe) eindeutig oder? Alle Duplikate sollen entfernt werden (a). Allerdings wiederspricht's ein wenig der zuerst geposteten Funktion doubles?, in der ja nur die mehrfach vorkommenden Elemente gelistet wurden (b). Darüber hinaus gibt's ja auch noch die Variante (c), dass all jene Elemente entfernt werden sollen, die mehrfach in der Liste vorkommen (also nur die einmalig vorkommenden Elemente erhalten bleiben) - Zweifel über Zweifel .. Zu (a) hab' ich mich ja schon oben ausgelassen, bleiben noch (b) und (c). Wie Axel bereits feststellte, lassen sich alle Überlegungen zu (a) direkt auf diese Fälle übertragen. Die zugehörigen member-Variationen gab's ja bereits zur Genüge zu lesen, deshalb widme ich mich kurz der sorted-Ausprägung: ___________________________________________________________________ zu (b): Code:
(defun _getDups-sorted (liste erstesElement duplikate) (cond ;** Opt0: Liste leer -> fertig ((not liste) (reverse duplikate)) ;** Opt1: erstesElement taucht nocheinmal auf ist aber noch nicht als ;** Duplikat registriert -> Duplikat registrieren ((and (= erstesElement (car liste)) (/= erstesElement (car duplikate)) ) (_getDups-sorted (cdr liste) (car liste) (cons erstesElement duplikate) ) ) ;** Opt-last: kein neues Duplikat gefunden -> weitersuchen ('sonst (_getDups-sorted (cdr liste) (car liste) duplikate ) ) ) ) ; ;********************************************************** ; (defun getDups-sorted (#liste) (_getDups-sorted (cdr #liste) (car #liste) nil) )
Hier ist natürlich mit vl-sort kein Blumentopf zu gewinnen, denn da werden ja u.U. die Duplikte entfernt. ___________________________________________________________________ zu (c): Code:
(defun _getSingles-sorted (liste erstesElement singles duplikate) (cond ;** Opt0: Liste leer -> fertig ((not erstesElement) (reverse singles)) ;** Opt1: erstesElement taucht nicht nocheinmal auf -> Single registrieren ((and (/= erstesElement (car liste)) (/= erstesElement (car duplikate)) ) (_getSingles (cdr liste) (car liste) (cons erstesElement singles) duplikate ) ) ;** Opt-last: kein neues Unique gefunden -> weitersuchen ('sonst (_getSingles (cdr liste) (car liste) singles (cons erstesElement duplikate) ) ) ) ) ; ;********************************************************** ; (defun getSingles-sorted (#liste) (_getSingles-sorted (cdr #liste) (car #liste) nil nil) )
Achim Dabrunz [Diese Nachricht wurde von Dabrunz am 11. Mai. 2004 editiert.] [Diese Nachricht wurde von Dabrunz am 12. Mai. 2004 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: 11. Mai. 2004 15:33 <-- editieren / zitieren --> Unities abgeben:
Hi Achim, vielen Dank noch mal. Sorry, habe mich etwas verschrieben: "ich will eine Liste zurückhaben die doppelt vorkommende Elemente rauslöscht." Muß natürlich heißen: "ich will eine Liste zurückhaben die doppelt vorkommende Elemente ENTHÄLT." Böses Foul, sorry habe ich im Eifer des Gefechts 'n Wort verbuxelt :-( .. ------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
CAD-Huebner Ehrenmitglied V.I.P. h.c. Verm.- Ing., ATC-Trainer
Beiträge: 9803 Registriert: 01.12.2003 One AutoCAD 2.5 - 2024, AutoCAD, Civil 3D, Win10/Win11
|
erstellt am: 11. Mai. 2004 15:56 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hallo Axel, hatte ich doch tatsächlich vergessen den Code mit dem Sortieransatz zu posten, welcher ungleich schneller war. Hier ist er, deshalb konnte Marc mit meiner Codeänderung 2 Beiträge vorher ja auch gar nichts anfangen. Hab wieder das langsamere While genommen (Tschuldigung Cadwiesel, aber ich hab einen Hang zu While Schleifen), das hier eber keinen signifikanten Nachteil aufweist - oder?
Code:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (DEFUN DOUB-HUEBNER3 (lst / elem retval cnt) ; Achtung, diese Routine funktioniert nicht mit Integern, da ; VL-Sort wiederholte Vorkommen von gleichen Integern nur genau ; einmal zurückgibt. ; Mit Real und String funktioniert es wie vorgesehen ; evt. Typkonvertiwerung durchführen (SETQ lst (vl-sort lst (function (lambda (e1 e2)(<= e1 e2)))) cnt 0 ) (WHILE lst (SETQ elem (CAR lst)) (IF (= elem (CAR (SETQ lst (CDR lst)))) (SETQ cnt (1+ cnt)) (IF (> cnt 0) (SETQ retval (CONS elem retval) cnt 0 ) ) ) ) retval )
Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 11. Mai. 2004 17:10 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
DOUB-HUEBNER3 entspricht vom Ansatz getDups-sorted in einer iterativen Form und sollte dann auch ein vergleichbares Laufzeitverhalten aufweisen. Kannst du bitte nocheinmal deinen Test auf dem selben Rechner abfahren, allerdings mit den neuen Anregungen von Axel und den jetzt vorliegen Funktionen und Verbesserungs-Vorschlagen zusätzlich? - Die Zahlen bleiben dann vergleichbar. Übrigens sind's nicht nur INTEGERS, bei denen vl-sort ungewöhnlich reagiert -> besser nicht innerhalb der Funktion verwenden! 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: 11. Mai. 2004 23:43 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hi Udo, also hatte ich doch keine Tomaten auf den Augen;-) Noch ein Hinweis zum Abstoppen dieser Zeiten: Sehr verlässlich ist das alles nicht - man hat ja keinen Einfluss darauf, wieviel Prozessorzeit man kriegt. Jede noch so kleine Blähung in der Netzwerkleitung usw. verfälscht ganz ordentlich. Wirklich signifikante Daten kriegt man eigentlich nur, wenn man mit großen Datenmengen testet und den Durchschnitt (besser vielleicht sogar das Minimum) aus mindestens 10-20 Durchgängen nimmt. Ach ja, hier eine Funktion, mit der man sich ganz nette sortierte Testdaten fabrizieren kann: Code:
(defun mk-testdata(l s / m n rl c) (setq n 1 c 0) (while(< c l) (setq rl(cons n rl)c(1+ c)) (foreach m s (if(zerop(rem n m)) (setq rl(cons n rl)c(1+ c)) ) ) (setq n(1+ n)) ) rl )
Beispiel: (mk-testdata 1000000 '(3 4 5)) erzeugt eine sortierte Liste mit einer Million Elementen. Über die Liste in der foreach-Anweisung kann man grob steuern, wieviele Mehrfachelemente man drin haben will: (2) <=> Die Hälfte der Zahlen ist doppelt vorhanden (10) <=> Ein Zehntel Doppelte (3 4) <=> 50% (7/12 - 1/12) Doppelte und 1/12 Dreifache (3 4 5) <=> 2/3 Doppelte, 7/60 Dreier und 1/60 Vierer usw. Hand auf's Herz: wer hat schon mal die Funktion (gcd ...) verwendet? Diese Variante ist noch geringfügig schneller als Version 3, weil sie auf den Zähler verzichtet: Code:
(defun get-dups(lst / elem old result) ;(setq lst(vl-sort lst '<=)) (while lst (setq elem(car lst)) (if(= elem(car(setq lst(cdr lst)))) (if(/= elem old) (setq result(cons(setq old elem)result)) ) ) ) result )bzw. (defun remove-dups(lst / elem old result) ;(setq lst(vl-sort lst '<=)) (while lst (setq elem(car lst)) (if(/= elem(car(setq lst(cdr lst)))) (if(/= elem old) (setq result(cons(setq old elem)result)) ) ) ) (cdr result) )
Ich poste sie vor allem deshalb, damit man sieht, dass es für die Tempo-Überlegungen völlig egal ist, ob man die Duplikate oder die clean-list haben will. Der Unterschied ist ja nur das /= und das cdr bei der Rückgabe. Gruß, Axel ------------------ Meine AutoLisp-Seiten Meine private Homepage Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Meine Überzeugung... Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
CAD-Huebner Ehrenmitglied V.I.P. h.c. Verm.- Ing., ATC-Trainer
Beiträge: 9803 Registriert: 01.12.2003 One AutoCAD 2.5 - 2024, AutoCAD, Civil 3D, Win10/Win11
|
erstellt am: 12. Mai. 2004 00:23 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hallo Dabrunz, hallo Axel, ja ich werde die hier veröffentlichten Codes noch einmal testen, hab auch schon angefangen eine grafische Darstellung (mit Punkten) zu erstellen. X Achse Elementanzahl, Y-Achse sec. Das muss ich mir allerdings bis zum Wochenende aufsparen. Werde dann alle relevanten Codes einfließen lassen. Udo Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
barbarossa Mitglied Konstrukteur
Beiträge: 273 Registriert: 21.02.2003
|
erstellt am: 12. Mai. 2004 08:36 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hallo Leute, zu mir: ich habe keine Ahnung vom "LISP"eln. ABER, das Thema dieses Threads finde ich interessant. Meine bescheidene Bitte an Euch: Könnte jemand von Euch vielleicht zu diesem Thema die Problemstellung in allgemeiner sprachneutraler Form formulieren? Als Struktogramm oder eine Art Basic-Struktur (möchte bestimmt keinen hier beleidigen)? Die Aufgabenstellung (doppelte Elemente) ist, denke ich für jedes CAD-System interessant, welches Programmierfähigkeit hat. Aber nicht jedes läßt sich in LISP bedienen. Wer sich des Themas annimmt sei mein Dank gewiß. Gruß Barbarossa 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. Mai. 2004 09:09 <-- editieren / zitieren --> Unities abgeben:
|
CADwiesel Moderator CAD4FM UG
Beiträge: 1989 Registriert: 05.09.2000 AutoCAD, Bricscad Wir machen das Mögliche unmöglich
|
erstellt am: 12. Mai. 2004 09:18 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
@barbarossa Das hier ist ein Lisp Forum und nicht ein "Programme die auf allen CAD Programmen laufen" - Forum. Hier geht es auch nur um Lisp und alle die sich hir beteiligen wissen um was es sich misshandelt. ------------------ Gruß CADwiesel Besucht uns im CHAT
Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Dabrunz Mitglied
Beiträge: 127 Registriert: 28.05.2003
|
erstellt am: 12. Mai. 2004 10:17 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Zitat: Original erstellt von marc.scherer: [..] (GET-DUPS '(3 1 1 3)) Gibt (1) zurück?(remove-DUPS '(3 1 1 2 3 6 9 1 3 6)) Gibt (3 1 9 6 3 2 1 3) zurück?? Irgendwas stimmt da nicht...
Stimmt: Deine Listen! Dieser Algorithmus arbeitet, wie - ich kann mir die süffisante Bemerkung nicht verkneifen - oben das eine oder andere Mal erörtert, nur mir sortierten Listen. Du musst also zuerst sortieren (und diese Zeit bei Untersuchung des Komplexitäts-Verhaltens mit berücksichtigen). 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: 12. Mai. 2004 21:46 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Marc, da teile ich Achims Süffizanz, zumal die Sortierzeile ja (rauskommentiert) drinsteht - das hab ich extra gemacht, dass auch ganz Blinde merken, dass die Funktion sortierte Listen voraussetzt;-) Ja, und damit sind wir schon bei der Frage von Barbarossa: Nein, das kann so wohl keiner. Ein Teil der hier aufgeworfenen Fragen ist sehr AutoLisp-spezifisch, z.B. was den Gebrauch von (member ...) angeht. Sprachunabhängig ist allerdings der von Achim hier dargelegte Ansatz, der sich ja auch eindeutig als der schnellste erwiesen hat. Aber da noch ein Struktogramm draus machen? Das hätte Sinn, wenn es mehrere Kandidaten gäbe, die ihre Stärken und Schwächen haben (wie es z.B. bei den Sortier- oder Kompressionsalgorithmen der Fall ist) - aber die Sachlage ist hier doch so einfach, dass man es mit wenigen Worten zusammenfassen kann: Liste sortieren (egal, ob auf- oder absteigend), und dann alle Elemente rauswerfen, die (Marc::nicht) identisch mit ihrem Nachfolger sind. Listen im Sinne von Lisp-Listen gibt es allerdings nicht per se in jeder Programmiersprache - die VB-Collections sind etwas anderes. Hier geht es um das Konzept der verketteten Listen, d.h. Knotenstrukturen in der Form {Datum, Zeiger}. Der Startknoten entthält das erste Datum und einen Zeiger auf den zweiten Knoten, der wiederum ein Datum sowie den Zeiger auf das dritte Element enthält usw. Das Konzept der (einfach) verketteten Liste bringt es mit sich, dass nun mal der Zugriff auf ein bestimmtes Datum um so langsamer wird, je weiter sich das Datum am Ende der Liste befindet. Es gibt auch doppelt verkettete Listen {Datum, Vorwärtszeiger, Rückwärtszeiger}, die sind in der Mitte am langsamsten - aber nicht in AutoLisp, da gibt es nur den einfachen Typ. Reicht auch;-) Wenn dich das interessiert: Auf meinen AutoLisp-Seiten gibt es ordentliche grafische Darstellungen, wie die Knotenstrukturen in Lisp aufgebaut sind: http://www.autolisp.mapcar.net/lists.html - und (fast) genauso baut man sich eine verkettete Liste auch in anderen Sprachen. Jedenfalss heißt Lisp eben LISt Processing, weil hier die einfach verkettete Liste der zentrale Bestandteil der Sprache ist (in vielen anderen Sprachen ist die verkettete Liste nicht mal im Standard-Lieferumfang enthalten, und zentral ist das Konzept sonst nur in Verwandten wie Scheme oder SysRPL [die Sprache von meinem Taschenrechner, einem HP 48, RPL heisst Reverse Polish Lisp]). Zu Sortier- und ähnlichen Algorithmen kann ich wenig empfehlen. In dem von Achim gepriesenen The Art of Computer Programming ist wohl so einiges drin, ich hab's aber nur mal im Buchladen in der Hand gehabt;-) Dann gibt's noch Sedgewick, Algorithmen in ..., sehr brauchbar. Ich hab die Version 'in C', es gibt aber auch andere Ausgaben für andere Sprachen. Steht wohl überall das Gleiche drin, nur die Beispiele sind anders-codig. Aber es gibt sicherlich noch viel mehr - aber, falls es wirklich um VB geht: da ruhen solche Überlegungen meistens eher in der Schattenzone;-) Gruß, Axel ------------------ Meine AutoLisp-Seiten Meine private Homepage Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Meine Überzeugung... Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 12. Mai. 2004 23:21 <-- editieren / zitieren -->
Zitat: Original erstellt von mapcar: [...] Standard-Lieferumfang enthalten, und zentral ist das Konzept sonst nur in Verwandten wie Scheme oder SysRPL [die Sprache von meinem Taschenrechner, einem HP 48, RPL heisst Reverse Polish Lisp]).
Halt! Stop! Aus irgend einem mir unerfindlichen Grund gibt's wirklich Leute, die HPs RPL als Akronym für Reverse Polish Lisp halten (beim Googeln erbrachte das erschreckend viele Treffer :-(). Das L steht allerdings für Language, und RPL hat nicht wirklich viel mit LISP gemein, außer der umgekehrten polnischen Notation, die man als eine Tautologie nicht mehr extra anführen müsste, wenn es sich wirklich um einen LISP Dialekt handeln würde. Es gibt nun mal kein LISP ohne umgekehrte polnische Notation :-). Da HP die Ergebnisse der jeweiligen Rechenschritte auf einem Stack ablegt und diesen für RPL zugänglich macht, hat RPL sehr viel mehr Ähnlichkeit mit Forth (und somit auch z.B. mit Postscript). In http://c2.com/cgi/wiki?ForthPostscriptRelationship wird es auf den Punkt gebracht: "It seems to me that Forth is to stacks what Lisp is to lists." Gruß Tom Berger ------------------ Architekturwerkzeuge für AutoCAD: http://www.archtools.de |
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: 13. Mai. 2004 08:31 <-- editieren / zitieren --> Unities abgeben:
Hi, @Achim, @Axel: "Süffisanz" Ja, ja, habt ja recht. Haut nur auf mir rum :-(. Habe mir in diesem Thread zwei geistige Totalausfälle geleistet. Sorry. War'n 'n bißchen hektisch an mehreren Sachen gleichzeitig zugange. Kommt nicht wieder vor. ------------------ Ciao, Marc Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Brischke Moderator CAD on demand GmbH
Beiträge: 4187 Registriert: 17.05.2001 AutoCAD 20XX, defun-tools (d-tools.eu)
|
erstellt am: 13. Mai. 2004 08:42 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|
CADwiesel Moderator CAD4FM UG
Beiträge: 1989 Registriert: 05.09.2000 AutoCAD, Bricscad Wir machen das Mögliche unmöglich
|
erstellt am: 13. Mai. 2004 09:09 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Zitat: Habe mir in diesem Thread zwei geistige Totalausfälle geleistet. Sorry. War'n 'n bißchen hektisch an mehreren Sachen gleichzeitig zugange. Kommt nicht wieder vor.
na,na Marc - lehn dich da mal nicht so Weit aus dem Fenster -
------------------ Gruß CADwiesel Besucht uns im CHAT
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: 13. Mai. 2004 09:18 <-- editieren / zitieren --> Unities abgeben:
|
mapcar Mitglied CADmin
Beiträge: 1250 Registriert: 20.05.2002 Time flies like an arrow, fruit flies like a banana (Groucho Marx)
|
erstellt am: 13. Mai. 2004 10:47 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
@marc: Teil 1 glaube ich dir auf's Wort. Ich hab hier grad kürzlich auch ein bisschen am Thema vorbeiargumentiert (ging irgendwie um verschachtelte Blöcke) - aber dass das nicht wieder vorkommt? Wer kann das schon von sich behaupten??? Zu weit aus dem Fenster gelehnt bedeutet Absturzgefahr;-) @tom: Ich kann dir das Gegenteil im Moment nicht beweisen - im Entwicklerhandbuch des 48 habe ich bei einer kurzen Suche grad eben überhaupt keinen Hinweis auf den Namen RPL gefunden. Aber: Der Stack des 48 hat bei RPL die ganz normale Funktion der Parameterübergabe an Funktionen, ich würde sogar behaupten, er spielt da überhaupt nicht die zentrale Rolle wie bei Forth. In RPL kann man ja auch Listen auf den Stack legen... Endgültiges Argument dürfte allerdings dieses sein: Vor ein paar Jahren habe ich meinem 48 einen dicken Speicherchip spendiert und dann - halt dich fest - einen Teil meiner AutoLisp-Bibliothek übertragen. Das bedeutet: Nicht in eine andere Sprache portiert, sondern nur ein wenig angepasst (Zeichensatz, Namenskonventionen, Anpassung an den Port-Speicher usw.). Natürlich nur die allgemeinen Listenfunktionen, entget macht auf einem Taschenrechner wenig Sinn;-) Warum mir hier nun grad RPL als Beispiel einfiel, ist die Tatsache, dass viele meiner Funktionen wie remove-dups, list-shift, list-union, remove-if-not usw. auf dem 48 unbeeindruckt weiterlaufen. Ja, genau dieses hier vorgestellte remove-dups läuft auch auf dem 48, nur SETQ heisst da anders. Es gibt auch APPLY (heißt und funktioniert genauso) und MAPCAR (heisst aber DOSUBS) usw. Tja, wenn das kein LISP ist? Ein ähnlicher Fall wie in Mathematica... Ob nun Reverse Polish Lisp oder Language draufsteht - drin ist's auf jeden Fall! Sonst würde Google auch nicht die 'erschreckend' vielen Treffer liefern;-) Wo ich allerdings geschludert habe, ist das Durcheinanderbringen von RPL und SysRPL (siehste, marc, es passiert!) - ist halt lang, lang her:-( Wenn ich mich jetzt recht erinnere, ist Sys der zugrunde liegende Assembler des SATURN. Gruß, Axel ------------------ Meine AutoLisp-Seiten Meine private Homepage Mein Angriff auf dein Zwerchfell Mein Lexikon der Fotografie Mein gereimtes Gesülze Meine Überzeugung... [Diese Nachricht wurde von mapcar am 13. Mai. 2004 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
GottesGeschenk Mitglied Bauingenieur
Beiträge: 229 Registriert: 23.02.2007 winxp pro sp3 / intel p4 3GHz / 2,5GB RAM / CAD 2011
|
erstellt am: 12. Nov. 2011 12:06 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
hallo LISP-Freunde ich bunutze diese defun: (defun DOUBLES? (LST / VAL RETVAL) (foreach VAL lst (if (not (member VAL RETVAL)) (setq RETVAL (cons VAL RETVAL)) ) ) RETVAL ) (length schnittpunktliste) gibt mir 126 zurück (length (DOUBLES? schnittpunktliste)) gibt mir 103 zurück obwohl ich weiß, dass es 63 sein müssen. die einträge in der schnittpunktliste sind doppelt vorhanden. habt ihr da eine erklärung für? gruß theo Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Meldin Mitglied
Beiträge: 398 Registriert: 15.07.2011 ACA2020 Windows10
|
erstellt am: 12. Nov. 2011 12:26 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|
joern bosse Ehrenmitglied Dipl.-Ing. Vermessung
Beiträge: 1763 Registriert: 11.10.2004 Window 11 ACAD 2021 CIVIL 2021 BricsCAD ab V14 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz 2.80 GHz 32.0GB RAM NVIDIA GeForce MX450<P>
|
erstellt am: 12. Nov. 2011 12:31 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|
GottesGeschenk Mitglied Bauingenieur
Beiträge: 229 Registriert: 23.02.2007 winxp pro sp3 / intel p4 3GHz / 2,5GB RAM / CAD 2011
|
erstellt am: 12. Nov. 2011 12:33 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
diese z.B. (setq liste '((121.825 -230.808 53.7324) (113.455 -231.896 53.7091) (121.825 -230.808 53.7324) (107.585 -232.606 53.6115) (113.455 -231.896 53.7091) (107.585 -232.606 53.6115) (104.722 -232.936 53.5762) (104.722 -232.936 53.5762) (94.9706 -233.975 53.4445) (94.923 -233.979 53.4439) (94.9706 -233.975 53.4445) (94.923 -233.979 53.4439) (76.0698 -235.785 53.6054) (76.0698 -235.785 53.6054) (76.0605 -235.654 53.5231) (76.0053 -234.879 53.1457) (76.0605 -235.654 53.5231) (73.8525 -234.598 52.8909) (76.0053 -234.879 53.1457) (73.8525 -234.598 52.8909) (73.4219 -234.629 52.7494) (73.4219 -234.629 52.7494) (73.0052 -234.658 52.8892) (73.0052 -234.658 52.8892) (70.8203 -235.248 53.1774) (70.8649 -235.877 53.5622) (70.8203 -235.248 53.1774) (70.8649 -235.877 53.5622) (70.8774 -236.054 53.6312) (70.8854 -236.167 53.6457) (67.2632 -236.637 53.6635) (70.8854 -236.167 53.6457) (67.2632 -236.637 53.6635) (54.8797 -237.3 53.6041) (70.8774 -236.054 53.6312) (54.8797 -237.3 53.6041) (54.1507 -237.336 53.6039) (51.8495 -237.43 53.517) (54.1507 -237.336 53.6039) (48.9874 -237.546 53.5219) (51.8495 -237.43 53.517) (48.9874 -237.546 53.5219) (47.1825 -237.607 53.6405) (47.1825 -237.607 53.6405) (40.736 -237.802 53.7021) (40.736 -237.802 53.7021) (24.0416 -237.954 53.5467) (24.0389 -236.665 52.987) (24.0416 -237.954 53.5467) (21.5348 -236.029 52.611) (24.0389 -236.665 52.987) (21.1926 -236.029 52.5912) (21.5348 -236.029 52.611) (20.9501 -236.03 52.6741) (21.1926 -236.029 52.5912) (18.8413 -236.869 53.1467) (12.2425 -237.697 53.4744) (18.8413 -236.869 53.1467) (12.2425 -237.697 53.4744) (20.9501 -236.03 52.6741) (18.882 -236.034 52.6131) (18.8397 -236.044 52.6179) (11.5807 -237.689 53.4489) (10.2591 -237.671 53.3824) (18.882 -236.034 52.6131) (18.8397 -236.044 52.6179) (11.5807 -237.689 53.4489) (10.2591 -237.671 53.3824) (7.55953 -237.636 53.5692) (-0.452754 -237.463 53.6337) (7.55953 -237.636 53.5692) (-0.452754 -237.463 53.6337) (-3.83629 -237.368 53.5981) (-3.83629 -237.368 53.5981) (-4.08484 -237.36 53.5711) (-4.08484 -237.36 53.5711) (-4.41656 -237.349 53.5857) (-4.99833 -237.33 53.5907) (-4.41656 -237.349 53.5857) (-4.99833 -237.33 53.5907) (-25.1654 -236.406 53.5046) (-32.8733 -235.917 53.5089) (-32.9126 -235.908 53.5083) (-32.8733 -235.917 53.5089) (-32.9126 -235.908 53.5083) (-25.1654 -236.406 53.5046) (-32.8808 -235.476 53.4655) (-32.8533 -235.104 53.3187) (-32.8808 -235.476 53.4655) (-32.8144 -234.575 52.878) (-32.8533 -235.104 53.3187) (-32.8144 -234.575 52.878) (-35.7128 -234.006 52.6054) (-35.7128 -234.006 52.6054) (-36.063 -233.98 52.5264) (-36.4034 -233.955 52.6353) (-36.063 -233.98 52.5264) (-36.4034 -233.955 52.6353) (-38.0032 -234.259 52.7927) (-38.0032 -234.259 52.7927) (-38.0524 -234.927 53.2438) (-38.0524 -234.927 53.2438) (-38.0699 -235.165 53.4089) (-38.0851 -235.37 53.4542) (-39.3923 -235.433 53.4621) (-45.6482 -234.92 53.3198) (-38.0699 -235.165 53.4089) (-38.0851 -235.37 53.4542) (-39.3923 -235.433 53.4621) (-51.7153 -234.369 53.3143) (-45.6482 -234.92 53.3198) (-59.9472 -233.547 53.3822) (-51.7153 -234.369 53.3143) (-59.9472 -233.547 53.3822) (-62.6902 -233.25 53.3228) (-62.6902 -233.25 53.3228) (-64.3646 -233.066 53.2946) (-64.3646 -233.066 53.2946) (-65.8116 -232.906 53.324) (-65.8116 -232.906 53.324) (-68.1898 -232.629 53.4) (-75.8717 -231.697 53.3826) (-68.1898 -232.629 53.4) (-88.8914 -229.921 53.3108) (-88.8914 -229.921 53.3108) (-75.8717 -231.697 53.3826)) ) edit: die liste wurde geändert
[Diese Nachricht wurde von GottesGeschenk am 12. Nov. 2011 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Meldin Mitglied
Beiträge: 398 Registriert: 15.07.2011 ACA2020 Windows10
|
erstellt am: 12. Nov. 2011 12:38 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
Hehe, jaja, 66 sind es laut deiner ersten Liste, ist aber auf jeden fall ein Rundungsfehler bzw. das Ergebniss ist richtig nur die Darstellung ist falsch. ------------------ Gruß Wolfgang Alias: Rabbit007 und Wolli1 die aus unerklärlichen Gründen aus dem System hier gelöscht wurden. [Diese Nachricht wurde von Meldin am 12. Nov. 2011 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Meldin Mitglied
Beiträge: 398 Registriert: 15.07.2011 ACA2020 Windows10
|
erstellt am: 12. Nov. 2011 12:39 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|
joern bosse Ehrenmitglied Dipl.-Ing. Vermessung
Beiträge: 1763 Registriert: 11.10.2004 Window 11 ACAD 2021 CIVIL 2021 BricsCAD ab V14 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz 2.80 GHz 32.0GB RAM NVIDIA GeForce MX450<P>
|
erstellt am: 12. Nov. 2011 12:40 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|
GottesGeschenk Mitglied Bauingenieur
Beiträge: 229 Registriert: 23.02.2007 winxp pro sp3 / intel p4 3GHz / 2,5GB RAM / CAD 2011
|
erstellt am: 12. Nov. 2011 12:44 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
danke für die antworten schon mal (setq durchstoßpunkt (cal "ILP(p1,p2,p3z,p4z,p5z)")) (setq schnittpunktliste (append (list durchstoßpunkt) schnittpunktliste)) damit stellte ich die liste zusammen die schnittpunktliste ist 132 lang die (double? schnittpunktliste) ist 103 lang, statt 66. Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
GottesGeschenk Mitglied Bauingenieur
Beiträge: 229 Registriert: 23.02.2007 winxp pro sp3 / intel p4 3GHz / 2,5GB RAM / CAD 2011
|
erstellt am: 12. Nov. 2011 12:50 <-- editieren / zitieren --> Unities abgeben: Nur für marc.scherer
|