Searching a Sorted Matrix Faster
twistedoakstudios.com
Searching a Sorted Matrix Faster
1–10 of 11 posts
Re: Searching a Sorted Matrix Faster
#2This is a very interesting article.
A minor quibble - it is very difficult to find a paradigm in which the running time of the proposed algorithm differs from simply choosing the best of the obvious algorithms.
Line at a time takes O( max(w,h) ). Binary searching each row and column separately takes O( min(w,h) log(max(w,h) ). Therefore, implementing both basic algorithms and using the faster one at run-time will run in time O(min(max(w,h), min(w,h)log(max(w,h)).
Which is very close to the proposed run-time - unfortunately so much so that it is very hard to find a sequence of (w,h) for which the proposed algorithm works asymptotically better than simply doing "the obvious thing".
But it is possible! And the lower bounds are nice!
Re: Searching a Sorted Matrix Faster
#3You could also use SMAWK.
Re: Searching a Sorted Matrix Faster
#4Great article. I think considering lower bounds and building intuition of a problem before attempting to solve it is a major step in algorithm design lots of people miss. If you don't really know your problem well, how can you ever be certain that your solution is good, let alone optimal!
Re: Searching a Sorted Matrix Faster
#5This is a very interesting article. A minor quibble - it is very difficult to find a paradigm in which the running time of the proposed algorithm differs from simply choosing the best of the obvious algorithms. Line at a time takes O( max(w,h) ). Binary searching each row and column separately takes O( min(w,h) log(max(w,h) ). Therefore, implementing both basic algorithms and using the faster one at run-time will run…
I (the author) actually did lose a lot of time trying to prove those weren't the same bound! Eventually I found a variable assignment that made it obvious:
let w = n/log(n)
let h = n
(Note: I use ↑ and ↓ as binary operators for max and min.)
(Note: @= means asymptotically equal. Analogous for @Re: Searching a Sorted Matrix Faster
#6This is a very interesting article. A minor quibble - it is very difficult to find a paradigm in which the running time of the proposed algorithm differs from simply choosing the best of the obvious algorithms. Line at a time takes O( max(w,h) ). Binary searching each row and column separately takes O( min(w,h) log(max(w,h) ). Therefore, implementing both basic algorithms and using the faster one at run-time will run…
I (the author) actually did lose a lot of time trying to prove those weren't the same bound! Eventually I found a variable assignment that made it obvious: let w = n/log(n) let h = n (Note: I use ↑ and ↓ as binary operators for max and min.) (Note: @= means asymptotically equal. Analogous for @
Very nice! I'm glad that you worried about this and I have to admit that your asymptotic example is nicer than mine.
Re: Searching a Sorted Matrix Faster
#7You could also use SMAWK.
http://www.egr.unlv.edu/~larmore/Courses/CSC477/monge.pdf
How? That is an algorithm for a completely different problem, which is not obviously reducible to this one.
Re: Searching a Sorted Matrix Faster
#8I wrote a version in Python: https://gist.github.com/agfor/6225437
The original code can be used under CC BY-SA 3.0 since it was posted on Stack Overflow: http://stackoverflow.com/a/2468729/500584
Re: Searching a Sorted Matrix Faster
#9I wrote a version in Python: https://gist.github.com/agfor/6225437 The original code can be used under CC BY-SA 3.0 since it was posted on Stack Overflow: http://stackoverflow.com/a/2468729/500584
Nice.
Small clarification, you have this:
if height I noticed that you noticed col_max_row was redundant with max_row. I was wondering if anyone would. (It used to not be, when I wasn't taking advantage of eliminating rows during the binary search. It made the animations look really dumb, so I fixed that but didn't notice the redundancy.)
Oh, lastly, some of your tests are brittle. search_sorted_matrix(example, 1) is not required to return (0, 0). Tweaking the implementation could conceivable change that to (0,1) or (0, 2). What's important is that M[result] == query.
Re: Searching a Sorted Matrix Faster
#10I wrote a version in Python: https://gist.github.com/agfor/6225437 The original code can be used under CC BY-SA 3.0 since it was posted on Stack Overflow: http://stackoverflow.com/a/2468729/500584
Nice. Small clarification, you have this: if height Does zip(* matrix) complete in constant time, or time proportional to w*h? I was only able to get away with transposing because I used a LazyTranpose method that finished in constant time and added only constant overhead to each access. I noticed that you noticed col_max_row was redundant with max_row. I was wondering if anyone would. (It used to not be, when I wasn…
Yeah, zip is w*h. I meant to replace it once everything was working but forgot. It's simple to write a "TransposedMatrix" wrapper that only adds constant overhead:
class TransposedMatrix(object):
def __init__(self, matrix, index = None):
self.matrix = matrix
self.index = index
def __getitem__(self, index):
if self.index is None:
return TransposedMatrix(self.matrix, index)
return self.matrix[index][self.index]
def __len__(self):
if self.index is None:
return len(self.matrix[0])
return len(self.matrix)
The tests are definitely quick & dirty; I'm aware there can be more than one correct answer.