Search through big list of lists

Question

I have a list of coordinates (x and y like this: coordinates = [[1, 2], [2, 3]] but much bigger) that updates every iteration (appends new list). So I need to search if current_pos (which is also a list like [4, 10]) is in coordinates. Here is my snippet of code:

for move in range(len(movement_string)):
    # ...
    # code changes current_pos
    # ...
    if current_pos in coordinates:
        fail = True
        failed_move = move + 1
        break
    else:
        coordinates.append(current_pos)

It works pretty fine with small lists, but it takes too long time for big lists with 10.000 - 1.000.000 items. I think the problem is in searching through list, because as it becomes bigger, the time it uses becomes also longer.

If the order of `coordinates` does not matter then it can be a set of tuples instead of list of lists. Then `current_pos in coordinates` becomes an O(1) operation instead of O(n) — DeepSpace, Dec 27 '18 at 15:32
@Austin it just a string like `DDRRRULLDL` that says which direction to turn and this changes `current_pos`. — neonfox, Dec 27 '18 at 15:51

score 1 · Accepted Answer · answered Dec 27 '18 at 15:35

just turn coordinates to a set

coordinates = set()

and make current_pos a tuple so you can insert it in a set. At some point:

current_pos = tuple(current_pos)

then your loop becomes:

for move in range(len(movement_string)):
    # ...
    # code changes current_pos
    # ...
    if current_pos in coordinates:
        fail = True
        failed_move = move + 1
        break
    else:
        coordinates.add(current_pos)

and that's it. You get O(1) lookup so it doesn't depend on the length of the coordinates set.

If order matters, just creates a set as above and keep the list too to append to if not already seen (widely covered like here: How do you remove duplicates from a list whilst preserving order?).

I had the same idea exactly. Was worth turning it into an answer — Jean-François Fabre, Dec 27 '18 at 15:37

Search through big list of lists

1 Answers1