3 ms·

I wrote a version in Python: https://gist.github.com/agfor/6225437 https://gist.github.com/agfor/6225437 The original code can be used under CC BY-SA 3.0 since

by agf 13y ago

I wrote a version in Python: https://gist.github.com/agfor/6225437 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 http://stackoverflow.com/a/2468729/500584

Strilanc 13y ago
Nice. Small clarification, you have this: if height < width: result = search_sorted_matrix(zip(*matrix), target) return result and result[::-1] 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'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.
- agf 13y ago
  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) and I've updated the gist to do that. Thanks for pointing it out. The tests are definitely quick & dirty; I'm aware there can be more than one correct answer.

by agf 13y ago

Strilanc 13y ago

Nice. Small clarification, you have this: if height < width: result = search_sorted_matrix(zip(*matrix), target) return result and result[::-1] 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'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.

agf 13y ago
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) and I've updated the gist to do that. Thanks for pointing it out. The tests are definitely quick & dirty; I'm aware there can be more than one correct answer.