3
\$\begingroup\$

I recently started solving programming challenges and this one is causing me performance trouble. The problem statement is the following:

You are given a 2d matrix where each cell contains an integer weight, a start and an end position. The goal is to find the maximal smallest element from all paths from start to end.

Example

If we consider this example we have the following paths:

  • \$P_1: 14,15,16,1,15,17,17 \min(P_1) = 1\$
  • \$P_2: 14,15,16,1,15,5,17 \min(P_2) = 1\$
  • \$P_3: 14,15,16,18,8,5,17 \min(P_3) = 5\$
  • \$\dots\$
  • \$P_n\$

So the maximal smallest element is \$\max(\min(paths)) = 5\$ as outlined in the picture.

The input has row number of lines and is given in the following form as a .txt file:

row col
start_x start_y
dest_x dest_y
weight weight weight, ...
weight weight weight, ... in total col weights
...

Example input:

3 6
0 0
5 1
14 15 16 1 15 17
12 1 18 8 5 17
3 15 16 4 6 15

with the following restrictions:

  • \$1 \le\$ row, col \$\le 1000\$
  • \$0 \le\$ start_x, dest_x \$\lt\$ row
  • \$0 \le\$ start_y, dest_y \$\lt\$ col
  • \$1 \le\$ weight \$\le 10^9\$

My approach is to solve this with a modified Dijkstra algorithm. Instead of returning the maximal length I change the relaxation step to returning the min of the current position and the neighbour.

I use a max binary heap from the official Python doc which uses the heapq algorithm. To change the min heap to a max heap I just insert with negative priorities. That binary max heap should support extract_min, insert and decrease keys in logarithmic time.

class PriorityQueue(object):

    def __init__(self, t=None):
        self._pq = [] if t is None else t  # list of entries arranged in a heap
        self._entry_finder = {}  # mapping of tasks to entries
        self._REMOVED = '<removed-task>'  # placeholder for a removed task
        self._counter = count()  # unique sequence count

    def add_task(self, task, priority=0):
        """Add a new task or update the priority of an existing task"""
        if task in self._entry_finder:
            self.remove_task(task)
        count = next(self._counter)
        entry = [-priority, count, task]
        self._entry_finder[task] = entry
        heappush(self._pq, entry)

    def remove_task(self, task):
        """Mark an existing task as REMOVED.  Raise KeyError if not found."""
        entry = self._entry_finder.pop(task)
        entry[-1] = self._REMOVED

    def pop_task(self):
        """Remove and return the lowest priority task. Raise KeyError if empty."""
        while self._pq:
            priority, count, task = heappop(self._pq)
            if task is not self._REMOVED:
                del self._entry_finder[task]
                return task
        raise KeyError('pop from an empty priority queue')

    def is_empty(self):
        """Return True if the queue is empty, False otherwise."""
        return not bool(self._pq)

To represent the positions I use a namedtuple Point. The weights get saved in a dict that maps each Point to its weight.

def read_input(filename):
    """Input has row number of lines in the following form:
        # row #col
        start_x start_y
        dest_y dest_y
        weight weight weight, ... in total #col weights

        ;param row, col: int, 1 <= row, col <= 1000
        :param start_x, dest_x: int, 0 <= start_x, dest_x < row
        :param start_y, dest_y: int, 0 <= start_y, dest_y < col
        :param weight: int, 1 <= weight <= 10^9
        :return: dict

        To represent the positions I use a namedtuple "Point". The weights get
        saved in a dict that maps each Point to its weight.
    """
    global row, col
    weights = {}
    with open(filename) as fin:
        for count, line in enumerate(fin):
            if count == 0:
                row, col = (int(i) for i in line.split())
            elif count == 1:
                start_x, start_y = (int(i) for i in line.split())
            elif count == 2:
                dest_x, dest_y = (int(i) for i in line.split())
            else:
                for x, weight in enumerate(line.split()):
                    pos = Point(x, count - 3)
                    weights[pos] = int(weight)
    start = Point(start_x, start_y)
    dest = Point(dest_x, dest_y)
    return weights, start, dest

Now comes my main function that uses Dijkstra by initialising the priority queue and a visited set to check which positions have already been visited:

def find_max_bottleneck(weights, start, dest):
    """Use a modified Dijkstra to find the max bottleneck from start to dest.

    It uses the proposed binary priority queue from
    https://docs.python.org/3.6/library/heapq.html. But as I need a max heap
    I just insert the priorities with negative values. That binary max heap
    should support extract_min, insert and decrease key in logarithmic time.

    As I have v = row*col vertices my algorithm should run in O(v + v*log(v))
    which is equal to O(v*log(v)).

    :param row, col: int
    :param weights: dict from Point -> weight
    :param start, dest: namedtuple Point
    :return: int
    """
    q = PriorityQueue()
    q.add_task(start, weights[start])  # add starting Point to queue
    visited = {}  # set to keep track of visited Points
    while dest != start:  # do until dest is reached
        pos = q.pop_task()
        visited[pos] = True
        t = get_neighbours(pos, row, col)
        for neighbour in t:
            if not visited.get(neighbour, False):
                relax(pos, neighbour, weights, q)
        start = pos
    return weights[dest]

The get_neighbbours and relax functions:

def get_neighbours(pos, row, col):
    """Return a list of neighbours of Point pos. A valid neighbour is one step
    north, one step east, one step south or one step west.
    :param pos: namedtuple Point
    :param row: int
    :param row: col
    :return: list of Points
    """
    t = []
    if pos.x > 0:
        t.append(Point(pos.x - 1, pos.y))
    if pos.y > 0:
        t.append(Point(pos.x, pos.y - 1))
    if pos.x < col - 1:
        t.append(Point(pos.x + 1, pos.y))
    if pos.y < row - 1:
        t.append(Point(pos.x, pos.y + 1))
    return t

def relax(pos, neighbour, weights, q):
    """Computes the min of current position and the neighbour because we look
    for the min bottleneck.

    :param i: int
    :param j: int
    :param weights: list of list
    :param q: Max priority queue
    :param neighbour_index: int
    """
    c = min(weights[neighbour], weights[pos])
    q.add_task(neighbour, c)
    weights[neighbour] = c

The starting bits:

if __name__ == '__main__':
    Point = namedtuple('Point', ['x', 'y'])
    weights, start, dest = read_input('input10.txt')
    bottleneck = find_max_bottleneck(weights, start, dest)
    print(bottleneck)

Edit: To make it work you need the following imports:

from heapq import heappush, heappop
from collections import namedtuple
from itertools import count

My code is working but it is too slow for the extreme cases where row, col = 1000. That means 1 million positions. The time limit is 10 seconds and my solution needs between 20-25 seconds. Why is that? As far as I can tell my algorithm is in \$O(v*log(v))\$ with v = row*col which should be fast enough with the restrictions.

  • Is my algorithm too slow? If there is a better one, you don't need to provide an implementation.

  • Is my implementation too slow? If yes, which part is causing it? Is it the binary heap data structure? Would another data structure like a Fibonacci heap give a huge enough performance gain?

  • Is Python slow? Or in other words: Would an implementation in C++ or Java with the same idea be faster?

  • How well written is my code? I am only using Python since half a year.

You don't need to answer all my questions but these are the ones I am asking myself. In general I am asking for some help if you were in my situation where you finished coding an answer but it is too slow. What do you do? How do you find the parts that are slowing your code down? I tried to use the cProfile module but as I haven't any experience in optimising code I am a bit lost.

Link to the input file that I do not pass in the 10s time limit: input10.txt

Correct result for input10.txt: 231215

\$\endgroup\$
  • \$\begingroup\$ Alternative algorithm: Binary search on the answer. For x, check whether you can reach destination from start using only blocks >=x. Find the largest value of x that works using binary search. \$\endgroup\$ – Raziman T V Feb 6 '17 at 20:13
  • \$\begingroup\$ @RazimanTV Do you mean checking all paths with elements > x? \$\endgroup\$ – tricktron Feb 6 '17 at 22:18
  • \$\begingroup\$ Just check for the existence of such a path. \$\endgroup\$ – Raziman T V Feb 6 '17 at 22:23
  • \$\begingroup\$ @RazimanTV What would be the complexity of your algorithm? \$\endgroup\$ – tricktron Feb 6 '17 at 22:44
  • \$\begingroup\$ O(RC log W) but with low constant factors. \$\endgroup\$ – Raziman T V Feb 7 '17 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.