Каков наиболее эффективный способ добавить элемент в список, только если его еще нет?

Question

У меня есть следующий код в Python:

def point_to_index(point):
    if point not in points:
        points.append(point)
    return points.index(point)

Этот код ужасно неэффективен, тем более что я ожидаю, что points будет содержать несколько миллионов элементов.

Если точки нет в списке, я пересекаю список 3 раза:

1. найдите и решите, что его там нет
2. перейти в конец списка и добавить новый элемент
3. идти до конца списка, пока не найду индекс

Если это в списке , я перейду его дважды: 1. найдите и решите, что это там 2. идти почти до конца списка, пока не найду индекс

Есть ли более эффективный способ сделать это? Например, я знаю, что:

• Я с большей вероятностью вызову эту функцию с точкой, которой нет в списке.
• Если точка находится в списке, скорее всего, ближе к концу, чем в начале.

Так что, если бы у меня была строка:

if point not in points:

поиск в списке с конца до начала, это улучшит производительность, когда точка уже находится в списке.

Однако я не хочу делать:

if point not in reversed(points):

потому что я представляю, что reversed(points) само по себе будет стоить огромных затрат.

Также я не хочу добавлять новые точки в начало списка (при условии, что я знал, как это сделать в Python), поскольку это изменило бы индексы, которые должны оставаться постоянными, чтобы алгоритм работал.

Единственное улучшение, которое я могу придумать, - это реализовать функцию всего за один проход, если это возможно от конца до начала. Нижняя строка:

• Есть ли хороший способ сделать это?
• Есть ли лучший способ оптимизировать функцию?

Редактировать: Я получил предложения по реализации этого всего за один проход. Есть ли способ для index() пройти от конца к началу?

Редактировать: Люди спрашивают, почему индекс является критическим. Я пытаюсь описать трехмерную поверхность, используя OFF формат файла . Этот формат описывает поверхность, используя ее вершины и грани. Сначала перечисляются вершины, а грани описываются с использованием списка индексов вершин. Вот почему, когда я добавляю вихрь в список, его индекс не должен меняться.

Редактировать: Были некоторые предложения (например, igor's ) использовать диктовку. Это хорошее решение для сканирования списка. Однако, когда я закончу, мне нужно распечатать список в том же порядке, в котором он был создан. Если я использую dict, мне нужно распечатать ключи, отсортированные по значению. Есть ли хороший способ сделать это?

Редактировать: Я реализовал www.brool.com предложение . Это было самым простым и быстрым. По сути, это заказанный Dict, но без накладных расходов. Производительность отличная!

Answer 1

Вы хотите использовать set :

>>> x = set()
>>> x
set([])
>>> x.add(1)
>>> x
set([1])
>>> x.add(1)
>>> x
set([1])

Набор содержит только один экземпляр любого добавляемого вами элемента, и это будет намного эффективнее, чем повторять список вручную.

Эта страница викибукс выглядит хорошим учебником, если вы ранее не использовали наборы в Python.

Answer 2

Это будет проходить не более одного раза:

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 или set точек для проверки на членство, поскольку оба этих типа могут выполнять тесты на членство в O (1). Конечно, будет существенная стоимость памяти.

Очевидно, что если бы точки были как-то упорядочены, у вас было бы много других возможностей для ускорения этого кода, особенно с помощью бинарного поиска для проверки членства.

Answer 3

Если вы беспокоитесь об использовании памяти, но хотите оптимизировать общий случай, сохраните словарь с последними n точками и их индексами. points_dict = словарь, 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

Answer 4

def point_to_index(point):
    try:
        return points.index(point)
    except:
        points.append(point)
        return len(points)-1

Обновление: Добавлено в код исключения Натана.

Answer 5

То, что вы действительно хотите, это упорядоченный дикт (ключ определяет порядок):

• Рецепт: http://code.activestate.com/recipes/107747/
• PEP: http://www.python.org/dev/peps/pep-0372/

Answer 6

Как уже говорили другие, подумайте об использовании 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