From: "Jeffrey R. Carter" <spam.jrcarter.not@spam.not.acm.org>
Subject: Linear Search
Date: Wed, 28 Sep 2016 09:41:54 -0700
Date: 2016-09-28T09:41:54-07:00 [thread overview]
Message-ID: <nsgrs8$a1j$1@dont-email.me> (raw)
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
next reply other threads:[~2016-09-28 16:41 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-09-28 16:41 Jeffrey R. Carter [this message]
2016-09-28 17:23 ` Linear Search Niklas Holsti
2016-09-28 18:24 ` Jeffrey R. Carter
2016-09-28 21:03 ` Niklas Holsti
2016-09-28 22:20 ` Jeffrey R. Carter
2016-09-28 20:21 ` Randy Brukardt
2016-09-28 23:08 ` Jeffrey R. Carter
2016-09-29 5:40 ` Randy Brukardt
2016-09-29 4:39 ` Paul Rubin
2016-09-29 4:47 ` Jeffrey R. Carter
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox