enperezzeledon

Obviously, I haven’t forgotten how to keep this blog updated, but I have ignored it for the past 2 years (and before that there was a 6 month delay in posting). There’s been a lot going on in my life these past 2+ years. I’m sure there’s a lot going on in everyone’s lives since ... Read more Software almacen de Cea Ordenadores...

Suppose you have an list of distinct elements which has been sorted and rotated. How would you look up an element within that list? For example, the list: [7, 11, 13, 19, 2, 3, 5] is sorted (the first 7 primes, in order) and rotated (to put 7 first). With this list as input, then: look up 13 returns 2 since 13 is at index 2 look up 2 returns 4 look up 4 returns the sentinel value -1 The obvious technique is to just search the list: def lookup(values, v): try: return values.index(v) except IndexError: return -1 This is a linear algorithm which processes the entire list. Is there…

In the previous article I noted that Python’s heapq module is the only part of standard Python I could think of which deals with sorting, but which doesn’t give you full control over the sort order. That means you need to take care when using a heapq as a priority queue. For example, the A* search algorithm is a best first path finder. It maintains a priority queue of possible steps to take, ordered by an estimate of the total distance of the path routed through these steps. At each stage it pops the next step — the one with the shortest estimated total distance — from the queue, then…