Здравствуйте, Mab, Вы писали:
Mab>Это, кстати, и показывают тесты, которые я привел ранее -- хештаблица .NET обгоняет std::map на 50 элементах.
Осталось только выяснить как часто встречается switch в котором 50 case. Я такой встречал только в двух случаях — генерённый конечный автомат и ручная обработка оконных сообщений. Оба случая далеко не самые распространённые.
К тому же есть ещё один момент — константность. То что стоит после case перед : не должно меняться во времени. а вот с константами в .Net немного фигово. Фактически она существует только для value типов.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, alexeiz, Вы писали: A>>Для количества элементов в контейнере равное 1 дерево будет быстрее хэш-таблицы, это очевидно. Для достаточно большого количества элементов хэш-таблица с хорошей хэш-функцией будет быстрее дерева. Значит, есть такое количество элементов, вплоть до которого дерево будет быстрее чем хэш-таблица.
Mab>Ты ошибаешься вот в чем: в отличие от дерева, у хештаблицы есть дополнительный параметр -- коэффициент заполнения, который напрямую влияет на скорость. Если его сделать достаточно большим и считать, что хешфункция хорошая, то время доступа будет O(1). Так что такое лобовое сравнение с деревом не годится. Засчет дополнительного расхода по памяти хештаблица может успешно обогнать дерево на любых размерах. Вопрос только в том, устраивает ли тебя такой tradeoff.
Опять мне приводят ассимптотики. Ассимтотики неприменимы в этой области N.
Mab>Это, кстати, и показывают тесты, которые я привел ранее -- хештаблица .NET обгоняет std::map на 50 элементах.
Что показывают твои тесты, так это то, что для .NET нет эффективной реализации коллекции основанной на дереве. Сравнения же .NET и std::map не к месту, т.к. объектные модели в .NET и в C++ абсолютно разные.
Здравствуйте, alexeiz, Вы писали:
A>Опять мне приводят ассимптотики. Ассимтотики неприменимы в этой области N.
При чем тут асимптотики? Твое утверждение A>Значит, есть такое количество элементов, вплоть до которого дерево будет быстрее чем хэш-таблица.
не верно, т.к. подбором коэффициента заполнения можно добиться того, чтобы хештаблица обноняла дерево на любом размере. Асимптотика тут побоку.
A> Сравнения же .NET и std::map не к месту, т.к. объектные модели в .NET и в C++ абсолютно разные.
При чем тут объектные модели?? Приведено два фрагмента кода, решающие одну и ту же задачу. Если посмотреть внимательно, то видно, что даже действия с коллекцией одни и те же производятся вплоть до наличия общего генератора случайных чисел.
Или, думаешь, если хештаблицу из .NET переписать на C++, то она станет медленнее работать что ли?
Здравствуйте, Mab, Вы писали:
Mab>не верно, т.к. подбором коэффициента заполнения можно добиться
Можно. Кто же спорит? но делать это должен будет компилятор для предопределённой функции.
P.S. Никто не говорит, что хеш-таблицы это плохо. Не надо доказывать что хеш-таблицы вообще это при некотором перерасходе памяти быстрее, чем деревья вообще. У нас тут случай оператора switch — сомнительная хеш-функция и 5-20 case'ов.
Здравствуйте, adontz, Вы писали:
A>Осталось только выяснить как часто встречается switch в котором 50 case. Я такой встречал только в двух случаях — генерённый конечный автомат и ручная обработка оконных сообщений. Оба случая далеко не самые распространённые.
Компилятор C# для свитча по строкам использует хэш-таблицу если количество элементов превышает 6 элементов. До этого разруливает на if-ах. Ну, а деревья вообще никогда не использует, так как не разумно.
A>К тому же есть ещё один момент — константность. То что стоит после case перед : не должно меняться во времени. а вот с константами в .Net немного фигово. Фактически она существует только для value типов.
Тут ты отчасти прав. Вот только константность обеспечивается еще неизменяемостью объектов. Например, строки именно не изменяемые объекты.
Однако дотнет же не запрещает использовать изменяемые объекты в хэш-таблицах. Так можно было и в свитчах позволить использовать.
Но уверен, что это не сделано именно из соображений константности.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, alexeiz, Вы писали:
A>Что показывают твои тесты, так это то, что для .NET нет эффективной реализации коллекции основанной на дереве. Сравнения же .NET и std::map не к месту, т.к. объектные модели в .NET и в C++ абсолютно разные.
Изумительный вывод! Если его развить, то для С++ вообще нет эффективной реализации коллекции! Я плякаль.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, Mab, Вы писали:
Mab>>не верно, т.к. подбором коэффициента заполнения можно добиться
A>Можно. Кто же спорит? но делать это должен будет компилятор для предопределённой функции.
Это уже делает текущая реализация хэш-таблицы. У нее есть параметр "коэффициент заполнения" который автоматически перестраивает хэш-таблицу если он превышен. По умолчанию задан довольно разумный коэффициент, но ты можешь задать его вручную.
A>P.S. Никто не говорит, что хеш-таблицы это плохо. Не надо доказывать что хеш-таблицы вообще это при некотором перерасходе памяти быстрее, чем деревья вообще. У нас тут случай оператора switch — сомнительная хеш-функция и 5-20 case'ов.
И кто будет виноват если делает что-то сомнительное? Мне все безрукие уроды по барабану. Если человек идиот, то это надолго. Я же хотел бы не писать каждый раз килограм кода, а иметь удобный синтаксический сахар. Эффективность же это моя проблема. Если я посчитаю, что для одной из миллиона задачь дерево более примлемо, то воспольуюсь им забив на свитчь.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, alexeiz, Вы писали:
A>За границы разумного выходят твои книжные знания. Ассимптотичное поведение не имеет ни малейшего значения для малых N.
Можно без умных слов? Что ты скажешь на тесты маба
Вроде как твои заявленные 100 элементов, а реализация на управляемом языке с кучае рантайм проверок и далеком от идеала оптимизирующим компилятором рвет твое дерево как тузик грелку. Хороши "книжные знания".
A>Для количества элементов в контейнере равное 1 дерево будет быстрее хэш-таблицы, это очевидно.
Да? И что же тут очевидного? И вообще, о какой скорости тут можно говорить?
A> Для достаточно большого количества элементов хэш-таблица с хорошей хэш-функцией будет быстрее дерева.
С хорошей то? Да, для любого!
A> Значит, есть такое количество элементов, вплоть до которого дерево будет быстрее чем хэш-таблица.
Да, с чего же это?
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Mab, Вы писали:
A>>Опять мне приводят ассимптотики. Ассимтотики неприменимы в этой области N. Mab>При чем тут асимптотики? Твое утверждение A>>Значит, есть такое количество элементов, вплоть до которого дерево будет быстрее чем хэш-таблица. Mab>не верно, т.к. подбором коэффициента заполнения можно добиться того, чтобы хештаблица обноняла дерево на любом размере. Асимптотика тут побоку.
Правда при этом нужно говорить подбором значений можно сделать так, что никакой коэффициент не спасет.
Второй недостаток невозможность хранить повторяемые значения.
Здравствуйте, GlebZ, Вы писали:
GZ>Разве там ключ не должен быть уникальным?
В смысле? Ключ здесь уникальный. Только ему соответствует не одно значение, а список. Конечно, придется дописать некоторый код. Если лень -- можно взять PowerCollections, там есть MultiDictionary, где это уже сделано за нас.
В общем, никаких теоретических трудностей с множественными значениями нет.
Здравствуйте, Mab, Вы писали:
Mab>В смысле? Ключ здесь уникальный. Только ему соответствует не одно значение, а список. Конечно, придется дописать некоторый код. Если лень -- можно взять PowerCollections, там есть MultiDictionary, где это уже сделано за нас. Mab>В общем, никаких теоретических трудностей с множественными значениями нет.
Ой-ли. Обычно для хеш таблицы с одинаковыми значениями N скорость вставки равняется О(N). Для деревьев логарифмическая сложность сохраняется.
Здравствуйте, GlebZ, Вы писали:
GZ>Ой-ли. Обычно для хеш таблицы с одинаковыми значениями N скорость вставки равняется О(N).
Еще раз. Повторяю. Постарайся осмыслить: ключи в хештаблице будут уникальны. Но каждому будет соответствовать список значений (раз это многозначное отображение).
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, GlebZ, Вы писали:
GZ>>Ой-ли. Обычно для хеш таблицы с одинаковыми значениями N скорость вставки равняется О(N). Mab>Еще раз. Повторяю. Постарайся осмыслить: ключи в хештаблице будут уникальны. Но каждому будет соответствовать список значений (раз это многозначное отображение).
Понятно. Ты просто не понял. Я под значением подразумевал классическое определение значения в хеш-таблицах, по которому генерится ключ.
Здравствуйте, GlebZ, Вы писали:
GZ>Понятно. Ты просто не понял. Я под значением подразумевал классическое определение значения в хеш-таблицах, по которому генерится ключ.
Точно. Ничего не понял Что за "значение" по которому генерится "ключ"?
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, GlebZ, Вы писали:
GZ>>Понятно. Ты просто не понял. Я под значением подразумевал классическое определение значения в хеш-таблицах, по которому генерится ключ. Mab>Точно. Ничего не понял Что за "значение" по которому генерится "ключ"?
Sorry, опять неверно высказался. Что такое классическая хеш таблица. Это некоторый массив значений. По этим значениям с помощью некоторой хеш функции определяется позиция (иногда позиция для дальнейшего поиска в случае неуникальных значений). Просто в данном случае (да и в большинстве реализаций) хеш таблица является также контейнером других объектов. И в этом случае действительно появляется ключ(но он необязательный аттрибут любой хеш таблицы).
Здравствуйте, GlebZ, Вы писали:
GZ>Sorry, опять неверно высказался. Что такое классическая хеш таблица. Это некоторый массив значений. По этим значениям с помощью некоторой хеш функции определяется позиция (иногда позиция для дальнейшего поиска в случае неуникальных значений). Просто в данном случае (да и в большинстве реализаций) хеш таблица является также контейнером других объектов. И в этом случае действительно появляется ключ(но он необязательный аттрибут любой хеш таблицы).
Господи, какой <пип>!
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
А мы switch делаем для произвольных объектов ? или конкретных ,int ? string ?
Не нужно забывать также что в хештабличке также используется оператор == который для множеств даст те же грабли . А с плохой хеш функцией вообще может дать наихудшую производительность в плохом случае. А дерево работает стабильно .
Давайте думать есть ли случаи когда оператор < реализовать тяжело , а == легко.
A>Влад, GetHashCode для строк и GetHashCode для произвольного класса написанного Васей Пупкиным ну очень различаются по качеству.
Любой набор данных это некая последовательность байтов. Применяя для них выверенные алгоритмы для строк, ты мало чем рискуешь. Другое дело, что не везде нужно подходить так тупо.
и солнце б утром не вставало, когда бы не было меня
но делать это должен будет компилятор для предопределённой функции.
