Array vs Object vs Dictionary vs Vector

[expl]

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

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

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

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

[Sintesis]

Сообщение от GBee

:о) Почти все наследуется от Object.

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

[wvxvw]

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

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

[gloomyBrain]

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

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

[Psycho Tiger]

То есть да, у нас не всегда время доступа O(1), но мы можем с уверенностью говорить что время доступа стремится к O(1).

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

[gloomyBrain]

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

[wvxvw]

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

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

[Korchy]

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

[expl]

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

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

[Korchy]

Сообщение от expl

Троллите?

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

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