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=-0.4 required=5.0 tests=AC_FROM_MANY_DOTS,BAYES_00 autolearn=no 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!.POSTED!not-for-mail From: "Jeffrey R. Carter" Newsgroups: comp.lang.ada Subject: Linear Search Date: Wed, 28 Sep 2016 09:41:54 -0700 Organization: Also freenews.netfront.net; news.tornevall.net; news.eternal-september.org Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Injection-Date: Wed, 28 Sep 2016 16:41:45 -0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="6df4b173985f7c5c043cea362c370ff7"; logging-data="10291"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/iUXJiDXE0ipkKfrm3db5XKPhs+ukG9lo=" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.3.0 X-Mozilla-News-Host: snews://news.eternal-september.org:563 Cancel-Lock: sha1:msBFPfin6SFRG7YFJl7ZU9TVY+o= Xref: news.eternal-september.org comp.lang.ada:31921 Date: 2016-09-28T09:41:54-07:00 List-Id: 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. -- Jeff Carter "Death awaits you all, with nasty, big, pointy teeth!" Monty Python & the Holy Grail 20