Array vs Object vs Dictionary vs Vector
 

Доброго времени суток! ActionScript 3 изучаю недавно, вот обнаружил, что язык ActionScript 3 имеет 4 типа коллекций - Array, Object, Dictionary, Vector. Поскольку опыта у меня мало, хотелось бы узнать мнение опытных - какой тип коллекции и когда лучше использовать.
Спасибо!

Это резюме в Яндекс. Я бы вас пока не брал туда )

Да, вы правы. Но я туда и не собираюсь) Но всё-же, произошло стечение обстоятельств - совсем недавно я задумался над этим вопросом и вчера увидел подобный на Яндексе - стало еще интереснее)

Array - динамический тип данных. Обращение к данным по индексу.
Object - динамический тип данных, Обращение к данным по строковому идентификатору.
Vector - данные могут быть только одного типа, обращение по индексу. Более быстрый чем остальные.

А Dictionary еще быстрее всех перечисленных. И доступ туда по объектам. Это всё почти "определения". Но, когда лучше какой использовать...

Ну как-бы, из определения и следует, когда и какой нужно использовать.

Нужно хранить разные типы данных - Array. Карту игрового мира 150x150 с постоянными обращениями - Vector

С Вектором всё понятно. А вот хранить разные типы данных - можно использовать Array, Dictionary, Object.
Допустим у меня есть класс User:
Чтобы хранить пачку таких юзеров я могу использовать следующее:
Да и вектор сюда тоже вполне подойдет.

Что лучше? =)

Как я понял по последним дебатам местных профессионалов. Имеет смысл использовать только Vector и Dictionary.
Object это вобще не коллекция.
Array же уступает в быстродействии вектору.

Array отметается, Согласен - неудобно, да и не нужно, раз есть Vector.
Что касается Object - может это и не коллекция, дело не в терминологии, но хранить свойства он позволяет и использовать его можно с тем же успехом, что и Dictionary. Только у Dictionary скорость доступа к данным по ключу быстрее чем у Object. Ввиду скорости - предпочтении остается за Dictionary. А если скорость не учитывать, а учитывать лишь удобство использования (переборы, сортировка, заполнение и пр.)

Можно пруфы?

В словаре в качестве ключа может быть объект.

Вектор проигрывает массиву в универсальности.

Короче по обстоятельствам надо использовать. Я люблю массив и объект вкупе. Массив для массовых операций, объект, как хеш для быстрого доступа к конкретному элементу по ключу.

Вот как бы подкрепите свои слова измерениями что ли...
Лично по моим наблюдениям, словарь имеет такую же скорость доступа как у Object или даже медленнее. Array с доступом по числовому индексу (не по строчному) обгоняет и Object и Dictionary.

Object не может заменить Dictionary, и наоборот. Object чаще всего используют для хранения небольшого объема данных описывающих какую то конкретную сущность (например временные данные, получаемые в ходе вычислений).
Словарь - используют для быстрого доступа к информации об конкурентном объекте. например, есть N кнопок. по клику нужно увеличивать счетчик кликов конкретной кнопки.

Склонен поспорить с Вами. В случае со строковыми ключами поведение эдентично. И то и другое представляют собой структуру Map, только Object разрешает исключительно строковые ключи, а Dictionary - любые ключи (правда, ключи простых типов он приводит к строковым и не может по таким ключам держать слабые ссылки).

не совсем понимаю в чем спор.
если формулу 1 использовать как грузовую машины ее скорость будет равна скорости трактора.
ну да. только зачем?

В "наоборот".

ну это получается забивание гвоздей микроскопом.
только зачем?

Stone, мое высказывание по поводу использования Dictionary/Object будет полезно (мне так кажется) автору темы и всем кто ее будет читать. Я предлагаю остановиться на этом моменте. Да и, думаю, мы с Вами уже вышли из возраста, когда нужно кому-то что-то доказывать. Тем более что никто из нас (вероятно) не пользуется Dictionary в описанном ключе =)

Это каких дебатов?

Массивы и векторы - это коллекции в которых разрешены повторения. С точки зрения использования, асимптотическая сложность чтения и записи: O(1), в определенных случаях возможна сортировка. Если сортировка возможна, то ее асимптотичекая сложность: O(n log n). В массивах и векторах, если их можно линейно упорядочить, поиск элемента возможен с асимптотической сложностью O(log n) (т.н. бинарный поиск).
Удаление или добавление из/к таких/м коллекций/ям, это O(n) операция (т.как нужно копировать всю коллекцию).
Массивы отличаются от векторов тем, что не декларируют тип элементов.
Типы векторов в AS3 не совместимы по присваиванию. Это значит, что Vector.<EventDispatcher> не является под-типом Vector.<Object>, тем не менее есть тип, которому принадлежат все векторы: Vector.<*>.

