Skip to content

Оптимизация Append

Представьте, что у нас есть пользователь, который прокручивает свои страницы Feed, как в любой другой социальной сети. Поскольку посты упорядочены в хронологическом порядке на основе publishDate, Feed будет расти все больше и больше по мере того, как пользователь прокручивает его и все больше Post’ов прикрепляется к Feed. Учитывая подход, мы взяли функцию Append, так как чем длиннее Feed, тем длиннее будет становиться Append. Почему? Потому что мы должны обойти все Feed, чтобы добавить в конце Post. Если ты слышал о нотации Big-O, этот алгоритм имеет O(n) временную сложность, а это означает, что он всегда будет проходить через все Feed, прежде чем к нему добавится Post.

Это может быть неэффективно, особенно если Feed становится довольно длинным. Как же мы можем улучшить функцию Append и уменьшить ее асимптотическую сложность?

Видите ли, поскольку наша структура данных Feed представляет собой просто список Post’ов, чтобы пройти по ней, нам нужно знать начало списка (называемого start), который является указателем типа Post. Поскольку в нашем примере Append всегда добавляется Post в конец Feed, мы могли бы значительно улучшить производительность алгоритма, если бы знали не только о его элементе start, но и об этом элементе end. Конечно, всегда есть компромисс с оптимизацией, и компромисс здесь заключается в том, что структура данных будет потреблять немного больше памяти (для нового атрибута в структуре Feed).

Расширить нашу структуру данных Feed довольно просто:

Но наш алгоритм Append нужно будет настроить для работы с новой структурой файла Feed. Это версия Append использует атрибут end Post:

Выглядит немного проще, не так ли? Итак, хорошие новости:

  1. Код стал проще и короче.
  2. Мы значительно улучшили временную сложность функции.

Теперь алгоритм делает две вещи. Если Feed пустой, он устанавливает новый Post как начало и конец элемента Feed. В противном случае он устанавливает новый Post как элемент end и прикрепляет его к предыдущему Post в списке. Вдобавок к тому, насколько он прост, этот алгоритм теперь имеет сложность большого O(1), также известную как «постоянное время». Это означает, что Append будет работать одинаково — независимо от длины конструкции Feed.

Довольно просто, правда? Но давайте представим, что на самом деле Feed —это список Post’ов в нашем профиле. Следовательно, они наши, и мы должны иметь возможность их удалить.