From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Rusi Newsgroups: gmane.emacs.help Subject: Re: return first element in list with certain property Date: Wed, 22 Nov 2017 06:52:20 -0800 (PST) Message-ID: References: <8660a60zjn.fsf@zoho.com> <87mv3gzndx.fsf@ericabrahamsen.net> <86ine4y7jy.fsf@zoho.com> <874lpozk0y.fsf@ericabrahamsen.net> <8660a4xuou.fsf@zoho.com> <20171121225216.17011915608ecbb6021c9bc2@speakeasy.net> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1511362539 14635 195.159.176.226 (22 Nov 2017 14:55:39 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 22 Nov 2017 14:55:39 +0000 (UTC) Injection-Date: Wed, 22 Nov 2017 14:52:21 +0000 User-Agent: G2/1.0 To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Wed Nov 22 15:55:28 2017 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eHWQp-0002VQ-3E for geh-help-gnu-emacs@m.gmane.org; Wed, 22 Nov 2017 15:55:19 +0100 Original-Received: from localhost ([::1]:39926 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eHWQw-0006BN-8W for geh-help-gnu-emacs@m.gmane.org; Wed, 22 Nov 2017 09:55:26 -0500 X-Received: by 10.55.72.141 with SMTP id v135mr7246579qka.24.1511362341279; Wed, 22 Nov 2017 06:52:21 -0800 (PST) X-Received: by 10.31.157.131 with SMTP id g125mr1890265vke.14.1511362340919; Wed, 22 Nov 2017 06:52:20 -0800 (PST) Original-Path: usenet.stanford.edu!m31no608995qtf.0!news-out.google.com!t48ni1424qtc.1!nntp.google.com!m31no608994qtf.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Original-Newsgroups: gnu.emacs.help In-Reply-To: <20171121225216.17011915608ecbb6021c9bc2@speakeasy.net> Complaints-To: groups-abuse@google.com Original-Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=117.195.51.63; posting-account=mBpa7woAAAAGLEWUUKpmbxm-Quu5D8ui Original-NNTP-Posting-Host: 117.195.51.63 Original-Xref: usenet.stanford.edu gnu.emacs.help:220942 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.21 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" Xref: news.gmane.org gmane.emacs.help:115052 Archived-At: On Wednesday, November 22, 2017 at 9:22:18 AM UTC+5:30, James K. Lowden wro= te: > On Tue, 21 Nov 2017 19:37:01 +0100 > Michael Heerdegen wrote: >=20 > > Philipp Stephani writes: > >=20 > > > Please consider Knuth's statement about premature optimization. > > > Until your users have actually complained about the speed of your > > > product and you have benchmarked it and isolated cl-find-if as the > > > culprit, there's no need to micro-optimize. Presumably cl-find-if > > > has performed two iterations for years or decades without anybody > > > being bothered enough to improve it. > >=20 > > Not only that. Seems the second iteration is at least ~50 times > > faster than the first one (using `elt' that is much faster than a > > loop), so it doesn't matter anyway. If your program is slow, the > > second iteration will never be the culprit. >=20 > Not only that. ;-) Traversing the list twice is still O(n). =20 >=20 > I would guess in elisp the typical list is on the order of a dozen > elements. As Rob Pike says,"Fancy algorithms are slow for small N, and > N is almost always small." =20 >=20 > No matter how long the list is, it traversing it twice will only take > at most twice as long. If your design fails when your data size > doubles, you have problems emacs won't solve. =20 I dont think its quite as simple as that=E2=80=A6 Consider python wherein - C is typically 2 orders of magnitude (hundreds of times) faster than pyth= on - the two can cohabit quite closely; eg moving a ordinary python loop to a= =20 vector numpy operation implicitly moves python to C with corresponding spee= dup (and speed-down due to conversion etc) And so the two versions are not just comparing loop vs loop-loop but loop=E2=82=81 vs loop=E2=82=82 - loop=E2=82=83 where the =E2=82=81=E2=82=82=E2=82=83 can vary across {interpreter, bare-me= tal} we could have all manner of possibilities of speedup and speed-down Sure its not nearly as simple to add C to elisp as to python However it is essentially the same thing: elisp and python are interpreters sitting on top of C. Which in big-O terms means 1 loop vs 2 constant multip= lier vs bare-metal vs interpretive overhead multiplier