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!newsfeed.kamp.net!newsfeed.kamp.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups: comp.lang.ada
Subject: Re: Linear Search
Date: Wed, 28 Sep 2016 19:23:14 +0200
Organization: Tidorum Ltd
Message-ID: <e52ck2Fos4U1@mid.individual.net>
References: <nsgrs8$a1j$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net sfmII6C4cX161MGiZS0uFwMgm96kO7pSfVa6Qvt9kxXr7Xg4ZZ
Cancel-Lock: sha1:bvEjxfyG1RYKatn8JChO08ptc44=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:45.0)
 Gecko/20100101 Thunderbird/45.3.0
In-Reply-To: <nsgrs8$a1j$1@dont-email.me>
Xref: news.eternal-september.org comp.lang.ada:31922
Date: 2016-09-28T19:23:14+02:00
List-Id: <comp.lang.ada>

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

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .