From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Pascal J. Bourguignon" Newsgroups: gmane.emacs.help Subject: Re: How to delete all nil properties from a plist? Date: Thu, 06 Aug 2015 01:30:50 +0200 Organization: Informatimago Message-ID: <87mvy5nwid.fsf@kuiper.lan.informatimago.com> References: <87oaiq3buh.fsf@mbork.pl> <87mvya3bij.fsf@mbork.pl> <871tfmv5d5.fsf@kuiper.lan.informatimago.com> <87si81u09e.fsf@kuiper.lan.informatimago.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1438817728 8207 80.91.229.3 (5 Aug 2015 23:35:28 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 5 Aug 2015 23:35:28 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Thu Aug 06 01:35:24 2015 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ZN8DU-00073H-E3 for geh-help-gnu-emacs@m.gmane.org; Thu, 06 Aug 2015 01:35:24 +0200 Original-Received: from localhost ([::1]:42779 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZN8DT-0002mX-Fr for geh-help-gnu-emacs@m.gmane.org; Wed, 05 Aug 2015 19:35:23 -0400 Original-Path: usenet.stanford.edu!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 78 Original-X-Trace: individual.net +y5TlyB7+yJvEG0ePP12CQE+6PHXnK069Ivy+E8bnjECZTa65p Cancel-Lock: sha1:ZTAwMjJjYmJlNTNlZTgzYTgyZjFhN2ZkZWUwZTRmNjFiZTkyOGE2MQ== sha1:GegrstdNuVPc1bcGGn3L0c6m2jU= Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) Original-Xref: usenet.stanford.edu gnu.emacs.help:213989 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:106274 Archived-At: Emanuel Berg writes: > "Pascal J. Bourguignon" > writes: > >>>> This is horrible. Again, you can't prevent >>>> yourself writing O(n²) code when O(n) would >>>> do perfectly. >>> >>> Is it `append' or `butlast' that is linear as well? >> >> Both. > > OK! > > It would be useful to have a list with the time > complexities of all the list operators. Because here > (with `append' and `butlast') it isn't clear from what > those functions do that they are linear. On the > contrary: if we think of an open bike chain in > a workshop, then to put another link at either end > isn't linear, it is O(1), as is removing a link from > either end. Depends on what end of the chain you hold. To make it easier, imagine this bike chain, but 10 km long, obviously, you have one end in hand, and the other is stored three workshop beyond. To find this other end, you have to go thru each link. O(n). There is no such list of complexities because: 1- it is obvious. When you've studied lisp, you have implemented most of them. 2- in most cases, the algorithms are not specified, so an implementation would be free to provide something more efficient, if it was possible. 3- there is some expectations on the part of CL users, and sometimes an implementation may use a worse algorithm. Then its users will complain and a better algorithm is implemented. So mostly all implementations have similar time and space complexities. Nonetheless, if you find it would be useful to have such a list, you can establish it. There are 636 functions in CL. If you research the best algorithms for each, noting the time and space complexities, and finding what complexities and (approximate) actual factors each implementation provide, for 2 functions each day, you will be done in less than a year. > So I think my algorithm is actually linear (but not > the implementation you saw) if only I replaced those > functions with manually re-linking the items (because > if the list is built manually, the last item could be > stored, and then linked further to in constant time > which would imply appending to the list as that item > is already part of the list, the last part) - I don't > know how to do that right now, perhaps I'll be back if > I don't find something else to do... Absolutely. Also, notice that doing that, or consing onto the beginning of the list and calling nreverse when you're done are equivalent time-complexity wise. There may be some difference re: cache in actual contemporaneous computers but it can be seen only on very long lists. -- __Pascal Bourguignon__ http://www.informatimago.com/ “The factory of the future will have only two employees, a man and a dog. The man will be there to feed the dog. The dog will be there to keep the man from touching the equipment.” -- Carl Bass CEO Autodesk