Re: Linear Search

["Randy Brukardt" <randy@rrsoftware.com>]

"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.