The story I linked to yesterday on a quantum computing development says this:
If a traditional computer were given the task of looking up a person's phone number in a telephone book, it would look at each name in order until it found the right number.
That's just stupid. The phonebook is in order for a start. So at worst, you'd use a binary search (but there are better things to do than that). That's already "exponentially better" (using their own words).
4 comments:
I'd love to see the day when we can give a computer a task stated in plain English, like "look up this person's number in the phone book", and it will successfully (and efficiently) perform it. In the meantime, I'll stick with good programming by humans to solve well-defined problems. Rather depressing how little people understand computers, isn't it?
How well does a binary search algorithm lend itself to parallel processing?
What if you split up the hpone book into equal sized segments and have each processor run it's own search on it? Would you see proportional gains in performance with all searching algorithms, or would you only notice gains if you have each processor read entries in order?
binary search on its own can be adapted to parallel processing (for example, by going down a few nodes and handing subtrees to each processor), but it would work much better on something like, say, an indexed/radix search (one of the better things that I mentioned) - i.e. "splitting up the phone book".
You don't have to search each sub-piece sequentially; you can still use hash tables or red-black trees or whatever other nifty data structure you have to hand.
Of course all of this discussion is what you can do with purely "ordinary" computers. A quantum computer ought to be able to achieve these kind of savings and quite a bit more.
Post a Comment