Python: Быстрое удаление из deque по индексу

Объект deque в python — это коллекция, представляющая собой нечто общее между стеком и очередью. deque (double-ended queue — двусторонняя очередь) позволяют потокобезопасно добавлять и «отщипывать» элементы только с начала и конца коллекции, зато за константное время O(1). Начиная с python 2.5 появилась возможность удалять из коллекции по значению. Я предлагаю свою реализацию удаления — по индексу, которая основана на возможности «вращать» deque и быстрее чем стандартное удаление из deque в 1000 элементов на 60%. Чем длиннее deque тем больше выигрыш производительности.

def deque_remove_by_index(dq,idx):
    l = len(dq)
        if idx<=l*0.5:
            dq.rotate(-idx)
            dq.popleft()
            dq.rotate(idx)
        else:
            dq.rotate(l-1-idx)
            dq.pop()
            dq.rotate(idx-l+1)
Запись опубликована в рубрике Алгоритмы, На заметку с метками , , . Добавьте в закладки постоянную ссылку.

Один комментарий: Python: Быстрое удаление из deque по индексу

  1. Konstantin говорит:

    Быстрее, но уже не thread-safe.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *