delete does not work

Discussion of Common Lisp

Re: delete does not work

Postby sylwester » Thu Oct 26, 2017 3:07 pm

pjstirling wrote:Using a loop over POP is O(n) in both.


pop does a setq. It won't alter the argument. In my description I'm doing consecutive delete of random elements until I'm at one last using double loop will end up being O(n^2) time and O(1) space. By making the delete O(1), as in hash, you can get it O(n) time in total.

delete is not about time complexity. It's about space complexity. Using remove will cons n^2 times. eg, a small list of a million elements will cons 8TB memory on a 64 bit machine while none by using delete. If you want a functional interface you copy the initial list ie. cons 8MB. It sure beats 8TB memory usage. When you have a copy using delete in place of remove is not possible to detect by the user except perhaps the user gets the result the same day.
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p
sylwester
 
Posts: 127
Joined: Mon Jul 11, 2011 2:53 pm

Re: delete does not work

Postby David Mullen » Fri Oct 27, 2017 3:24 pm

It says something about the appeal and tractability of Lisp's lists that we're talking about million-element lists. I mean, you could argue for a vector because that would halve the per-element overhead. But it's kind of hard to beat the sheer handiness of lists. It's why we all (most of us, anyway) reach for lists first, despite the other structures on the menu. (And, hey, they've worked out pretty well for representing source code.)
David Mullen
 
Posts: 65
Joined: Mon Dec 01, 2014 12:29 pm

Re: delete does not work

Postby sylwester » Sun Oct 29, 2017 12:54 pm

Not using mutating functions is the way to go when developing since you don't want to spend time micro optimizing code that does not need optimization.
delete *is* compatible with remove in every implementation of Common Lisp so I don't understand how you can state remove is more compatible.
As long as you, in the same way as remove, use the returned value you are in the clear with both functions.
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p
sylwester
 
Posts: 127
Joined: Mon Jul 11, 2011 2:53 pm

Previous

Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 2 guests

cron