From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!feeder.eternal-september.org!gandalf.srv.welterde.de!news.jacob-sparre.dk!franka.jacob-sparre.dk!pnx.dk!.POSTED!not-for-mail
From: "Randy Brukardt" <randy@rrsoftware.com>
Newsgroups: comp.lang.ada
Subject: Re: Linear Search
Date: Wed, 28 Sep 2016 15:21:30 -0500
Organization: JSA Research & Innovation
Message-ID: <nsh8nk$4qh$1@franka.jacob-sparre.dk>
References: <nsgrs8$a1j$1@dont-email.me> <e52ck2Fos4U1@mid.individual.net>
NNTP-Posting-Host: rrsoftware.com
X-Trace: franka.jacob-sparre.dk 1475094068 4945 24.196.82.226 (28 Sep 2016
 20:21:08 GMT)
X-Complaints-To: news@jacob-sparre.dk
NNTP-Posting-Date: Wed, 28 Sep 2016 20:21:08 +0000 (UTC)
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2900.5931
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.6157
X-RFC2646: Format=Flowed; Response
Xref: news.eternal-september.org comp.lang.ada:31929
Date: 2016-09-28T15:21:30-05:00
List-Id: <comp.lang.ada>

"Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
news:e52ck2Fos4U1@mid.individual.net...
> On 16-09-28 18:41 , Jeffrey R. Carter wrote:
>> This is not really Ada related, but on an Intel Atom x5-Z8500 computer 
>> running
>> Linux Mint 18, I can find the maximum of 70 million random Unsigned_32s
>> (generated using the Threefry RNG), using a sequential linear search, in 
>> about
>> 200 ms. This is fast enough that it appears instantaneous to a human.
>>
>> Since the processor has 4 cores, a parallelization of the search using 8 
>> tasks
>> should be able to search 500 million values in about the same time (if 
>> they fit
>> in memory).
>>
>> I can't imagine any real application in which I would keep that many 
>> values in
>> memory. Usually they'd be in some sort of DB that would do the search for 
>> me. So
>> now I'm wondering if there's really any need for O(log N)-search-time 
>> structures.
>
> Sure there is: when you have to do the search, say, 1000 times per 
> second... because you are servicing 1000 net queries per second...

Or, say compiling Ada and the search is in generated parse tables. (I was 
able to speed up the parsing speed of our compiler by an order of magitude 
by replacing the linear search for the next symbol by a tuned search.)

                                      Randy.