How to compare two elements in a list in constant time

Suppose I have a list of elements like [5, 3, 1, 2, 4], and I want to compare two elements by position. Whichever comes first in the list is greater, or true. So:

compare(5, 3) 开发者_开发知识库# true
compare(2, 1) # false
compare(3, 4) # true

How can I do that in constant time? One way I thought of doing this was using maps, where the key is the element and the value is the position in the list:

order = {5: 0, 3: 1, 1: 2, 2: 3, 4: 4}

Then we have amortized O(1) time, but this will be O(N) space. Does anyone have a more elegant solution?

Your map idea looks pretty good. The fact that a map is O(N) for memory shouldn't be a problem, because you can't get less than O(N) unless you use compression techniques (a list is O(N) as well).

Also, since the map stores the indices of each element, you could forget about the original list, and just use the map. That is, unless you need the list for some reason. Even if you need to insert an element into the middle (say at position 3), you can update the map in linear time just by iterating over the element and incrementing the necessary indices.

So, the map looks to be just as efficient a solution as the list for basic operations, with the added awesomeness of an O(1) compare function. As for elegance, the map is pretty hard to beat since it doens't require any extra work beyond what's described here.

If you have to start from a list and you are only doing the operation a few times, use:

def compare(ls, n1, n2):
    return ls.index(n1) > ls.index(n2)

If you can choose the representation beforehand, or if you will need to do this many times with the same list, do what you did with the dictionary.

Remember also that the list uses O(N) space, so the addition of O(N) space of the dictionary is no big deal.

correction: the compare function above will take O(1) time, because accesses in python take O(1) time, see http://wiki.python.org/moin/TimeComplexity