chavlji Posted April 21, 2009 Share Posted April 21, 2009 I have list of 1.000.000 elements. Now i have to check each item by each other item: that is 1mio*1mio/2 iterations. Each time it checks if lets say item i is same as item j. If it is it should delete it. And now the problem: 1mio*1mio is... alot It is very time consuming. It is not wise to phisicaly delete items that are same. This would take reconstruction of whole list in memory each time. And it would last forever at that amount of items. It would be wiser to mark same items and delete them afterwards: In C++ I each item of list would be a record consisitng of Deleted:boolean, Value:integer. If two items would be the same I would simply set Deleted value of this item to true. At the end I would go through all items and erase all that has Deleted true. In lisp I would have a list ( (0,21.5) (0,21.2) (0,43.2) (0,23) ... ) where first item of each item would mean deleted (0 at all showned) and second would be the value. But how to set 0 to 1 afterwards ? That is: How to change the certain vales inside lists directly ? Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted April 21, 2009 Share Posted April 21, 2009 Are you saying you want to rid the list of duplicates? Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted April 21, 2009 Share Posted April 21, 2009 If so, this is from CAB: ;; CAB 12/02/05 (defun unique (lst / result) (while (setq itm (car lst)) (setq lst (vl-remove itm lst) result (cons itm result))) result) You may want to reverse the result of this to keep the items in the correct order Quote Link to comment Share on other sites More sharing options...
chavlji Posted April 21, 2009 Author Share Posted April 21, 2009 On 1mio*1mio it would take years this way. It is not right to delete each item along executing. That way the "whole" list will be rewritten lets say 500.000.000.000 times ! Along execution it should only MARK duplicates and construct new list afterwards... But how to MARK an item in lisp? Quote Link to comment Share on other sites More sharing options...
David Bethel Posted April 21, 2009 Share Posted April 21, 2009 A simple form would be: [b][color=BLACK]([/color][/b]defun deldup [b][color=FUCHSIA]([/color][/b]tl / dl[b][color=FUCHSIA])[/color][/b] [b][color=FUCHSIA]([/color][/b]foreach a tl [b][color=NAVY]([/color][/b]if [b][color=MAROON]([/color][/b]not [b][color=GREEN]([/color][/b]member a dl[b][color=GREEN])[/color][/b][b][color=MAROON])[/color][/b] [b][color=MAROON]([/color][/b]setq dl [b][color=GREEN]([/color][/b]cons a dl[b][color=GREEN])[/color][/b][b][color=MAROON])[/color][/b][b][color=NAVY])[/color][/b][b][color=FUCHSIA])[/color][/b] [b][color=FUCHSIA]([/color][/b]reverse dl[b][color=FUCHSIA])[/color][/b][b][color=BLACK])[/color][/b] [b][color=BLACK]([/color][/b]setq l '[b][color=FUCHSIA]([/color][/b]22 33 44 33 44 33 66 77 88 99 22 44 33 22 33 44 33 44 33 66 77 88 99 22 44 33 22 133 144 133 144 133 166 177 88 99 22 44 33 22 33.1 44.1 33.1 44.1 33 66 77 88 99 22 44 33[b][color=FUCHSIA])[/color][/b][b][color=BLACK])[/color][/b] [b][color=BLACK]([/color][/b]prin1 [b][color=FUCHSIA]([/color][/b]deldup l[b][color=FUCHSIA])[/color][/b][b][color=BLACK])[/color][/b] The amount of time would be dictated by how many duplicates that there are. More duplicates = less time Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted April 21, 2009 Share Posted April 21, 2009 That would work but the VL version would be quicker - vl-remove-item takes out all the duplicates of an item in one hit, so you wouldn't need to shuffle through the set. Quote Link to comment Share on other sites More sharing options...
jammie Posted April 21, 2009 Share Posted April 21, 2009 Hey chavlji, What sort of routine are you developing? Is it possible to process and sort the information into smaller lists instead of one large list? Quote Link to comment Share on other sites More sharing options...
ronjonp Posted April 22, 2009 Share Posted April 22, 2009 A simple form would be: [b][color=BLACK]([/color][/b]defun deldup [b][color=FUCHSIA]([/color][/b]tl / dl[b][color=FUCHSIA])[/color][/b] [b][color=FUCHSIA]([/color][/b]foreach a tl [b][color=NAVY]([/color][/b]if [b][color=MAROON]([/color][/b]not [b][color=GREEN]([/color][/b]member a dl[b][color=GREEN])[/color][/b][b][color=MAROON])[/color][/b] [b][color=MAROON]([/color][/b]setq dl [b][color=GREEN]([/color][/b]cons a dl[b][color=GREEN])[/color][/b][b][color=MAROON])[/color][/b][b][color=NAVY])[/color][/b][b][color=FUCHSIA])[/color][/b] [b][color=FUCHSIA]([/color][/b]reverse dl[b][color=FUCHSIA])[/color][/b][b][color=BLACK])[/color][/b] [b][color=BLACK]([/color][/b]setq l '[b][color=FUCHSIA]([/color][/b]22 33 44 33 44 33 66 77 88 99 22 44 33 22 33 44 33 44 33 66 77 88 99 22 44 33 22 133 144 133 144 133 166 177 88 99 22 44 33 22 33.1 44.1 33.1 44.1 33 66 77 88 99 22 44 33[b][color=FUCHSIA])[/color][/b][b][color=BLACK])[/color][/b] [b][color=BLACK]([/color][/b]prin1 [b][color=FUCHSIA]([/color][/b]deldup l[b][color=FUCHSIA])[/color][/b][b][color=BLACK])[/color][/b] The amount of time would be dictated by how many duplicates that there are. More duplicates = less time David, Try using vl-position in these instances. From my experience it's much faster than member since it only returns the index rather than the item and the remaining list. Ron Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted April 22, 2009 Share Posted April 22, 2009 David, is VL available on R12? Quote Link to comment Share on other sites More sharing options...
David Bethel Posted April 22, 2009 Share Posted April 22, 2009 Lee, No VL didn't become available until 2000. -David Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted April 22, 2009 Share Posted April 22, 2009 I see, thanks Lee Quote Link to comment Share on other sites More sharing options...
Se7en Posted April 22, 2009 Share Posted April 22, 2009 On 1mio*1mio it would take years this way.It is not right to delete each item along executing. That way the "whole" list will be rewritten lets say 500.000.000.000 times ! Along execution it should only MARK duplicates and construct new list afterwards... But how to MARK an item in lisp? A list of 1 milion items!? That is a huge amount of data to process! Im not even sure you got enough stack. (Im interested: Have you retrieved this amount of data or is this still theory?) > But how to MARK an item in lisp? You cant/dont; Autolisp high level. You got nothing for control. Quote Link to comment Share on other sites More sharing options...
David Bethel Posted April 22, 2009 Share Posted April 22, 2009 You cant/dont; Autolisp high level. You know it has always surprised me that most people don't understand that AutoLsip is a very high level language. We don't have to do any housekeeping anymore. All of the stack heaps, memory allocations, etc are preset. Even Vl is lower due to fact that you must implicitly load its command module (vl-load-com). I've done a bit assmbly langauge stuff in a past life and man was it complicated, Just to know if was going to be a far call or not. -David Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted April 22, 2009 Share Posted April 22, 2009 What exactly is the difference between "high-level programming languages" as opposed to other languages? Which is the most powerful? Could you give me some info on the whole levels of programming languages please? Quote Link to comment Share on other sites More sharing options...
David Bethel Posted April 22, 2009 Share Posted April 22, 2009 Here's synopsis. -David http://www.webopedia.com/TERM/H/high_level_language.html Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted April 22, 2009 Share Posted April 22, 2009 Thanks David - that clears things up nicely. I never realised LISP was a high-level language.... I always thought high level languages needed much more knowledge to write... but I don't really know all that much in the programming background of things. Quote Link to comment Share on other sites More sharing options...
chavlji Posted April 22, 2009 Author Share Posted April 22, 2009 I did it! I've created ActiveX DLL in Delphi and registered it in Autocad. Now I am sending all needed data to DLL wich is actually creating and processing the list with 1 mio items. It then returns a result to VLISP (a list of about 1000 items). I dont think it could be done in VLISP. Even creating a list of 1 mio items seems to be too much time consuming... i interrupted it after 10 minutes. Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted April 22, 2009 Share Posted April 22, 2009 Again, though - why 1 million items..??? Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.