Что самый эффективный путь состоит в том, чтобы добавить элемент к списку, только если еще не там?
Разработайте размещенный на первой полосе компонент и корзину, которые не работают исходно в brower. При использовании чего-то как Flex/Flash или Silverlight намного более трудно очистить, и Вы имеете полный контроль над коммуникацией сервера и таким образом можете экранировать содержание полностью от сценаристов.
6 ответов
Если вас беспокоит использование памяти, но вы хотите оптимизировать общий случай, сохраните словарь с последними n точками и их индексами. points_dict = dictionary, max_cache = размер кеша.
def point_to_index(point):
try:
return points_dict.get(point, points.index(point))
except:
if len(points) >= max_cache:
del points_dict[points[len(points)-max_cache]]
points.append(point)
points_dict[points] = len(points)-1
return len(points)-1
Вы хотите использовать набор :
>>> x = set()
>>> x
set([])
>>> x.add(1)
>>> x
set([1])
>>> x.add(1)
>>> x
set([1])
Набор содержит только один экземпляр любого добавляемого вами элемента, и он будет намного эффективнее, чем повторение списка вручную.
Эта страница викибуков выглядит как хороший учебник, если вы раньше не использовали наборы в Python.
Это будет проходить не более одного раза:
def point_to_index(point):
try:
return points.index(point)
except ValueError:
points.append(point)
return len(points)-1
Вы также можете попробовать эту версию, которая учитывает, что совпадения, вероятно, будут ближе к концу списка. Обратите внимание, что reversed () почти не требует затрат даже для очень больших списков - он не создает копию и не просматривает список более одного раза.
def point_to_index(point):
for index, this_point in enumerate(reversed(points)):
if point == this_point:
return len(points) - (index+1)
else:
points.append(point)
return len(points)-1
Вы также можете рассмотреть возможность сохранения параллели dict или набор точек для проверки принадлежности, поскольку оба этих типа могут выполнять тесты принадлежности в O (1). Конечно, это потребовало бы значительных затрат памяти.
Очевидно, если бы точки были упорядочены каким-либо образом, у вас было бы много других вариантов для ускорения этого кода, в частности, используя двоичный поиск для тестов членства.
def point_to_index(point):
try:
return points.index(point)
except:
points.append(point)
return len(points)-1
Обновление: Добавлено в исключении Натана код.
Как говорили другие, рассмотрите возможность использования set или dict. Вы не объясняете, зачем вам индексы. Если они нужны только для назначения уникальных идентификаторов точкам (и я не могу легко найти другую причину их использования), то dict действительно будет работать намного лучше, например,
points = {}
def point_to_index(point):
if point in points:
return points[point]
else:
points[point] = len(points)
return len(points) - 1
На самом деле вам нужен упорядоченный диктант (порядок определяется вставкой ключа):