CS Notes

collections

5 min read

Коллекции

Предпосылки: Циклы (while), Функции (определение, вызов, параметры, возврат значения).

← Функции | Память →

final_total(subtotal, discount, tax_rate) хорошо считает один заказ продавца. Но за день маркетплейс принимает тридцать заказов, и до сих пор каждый новый заказ значит ещё одну именованную переменную:

subtotal_1 = 2400
subtotal_2 = 1800
subtotal_3 = 3500
subtotal_4 = 900
subtotal_5 = 2100
# ... ещё 25 таких же строк ниже
 
total_1 = final_total(subtotal_1, 150, 0.10)
total_2 = final_total(subtotal_2, 0,   0.10)
total_3 = final_total(subtotal_3, 200, 0.10)
# ... ещё 27 вызовов с руками

Уродство видно сразу. Имена различаются только номером, и тридцать почти одинаковых строк хочется обойти циклом — но цикл не умеет перебирать subtotal_1, subtotal_2, subtotal_3. Для него это тридцать независимых имён, а не один набор. Нужна структура, в которой тридцать значений живут как одно целое.

Массив

Массив (array — «ряд», «набор») хранит упорядоченную последовательность значений, к каждому из которых можно обратиться по номеру. Номер называется индексом и начинается с нуля:

subtotals = [2400, 1800, 3500, 900, 2100]   # и так далее до 30-го
 
puts subtotals[0]   # 2400
puts subtotals[2]   # 3500

Тридцать значений теперь лежат в одной переменной. Индекс i — обычное целое число, а значит, по массиву можно пройти циклом:

i = 0
while i < subtotals.length   # .length — количество элементов
  puts final_total(subtotals[i], 150, 0.10)
  i = i + 1
end

Вместо тридцати параллельных имён — одно имя и индекс. Как массив устроен в памяти и почему обращение по индексу стоит одной операции — в массиве.

В C массив объявляется с фиксированным размером:

int subtotals[5] = {2400, 1800, 3500, 900, 2100};

Если заказов станет шесть, код нужно менять: размер зашит в объявление.

Динамический массив

В реальной программе количество заказов заранее неизвестно. Сегодня их три, завтра тридцать, на распродаже — триста. Фиксировать размер наперёд нельзя.

В Ruby массивы динамические: можно начать с пустого и добавлять элементы по мере поступления:

subtotals = []
subtotals << 2400    # << добавляет в конец
subtotals << 1800
subtotals << 3500

Когда места внутри не хватает, массив сам расширяется. Как именно он растёт и почему добавление в конец в среднем стоит одной операции — в динамическом массиве.

Итерация

Итерация (от лат. iterare — «повторять») — один проход по элементам коллекции. Массив плюс цикл вместе закрывают задачу, с которой начиналась заметка: посчитать сумму по всем заказам одним правилом, независимо от их количества.

subtotals = [2400, 1800, 3500, 900, 2100]
 
sum = 0
i = 0
while i < subtotals.length
  sum = sum + subtotals[i]
  i = i + 1
end
 
puts sum    # 10700

Один цикл вместо тридцати почти одинаковых строк. И если завтра заказов станет триста — код останется тем же, поменяется только содержимое массива.

Хеш

Массив работает, пока значения различаются только порядком: первый заказ, второй, третий. Но у самого заказа внутри — разнородные поля: сумма, скидка, ставка налога, имя покупателя. Их естественно искать не по номеру, а по имени.

Если держать заказ как два параллельных массива, связь между ними приходится удерживать в голове:

fields = ["subtotal", "discount", "tax_rate"]
values = [2400, 150, 0.10]

values[1] — это скидка или ставка? Ответ зависит от порядка, и при любом изменении структуры параллельные массивы начинают расходиться — ровно как subtotal_1, subtotal_2 в начале заметки, только в другой плоскости.

Хеш (hash — «нарезать, перемешать»: ключ превращается во внутренний адрес, где лежит значение) хранит пары ключ -> значение:

order = {
  "subtotal"  => 2400,
  "discount"  => 150,
  "tax_rate"  => 0.10
}
 
puts order["subtotal"]   # 2400
puts order["discount"]   # 150

Теперь структура сама говорит, что хранится внутри: не нужно помнить, что скидка идёт второй. Как хеш устроен внутри и почему поиск по ключу в среднем не зависит от размера — в хеш-таблице.

Вложенные структуры

Коллекции комбинируются. Массив заказов, где каждый заказ — хеш с полями, закрывает ту самую задачу «тридцать заказов маркетплейса», с которой начиналась заметка:

def final_total(subtotal, discount, tax_rate)
  taxable = subtotal - discount
  taxable + (taxable * tax_rate)
end
 
orders = [
  { "customer" => "Alice",   "subtotal" => 2400, "discount" => 150, "tax_rate" => 0.10 },
  { "customer" => "Bob",     "subtotal" => 1800, "discount" => 0,   "tax_rate" => 0.10 },
  { "customer" => "Charlie", "subtotal" => 3500, "discount" => 200, "tax_rate" => 0.10 }
]
 
i = 0
while i < orders.length
  order = orders[i]
  total = final_total(order["subtotal"], order["discount"], order["tax_rate"])
  puts order["customer"]
  puts total
  i = i + 1
end

Функция по-прежнему считает один заказ; коллекция хранит сразу много заказов; цикл прогоняет функцию по всем. Три инструмента, сложенные вместе, дают одну рабочую конструкцию — сколько бы заказов ни пришло.

Остаётся странность, которую заметка обошла. После copy = orders в обоих именах окажется один и тот же список заказов или две независимые копии? Если добавить новый заказ через copy, увидит ли его orders? Ответ не в самом массиве, а в том, как переменные и данные лежат в памяти.

Sources

  • Thomas, D. et al., 2023, Programming Ruby 3.3. Pragmatic Bookshelf.
  • Knuth, D., 1998, The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley.

← Функции | Память →

Graph View