Вставка Post
Теперь, когда у нас есть добавление и удаление, давайте рассмотрим отчасти гипотетический случай. Представьте, что источник, производящий Post’ы, отправляет их нашему приложению в нехронологическом порядке. Это означает, что Post’ы необходимо расположить в правильном порядке в зависимости от publishDate в Feed. Вот как это будет выглядеть:
По сути, этот алгоритм очень похож на алгоритм в функции Remove, потому что, хотя они делают совершенно разные вещи (добавление или удаление Post в Feed), в их основе лежит поиск. Это означает, что обе функции на самом деле обходят весь массив в Feed в поисках Post’a, совпадающего с publishDate, полученным в аргументе функции. Единственное отличие заключается в новом значении Insert, который будет помещен Post в то место[АК1] , где совпадают даты, в то время как Remove удалит Post из Feed.
Кроме того, это означает, что обе эти функции имеют одинаковую временную сложность, которая составляет O(n). Это означает, что в худшем случае функции должны будут пройти весь Feed, чтобы добраться до элемента, в который необходимо вставить (или из которого нужно удалить) новый Post.
Что если бы мы использовали массивы?
Если ты задаешься этим вопросом, — ты прав. Мы могли бы хранить все Post’ы в массиве (или в слайсе в Go), легко помещать в него элементы и даже иметь произвольный доступ со сложностью O(1).
Из-за природы массивов, значения которых должны храниться в памяти одно за другим, чтение происходит действительно быстро и дешево. Если у нас есть что-то хранящееся в массиве, получить его так же просто, как получить к нему доступ по индексу, начинающемуся с 0. Когда дело доходит до вставки элемента, что в середину, что в конец, массивы становятся менее эффективными по сравнению со списками. Это связано с тем, что, если в массиве недостаточно памяти, зарезервированной для новых элементов, ему придется зарезервировать ее и использовать. Но, если следующие адреса памяти не свободны, ему придется «переехать» на новый адрес памяти, где будет место для всех элементов (и новых, и старых).
Глядя на все примеры и обсуждения, которые у нас были, мы можем создать таблицу с временной сложностью для каждого из созданных нами алгоритмов и сравнить их с теми же алгоритмами для массивов:
Action | Array | Linked list |
Access | O(1) | O(n) |
Search | O(n) | O(n) |
Prepend | O(1) | O(1) |
Append | O(n) | O(1) |
Delete | O(n) | O(n) |
Как видишь, когда ты сталкиваешься с определенной проблемой, выбор правильной структуры данных может действительно создать или разрушить продукты, которые ты создаешь. Для постоянно растущих Feed, где вставка Post имеет первостепенное значение, связанные списки работают намного лучше, потому что вставки действительно проще. Но если бы у нас была другая проблема, которая требовала бы частых удалений или многократных извлечений/поисков, то нам пришлось бы выбрать правильную структуру данных для этой проблемы.
Вы можете увидеть всю реализацию Feed и поиграть с ней здесь. Кроме того, в Go есть собственная реализация связанных списков с некоторыми уже встроенными функциями. Документацию можно посмотреть здесь.
С оригиналом статьи ты можешь ознакомиться по ссылке.
Также рекомендуем изучить дополнительные источники и поработать с кодом в тренажере: