Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, adontz, Вы писали:
A>>Влад, я не против хеш-таблиц, я прекрастно понимаю, все их преимущества! Но хеш-таблицам нужны хеш-функции, а писать их будет кто-попало. И я думаю, что от этого проблем будет больше чем пользы.
VD>Любые функции может писать кто попало. При этом результат может быть печальным. И какие из этого можно сделать выводы?
Мне кажется имелось ввиду , что оператор сравнения можно написать правильно и неправильно , а хеш еще и можно написать плохо.
Здравствуйте, minorlogic, Вы писали:
M>Мне кажется имелось ввиду , что оператор сравнения можно написать правильно и неправильно , а хеш еще и можно написать плохо.
Вот! Хорошо сформулировал! У оператора < есть всего два состояния: правильно написан и неправильно написал. А у функции GetHashCode() весь спектр приключений
Здравствуйте, minorlogic, Вы писали:
M>Давайте думать есть ли случаи когда оператор < реализовать тяжело , а == легко.
ОК. Реализуй компаратор для пары object-ов
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, minorlogic, Вы писали:
M>>Давайте думать есть ли случаи когда оператор < реализовать тяжело , а == легко. Mab>ОК. Реализуй компаратор для пары object-ов
Здравствуйте, minorlogic, Вы писали:
M>В чем сложность , не уловил . Можно подробнее ?
Как устроить дерево поиска, хранящее произвольные объекты (object)? Равенство есть автоматически -- object.ReferenceEquals. Как предлагается устраивать сравнение?
Здравствуйте, Mab, Вы писали:
Mab>Как устроить дерево поиска, хранящее произвольные объекты (object)? Равенство есть автоматически -- object.ReferenceEquals. Как предлагается устраивать сравнение?
Если типы объектов не равны, то сравнивать просто строковые названия типов. Если же равны, то использовать operator < для типа.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, GlebZ, Вы писали:
GZ>>Sorry, опять неверно высказался. Что такое классическая хеш таблица. Это некоторый массив значений. По этим значениям с помощью некоторой хеш функции определяется позиция (иногда позиция для дальнейшего поиска в случае неуникальных значений). Просто в данном случае (да и в большинстве реализаций) хеш таблица является также контейнером других объектов. И в этом случае действительно появляется ключ(но он необязательный аттрибут любой хеш таблицы).
VD>Господи, какой <пип>!
А зачем такой пип. Ключ нужен для только быстрого сравнения. Если этого не нужно (например спец хэш таблицы где ключ и есть сам объект и дополнительного ключа не надо (байт, ворд, 3 байта, дворд), или в качестве экономии 4 байт на запись.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, minorlogic, Вы писали:
M>>В чем сложность , не уловил . Можно подробнее ? Mab>Как устроить дерево поиска, хранящее произвольные объекты (object)? Равенство есть автоматически -- object.ReferenceEquals. Как предлагается устраивать сравнение?
Скорее всего если есть механизм определения типа во время выполнения , то и сравнивать этот механизм позволит (по имени , по id и т.д)
Здравствуйте, minorlogic, Вы писали:
M>Скорее всего если есть механизм определения типа во время выполнения , то и сравнивать этот механизм позволит (по имени , по id и т.д)
В смысле "скорее"? Покажите мне этот механизм в .NET. Подсказка: никаких имен и id у объектов в общем случае нет.
Здравствуйте, adontz, Вы писали:
A>Причём тут object? Я же сказал — "если типы равны". То есть у нас есть две переменные типа object, на на самом деле они обе типа T и мы вызываем A>
A>bool T::operator < (T t);
A>
Хм. А с чего ты взял, что тип T определил такой оператор? Я рассматриваю случай, когда, скажем, нужно устроить ассоциативную таблицу, где ключами будут приходящие извне экземпляры сслочного типа, про который мне ничего не известно.
Здравствуйте, minorlogic, Вы писали:
M>Мне кажется имелось ввиду , что оператор сравнения можно написать правильно и неправильно , а хеш еще и можно написать плохо.
Готов за деньги написать/переписать любой код настолько плохо, что вы ужаснетесь.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>>и понеслась... GZ>Разве там ключ не должен быть уникальным?
Он там и уникален. Просто вместо одного объекта хранится список. Для вэлютипов это понятно бессмысленно, так как равные вэлью-типы ничем не отличаются. Но для объектов это более чем разумно.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
V>>Кстати, несмортя на то, что вопрос не плохой, стоит сделать акцент на том, что удовлетворение всех вовсе не обязательно. Т.е. для кого-то эти массивы равны, если рассматриваются как множества, а для кого-то нет. Действительно, для некоторых задач предпочтительней map-ы, основанные на отношении порядка. Это никак не противоречит тому, что для других задач отношение порядка по боку.
VD>Ага. И если вернуться к вопросу реализации switch-а, то казалось бы зачем для этого упорядычивание?
А что, компилятор не в состоянии определить, какой подход лучше? Если у нас, например, целые или enum из непрерывного последовательного диапазона, то в этом случае как хеш, так и мап и на фиг не сдались.
И еще, для switch по длинным строковым константам map работает лучше хеш ф-ии. Т.е., я вообще за то, чтобы конкретную реализацию switch компилятор выбирал исходя из типов и значений констант.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, vdimas, Вы писали:
V>>Дело не в сериализации, а в получении упорядоченного множества элементов коллекции. (наверно adontz имел в виду это). В приведенной ссылке одному богу известно зачем Wolfhound использовал Hashtable. Оно там вовсе не нужно.
VD>Зачем Wolfhound хэш-таблица как раз понятно.
Мне не понятно. Там банальный список состояний. По НКА-графу автомат все-равно не работает реально, т.е. это промежуточное представление.
VD>А вот зачем нужно упорядычивание для реализации switch-а?
Пример Wolfhounda не имеет отношения к свичу. Отношение порядка нужно для построения мапов или сортированных последовательностей. И в чем прикол ситуации, так это в том, что графах НКА в реальной жизни от вершин отходит в среднем менее десятка дуг. Именно на таких объемах сама Microsoft рекомендует использовать SortedList вместо Hashtable. Тем более присоединяюсь, т.к. ключами в этом случае являются символы — суть целочисленные значения, для которых заведомо определено отношение порядка.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, vdimas, Вы писали:
V>>Если твой StateSet рассматривать как упорядоченное множество State-ов, то отношение порядка для него строится более чем легко при существовании отношения порядка для самих State-ов.
V>>Для введения отношения порядка самих States достаточно их пронумеровать, желательно в порядке ввода в грамматику (например, начиная с состояния Start и далее последовательно таким образом, чтобы новые состояния в грамматику вводились как результат перехода из уже существующего множества состояний... хотя и это не обязательно, просто такое отношение порядка удобно может использоваться и в др. случаях, например при построении визуального отображения графа грамматики)
VD>Здорово! И по ходу преобразования НКА в ДКА мы много раз будет удалять и добавлять состояния. При этом будут меняться характеристики множеств. Они то будут "больше" других, то "меньше". Для решаемой задачи — это не имеет никакого значения. Но мы, чисто от вредности, будет пересчитаывать все внутренние структуры.
Немного не так. При построении ДКА (если это вообще возможно для данного НКА) мы "склеиваем" несколько состояний НКА в одно состояние ДКА. Т.е., новое (промежуточное) представление ДКА — отображение "старых" состояний и переходов НКА на оные ДКА. По окончании алгоритма промежутоное представление обычно приводят к более простому представлению, т.к. нас не интересуют исходные состояния НКА, именно в этот момент новые состояния ДКА можно пронумеровать. (Хинт — это здорово помогает при сохранении и восстановлении графа НКА)
VD>А смысл? Хэш-таблица решает задачу без побочных эффектов и к тмоу же далате это быстрее чем другие методы.
Я ведь вообще не собираюсь спорить ни с одной из сторон. Мне лишь кажется странным упорное отстаивание участниками своих точек зрения, в то время как очень многие неоднократно убеждались в неуниверсальности и негарантированной эффективности каждого из подходов. Простота реализации и эффективность работы каждого из вариантов зависят от характера (типа) данных и банально от самих данных.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Mab, Вы писали:
Mab>>На приведенный пример есть одно возражение: число корзин хеш-таблицы -- всегда простое число, так что 100 там не может быть даже теоретически.
VD>Это эвристика котору не обязательно соблюдать. Так что "всегда" в данном случае говорить неуместно.
Почему эвристика? Банально у простого числа (размера таблицы) и произвольного другого числа (значение хеш ф-ии) отсутствуют общие делители (т.е. хеш ф-ия которая выдает некие кратные значения не будет попадать на одни и те же ячейки по кругу). Остается только случай кратности значения хеш ф-ии длине таблицы, которых заведомо меньше.
Mab>Хм. А с чего ты взял, что тип T определил такой оператор? Я рассматриваю случай, когда, скажем, нужно устроить ассоциативную таблицу, где ключами будут приходящие извне экземпляры сслочного типа, про который мне ничего не известно.
