Массивы

В математике одна из распространённых моделей понятия последовательность элементов множества M — отображение из промежутка целых чисел в M. В программировании аналогичная модель называется термином массив.

Структуры данных

Под термином структура данных обычно понимают некий способ хранения и организации данных, поддерживающий как минимум следующий набор операций:

добавление новых данных
извлечение (поиск) данных

Многие структуры данных также поддерживают:

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

Массив как структура данных

Массивы в программировании характеризуются способом поиска данных: данные можно получить по целочисленному ключу (называемому также номером или индексом), причём множество возможных ключей обязано быть промежутком целых чисел (т.е. содержать все целые числа между любыми своими двумя элементами).

Такое ограничение на множество ключей связано с тем, что чаще всего поиск данных в массиве осуществляется эффективно за счёт последовательного хранения в памяти компьютера этих данных (или ссылок на них). При последовательном хранении данных единицу данных номер i можно получить, отступив от начальной единицы данных (номер a) на (i-a) «ячеек памяти» (для простоты считаем, что одна ячейка хранит одну единицу данных).

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

Далее мы дадим описание основных операций с массивами и проведём небольшой анализ их производительности. Очень важно понимать, что этот анализ применим только к тем языкам программирования (а точнее, к тем их реализациям), в которых массивы реализованы именно как непрерывные блоки памяти. Среди широко распространённых контрпримеров, например, находятся тексты в Javascript: во всех современных реализациях этого языка текстовые данные даже близко не похожи на эту простую модель.

Идеальный массив

Сейчас мы опишем «идеальный» массив — некий общий знаменатель встречающихся в реальных языках программирования массивов. Для того, чтобы придать словам некую формальную семантику, описание будем сопровождать кодом на языке python. Самым близким к «идеальному» массиву типом данных в python является «список» list. В терминах этого типа мы и дадим описание.

Основные операции с массивом: создание с одновременным заполнением данными и получение данных по номеру.

def array_new(size, gen):
    return [gen(i) for i in range(size)]
    
def array_get(array, i):
    return array[i]
    
def array_size(array):
    return len(array)

Именно эти три операции (в тех или иных разновидностях) предоставляют все языки программирования, в которых есть встроенный тип данных массив. Они связаны между собой следующим свойством (для всех i в промежутке [0,size)):

array_get(array_new(size, gen), i) == gen(i)

Также часто есть возможность мутировать массив:

def array_set(array, i, x):
    array[i] = x
    return array

Естественно, мутация должна удовлетворять свойству:

array_get(array_set(a, i, x), i) == x

Также очень желательно, чтобы два любых вызова array_get(_,i), между которыми не было вызова array_set(_,i,_) на тот же массив, давали один и тот же результат.

Поиск по массиву

Хотя массив предоставляет возможность быстро получить доступ к элементу по его номеру, зачастую это совсем не то, что нужно. Обычно нам нужно найти все элементы, удовлетворяющие какому-то свойству p. Если есть возможность как-то связать это свойство с номерами элементов, то, можно сказать, нам повезло. Обычно же верно одно из двух:

свойство p вообще никак не увязывается с номерами данных
свойство p можно увязать с номерами данных, но при этом разброс номеров данных оказывается слишком большим, и массив неэффективно расходует память

Поясним вторую ситуацию на простом примере: допустим, что мы храним слова. Каждое слово можно тривиально преобразовать в число. Например, если слово состоит из символов таблицы ASCII, подойдёт следующая процедура:

def str_to_int(s):
    result = 0
    for x in s: 
        result *= 128
        result += ord(x)
    return result

Но вот только слово foobar преобразуется в число 3534724051186, а слово banana — в число 3393524889441. Разность между этими числами равна 141199161745 — именно такой минимальный размер должен иметь массив, позволяющий хранить одновременно слова banana и foobar.

На самом деле, конечно, всё не так плохо: если не требовать инъективность отображения, преобразующего данные в числа, и хранить эти данные в массиве массивов (по номеру i хранится массив всех данных, которые преобразуются в число i) или же каким-то другим образом договориться о разрешении конфликта одинаковых номеров, то можно получить довольно эффективную схему хранения данных. Такой подход называется хэш-таблицами и, например, лежит в основе типа dict языка python.

Добавление элемента

Предположим, что нам нужно добавить в массив (для простоты — в его конец) новый элемент. Наивная реализация добавления такова:

def array_append(a,x):
    n = array_size(a)

    return array_new(n+1, lambda i: array_get(a,i) if i < n else x)

Основная её проблема — время работы, пропорциональное длине массива. Это приводит к тому, что время добавления n элементов становится пропорционально квадрату n (что катастрофически плохо — миллион элементов за разумное время уже не добавить).

Тем не менее, в терминах идеального массива можно определить расширяемый массив:

def earray_new():
    return [0, array_new(8, lambda x: None)]
    
def earray_get(a, i):
    if i >= a[0]: raise RuntimeError("выход за пределы массива")
    return array_get(a[1], i)

def earray_size(a):
    return a[0]

def earray_set(a, i, x):
    if i >= a[0]: raise RuntimeError("выход за пределы массива")
    array_set(a[1], i, x)
    return a

def earray_append(a, x):
    current_size = a[0]
    old_array    = a[1]
    
    if current_size < array_size(old_array):
        new_array = old_array
    else:
        new_array = array_new(current_size*2, lambda i: array_get(old_array, i) if i < current_size else None)
    
    array_set(new_array, current_size, x)
    
    a[0] = current_size+1
    a[1] = new_array
    
    return a

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

Отметим, что тип list языка python — это именно расширяемый массив (то есть добавление новых элементов в конец осуществляется достаточно эффективно).

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