Списки, кортежи и keyword-списки

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

Список — для переменной длины и обхода; кортеж — для фиксированной группы; keyword list — для опций. Перепутаешь — получишь медленный код.

Список — связная цепочка ячеек. Дёшево добавлять в голову и обходить, дорого — лезть по индексу или в конец:

list = [1, 2, 3]
[0 | list]            # [0, 1, 2, 3] — O(1), добавили в голову
list ++ [4]           # [1, 2, 3, 4] — O(n), проход до конца
length(list)          # 3 — тоже O(n)

Кортеж хранится непрерывно — быстрый доступ по индексу, но дорогое «изменение» (копирование всего):

point = {3, 4}
elem(point, 0)        # => 3, O(1)
put_elem(point, 0, 9) # => {9, 4} — копирует кортеж

Keyword list — список пар {ключ-атом, значение} с сахаром, классика для опций функций:

opts = [sort: true, limit: 10]
Keyword.get(opts, :limit)   # => 10

Как работает под капотом (BEAM)

Список — это односвязная структура: каждая ячейка хранит значение (head) и ссылку на остаток (tail). Поэтому добавление в голову через [x | list] бесплатно — старый список переиспользуется как хвост, а доступ к n-му элементу требует пройти n ссылок. Кортеж же лежит в памяти подряд, как массив фиксированной длины, отсюда быстрый elem/2, но «изменение» означает копирование всего кортежа. Keyword list под капотом — обычный список кортежей-пар, поэтому он сохраняет порядок и допускает повторяющиеся ключи.

  Список:  [1 | [2 | [3 | []]]]
            head  head  head  конец
            добавить в голову = O(1)

  Кортеж:  | 3 | 4 |   (подряд в памяти)
            доступ по индексу = O(1)

Та же идея на Python ▶

В Python list ближе к динамическому массиву, tuple — к кортежу Elixir, dict — к keyword-опциям.

# Список: добавление и обход
nums = [1, 2, 3]
nums = [0] + nums            # как [0 | list]
print(nums)                  # [0, 1, 2, 3]

# Кортеж: фиксированная группа, доступ по индексу
point = (3, 4)
print(point[0])              # 3
point = (9,) + point[1:]     # "изменение" = новый кортеж
print(point)                 # (9, 4)

# Keyword-опции через словарь
opts = {"sort": True, "limit": 10}
print(opts.get("limit"))     # 10

Частые ошибки

Добавлять в конец списка в цикле. list ++ [x] — O(n); в горячем цикле это квадратичная катастрофа. Копите в голову и в конце разверните.
Брать length в условии цикла. Это O(n) каждый раз; матчите на [] вместо проверки длины.
Хранить динамические данные в кортеже. Кортеж — для фиксированной структуры, а не для коллекции переменного размера.

Best practices

Накапливайте элементы добавлением в голову, затем один раз Enum.reverse — это O(n) вместо O(n²).
Используйте кортежи для возврата нескольких значений и фиксированных записей вроде {:ok, data}.
Передавайте опции функций keyword-списком — это идиома стандартной библиотеки.

Итог. Три похожие структуры решают три разные задачи. Понимание их стоимости отделяет наивный код от быстрого. Дальше — модуль Enum, который красиво обходит коллекции, и его ленивый собрат Stream.

Практическое правило выбора

Сведём выбор структуры к простому правилу. Нужна последовательность, которую вы перебираете и наращиваете с головы — список. Нужна фиксированная группа разнородных значений, к которым обращаетесь по позиции (как запись с полями), — кортеж. Нужно передать набор опций функции — keyword list. Нужен словарь с произвольными ключами и быстрым доступом — map. Перепутав, вы не получите ошибку компиляции, но можете получить неожиданно медленный код.

Классический антипаттерн новичка — строить список добавлением в конец внутри цикла. Поскольку это O(n) на каждом шаге, обработка тысячи элементов превращается в миллион операций. Правильная идиома: накапливать добавлением в голову (O(1)) и один раз развернуть результат через Enum.reverse в конце, либо вовсе использовать Enum.map/reduce, которые делают это эффективно за вас. Понимание стоимости операций здесь — не педантизм, а разница между сервисом, который держит нагрузку, и тем, который ложится под ней.