Кроме этого есть много деталей реализации, которые делают теорию не такой простой и однозначной. Но для краткости, не будем вдаваться в подробности.

Хеш-таблицы - это коллекции в которых запрещены повторения. Асимптотическая сложность чтения, записи, удаления и добавления - O(1). Хеш-таблицы по-определению не сортируются, зато поиск в них - опять же, O(1).
Object - не смотря на то, что во многих отношениях ведет себя как хеш-таблица с ключами строкового типа, на самом деле не совсем хеш таблица. Т.как AS3 не различает на уровне синтаксиса вызов метода специализирующегося на каком-то типе и попытку получить значение по ключу из хеш-таблицы, некоторые ключи в Object просто нельзя положить (т.как они совпадают с уже существующими методами).
Dictionary - позволяет использовать произвольные объекты в качестве ключей (в отличие от Object, где это только строки). Но обладает все теми же недостатками. Кроме того, в виду тех же недостатков синтаксиса, изза которых нельзя отличить вызов собственного метода от поиска значения по ключу, хранение ключей примитивных типов в Dictionary работает следующим образом: сначала простые типы конвертируются в строку, а потом хранятся отдельно от ссылочных типов. И, хотя, часто разницей можно принебречь, это может привести к ошибкам приведения типов, которые тяжело обнаружить.

wvxvw, а можно подробнее про повторения? а то не совсем понятно

Что за повторения?

[1, 2, 1]
Элемент `1' повторяется в коллекции 2 раза:
{"a" : 1, "a" : 2}
Повторения запрещены, `a' нельзя повторять.

Умм... А правильно тут сравнивать ключ объекта и значение массива? Значения то и там и там могут повторяться, а ключи нет.

Dictionary к стати наследуется от Object, может там конечно многое переопределяется, но всё-же.

:) udaаff прав

Добавлено через 4 минуты
:о) Почти все наследуется от Object.

