Связанный список Python O (1) вставляет/удаляет

Списки Python являются o (1) для операций в конце списка . Если вы будете делать всю свою вставку в полукопческую моду - по аналогии с C, сохраняя только один указатель в середину списка как «курсор» сортов - вы можете сэкономить себе много усилий Просто используя два списка Python. Один список для того, что перед курсором, один для того, что после; Перемещение курсора включает в себя вытягивание следующего элемента из одного списка и добавления его к другому. Это дает вам произвольную o (1) вставку в расположение курсора, с гораздо менее усилием и переименованием колеса, чем сделать всю новую структуру данных, позволяя вам повторно использовать много существующих функций списка.

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

Редактировать: Вы не серьезно думаете о том, чтобы на самом деле делать «двоичный поиск» в связанном списке, вы? Двоичный поиск даже не имеет смысла на внутренней последовательной структуре данных ...

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

Вот пост блогов , разделяющий вашу боль. Он включает в себя реализацию связанного списка и сравнения производительности.

Возможно Blist было бы лучше, хотя (из здесь )?

Случайные случаи, когда Blist немного медленнее, чем список Python Как следует (o (log n) против o (1)):

1. большой список, который никогда не изменяет длину.
2. Большие списки, где вставки и удаления являются только в конце Список (lifo).

с этим отказ от ответственности, вот некоторые случаи использования, где Блайцы значительно быстрее, чем Встроенный список:

1. вставка или удаление из большого списка (O (LOG N) против O (N))
2. Принимая большие ломтики больших списков (o (log n) vs o (n) )
3. Удаление мелких копий крупных списков (o (1) против O (n))
4. изменение больших ломтиков больших списков (o (log n + log k) против o (n + k))
5. Умножьте список, чтобы сделать большой, редкий список (O (o log k) vs. O (kn))

Обратите внимание, что он фактически реализован как дерево B +, обеспечивая отличную производительность для всех этих операций.

Есть один связанный список здесь (рецепт 17.14 в Python Cookbook 1st Ed), но вряд ли «зрелые» или богатые - это просто делает очередь ФИФО, так что это довольно минимально.

Этот рецепт - очень лаконичная реализация C (только для чтения), подобных ведрам, подобному вкладу - просто автомобиль, CDR и минусы; Опять же, не богатый тип, скорее минимальный (и использовать его для мусорных данных, в отличие от чистого функциональных подходов, вам нужно по меньшей мере добавить setcar и setcdr). Это может быть лучшее отправная точка для вас просто потому, что господа-клетки настолько как общеизвестно гибкие и знакомые.

Некоторые из необходимых вами операций, вероятно, лучше всего сделаны существующими примитивами Python. Например, для сортировки трудно понять, как катиться своим собственным сортировкой может побить производительность сортировки Python (как долго, как вы делаете LinkedList Введите Python Итали, поэтому он хорошо играет с остальной частью языка и библиотеки ;-), учитывая мощность алгоритма Timsort , реализованного в Runtime Python.

Больше в целом я предлагаю вам тщательно Timeit Вещи на каждом шагу по способу рассмотреть вопрос о том, сколько C-кодируемый подход действительно покупает вас (по сравнению с тривиальным C-кодированным, иллюстрированным рецептом в Напечатанная кулинарная книга, URL-адрес которой я даю в начале этого ответа) - это будет важно зависеть от размера и характера списков вашей приложения, поэтому вы лучше всего размещены для организации этих тестов, конечно.

Да еще не видели, но я обнаружил, что встроенный System.diagnostics Traissource и Tracelisteners очень мощные для регистрации. Мы создали ряд высокопроизводительных пользовательских Tracelisteners для разных источников данных, которые мы сохраняем журналы.

Мы включаем и все разные слушатели в файле конфигурации все время. Мы используем преимущества System.diagnostics.correlationmanager, чтобы пройти цепочку исполнения через многие серверы, процессы и потоки через журналы.

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

