1
В настоящее время я выполняю проект, в котором я должен проверять несколько раз, если заданная двумерная точка является «законной», то есть, если она находится в границах сетки, и если она hasn ' ранее посещали. Сетка имеет фиксированный размер H x W, поэтому я думал, что могу хранить их не в наборе, а в 2D-таблице поиска. К моему удивлению, это значительно медленнее, чем проверка наличия в наборе, хотя это (теоретически) операция O(logn), в отличие от O(1) с простым поиском массива.Поиск списка медленнее, чем заданный поиск
Первая попытка:
class PointSet:
def __init__(self, h, w):
if h <= 0 or w <= 0:
raise ValueError("Invalid size")
self.h = h
self.w = w
self.lookup = [[False for _ in range(w)] for _ in range(h)]
self.size = 0
def add(self, point):
r, c = point
self.lookup[r][c] = True
self.size += 1
def remove(self, point):
r, c = point
self.lookup[r][c] = False
self.size -= 1
def __contains__(self, point):
r, c = point
return 0 <= r < self.h and 0 <= c < self.w and self.lookup[r][c]
def __bool__(self):
return self.size != 0
def __len__(self):
return self.size
# H, W = ...
# pointset = PointSet(H, W)
# if (3, 5) in pointset:
# ...
Вторая попытка:
# pointset = set()
# if (3, 5) in pointset:
# ...
Второй код выполняется гораздо быстрее. Почему это так?
У обоих наборов и списков есть сложность «get()(), поэтому я считаю, что разница состоит в том, что наборы являются встроенными (скорее всего, реализованы на C), тогда как ваш пользовательский« PointSet »написан в python и, следовательно, медленнее. –
@Rawing: Это то, о чем я и думал, подумал, что, возможно, я не заметил ничего очевидного, что бы устранить сложность. Спасибо – shooqie
Я заметил, что я увеличиваю размер моего набора каждый раз, когда я вызываю метод 'add()', даже если точка уже была посещена. Это как-то все еще работает в моем коде; однако не изменил время выполнения. – shooqie