Соответствие какова N сложность получения данных? #793327

Что быстрее Таблица значений с индексом или Соотвестствие?

различия не обладают статистической достоверностью - проверено экспериментально года 3 назад на разных объемах

я отдаю предпочтение соответствию в виду более простого и понятного синтаксиса. Если Кэш[Значение] = Неопределено тогда Если Кэш.НайтиСтроку(Значение, Колонка) = Неопределено Тогда меньше букв, больше толку

Получения данных или поиска по ключу?

поиск по ключу по логике Соотвествие должно иметь порядок O, а таблицазначений с индексом O(log(N)) В свое время тестировал СписокЗначений там O(N^1.2)

тебе ехать или шашечки?

Соответствие не может иметь O - такое только у доступа в массиве по индексу. Скорее всего (не могу ручаться точно) - Соответствие основано на хэш-таблицах, а индекс в ТЗ на деревьях.

соответствие быстрее

соответствие быстрее для примитивных типов

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

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

Нафига гадать, если можно просто попробовать. Все равно неизвестно, как оно в 1с внутри работает. Может оно внутри одинаково абсолютно.

Хэш еще как бы почитать тоже нужно и на это тоже тратится время.

Всё верно написали. Я то имел ввиду, что О ГАРАНТИРОВАНО даёт только доступ к массиву по индексу. С хешем это не гарантировано и в худшем случае может достигнуть O(N) - если все ключи попали в один букет. На практике несколько коллизий всегда бывает.

Это из разряда что быстрая сортировка это не О(N ln N), а в худшем случае это квадрат? В алгоритмике, если не указано иное - пишут среднюю сложность алгоритма, а если речь идет о худшем случае, то это обговаривается отдельно. Операция с хеш-таблицей О, быстрая сортировка О большое от N логарифмов. А в худшем случае случае операция с хеш-таблицей О(N), быстрая сортировка О(N*N) В все написано верно, в - неверно.

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

более того худший случай наиболее популярных алгоритмов хештаблицы это бесконечность как и средний.

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

Максимальное - О(N) при добавлении элемента (add) при расширении таблицы. Так как это происходит раз в N операций добавления, на сложность алгоритма "в среднем" это не влияет. вероятность О(N) в остальных случаях исчезающе мала. Количество проб "в среднем" в случае возникновения коллизии не зависит от размера таблицы. Поэтому сложность операций по Хеш-таблице "в среднем" равна О. Еще немного информации о реализации Hashtable в .Net

Так что быстрее, ТЗ или соответствие?

если алгоритмы где теоретически возможно зацикливание F=hash(S) Если не найден, то F=hash(S+F) атака на такое не найдена, но теоритически он имеет сложность бесконечность. Все современные алгоритмы лишены данной проблемы. Древние тоже были лишёны.

соотвествие

Зацикливание чего?! Даже если у тебя хеш-функция всегда выдает одно значение - сложность О(N) У тебя весь список хранится в одной ячейке.