«Я переполняю переписку в списке (один за другим), используя посетителя на каждой записи, начиная с начала или позиции, найденного бинарным поиском. Когда запись соответствует предикату Найдено, он удален из списка, а затем другой двоичный поиск выполняется на подмножестве списка, начиная с предыдущей позиции удаленной записи «

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

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

Отредактируйте:

Другая структура данных, которая может быть подходящей, является резьбовым двоичным деревом . Это похоже на регулярное двоичное дерево, но каждый узел листьев указывает на следующий / предыдущий поддель, поэтому его можно итерацию, как это эффективно как связанный список. Реализация его в Python остается в качестве упражнения для читателя (или Google).

Это озадачивается, что все требуют обоснования необходимости связанного списка. Связанные списки являются одним из наиболее элементарных структур данных по причине: у них есть свойства, которые отсутствуют другие основные структуры данных, и если вам нужны эти свойства, вам нужен связанный список или один из его близких родственников. Если вы не понимаете, почему связанные списки - это важная структура данных, которая не всегда может быть заменена на детях или двоичное деревом, вы никогда не должны были передавать свой класс «Intro в структуры данных».

Вот быстрая реализация, поддерживая обычные вещи: вставка постоянного времени в любой точке с учетом ссылки на узел, разделение списка в два списка и вставляя список в середину другого списка (SLICE). Поддерживаются универсальные интерфейсы Python: Push, Push, Pushleft, Poopleft, продление, обычная итерация, итерация на ломтике (Getiter).

Я только что написал это, так что до употребления до употребления, но не протестирован продукцией; Возможно, есть все еще ошибки.

def _ref(obj):
    """
    weakref.ref has a bit of braindamage: you can't take a weakref to None.
    This is a major hassle and a needless limitation; work around it.
    """
    from weakref import ref
    if obj is None:
        class NullRef(object):
            def __call__(self): return None
        return NullRef()
    else:
        return ref(obj)

class _node(object):
    def __init__(self, obj):
        self.obj = obj
        self._next = None
        self._prev = _ref(None)
    def __repr__(self):
        return "node(%s)" % repr(self.obj)

    def __call__(self):
        return self.obj

    @property
    def next(self):
        return self._next

    @property
    def prev(self):
        return self._prev()

