1с что быстрее массив или соответствие
Иногда встает вопрос, что лучше использовать, а чаще всего в стандартных конфигурациях 1С и их партнеров при обновлении может, происходит преобразование данных в другие объекты метаданных и почему то они строят структуру, где ключом является код объекта?! А там же может быть значение, которое начинается на цифру и сразу же выходит ошибка.
Таблица сравнения построена по версии справки из Конфигуратора:
Структура
Соответствие
Возможно обращение к значению элемента посредством оператора [. ]. В качестве аргумента передается значение ключа элемента.
Для объекта доступен обход коллекции посредством оператора Для каждого … Из … Цикл. При обходе выбираются элементы коллекции.
Представляет собой коллекцию пар КлючИЗначение . При этом ключ может быть только строковым и должен удовлетворять требованиям, предъявляемым к именованию переменных встроенного языка.
К значениям структуры можно обращаться как к свойствам объекта. При этом ключ используется как имя свойства.
Структура используется обычно для хранения небольшого количества значений, каждое из которым имеет некоторое имя.
Представляет доступ к соответствию.
Доступность: Тонкий клиент, веб-клиент, сервер, толстый клиент, внешнее соединение.
Возможен обмен с сервером. Сериализуется. Данный объект может быть сериализован в/из XDTO. Тип XDTO, соответствующий данному объекту, определяется в пространстве имен .
Имя типа XDTO: Structure
Имя типа XDTO: Map
Может использоваться в реквизитах управляемой формы.
Запись = Новый Структура ;
Запись = Новый Соответствие ;
Запись . Вставить ( "Ключ" , "Значение" );
Кроме этого: Структура упорядочивает элементы при добавлении, а соответсвие нет.
Вернемся к теме:
Для «Структура» ключ должен быть введен по всем правилам объявления переменных, а «Соответствие» нет.
Можно просто заменить тип переменной и заменить метод «Свойство» на «Получить». Обычно этого достаточно.
Но бывают и неожиданные результаты при использовании «Соответствие».
Например, платформа даёт добавить значение с ключом = Неопределенно, а вот считать нельзя, так как по факту запись не была добавлена, но и ошибку не выдал.
Предлагаю код для проверки исключительных ситуаций. Код можно добавить на пустой форме, добавив 2 таблицы значений с именами табСтруктура и табСоответствие .
Процедура КнопкаВыполнитьНажатие ( Кнопка )
Для А = 1 По 500000 Цикл
ВставитьИПроверить ( мСтруктура , Стр , Стр );
Сообщить ( "Структура - " + ( ТекущаяДата () - тДата ));
ВставитьИПроверить ( мСтруктура , Тест , Тест );
Для А = 1 По 500000 Цикл
ВставитьИПроверить ( мСоответствие , Стр , Стр );
Сообщить ( "Соответствие - " + ( ТекущаяДата () - тДата ));
ВставитьИПроверить ( мСоответствие , Тест , Тест );
Процедура ВставитьИПроверить ( Список , Ключ , Значение );
мТип = ТипЗнч ( Список );
//проверка возможно добавить или нет
Список . Вставить ( Ключ , Значение );
Сообщить ( "" + мТип + ": Не возможно добавить ключ [" + Значение + "]." );
Если НЕ (( мТип = Тип ( "Соответствие" ) И НЕ Список . Получить ( Ключ ) = Неопределено)
ИЛИ ( мТип = Тип ( "Структура" ) И НЕ Список . Свойство ( Ключ ) = Неопределено)) Тогда
Сообщить ( "" + мТип + ": Выполнено неявное преобразование типов и/или данных ключа [" + Значение + "]." )
Сообщить ( "" + мТип + ": Невозможно получить значение по ключу [" + Значение + "].
| Возможно было выполнено неявное преобразование типов и/или данных ключа." )
Процедура ОсновныеДействияФормыПроверка ( Кнопка )
мСсылка = Справочники . Валюты . ПустаяСсылка ();
// добавление новый элементов в Структуру
ВставитьИПроверить ( мСтруктура , "Ключ1" , "Ключ1" );
ВставитьИПроверить ( мСтруктура , "1Ключ" , "1Ключ" );
ВставитьИПроверить ( мСтруктура , мСсылка , "Справочники.Валюты.ПустаяСсылка()" );
ВставитьИПроверить ( мСтруктура , табСтруктура , "ТаблицаЗначений" );
ВставитьИПроверить ( мСтруктура , Неопределено, "Неопределено" );
ВставитьИПроверить ( мСтруктура , null, "null" );
// добавление новый элементов в Соответствие
ВставитьИПроверить ( мСоответствие , "Ключ1" , "Ключ1" );
ВставитьИПроверить ( мСоответствие , "1Ключ" , "1Ключ" );
ВставитьИПроверить ( мСоответствие , мСсылка , "Справочники.Валюты.ПустаяСсылка()" );
ВставитьИПроверить ( мСоответствие , табСоответствие , "ТаблицаЗначений" );
ВставитьИПроверить ( мСоответствие , Неопределено, "Неопределено" );
ВставитьИПроверить ( мСоответствие , null, "null" );
// выводим результат на форму
Для Каждого Стр Из мСтруктура Цикл
нСтр = табСтруктура . Добавить ();
нСтр . Ключ = Стр . Ключ ;
нСтр . Значение = Стр . Значение ;
ЭлементыФормы . табСтруктура . СоздатьКолонки ();
Для Каждого Стр Из мСоответствие Цикл
нСтр = табСоответствие . Добавить ();
нСтр . Ключ = Стр . Ключ ;
нСтр . Значение = Стр . Значение ;
ЭлементыФормы . табСоответствие . СоздатьКолонки ();
мСтруктура = Новый Структура ;
мСоответствие = Новый Соответствие ;
табСтруктура . Колонки . Добавить ( "Ключ" );
табСтруктура . Колонки . Добавить ( "Значение" );
табСоответствие . Колонки . Добавить ( "Ключ" );
табСоответствие . Колонки . Добавить ( "Значение" );
Структура : Не возможно добавить ключ [1Ключ].
Структура : Не возможно добавить ключ [Справочники.Валюты.ПустаяСсылка()].
Структура : Не возможно добавить ключ [Неопределено].
Структура : Не возможно добавить ключ [null].
Соответствие : Выполнено неявное преобразование типов и/или данных ключа [Неопределено].
Прошу обратить внимание: Что ТаблицаЗначений при добавлении в Структуру было преобразовано к строке "ТаблицаЗначений".
Последний раз у меня возникла такая ситуация при обновлении 1С:Консолидация ПРОФ с 1.3.3.7 (1.3.4.1) на 2.0.1.4 (2.0.2.6)
Строилась "Структура" по коду справочника "Операнды показателей".
Исправляется 1 строкой в Общих модулях.УправлениеОтчетами строка 3622.
"СтруктураПолей=Новый Структура;" заменить на "СтруктураПолей=Новый Соответствие;"
Специальные предложения
Последний раз у меня возникла такая ситуация при обновлении 1С:Консолидация ПРОФ с 1.3.3.7 (1.3.4.1) на 2.0.1.4 (2.0.2.6)
Строилась "Структура" по коду справочника "Операнды показателей".
Исправляется 1 строкой в Общих модулях.УправлениеОтчетами строка 3622.
"СтруктураПолей=Новый Структура;" заменить на "СтруктураПолей=Новый Соответствие;"
(1) Согласен c awk, это разные объекты с разным назначением.
(12) kereo, менять коды не вариант.
Так как на этих кодах справочника построены формулы расчета.
Но и это не самое страшное, видать для повышения скорости работы почти в каждом справочники, есть реквизит типа ХранилищеЗначения, которое в себе хранит копию почти всех реквизитов объекта + какие-то промежуточные расчеты.
Потом эти формулы используются в макетах, где они тоже берутся не из справочников, а из ХранилищеЗначения.
Возможно, где то еще есть ХранилищеЗначения на ХранилищеЗначения на ХранилищеЗначения, но дальше углубляться не стал.
Так как их надо будет обновлять. А это не просто, всё-таки это 1С: Консолидация.
(1)
вы непонятно что проверяете своим кодом. Лучше уберите его совсем.
В очередной раз доказали, что в ключ структуры ничего, кроме "правильной" строки, внести нельзя?
Доказали, что Соответствие может принимать любые ключи и любые значения?
И кому, кроме Вас, взбредет в голову давать ключу (ключу!) значение Неопределено (и Соответствие правильно ничего показывает - это же значение Непопределено) или Null?
Самое главное - что для получения значения Соответствия у запрашиваемого ключа должен быть обязательно тот же самый тип данных, что и при создании ключа - у автора ни слова (видимо, не знает).
Прошу обратить внимание: Что ТаблицаЗначений при добавлении в Структуру было преобразовано к строке "ТаблицаЗначений".
И никаких преобразований ни Структура, ни Соответствие не делают - разве что преобразуются в строковой ключ (Структура) таким образом:
где Ключ - строка, либо для Соответствия - по правилу преобразования 1С последовательности значений: все следующие значения - принимают тип данных (если это возможно) первого из слагаемых, иначе - ошибка.
ТаблицаЗначений как была ТЗ, так ей и остается. Разве что Вы сами себя там запутали, и превратили на каком-то этапе в строку (даже ковырять не хочется столь бестолковый код).
Так что лучше разберитесь по-настоящему, что и как, а пока статья - ни о чем, и никак никому не поможет, а только запутает.
Единственно верное замечание -
и то, упорядочивает не "значения", а строковые ключи, и, естественно, Соответствие не сможет никогда упорядочить ссылку на объект и число с Неопределено - т.е. все, что взбредет туда засунуть в Ключ.
Так что и по этому вопросу - у автора нет понятия.
Написал тут отчёт для экономистов, а он тормозит - 30 секунд формируется. Частое использование не предполагалось, но не люблю, когда отчёты тормозят, а тут ещё и сортировка по хитро рассчитанному полю понадобилась - переписал. Всё равно почти 10 секунд. Замер производительности вывел в рекордсмены строку
с результатом 3.1 сек. для 3819 вызовов
Список перед этим был заполнен уникальными значениями из результата запроса:
У меня как-то ещё со времён 7.7 привычка использовать для подобных целей объект СписокЗначений и была убеждённость, что разработчики платформы поддерживают некий хэш-индекс для быстрого поиска вхождений в список (в 7.7 для этого даже есть специальный метод Принадлежит()). Результат замера, тем не менее, намекал, что стоит ещё поискать. Попробовал так:
Формируем тем же запросом индексированную таблицу значений:
и слегка меняем строку с поиском:
результат - 0.027 сек.
Нет, я подозревал, что это может быть быстрее, но в 100 раз!
Чтобы два раза не вставать, попробовал с массивом:
результат - 3.3 сек. Скорости не ожидал - скорости не получил.
Больше значащих цифр во временах не даю, потому что они заметно меняются от запуска к запуску, но порядок величин сохраняется. Массив, например, попадал в диапазон 3.25-3.55 секунд.
Вывод очевиден - индексированная ТаблицаЗначений - наше всё.
Причём именно индексированная, важность чего многие (включая меня до сегодняшнего дня) склонны недооценивать. Я попробовал закомментировать создание индекса и сразу получил время 3.15 сек.
P.S. В каментах неоднократно упомянули Соответствие, а FlyVodolaz даже привёл код процедуры, сравнивающей в смысле поиска Соответствие и индексированную ТаблицуЗначений. Единственный минус той процедуры - искуственность примера (запрос выполняется к временной таблице, заполненной последовательными числами). Я решил проверить это на своём отчёте, для чего изменил соответствующие фрагменты:
Действительно, поиск выполняется быстрее (0.017 секунд), но вот открытие выборки из результата запроса отъедает 0,050 секунд против 0,029 для выгрузки в ТаблицуЗначений и индексации.
В итоге, суммарное время выполнения при использовании Соответствия получается больше, чем при использовании ТаблицыЗначений, но однозначного вывода в пользу того или другого способа для всех случаев жизни я из этого сделать не могу.
Скорее так: в том случае, когда в алгоритме массово используется поиск в одном и том же множестве и при этом результатом поиска является либо сам факт нахождения, либо какое-то одно значение, связанное с ключом поиска, однозначно надо брать Соответствие - оно быстрее.
В остальных случаях я бы использовал ТаблицуЗначений: во-первых, преимущество Соответствия в поиске, как показано выше, не всегда приводит к ускорению всего алгоритма, во-вторых, выгрузка в неё записывается короче, в-третьих, у неё больше возможностей. Например, в случае необходимости в неё легко добавить ещё колонок.
1. Место коллекции "соответствие" среди других универсальных коллекций значений.
массив предназначен для доступа к элементам массива;
структура используется для хранения небольшого количества значений, каждое из которых имеет некоторое имя;
список значений - это не сохраняемый в базе данных объект, который позволяет строить динамические наборы значений и манипулировать ими;
таблица значений - почти тоже, что список, только еще с колонками.
А вот про соответствие в хелпе написано только что данный объект "Представляет доступ к соответствию".
Не собираюсь поправлять техписателей 1С - другого определения давать не буду.
С моей точки зрения, соответствие занимает промежуточное положение между структурой и массивом, с одной стороны, и списком и таблицей значений, с другой, объединяя хорошие черты этих коллекций.
Все коллекции хранят множества элементов. Структура позволяет получить нужный элемент по имени, массив - по номеру, список и таблица значений - поиском (отбором) среди других элементов. А соответствие позволяет выбрать или изменить нужный элемент по "ключу" этого элемента. При этом в качестве ключа может использоваться значение почти любого типа (например, ссылка). Возможность выбора и изменения по ключу дает возможность обрабатывать заранее неизвестное количество элементов, при этом никак их не нумеруя. Получаем практически таблицу значений, проиндексированную по колонке "ключ".
И вот тут, думаю, для многих будет сюрпризом, что доступ к элементу соответствия по ключу происходит почти со скоростью доступа к массиву или элементу структуры! - Как будто по номеру!
Будем подавать на вход обработки случайные числа в диапазоне от 1 до КоличествоРазличныхЭлементов. Обработка должна будет проверять каждое число, чтобы определить: не встречалось ли очередное число в текущей последовательности раньше. Если такого числа не было - оно добавляется в коллекцию, иначе - увеличивается число его повторений.
То есть оценивается время выполнения конструкции ". " в цикле (фиг1)
В качестве конструкции ". " используется:
Вариант 1. Массив (фиг2)
Вариант 2. Соответствие (фиг3)
Вариант 3. Индексированная ТаблицаЗначений (фиг4)
Результаты сравнения показали, что отметка в массиве занимает на тестовом компьютере 2,45 мкс, в соответствии - 7,06 мкс, в индексированной таблице значений - 15,06 мкс, причем это время не зависит от числа элементов в коллекции! Прилагаемый к статье отчет "БыстродействиеКоллекций" позволит Вам перепроверить эти результаты.
Скорость доступа к элементам соответствия и независимость скорости доступа от размера коллекции "соответствие" может удивлять, если не догадываться о ее устройстве. Можно предположить, что используется хеш-функция и хеш-таблица. Хеш-функция вычисляет номер строки хеш-таблицы, где лежит ссылка на элемент. Простая косвенная адресация! Одно лишнее (по сравнению с массивом) обращение к памяти!
При использовании для решения этой задачи списка значений, неиндексированной таблицы значений или добавления чисел в таблицу значений без контроля повторений с последующей сверткой, получаются существенно более плохие результаты. Которые, к тому же, зависят от размеров коллекций . При этом самые лучшие результаты среди аутсайдеров дает свертка.
В комментариях к статье также уже посоветовали отметить, что еще одна прелесть соответствия в том, что перед присваиванием Соответствие[Ключ] = Значение не нужна проверка на существование элемента с этим ключом, так как отсутствующий элемент в этом случае вставляется в соответствие. В приведенных примерах этому красивому приему, к сожалению, места не нашлось.
2. Пример использования соответствия в задаче подсчета повторений слов.
Приведем пример программы, подсчитывающей число повторений каждого слова в заданном тексте. Обычное решение - запоминание отдельных слов в строках таблицы значений и последующая свертка по полю "Слово". Соответствие ускоряет основную операцию в этом алгоритме минимум в два раза! При этом получается не только самый быстрый, но и выразительный код. Чтобы учесть, что слово, прочитанное в переменную "Слово" строкового типа, встретилось еще раз, используется наглядная запись: Частота[Слово] = Частота[Слово] + 1. Правда, чтобы определить, что символ является буквой, использовать соответствие будет уже неправильно: встроенная функция поиска подстроки работает быстрее!
Текст программы приведен на фиг5 и в приложенном к статье отчете "ЧастотаСлов", позволяющем проанализировать любой текстовый файл.
Прилагаемый к статье скриншот показывает результат определения частоты слов в данной статье.
3. Пример использования соответствия в задаче представления ориентированного графа.
Если стоит задача сохранить в оперативной памяти и проанализировать связи объектов информационной базы, то эффективной оказывается использование следующей структуры: Соответствие "Граф" хранит связи объекта, ссылка на который определяется ключом. Значением соответствия "Граф" является вложенное соответствие "Связи", которое для каждого связанного элемента хранит вес связи.
Например, если переменные "Элемент1" и "Элемент2" хранят ссылки на два элемента справочника "Номенклатура", причем второй входит в спецификацию первого с весом 2, то выражение
Граф[Элемент1][Элемент2] будет равно 2.
Если связи нет, то выражение Граф[Элемент1][Элемент2] будет равно "Неопределено".
Если нужно сделать вес связи равным 1, это сделает следующий код: Граф[Элемент1][Элемент2] = 1.
При этом Элемент1 и Элемент2 могут быть как ссылкой на справочник, так и ссылкой на документ и другие объекты. То есть так можно обрабатывать любые связи!
Стоит предупредить, что обращаться к элементам вложенного соответствия можно только, если во внешнем соответствии существует ключ первого элемента. Поэтому перед обращением к связям требуется проверка Граф[Элемент1] <> Неопределено.
На фиг6 приведен фрагмент кода программы, который производит чтение из базы данных в оперативную память связей номенклатуры, задаваемых в конфигурации "Бухгалтерия предприятия" в справочнике "СпецификацииНоменклатуры".
Заключительные замечания.
1. Ничего нового здесь не изобретено, просто делюсь опытом. Сам узнал о сравнительной эффективности коллекций из статьи Сергея Осипова. Спасибо ему!
2. Использование соответствия в решении задач позволяет исключить поиск при обработке заранее непронумерованных данных. Таким образом существенно ускоряется реализация многих базовых алгоритмов. Пользуйтесь соответствием в случаях, когда не нужен весь функционал таблиц значений!
3. Несмотря на ориентированность языка 1С на решение бизнес-задач, в нем есть место настоящему программированию - кодингу, в том числе и самому хитроумному. Поэтому изучайте теорию алгоритмов и программ, не мусорьте в коде и сможете сберечь нервы и время пользователей, строки кода, место на дисках, циклы процессора, электроэнергию. Делайте мир лучше!
В данной статье пойдет речь о том, какие коллекции есть во встроенном языке 1С, их особенности и для чего они применяются.
В материале освещены сразу два вопроса собеседования программиста 1С:
- Чем отличается структура от соответствия?
- Можно ли сделать запрос по таблице значений?
Разработчику во встроенном языке доступны следующие объекты, описывающие коллекции:
Массив
Объект описывает коллекцию значений массива. У каждого элемента есть индекс. В 1С можно создавать многомерные массивы, например так:
В массиве можно искать элементы методом Найти(), но поскольку у массива нет индексов данный поиск выполняется не быстро. Метода сортировки массива разработчики 1С не добавили. Возможно, это сделано не просто так, т.к. сортировать можно другие коллекции
Массивы используются для передачи параметров в запрос, для выгрузки колонки таблицы значений, могут служить источником для списка значений.
Фиксированный массив
Тот же массив, но его элементы нельзя изменить, т.е. у него есть только методы Получить(), Найти(), ВГраница() и Количество(). Создается на основе обычного массива.
Данный объект как правило используется в свойствах интерфейсных объектов (элементов управления)
Список значений
Список значений можно представить в качестве следующей таблицы значений:
Как видно из структуры объекта, в поле «Значение» может быть любой объект.
Данный объект, в отличие от массива, уже содержит методы сортировки как по полю Значение, так и по полю Представление. Список значений можно заполнить элементами массива, используя метод ЗагрузитьЗначения().
Списки используются для передачи параметров в запрос, в качестве объекта сравнения в СКД и построителе, а также в отборах в интерфейсе.
Данный объект может быть отображен в интерфейсе, кроме того он имеет методы позволяющие показать диалог установки отметок в списке, диалог выбора значения из списка.
Структура
Структура представляет собой коллекцию пар КлючИЗначение. При этом ключ может быть только строковым и должен удовлетворять требованиям, предъявляемым к именованию переменных встроенного языка, т.е. ключом не может выступать строка «123ключ». К значениям структуры можно обращаться как к свойствам объекта. При этом ключ используется как имя свойства.
Пары Ключ-значение можно обойти циклом Для каждого … Из … Цикл, проверить существует ли свойство(ключ) структуры можно методом Свойство().
Структура используется обычно для хранения небольшого количества значений, каждое из которых имеет некоторое имя.
Соответствие
Соответствие как и структура представляет собой коллекцию пар КлючИЗначение. При этом, у соответствия в качестве ключа может выступать любое значение! Рекомендуется, чтобы в качестве ключа выступало значение примитивного типа или другого типа, значение которого может только присваиваться, но не может менять свое содержимое. Еще одной особенность соответствия является то, что это индексированная коллекция, т.е. поиск значения по ключу осуществляется очень быстро.
Пары Ключ-значение можно обойти циклом Для каждого … Из … Цикл.
Соответствие обычно используется в тех случаях, когда необходимо заполнить таблицу соответствия одного значения другому, причем размеры этой таблицы могут быть достаточно большими. Также очень удобно использовать соответствие в качестве кэша из-за высокой скорости поиска в нем.
Таблица значений
Таблица значений предназначена для хранения значений в табличном виде. Все основные операции с таблицей производятся именно через этот объект. Он позволяет манипулировать строками таблицы значений и предоставляет доступ к коллекции колонок. Колонки могут быть различных типов (в том числе множественных).
У таблицы значений есть метод Сортировать(), с помощью которого можно сортировать таблицу сразу по нескольким колонкам. С помощью метода Итог() можно сразу получить сумму колонки.
Причем, в запросе необходимо сразу поместить выбранную таблицу во временную, а после этого выполнять действия с ней.
В управляемом приложении данный объект доступен только на сервере! Другими словами, попытка создать на клиенте равно как и передать таблицу значений с сервера на клиент приведет к ошибке.
Некоторое время назад я сходил на собеседование в одну довольно большую и уважаемую компанию. Собеседование прошло хорошо и понравилось как мне, так и, надеюсь, людям его проводившим. Но на следующий день, в процессе разбора полетов, я обнаружил, что в ходе собеседования ответ на как минимум один вопрос был неверен.
Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?
Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!
На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.
Причиной неверного ответа было то, что я не удосужился досконально изучить те структуры, которые лежат в основе работы с коллекциями моего любимого языка. Правда, по результатам опроса нескольких знакомых разработчиков, оказалось что это не только моя проблема, очень многие вообще не задумываются, как работают коллекции в их любимых ЯП. А ведь используем мы их каждый день и не по разу. Так родилась идея этой статьи.
1. Array — он же индексированный массив.
Array — это коллекция фиксированного размера, состоящая из элементов одинакового типа.
- get_element_at(i): сложность O(1)
- set_element_at(i, value): сложность O(1)
Почему время доступа к элементу по индексу постоянно? Массив состоит из элементов одного типа, имеет фиксированный размер и располагается в непрерывной области памяти => чтобы получить j-й элемент массива, нам достаточно взять указатель на начало массива и прибавить к нему размер элемента умноженный на его индекс. Результат этого несложного вычисления будет указывать как раз на искомый элемент массива.
*aj = beginPointer + elementSize*j-1
2. List (список).
List — это список элементов произвольного типа переменной длины (то есть мы можем в любой момент добавить элемент в список или удалить его). Список позволяет перебирать элементы, получать элементы по индексу, а так же добавлять и удалять элементы. Реализации у List возможны разные, основные — это (Single/Bidirectional) Linked List и Vector. Классический List предоставляет возможность работы с ним напрямую и через итератор, интерфейсы обоих классов рассмотрим ниже.
- prepend(item): Добавить элемент в начало списка.
- append(item): Добавить элемент в конец списка.
- insert_after(List Iterator, item): Добавить элемент после текущего.
- remove_firts(): Удалить первый элемент.
- remove_after(List Iterator): Удалить элемент после текущего.
- is_empty(): Пуст ли List.
- get_size(): Возвращает размер списка.
- get_nth(n): Вернуть n-й элемент.
- set_nth(n, value): Задать значение n-му элементу.
- get_value(): получить значение текущего элемента.
- set_value(): задать значение текущему элементу.
- move_next(): переместиться к следующему элементу.
- equal(List Iterator): проверяет — ссылается ли другой итератор на тот же элемент списка.
Перейдем к реализациям списка.
2.1 Single Linked List
Однонаправленный связный список (односвязный список) представляет из себя цепочку контейнеров. Каждый контейнер содержит внутри себя ссылку на элемент и ссылку на следующий контейнер, таким образом, мы всегда можем переместиться по односвязному списку вперед и всегда можем получить значение текущего элемента. Контейнеры могут располагаться в памяти как им угодно => добавление в односвязный список нового элемента тривиально.
- prepend: O(1)
- insert_after: O(1)
- remove_first/remove_after: O(1)
- get_nth/set_nth: O(N)
Bidirectional Linked List мы подробно рассматривать не будем, вся разница между ним и Single Linked List заключается в том, что в контейнерах есть ссылка не только на следующий, но и на предыдущий контейнер, что позволяет перемещаться по списку не только вперед, но и назад.
2.2 Vector
Vector — это реализация List через расширение индексированного массива.
- prepend: O(N)
- append: Amort.O(1)
- insert_after: O(N)
- remove_first/remove_after: O(1)
- get_nth/set_nth: O(1)
Очевидно, что главное преимущество Vector'а — быстрый доступ к элементам по индексу, унаследовано им от обычного индексированного массива. Итерировать Vector так же достаточно просто, достаточно увеличивать некий счетчик на единицу и осуществлять доступ по индексу. Но за скорость доступа к элементам приходиться платить временем их добавления. Для того чтобы вставить элемент в середину Vector'a (insert-after) необходимо скопировать все элементы между текущим положением итератора и концом массива, как следствие время доступа в среднем O(N). То же и с удалением элемента в середине массива, и с добавлением элемента в начало массива. Добавление элемента в конец массива при этом может быть выполнено за O(1), но может и не быть — если опять таки потребуется копирование массива в новый, потому говорится, что добавление элемента в конец Vector'а происходит за Amort. O(1).
3. Ассоциативный массив(Словарь/Map)
Коллекция пар ключ=>значение. Элементы (значения) могут быть любого типа, ключи обычно только строки/целые числа, но в некоторых реализация диапазон объектов, которые могут быть использованы в качестве ключа, может быть шире. Размер ассоциативного массива можно изменять путем добавления/удаления элементов.
- add(key, value) — добавить элемент
- reassign(key, value) — заменить элемент
- delete(key) — удалить элемент
- lookup(key) — найти элемент
3.1 Hash Table
Как можно догадаться из названия, тут используются хэши. Механика работы Hash Table следующая: в основе лежит все тот же индексированный массив, в котором индексом работает значение хэша от ключа, а значением — ссылка на объект, содержащий ключ и хранимый элемент (bucket). При добавлении элемента — хэш функция вычисляет хэш от ключа и сохраняет ссылку на добавляемый элемент в ячейку массива с соответствующим индексом. Для получения доступа к элементу мы опять таки берем хэш от ключа и, работая так же как с обычным массивом получаем ссылку на элемент.
- Если хэш от ключа равен например 1928132371827612 — это ведь будет означать, что нам надо иметь массив соответствующего размера? А если у нас в нем всего 2 элемента?
- А если у нас хэши от двух разных ключей совпадут?
То есть, кроме значения ключа, она так же получает текущий размер массива, это необходимо для определения длины хэша: если мы храним всего 3 элемента — нет смысла делать хэш длиной в 32 разряда. Обратная сторона такого поведения хэш функции — возможность коллизий. Коллизии на самом деле характерны для Hash Table, и существует два метода их разрешения:
Chaining:
Каждая ячейка массива H является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.
Open addressing:
В массиве H хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива H в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.
- add: Amort.O(1)/O(N)
- reasign: Amort.O(1)/O(N)
- delete: Amort.O(1)/O(N)
- lookup: Amort.O(1)/O(N)
3.2 Binary Tree
На самом деле не просто Binary Tree, а Self-balancing Binary Tree. Причем следует отметить, что существует несколько различных деревьев, которые могут быть использованы для реализации Ассоциативного массива: red-black tree, AVL-tree и т.д. Мы не будем рассматривать каждое из этих деревьев в деталях, так как это возможно тема еще одной, отдельной статьи, а может и нескольких (если изучать деревья особо тщательно). Опишем только общие принципы.
Определение: двоичное дерево — древовидная структура данных в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. В случае, если у узла нет наследников — он называется листовым узлом.
- add: Amort.O(lgN)
- reasign: Amort.O(lgN)
- delete: Amort.O(lgN)
- lookup: Amort.O(lgN)
4. Множество (Set).
Сравнительные характеристики структур данных:
Структуры данных в различных языках программирования:
Ссылки:
Так же автор заглянул в исходники PHP и почитал доку по STL.
Upd. Да, в питоне есть обычный индексированный массив (array.array). Спасибо enchantner. С поправкой, тип не обязательно числовой, тип можно указывать.
Upd. Сделано много исправлений по тексту. idemura, zibada, tzlom, SiGMan, freeOne, Slaffko, korvindest, Laplace, enchantner спасибо за правки!
Upd.
Из комментариев zibada:
Да, вот как раз из-за отсутствия описания итерации по Map из статьи вообще непонятно, зачем, казалось бы, нужны деревья, когда есть хэши. (O(logN) против O(1)).
Нужны они затем, что перечислять элементы Map (или Set) можно хотеть:
— в любом, негарантированном порядке (HashMap, встроенные хэши в некоторых скриптовых языках);
— в порядке добавления (LinkedHashMap, встроенные хэши в некоторых других скриптовых языках);
— в порядке возрастания ключей + возможность перебрать только ключи в заданном диапазоне.
А вот для последнего случая альтернатива деревьям — только полная сортировка всей коллекции после каждого изменения или перед запросом.
Что долго и печально для больших коллекций, но вполне работает для небольших — поэтому в скриптовые языки деревья особо и не встраивают.
Читайте также: