haskell: a data structure for storing ascending integers with a very fast lookup
- by valya
Hello!
(This question is related to my previous question, or rather to my answer to it.)
I want to store all qubes of natural numbers in a structure and look up specific integers to see if they are perfect cubes.
For example,
cubes = map (\x -> x*x*x) [1..]
is_cube n = n == (head $ dropWhile (<n) cubes)
It is much faster than calculating the cube root, but It has complexity of O(n^(1/3)) (am I right?).
I think, using a more complex data structure would be better.
For example, in C I could store a length of an already generated array (not list - for faster indexing) and do a binary search. It would be O(log n) with lower ?oefficient than in another answer to that question. The problem is, I can't express it in Haskell (and I don't think I should).
Or I can use a hash function (like mod). But I think it would be much more memory consuming to have several lists (or a list of lists), and it won't lower the complexity of lookup (still O(n^(1/3))), only a coefficient.
I thought about a kind of a tree, but without any clever ideas (sadly I've never studied CS). I think, the fact that all integers are ascending will make my tree ill-balanced for lookups.
And I'm pretty sure this fact about ascending integers can be a great advantage for lookups, but I don't know how to use it properly (see my first solution which I can't express in Haskell).
