Здравствуйте, adontz, Вы писали:
WH>>А чем они хуже? А! Знаю! Такие объекты практически не возможно запихнуть в ту систему что ты тут позиционируешь как единственно верную. A>Я не сказал, что она единственно верная, я даже не говорю что она самая оптимальная, я говорю что в ней нету подводных камней. Ты вообще не те параметры хвалишь.
Подводный камни есть всегда. И как мы толькочно убедились они есть и в схеме с деревом ибо иногда ниписать less практически не возможно.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице?
Дерево работает быстрее, чем hash таблица, для малого количества элементов. Я проверял на std::set и stdext::hash_set из библиотеки VC8. Для .NET можно тоже проверить, знать бы только, где есть хорошая реализация контейнера, построеного на деревьях.
Здравствуйте, WolfHound, Вы писали:
WH>3)Может ты всетки определишь отношение порядка для StateSet? Или слабо?
Если твой StateSet рассматривать как упорядоченное множество State-ов, то отношение порядка для него строится более чем легко при существовании отношения порядка для самих State-ов.
Для введения отношения порядка самих States достаточно их пронумеровать, желательно в порядке ввода в грамматику (например, начиная с состояния Start и далее последовательно таким образом, чтобы новые состояния в грамматику вводились как результат перехода из уже существующего множества состояний... хотя и это не обязательно, просто такое отношение порядка удобно может использоваться и в др. случаях, например при построении визуального отображения графа грамматики)
WH>А если слабо то больше не делай заявлений типа WH>
Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net
Да разные подходы, чего тут спорить на ровном месте. Hash-подход хорошо работает в случае "хорошего" распределения значений относительно текущей величины хеш-таблицы. В других случаях оказывается удобным (или даже эффективным!!!) определить отношение порядка. Я бы ввел в коллекции оба вида контейнеров, и пусть пользуются на здоровье.
Кстати, экспериментировал с поиском для строк в разных коллекциях. В общем, самый быстрый — это ветвление по дереву по каждой следующей букве строки. Т.е. самым оптимальным оказался смешанный способ. В каждом узле дерева — хеш-таблица ветвлений по текущему символу.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, adontz, Вы писали:
A>>Друг, ты хоть с документацией сверяйся, а потом говори, если так не помнишь Mab>XmlSerializer не умеет работать с IDictionary. Только непонятно, при чем тут это...? Возьми BinaryFormatter, он замечательно сериализует твой класс.
Дело не в сериализации, а в получении упорядоченного множества элементов коллекции. (наверно adontz имел в виду это). В приведенной ссылке одному богу известно зачем Wolfhound использовал Hashtable. Оно там вовсе не нужно.
A>Суть в том, что классы реализующие IDictionary в частности, и коллекции вообще это проблема от которой надо избавляться, а не решать. И дело тут не в подходе (хеш или оператор), а в осмысленности. Вот два массива {1,2,3} и {3,1,2} равны или нет? Причём ответь так, чтобы всех удовлетворило. Очевидно, что ответа нет. Причём его нет и для хешей. А Wolfhound этим почему-то доказывает, что оператор < это плохо
Кстати, несмортя на то, что вопрос не плохой, стоит сделать акцент на том, что удовлетворение всех вовсе не обязательно. Т.е. для кого-то эти массивы равны, если рассматриваются как множества, а для кого-то нет. Действительно, для некоторых задач предпочтительней map-ы, основанные на отношении порядка. Это никак не противоречит тому, что для других задач отношение порядка по боку.
A>>Суть в том, что классы реализующие IDictionary в частности, и коллекции вообще это проблема от которой надо избавляться, а не решать. И дело тут не в подходе (хеш или оператор), а в осмысленности. Вот два массива {1,2,3} и {3,1,2} равны или нет? Причём ответь так, чтобы всех удовлетворило. Очевидно, что ответа нет. Причём его нет и для хешей. А Wolfhound этим почему-то доказывает, что оператор < это плохо WH>Ну почемуже сразу избавляться? WH>Все зависит от задачи. В моем случае равны. Соответственно я написал хеш и сравнение которым порядок до лампочки. Если бы порядок элементов в массиве имел значение то вычисление хеша и сравнение я бы реализовал иначе. WH>Сходи по моей ссылке и попробуй решить эту задачу без сравнения множеств...
Hint: там у тебя необязательно было использовать Hashtable в StateSet.
Здравствуйте, alexeiz, Вы писали:
A>Здравствуйте, WolfHound, Вы писали:
WH>>Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице?
A>Дерево работает быстрее, чем hash таблица, для малого количества элементов. Я проверял на std::set и stdext::hash_set из библиотеки VC8. Для .NET можно тоже проверить, знать бы только, где есть хорошая реализация контейнера, построеного на деревьях.
Это зависит не только от числа элементов, но и от относительного качества Hash-функции применительно к текущему размеру Hash-таблицы,
Здравствуйте, WolfHound, Вы писали:
WH>И как мы толькочно убедились они есть и в схеме с деревом ибо иногда ниписать less практически не возможно.
Никто ни в чём не убедился. Сравнением множеств, а не упорядоченных списков это вполне понятно более сложная вычислительная задача. но не неразрешимая. Прямо сейчас могу написать за O(n*log(n))
Здравствуйте, vdimas, Вы писали:
V>Это зависит не только от числа элементов, но и от относительного качества Hash-функции применительно к текущему размеру Hash-таблицы,
Нет-нет. Ты не прав. В .Net ве хеш функции чудесны, кто бы их не писал, по определению. Это преимущество компонентной среды.
Здравствуйте, adontz, Вы писали:
A>Вот два массива {1,2,3} и {3,1,2} равны или нет? Причём ответь так, чтобы всех удовлетворило.
Честно говоря, не вижу проблемы. Есть два различных понятия: set и sequence (ordered set). Какое из понятий применимо в данной задаче -- виднее тому, кто эту задачу решает. Для того и создан интерфейс IEqualityComparer<T>.
Здравствуйте, adontz, Вы писали:
V>>Это зависит не только от числа элементов, но и от относительного качества Hash-функции применительно к текущему размеру Hash-таблицы,
A>Нет-нет. Ты не прав. В .Net ве хеш функции чудесны, кто бы их не писал, по определению. Это преимущество компонентной среды.
Понимаешь, у твоих оппонентов есть один "мощщщный" аргумент. Каким бы плохим не был разброс Hash-значений относительно текущей величины таблицы, эта фишка все-равно работает, даже если время поиска элементов приближается к линейному
Т.е., фигня, что иногда - это самый неэффективный способ, "в среднем" работает нормально и ладно, особенно учитывая легкость написания самих hash-функций.
Тут надо отдать должное, что это "иногда" — крайний редкий случай. Поясню.
Текущая позиция элемента — это не само хеш-значение, а модуль по делению его на текущий размер таблицы. Предположим даже "очень плохую" хеш-функцию, возвращающую некие кратные значения, типа 0, 100, 200 и т.д., и "плохой" размер таблицы — 100 элементов. При заполнении на 70% произойдет rehash, и наша периодичность сама собой исчезнет. Однако, до этого момента поиск в такой таблице будет линейным. Однако, на практике, задержка таблицы в размере с периодичными наложениями встречается крайне редко, ибо rehash производится при первом же конфликте вставки, а вероятность его тем выше, чем больше неких значений, дающих кратный остаток от деления. Т.е. для описанного случая достаточно, чтобы наша "плохая" хеш-функция вернула буквально пару некратных значений, при основной массе кратных и мы резко ускорим наступление конфликта.
В итоге получается, что некая "плохая" хеш-функция будет провоцировать rehash при вставке до тех пор, пока эта функция не войдет ммм... в гармонию с неким очередным размером таблицы.
Исключение составляет вырожденный случай — генерация константного значения хеш-функцией. Очевидно, этот случай не может являться аргументом.
Здравствуйте, vdimas, Вы писали:
V>Текущая позиция элемента — это не само хеш-значение, а модуль по делению его на текущий размер таблицы. Предположим даже "очень плохую" хеш-функцию, возвращающую некие кратные значения, типа 0, 100, 200 и т.д., и "плохой" размер таблицы — 100 элементов.
На приведенный пример есть одно возражение: число корзин хеш-таблицы -- всегда простое число, так что 100 там не может быть даже теоретически.
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, alexeiz, Вы писали:
A>>Здравствуйте, WolfHound, Вы писали:
WH>>>Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице?
A>>Дерево работает быстрее, чем hash таблица, для малого количества элементов. Я проверял на std::set и stdext::hash_set из библиотеки VC8. Для .NET можно тоже проверить, знать бы только, где есть хорошая реализация контейнера, построеного на деревьях.
V>Это зависит не только от числа элементов, но и от относительного качества Hash-функции применительно к текущему размеру Hash-таблицы,
Для малого количества элементов hash функция не имеет большого значения.
Здравствуйте, Mab, Вы писали:
Mab>На приведенный пример есть одно возражение: число корзин хеш-таблицы -- всегда простое число
Кстати, а какая от этого польза?
Ведь если хеш-функция возвращает значения в диапазоне [0,N), а размер хеш-таблицы K, то вероятность того, что на одну ячейку придутся несколько значений N/K и не зависит от простоты K. Если хеш-функция плоха, то есть некоторые значения из диапазока [0,N) более вероятны чем другие для случайного аргумента, то простота K не исправит ситуации.
С одной стороны ясно, что простота K означает, что при увеличении размера хеш-балицы элементы попадут в другие места, но ведь для хорошей хеш-функции это должно быть безразлично.
Выходит проектировали сразу для плохой и хеш таблица заполненая меньше чем наполовину это норма?
Здравствуйте, adontz, Вы писали:
A>>>А что ты сможешь посчитать осмысленный хеш не перебрав все элементы множества? WH>>А это тут причем? A>А суть в том, что проблемы вообще нету, есть проблема написати быстро. Для неупорядоченных коллекций представляющих собой множества это нереально.
Ничего не понял. Что не реально? Хеш посчитать не реально?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, Mab, Вы писали:
Mab>>На приведенный пример есть одно возражение: число корзин хеш-таблицы -- всегда простое число
A>Кстати, а какая от этого польза?
Вопрос этот слишком сложен, чтобы можно было дать ответ прямо сходу. Некоторые (эвристические) соображения в пользу того, чтобы брать модуль равным простому числу, изложены в 3-м томе Искусства Программирования.
В контексте реализации .NET простой модуль необходим, т.к. там используется двойное хеширование, т.е. позиция (bucket) вычисляется так:
pos = (h1(obj) + k*h2(obj)) mod M
где h1, h2 -- две хеш-функции (первая совпадает с GetHashCode, вторая получается из нее), k -- число уже просмотренных позиций.
Такми образом, простота M гарантирует, что когда k пробегает значения 0..M-1 данная формула дает все позиции 0..M-1.
A>Выходит проектировали сразу для плохой и хеш таблица заполненая меньше чем наполовину это норма?
Конечно, странно ожидать от входных данных истинно равномерного распределения. Насчет 'наполовину' -- откуда это взялось, я не понял. Производительность хештаблицы тем хуже, чем больше в ней коэффициент заполнения. Какое именно значение выбрать в качестве оптимума -- решать пользователю исходя из memory-speed tradeoff.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, vdimas, Вы писали:
V>>Текущая позиция элемента — это не само хеш-значение, а модуль по делению его на текущий размер таблицы. Предположим даже "очень плохую" хеш-функцию, возвращающую некие кратные значения, типа 0, 100, 200 и т.д., и "плохой" размер таблицы — 100 элементов. Mab>На приведенный пример есть одно возражение: число корзин хеш-таблицы -- всегда простое число, так что 100 там не может быть даже теоретически.
Здравствуйте, adontz, Вы писали:
A>Ведь если хеш-функция возвращает значения в диапазоне [0,N), а размер хеш-таблицы K, то вероятность того, что на одну ячейку придутся несколько значений N/K и не зависит от простоты K. Если хеш-функция плоха, то есть некоторые значения из диапазока [0,N) более вероятны чем другие для случайного аргумента, то простота K не исправит ситуации. A>С одной стороны ясно, что простота K означает, что при увеличении размера хеш-балицы элементы попадут в другие места, но ведь для хорошей хеш-функции это должно быть безразлично. A>Выходит проектировали сразу для плохой и хеш таблица заполненая меньше чем наполовину это норма?
Это более чем норма. Посмотри на это по-другому. Хеш-таблица — это просто массив, нам не надо выделять память под ячейки связи, для образования некоей пространственной структуры как в деревьях. Т.е. все-равно довольно экономно.