Array - хитрореализованный список, до того хитрый, что добавление элементов с конца работает медленнее чем с 0-го (что нонсенс для Vector из С++ или List из C#)
Доступ по индексу за 0(1), удаление произвольного элемента за 0(N) - можно считать просто динамическим массивом.
В отличие от Vector - у Array доступ по индексу в 2 раза медленнее и не кидает исключений при выходе индекса за границы

Непонятно зачем, но может работать как хештаблица
Однако, если в качестве ключа в него попадёт "132423345" и сконвертится в числовой индекс - моментально огребёте с памятью. Ну и если большие числовые индексы задавать - тоже самое будет - я бы в качестве хеша не юзал.
Еще при использовании в качестве ассоциативного массива свойство lengh - вообще показывает неизвестно что, а не общее количество элементов.

Vector - Предсказуемый тип, работает практически так же как Vector из stl С++ или List из C#
Возможна типизация элементов
Но невозможны преобразования:
Object - он же динамический объект, он же предок всего и вся, он же Хеш-таблица
Причём, то, что он предок всего - не означает, что всё может работать как хеш-таблица. Такая вот забавная организация типов.
Если использовать как хеш-таблицу:
- любой ключ конвертирует в строку - поэтому с памятю как в случае с Array не огребёте
- но из-за этой конвертации теряет в производительности, если использовать числовые ключи
(object[13234] эквивалентно object["13234"])

Dictionary
Тоже хештаблица, но ключами могут быть любые объекты.
Со строковыми ключами работает с той же скоростью, что и Object, с числовыми не помню - но по крайней мере не шибко медленнее Object.
Применяется если в качестве ключа удобнее использовать объект, а не строку или число.

Вот наглядный тест:


Можно делать так-же связанные списки, в тесе они есть, то-же очень быстрые конкуренты аррею и вектору, а вот словарь и объект сильно проигрывают всем.

Нет, заметно не огребёте. Я это даже как-то использовал, вектор у меня сдувался по памяти, а массив работал. Немного писал про это http://www.flasher.ru/forum/blog.php?b=451

не все простые типы конвертируются в строку. но и наоборот строка с числом конвертируется в число
Так вот, чтобы избежать лишней конвертации следует хранить в хеш-таблицах так:
Ключи типа String только в Object
Ключи типа int, uint, Number, ссылки на объекты в Dictionary

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

Может на последних флешплеерах всё хорошо или данные Вам удачные попались.

Мы огребали при использовании в качестве ключей айдишников юзеров вконтакте - за 3 секунды загрузки профайлов 700 метров оперативы как ветром сдуло + бонусом подмораживание флешки на несколько секунд.
Еще ограбали, когда пытались юзать ключи (x * 100500 + y) в качестве адреса ячейки - тоже подмораживания флешки минус 500-800 метров.

При замене Array на Object (просто названия поменяли) - все эти чудеса резко исчезли.

Имел ввиду что это может сыграть роль в данном соревновании, ведь и словарь и объект могут в качестве ключа использовать имя ссылки, только блин, всё равно объект проигрывает, он оказывается вызывает метод toString() у ключа, а потом уже работает(.

:| Кого интересует можно ли повторять значения в хеш таблицах. Они вообще в таблицах не хранятся. В таблицах хранятся только ключи (указатели). Это фундаментальное свойство Блум фильтров, и его конкретной разновидности (с количеством хеш функций равном одному) - хеш таблице. Для блум фильтров вцелом, это свойство описывает соотношение между памятью и вероятной ошибкой чтения ключа, а для конкретного тривиального случая - хеш таблицы, это свойство описывающее сколько места нужно для хранения ключей. Т.е. если мы хотим хранить Х ключей, то нам нужно отвести памяти 2^n, где n такое, что при возведении двойки в эту степень число получится больше Х.
Естесственно, для больших таблиц где разница между Х и 2^n будет большая, то имеет смысл использовать бинарные деревя, например, составив их из 2^(n - 1) + 2^(n - 2) и т.п. Но это уже детали.

Главное, что ключи не могут повторятся, и именно ключи - это элементы хеш таблицы. Значения - не элементы таблицы.

wvxvw, начали мы говорить "что в массивах не так как в HashMap", а закончили "не повторяется в HashTable". В массивах тоже ключи не повторяются. Так что приведенное Вами (и оспоренное многими) различие этих структур фактически не существует.

Вообще если посмотрим на java-реализацию структуры HashMap (он же Dictionary), то мы увидим, что хэши от ключей могут повторяться. И вполне себе повторяются. Мы конечно можем сказать, что в java не "чистая" реализация структуры, но она реальная. И как я понимаю, именно такой подход используется в FlashPlayer. То есть да, у нас не всегда время доступа O(1), но мы можем с уверенностью говорить что время доступа стремится к O(1).
Это я к тому, что излишки памяти, выделяемые для HashMap, зависят все же не от "размера" ключа, а от количества объектов в структуре и эвристик плеера. Под эвристиками понимается определение необходимости перестроения структуры с целю оптимизации времени доступа.

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

Ну, скажем, само определние "хэш-таблица" на этом не настаивает. Я к тому, что ты всегда можешь увеличить ёмкость (capacity) и пересчитать хэш заново. Просто это, мягко говоря, неоптимально.

Ох блин... тоже нашли на что равнятся... Но да не важно. Массив состоит из элементов. Размер массива ровно такой, как размер элемента умножить на количество элементов. Хеш таблица (про карты я ничего не говорил, и вообще это к делу отношение не имеет), это таблица из указателей на значения. Размер значений не имеет значения, имеет значение только размер указателей. В общем случае (Блум фильтр) хеши могут повторятся (т.как их может быть много для одного ключа), но в тривиальном случае для одного единственного хеша - нет, не могут повторятся, т.как произойдет потеря данных.

Да, но бывают, естесственно, массивы типа как в Обжектив-Си и т.п. где в массив всегда складываются указатели (что позволяет "складывать разные объекты" в массив, хотя, на самом деле, просто складывает в массив указатели).
Реализация массивов в AS3 - вообще не похожа на массивы (это хеш таблицы с ключами - целыми беззнаковыми числами), но это "деталь реализации", и не нужно так себе представлять массивы, это суровое наследие всяких дурацких стандартов. Правильнее, наверное, называть это динамическим массивом. Но это уже такое... большинство сходится на названии ECMAScript Array.

А можно вопрос? Кто-нибудь разрабатывает реальные такто-зависимые приложения на flash, чтобы так обстоятельно считать, какой из наборов лучше по скорости? Если настолько критична скорость выполнения программы, не лучше выполнить этот кусок на С++ или если еще более критично - на ассемблере?

Троллите?
Как бы даже на одном из самых медленных языков - Phython использовать сет или список - дело различий в скрости выполнеия в десятки/сотни раз - просто потому что в одном случае - сложность логарифм - в другом линейная.
В какой вообще ситуации может быть не важен выбор структуры данных?

Нет, вопрос реальный.

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