Mike Simmons wrote:
Ryan McGuire wrote:Integer multiplies are pretty darn fast, but I bet an array lookup is at least a little faster.
Well, you seemed to be showing a hash lookup in some non-Java language, not an array lookup. I don't know how to do an array lookup with a string as key/index. Even if we use a proper array lookup by int index, we need to consider the cost of failed lookups. Like all caching strategies, the effectiveness depends on the ratio of uncached- to previously-cached- lookups.
A bit of a misunderstanding here.
Yes, my first post used a hash lookup. Once Martin pointed it out, I implicitly agreed that a hash lookup is pretty bad. I don't know of any "good" hash functions that A) don't include at least one multiply and B) don't degenerate into just an array lookup. e.g. For integer hash indexes, you could make the hash function return the index itself.
My second post backed away from the hash idea and tried to see if we we could use a plain old array lookup to possibly do better than the straightforward obvious solution.
Again, the solution to this question seems so obvious that I don't see much room for optimization. The only possibilities rely on an assumption or two. e.g. You could use an array to cache squares iff the maximum value is <= the max array size. There are other tricks we could use if we knew that the input array was sorted ahead of time. Also there may be an O(n*n) algorithm that's faster than the obvious linear algorithm for some inputs if we can be sure n is small enough and the input data is repetitive enough: e.g. [56,34,34,45,56,45,56,67,34,45,34,67,78,45,78,56,56,78,34,23,67,23,67,78,56,78,23] might be calculatable using an O(n*n) or O(n logn) algorithm faster than with the obvious O(n) way.