Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:85811 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 1312 invoked from network); 14 Apr 2015 18:35:42 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 14 Apr 2015 18:35:42 -0000 Authentication-Results: pb1.pair.com header.from=php@bof.de; sender-id=pass Authentication-Results: pb1.pair.com smtp.mail=php@bof.de; spf=pass; sender-id=pass Received-SPF: pass (pb1.pair.com: domain bof.de designates 80.242.145.70 as permitted sender) X-PHP-List-Original-Sender: php@bof.de X-Host-Fingerprint: 80.242.145.70 mars.intermailgate.com Received: from [80.242.145.70] ([80.242.145.70:57840] helo=mars.intermailgate.com) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id D9/97-47925-DFD5D255 for ; Tue, 14 Apr 2015 14:35:42 -0400 Received: (qmail 15758 invoked by uid 1009); 14 Apr 2015 20:35:38 +0200 Received: from 209.85.216.54 by mars (envelope-from , uid 89) with qmail-scanner-1.25-st-qms (clamdscan: 0.96.2/20321. spamassassin: 3.3.1. perlscan: 1.25-st-qms. Clear:RC:1(209.85.216.54):. Processed in 0.249722 secs); 14 Apr 2015 18:35:38 -0000 X-Antivirus-MYDOMAIN-Mail-From: php@bof.de via mars X-Antivirus-MYDOMAIN: 1.25-st-qms (Clear:RC:1(209.85.216.54):. Processed in 0.249722 secs Process 15751) Received: from mail-vn0-f54.google.com (gmail@bof.de@209.85.216.54) by mars.intermailgate.com with RC4-SHA encrypted SMTP; 14 Apr 2015 20:35:38 +0200 Received: by vnbg129 with SMTP id g129so6740459vnb.4 for ; Tue, 14 Apr 2015 11:35:36 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.140.94.104 with SMTP id f95mr25938100qge.38.1429036536824; Tue, 14 Apr 2015 11:35:36 -0700 (PDT) Received: by 10.140.49.75 with HTTP; Tue, 14 Apr 2015 11:35:36 -0700 (PDT) Received: by 10.140.49.75 with HTTP; Tue, 14 Apr 2015 11:35:36 -0700 (PDT) In-Reply-To: References: Date: Tue, 14 Apr 2015 20:35:36 +0200 Message-ID: To: Danylo Medinsky Cc: internals Content-Type: multipart/alternative; boundary=001a11394c8e260bb90513b37fd7 Subject: Re: [PHP-DEV] Re: Potential binary search optimization or feature From: php@bof.de (Patrick Schaaf) --001a11394c8e260bb90513b37fd7 Content-Type: text/plain; charset=UTF-8 Am 14.04.2015 20:24 schrieb "Danylo Medinsky" : > > ... until I can determine how much performance will be compromised > from the sorting. Sorting at least has to look at each array element once, and execute the comparison function once. Compare that to a searching scan, which can terminate once it finds the element it is looking for. You would need to remember that the array is already sorted, and make several binary searches (more than log(count(array)), to get a win. But with an arbitrary comparison function you cannot remember whether the array is sorted, because it is only sorted wrt. that specific comparison function. The only scenario where sort-first-then-search can make sense, is when you have to search for several items "in parallel" under a given comparison function, and your number of items to search for is clearly larger than log(count(array)). Patrick --001a11394c8e260bb90513b37fd7--