# Implementation note: all "_last" and "prev" links are weakrefs, to prevent circular references.
# This is important; if we don't do this, every list will be a big circular reference.  This would
# affect collection of the actual objects in the list, not just our node objects.
#
# This means that _node objects can't exist on their own; they must be part of a list, or nodes
# in the list will be collected.  We also have to pay attention to references when we move nodes
# from one list to another.
class llist(object):
    """
    Implements a doubly-linked list.
    """
    def __init__(self, init=None):
        self._first = None
        self._last = _ref(None)
        if init is not None:
            self.extend(init)

    def insert(self, item, node=None):
        """
        Insert item before node.  If node is None, insert at the end of the list.
        Return the node created for item.

        >>> l = llist()
        >>> a = l.insert(1)
        >>> b = l.insert(2)
        >>> d = l.insert(4)
        >>> l._check()
        [1, 2, 4]
        >>> c = l.insert(3, d)
        >>> l._check()
        [1, 2, 3, 4]
        """
        item = _node(item)

        if node is None:
            if self._last() is not None:
                self._last()._next = item
                item._prev = _ref(self._last())
            self._last = _ref(item)
            if self._first is None:
                self._first = item
        else:
            assert self._first is not None, "insertion node must be None when the list is empty"
            if node._prev() is not None:
                node._prev()._next = item
            item._prev = node._prev
            item._next = node
            node._prev = _ref(item)
            if node is self._first:
                self._first = item
        return item

    def remove(self, node):
        """
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> d = l.append(4)
        >>> e = l.append(5)
        >>> l.remove(c) # Check removing from the middle
        3
        >>> l._check()
        [1, 2, 4, 5]
        >>> l.remove(a) # Check removing from the start
        1
        >>> l._check()
        [2, 4, 5]
        >>> l.remove(e) # Check removing from the end
        5
        >>> l._check()
        [2, 4]
        """
        if self._first is node:
            self._first = node._next
        if self._last() is node:
            self._last = node._prev
        if node._next is not None:
            node._next._prev = node._prev
        if node._prev() is not None:
            node._prev()._next = node._next
        node._next = None
        node._prev = _ref(None)
        return node.obj

    def __nonzero__(self):
        """
        A list is true if it has any elements.

        >>> l = llist()
        >>> bool(l)
        False
        >>> l = llist([1])
        >>> bool(l)
        True
        """
        return self._first is not None


    def __iter__(self):
        """
        >>> l = llist([1,2,3])
        >>> [i() for i in l]
        [1, 2, 3]
        """
        return self.getiter(self._first, self._last())

    def _check(self):
        if self._last() is None:
            assert self._last() is None
            return []
        node = self._first
        ret = []
        while node is not None:
            if node._next is None:
                assert node == self._last()
            if node._prev() is None:
                assert node == self._first
            if node._next is not None:
                assert node._next._prev() == node
            if node._prev() is not None:
                assert node._prev()._next == node
            ret.append(node.obj)
            node = node._next
        return ret

    def getiter(self, first, last):
        """
        Return an iterator over [first,last].

        >>> l = llist()
        >>> l.append(1)
        node(1)
        >>> start = l.append(2)
        >>> l.extend([3,4,5,6])
        >>> end = l.append(7)
        >>> l.extend([8,9])
        >>> [i() for i in l.getiter(start, end)]
        [2, 3, 4, 5, 6, 7]
        """
        class listiter(object):
            def __init__(self, first, last):
                self.node = first
                self.final_node = last

            def __iter__(self): return self
            def next(self):
                ret = self.node
                if ret is None:
                    raise StopIteration
                if ret is self.final_node:
                    self.node = None
                else:
                    self.node = self.node._next
                return ret
        return listiter(first, last)

    def append(self, item):
        """
        Add an item to the end of the list.

        >>> l = llist()
        >>> l.append(1)
        node(1)
        >>> l.append(2)
        node(2)
        >>> l._check()
        [1, 2]
        """
        return self.insert(item, None)

    def appendleft(self, item):
        """
        Add an item to the beginning of the list.

        >>> l = llist()
        >>> l.appendleft(1)
        node(1)
        >>> l.appendleft(2)
        node(2)
        >>> l._check()
        [2, 1]
        """
        return self.insert(item, self._first)

    def pop(self):
        """
        Remove an item from the end of the list and return it.

        >>> l = llist([1,2,3])
        >>> l.pop()
        3
        >>> l.pop()
        2
        >>> l.pop()
        1
        >>> l.pop()
        Traceback (most recent call last):
        ...
        IndexError: pop from empty llist
        """
        if self._last() is None:
            raise IndexError, "pop from empty llist"
        return self.remove(self._last())

    def popleft(self):
        """
        Remove an item from the beginning of the list and return it.

        >>> l = llist([1,2,3])
        >>> l.popleft()
        1
        >>> l.popleft()
        2
        >>> l.popleft()
        3
        >>> l.popleft()
        Traceback (most recent call last):
        ...
        IndexError: popleft from empty llist
        """
        if self._first is None:
            raise IndexError, "popleft from empty llist"
        return self.remove(self._first)

    def splice(self, source, node=None):
        """
        Splice the contents of source into this list before node; if node is None, insert at
        the end.  Empty source_list.  Return the first and last nodes that were moved.

        # Test inserting at the beginning.
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> l2 = llist([4,5,6])
        >>> l.splice(l2, a)
        (node(4), node(6))
        >>> l._check()
        [4, 5, 6, 1, 2, 3]
        >>> l2._check()
        []

        # Test inserting in the middle.
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> l2 = llist([4,5,6])
        >>> l.splice(l2, b)
        (node(4), node(6))
        >>> l._check()
        [1, 4, 5, 6, 2, 3]
        >>> l2._check()
        []

        # Test inserting at the end.
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> l2 = llist([4,5,6])
        >>> l.splice(l2, None)
        (node(4), node(6))
        >>> l._check()
        [1, 2, 3, 4, 5, 6]
        >>> l2._check()
        []

        # Test inserting a list with a single item.
        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> l2 = llist([4])
        >>> l.splice(l2, b)
        (node(4), node(4))
        >>> l._check()
        [1, 4, 2, 3]
        >>> l2._check()
        []
        """
        if source._first is None:
            return
        first = source._first
        last = source._last()

        if node is None:
            if self._last() is not None:
                self._last()._next = source._first
            source._first._prev = self._last
            self._last = source._last
            if self._first is None:
                self._first = source._first
        else:
            source._first._prev = node._prev
            source._last()._next = node
            if node._prev() is not None:
                node._prev()._next = source._first
            node._prev = source._last
            if node is self._first:
                self._first = source._first
        source._first = None
        source._last = _ref(None)
        return first, last

    def split(self, start, end=None):
        """
        Remove all items between [node, end] and return them in a new list.  If end is None,
        remove until the end of the list.

        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> d = l.append(4)
        >>> e = l.append(5)
        >>> l._check()
        [1, 2, 3, 4, 5]
        >>> l2 = l.split(c, e)
        >>> l._check()
        [1, 2]
        >>> l2._check()
        [3, 4, 5]

        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> d = l.append(4)
        >>> e = l.append(5)
        >>> l2 = l.split(a, c)
        >>> l._check()
        [4, 5]
        >>> l2._check()
        [1, 2, 3]

        >>> l = llist()
        >>> a = l.append(1)
        >>> b = l.append(2)
        >>> c = l.append(3)
        >>> d = l.append(4)
        >>> e = l.append(5)
        >>> l2 = l.split(b, d)
        >>> l._check()
        [1, 5]
        >>> l2._check()
        [2, 3, 4]
        """
        if end is None:
            end = self._last()

        ret = llist()

        # First, move the region into the new list.  It's important to do this first, or
        # once we remove the nodes from the old list, they'll be held only by weakrefs and
        # nodes could end up being collected before we put it into the new one.
        ret._first = start
        ret._last = _ref(end)

        # Hook our own nodes back together.
        if start is self._first:
            self._first = end._next
        if end is self._last():
            self._last = start._prev

        if start._prev() is not None:
            start._prev()._next = end._next
        if end._next is not None:
            end._next._prev = start._prev
        start._prev = _ref(None)
        end._next = None

        return ret

    def extend(self, items):
        """
        >>> l = llist()
        >>> l.extend([1,2,3,4,5])
        >>> l._check()
        [1, 2, 3, 4, 5]
        """
        for item in items:
            self.append(item)

if __name__ == "__main__":
    import doctest
    doctest.testmod()

класс Python's deque равен 0(1) для вставки и удаления в начале и конце списка.

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

Вы можете соединить новый список в свой список, заменив один элемент. Чтобы вставить список [6, 7, 8] в [1, 2, 3, 4, 5] при индексе 2, вы получите

[1, 2, [3, 6, 7, 8], 4, 5]

, не изменяя длину большого (здесь 5 элемента) списка, у вас нет проблем с скоростью вас в настоящее время имею.

Вы можете «удалить» элемент из списка таким же образом, заменив его с пустым списком.

[1, 2, [], 4, 5]

для случаев повторения этого смешанного списка просты.

def IterateNestedList(xs):
    for x in xs:
        if isinstance(x, list):
            for y in IterateNestedList(x): yield y
        else: yield x