Здравствуйте, Mab, Вы писали:
Mab>Очень странная идея. Зачем сортировать хеши? A>>Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net Mab>Это не верно. Есть принципально два способа огранизации коллекций, поддерживающих быстрый поиск.
Ты внимательно почитай о чём речь. Мы говорили не о коллекциях, а об операторе switch по любым объектам. Чтобы это было реализовано не абы как, а качественно, из констант после case надо построить двочное дерево поиска. А для этого надо сами эти константы упорядочить. Иначе switch ничем не будет отличаться от последовательности if, а нам такой switch не нужен!
Здравствуйте, adontz, Вы писали:
A>Ты внимательно почитай о чём речь. Мы говорили не о коллекциях, а об операторе switch по любым объектам. Чтобы это было реализовано не абы как, а качественно, из констант после case надо построить двочное дерево поиска. А для этого надо сами эти константы упорядочить. Иначе switch ничем не будет отличаться от последовательности if, а нам такой switch не нужен!
Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, Mab, Вы писали:
Mab>>Очень странная идея. Зачем сортировать хеши? A>>>Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net Mab>>Это не верно. Есть принципально два способа огранизации коллекций, поддерживающих быстрый поиск.
A>Ты внимательно почитай о чём речь. Мы говорили не о коллекциях, а об операторе switch по любым объектам.
Ух ты Как далеко дискуссия зашла...
A>Чтобы это было реализовано не абы как, а качественно, из констант после case надо построить двочное дерево поиска. А для этого надо сами эти константы упорядочить.
Совершенно не обязательно. В switch стоит задача идентификации объекта, а не введения линейного порядка.
A>Иначе switch ничем не будет отличаться от последовательности if, а нам такой switch не нужен!
Почему же? Насколько понимаю, при большом количестве вариантов сейчас switch создает хештаблицу, после чего выбор нужного варианта делается запросом к ней. Этот подход эффективнее, чем бинарный поиск.
Здравствуйте, adontz, Вы писали:
WH>>Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице? A>Ну предложи что-то своё. Только так, чтобы работало
А что хеш таблица уже не работает?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, adontz, Вы писали:
WH>>>Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице? A>>Ну предложи что-то своё. Только так, чтобы работало WH>А что хеш таблица уже не работает?
Хеш ключа это индекс в хеш-таблице (обычный массив), значения которой это списки пар (ключ, значение). А что у нас возвращает замечательная функция GetHashCode()? А она у нас возвращает int, 32битное число. Размер массива который бы индексировался таким числом просто огромен, значительно превышает не только средний, но и максимальный объём памяти (который обычно 4Гб, но даже в 64 это всё не влезет).
Поэтому, ради экономии памяти, применяются разного рода компромиссные решения. В частности в MS реализации hash_map используется массив пар key-value размера 2^N, а сам хеш маскируется до младших N бит. Как результат хеш-функция не просто должна по возможности возвращать разные значения для разных аргументов, но и для случайных аргументов значения всех бит должны быть равновероятными и независимыми. Влад же (и судя по всему ты тоже) мне доказывает, что написание такой функции, это пара пустяков, а оператора < большая проблема.
Теперь вопрос — насколько хороша завязаная на хеш реализация? Правильный ответ — если хеш функция не удовлетворяет требованиям выше, то просто ужасна. Скорее всего после равенства хешей будет несколько проверок на равенство объектов и про average O(1) можно забыть, а про worsest O(N) вспомнить. И спомнить насильно.
А теперь домашнее задание
class Path
{
public char Drive;
public string Directory;
public string Filename;
public int Attributes;
public override int GetHashCode()
{
return/* Что тут надо написать, чтобы значения всех битов были равновероятны и независимы?
Причём не в теории, где Drive от 0 до 255, а на практике. */;
}
}
Подумай и над тем сколько вообще программистов знают в теории как писать такие функции, не говоря уже о практике. А вот оператор < это просто и понятно. Таким образом switch для произвольных объектов на основе хешей на практике не имеет никаких шансов быть сколько-нибудь оптимальным.
Здравствуйте, Mab, Вы писали:
Mab>Почему же? Насколько понимаю, при большом количестве вариантов сейчас switch создает хештаблицу, после чего выбор нужного варианта делается запросом к ней. Этот подход эффективнее, чем бинарный поиск.
Да, но только при условии, что хеш-функция нормальная (как я уже говорил, для случайного аргумента значения бит независимы и равновероятны). А для произвольных объектов написанных неизвестно кем это далеко не так
Здравствуйте, adontz, Вы писали: A>Да, но только при условии, что хеш-функция нормальная (как я уже говорил, для случайного аргумента значения бит независимы и равновероятны). А для произвольных объектов написанных неизвестно кем это далеко не так
Роман, а ты пробовал сам на практике хешфункции? Потому что я -- да, и опыт их использования положительный (по сравнению с деревьями поиска достигалось ускорение) Тот факт, что написав return 0; в GetHashCode можно убить производительность, ни у кого сомнений не вызывает. Только я бы поостерегся делать столь сильные выводы из этого.
Здравствуйте, Mab, Вы писали:
Mab>Роман, а ты пробовал сам на практике хешфункции? Потому что я -- да, и опыт их использования положительный (по сравнению с деревьями поиска достигалось ускорение)
С первой попытки? Иил всё таки игрался с хеш функцией? А может написал с первого раза, но до того прочёл кучу умных книжек?
Mab>Тот факт, что написав return 0; в GetHashCode можно убить производительность, ни у кого сомнений не вызывает. Только я бы поостерегся делать столь сильные выводы из этого.
Я говорю о другом. Есть множество программистов, которые пишут классы, которые потенциально могут использоваться в операторе switch.
Какой процент из них напишет сколько-нибудь разумную хеш-функцию? ИМХО если 10% то это будет уже просто замечательно. Речь ведь не о тебе или мне, а о решении, которое выйдет боком. Я напишу switch, а он будет жутко медленный из-за какого-то #$@%.
А вот в VC++ switch занимает от силы log(N) операций. И это гарантированно, а тут зависит от направления ветра во вторник.
Здравствуйте, adontz, Вы писали:
A>С первой попытки? Иил всё таки игрался с хеш функцией?
Честно говоря не знаю, с какой попытки, т.к. занимаюсь алгоритмами уже больше десяти лет. И ошибок за это время в них успал сделать кучу Конечно, почти наверняка сначала была книжка Но не могу припомнить, чтобы хоть раз возникал bottleneck в производительности именно из-за хештаблицы (а ничего сложнее, чем полином по модулю, циклические сдвиги и xor-ы я не использовал).
A>Я говорю о другом. Есть множество программистов, которые пишут классы, которые потенциально могут использоваться в операторе switch. A>Какой процент из них напишет сколько-нибудь разумную хеш-функцию?
В случае, если класс не определяет deep-семантики для равенства (т.е. равенство -- это равенство ссылок), то соответвующий GetHashCode из object обеспечивает замечательное распределение, т.к. вычисляется на основе sync block index, который чуть ли не уникален в пределах домена.
Если deep-семантика есть, то простой xor хешей компонент с циклическим сдвигом меня всегда выручал.
A>А вот в VC++ switch занимает от силы log(N) операций. И это гарантированно, а тут зависит от направления ветра во вторник.
Все-таки не нужно выдавать желаемое за действительно. VC++ свитч не может быть применен к произвольным классам. И в C# тоже не может, так что ничья.
Спору нет -- если хочешь гарантий производительности, то хеширование -- не твой метод. Но тогда придется вводить линейный порядок, а это тоже код, который нужно написать. И, кстати, что неприятно: ошибка в таком коде может обернуться кошмарной отладкой. Тот же std::set ничего не гарантирует, если предикат сравенения неправильный.
Сам, к сожалению, хорошо помню, как убил кучу времени на отладку чего-то подобного, а ошибка была в том, что нельзя сравнивать полярные углы векторов на плоскости через знак псевдоскалярного произведения -- транзитивности там нет, если не ограничиться полуплоскостью.
Так что бесплатный сыр...
Кстати, вот еще одно наблюдение на эту тему. В managed-средах вроде .NET и Java нет способа установить линейный порядок на объектах (в отличие от C++, где адрес служит уникальным идентификатором). Так что без хеширования ты вряд ли сможешь написать тот же Set<object>. Соответственно, нельзя будет организовать коллекцию объектов, если они первоначально не предназначались для этого (скажем, не реализуют IComparable<T>).
Здравствуйте, adontz, Вы писали:
A>Поэтому, ради экономии памяти, применяются разного рода компромиссные решения. В частности в MS реализации hash_map используется массив пар key-value размера 2^N, а сам хеш маскируется до младших N бит. Как результат хеш-функция не просто должна по возможности возвращать разные значения для разных аргументов, но и для случайных аргументов значения всех бит должны быть равновероятными и независимыми. Влад же (и судя по всему ты тоже) мне доказывает, что написание такой функции, это пара пустяков, а оператора < большая проблема.
Я не знаю что там в STL от MS он как извесно отстой. Но в .NET используются простые числа.
А написать хеш так чтобы он плохо работал на простых числах это не просто.
Ну разве что так
public override int GetHashCode()
{
return 0;
}
Других идей что-то в голову не приходит A>Теперь вопрос — насколько хороша завязаная на хеш реализация? Правильный ответ — если хеш функция не удовлетворяет требованиям выше, то просто ужасна.
А если в оператор < какойнибудь индус вставит Sleep(1000)? A>Скорее всего после равенства хешей будет несколько проверок на равенство объектов и про average O(1) можно забыть, а про worsest O(N) вспомнить. И спомнить насильно. A>А теперь домашнее задание
Вот только не надо мне тут экзамины устраивать.
А вобще обычно както так
class Path
{
public char Drive;
public string Directory;
public string Filename;
public int Attributes;
public override int GetHashCode()
{
int hash = 0;
hash ^= Drive.GetHashCode();
if (Directory != null)
hash ^= Directory.GetHashCode();
if (Filename != null)
hash ^= Filename.GetHashCode();
hash ^= Attributes.GetHashCode();
return hash;
}
public override bool Equals(object obj)
{
Path path = obj as Path;
if (path == null)
return false;
if (Drive != path.Drive)
return false;
if (Directory != path.Directory)
return false;
if (Filename != path.Filename)
return false;
if (Attributes != path.Attributes)
return false;
return true;
}
}
Если не хватает производительности (что в моей практике было только один раз когда я писал бинарный diff для файлов болие 4Г) можно и поизвращаться.
И вобще вот тебе домашние задание напиши оператор < для класса StateSet
. A>Подумай и над тем сколько вообще программистов знают в теории как писать такие функции, не говоря уже о практике.
А сколько программистов могут написать корректный Less? A>А вот оператор < это просто и понятно.
public bool Less(Path path)
{
if (path == null)
return false;
if (Drive < path.Drive)
return true;
if (Drive > path.Drive)
return false;
if (Directory < path.Directory)
return true;
if (Directory > path.Directory)
return false;
if (Filename < path.Filename)
return true;
if (Filename > path.Filename)
return false;
if (Attributes < path.Attributes)
return true;
if (Attributes > path.Attributes)
return false;
return false;
}
ЭТО просто и понятно? A>Таким образом switch для произвольных объектов на основе хешей на практике не имеет никаких шансов быть сколько-нибудь оптимальным.
Каким таким образом? Я что-то не понял.
Ты вобще на практике использовал хеш-таблици?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Кстати чуть не забыл... а как при помощи оператора < хранить в коллекции объекты разных типов. Я конечно понимаю что это попахивает извращением но всеже?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
WolfHound wrote: > Кстати чуть не забыл... а как при помощи оператора < хранить в коллекции > объекты разных типов. Я конечно понимаю что это попахивает извращением > но всеже?
Сначала сравнивать типы объектов (можно тупо сравнивать имена классов),
при совпадении типов — использовать оператор < для нужного типа.
Здравствуйте, WolfHound, Вы писали:
WH>Я не знаю что там в STL от MS он как извесно отстой.
Давай без огульных оскорблений. Тот STL что идёт с VS к MS не имеет прямого отношения. Кроме того, раз уж в этом hash_map отстой, ты уж покажи другой, тот который не отстой Надо же с чем-либо сравнивать.
WH>Но в .NET используются простые числа.
Откуда они берутся? Как назначаются? Кроме того проблема-то, если ты не заметил, в вычислении хеша от пользовательских классов, а не библиотечных.
WH>Других идей что-то в голову не приходит
Запросто
class A
{
private string _s1;
private string _s2;
public override int GetHashCode()
{
return _s1.GetHashCode() ^ _s2.GetHashCode();
}
}
А по логике работы _s1 и _s2 часто равны. Этого конечно не будет каждый раз, но когда случится, причины тормозов найти будет очень трудно.
A>>Теперь вопрос — насколько хороша завязаная на хеш реализация? Правильный ответ — если хеш функция не удовлетворяет требованиям выше, то просто ужасна. WH>А если в оператор < какойнибудь индус вставит Sleep(1000)?
А почему бы не вставить Sleep(1000) в вычисление GetHashCode()? Какие-то ну очень неубедительные аргументы. Я бы вставил 17 смайликов со своей стороны, но я не такой.
WH>И вобще вот тебе домашние задание напиши оператор < для класса StateSet
Hashtable помешает и правильно. Классы реализующие IDictionary нельзя и сериализовать. В том, что StateSet нельзя будет использовать в операторе switch для меня нет ничего удивительного.
WH>
WH> public bool Less(Path path)
WH> {
WH> if (path == null)
WH> return false;
WH> if (Drive < path.Drive)
WH> return true;
WH> if (Drive > path.Drive)
WH> return false;
WH> if (Directory < path.Directory)
WH> return true;
WH> if (Directory > path.Directory)
WH> return false;
WH> if (Filename < path.Filename)
WH> return true;
WH> if (Filename > path.Filename)
WH> return false;
WH> if (Attributes < path.Attributes)
WH> return true;
WH> if (Attributes > path.Attributes)
WH> return false;
WH> return false;
WH> }
WH>
WH>ЭТО просто и понятно?
Мне вполне понятно. По крайней мере я точно знаю что делать если какое-либо поле добавится или убавится. Это легко поддерживаемый код. Есть опасность, что после вставки нового поля оно не будет учтено, но такая же опасность есть и с GetHashCode().
A>>Таким образом switch для произвольных объектов на основе хешей на практике не имеет никаких шансов быть сколько-нибудь оптимальным. WH>Каким таким образом? Я что-то не понял.
В теории всё замечательно, но на практике написание хороших хеш-функций это проблема.
WH>Ты вобще на практике использовал хеш-таблици?
Ну вообще улётный аргумент. И в каждую вставлял Sleep(1000)
Здравствуйте, Cyberax, Вы писали:
C>Сначала сравнивать типы объектов (можно тупо сравнивать имена классов), C>при совпадении типов — использовать оператор < для нужного типа.
. A>Hashtable помешает и правильно. Классы реализующие IDictionary нельзя и сериализовать. В том, что StateSet нельзя будет использовать в операторе switch для меня нет ничего удивительного.
1)Причем тут сериализация?
2)Hashtable прекрасно сериализуется. Учи матчасть.
3)Может ты всетки определишь отношение порядка для StateSet? Или слабо?
А если слабо то больше не делай заявлений типа
Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
A>class Path
A>{
A> public char Drive;
A> public string Directory;
A> public string Filename;
A> public int Attributes;
A> public override int GetHashCode()
A> {
A> return
A> /* Что тут надо написать, чтобы значения всех битов были равновероятны и независимы?
A> Причём не в теории, где Drive от 0 до 255, а на практике. */;
A> }
A>}
A>
Подумай и над тем сколько вообще программистов знают в теории как писать такие функции, не говоря уже о практике.
На практике все очень просто — дефолтная реализация GetHashCode() прекрасно для switch подходит.
... << RSDN@Home 1.2.0 alpha rev. 624 on Windows XP 5.1.2600.131072>>
Здравствуйте, WolfHound, Вы писали:
WH>1)Причем тут сериализация?
При том что есть задачи в которых поддерживать классы реализующие интерфейс IDictionary такая большая проблема, что легче их не поддерживать.
WH>2)Hashtable прекрасно сериализуется. Учи матчасть.
Я рыдаю.
Друг, ты хоть с документацией сверяйся, а потом говори, если так не помнишь
public class A
{
[XmlElement("ht")]
public Hashtable _ht = new Hashtable();
public A()
{
_ht.Add(1, "a");
_ht.Add(2, "b");
_ht.Add(3, "c");
}
}
class Program
{
static void Main(string[] args)
{
/*
В этой строке получаем исключение.
Cannot serialize member A._ht of type System.Collections.Hashtable, because it implements IDictionary.
При использовании Dictionary<int, string> ситуация аналогичная.
*/
XmlSerializer xs = new XmlSerializer(typeof(A));
/* Сюда уже не доходит, я просто для полноты картины написал этот код */
A a = new A();
using (TextWriter tw = File.CreateText("test.xml"))
{
xs.Serialize(tw, a);
tw.Close();
}
}
}
WH>3)Может ты всетки определишь отношение порядка для StateSet? Или слабо?
Что значит слабо? Есть инструмент — оператор switch и есть множество классов которые в нём можно использовать. Классы реализующие интерфейс IDictionary в это множество не входят. Не надо доводить до маразма. И уж точно аргументация "слабо", "не слабо" не привносит в дискуссию элементы интеллекта.
WH>А если слабо то больше не делай заявлений типа WH>
Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net
Вобщем все аргументы против "operator <" свелись к тому что Индусы пишут в "operator <" вызов Sleep(1000); и поэтому он медленный
Роме слабо реализовать этот оператор для класса StateSet. Правда он в операторе switch представляется с трудом, но это не важно.
Очень интересно, но совершенно не убедительно.
Здравствуйте, AndrewVK, Вы писали:
AVK>На практике все очень просто — дефолтная реализация GetHashCode() прекрасно для switch подходит.
Так ли уж?
public class A
{
public int data = 3;
public A()
{
}
}
A a1 = new A();
A a2 = new A();
int h1 = a1.GetHashCode();
int h2 = a2.GetHashCode();
Как нетрудно убедиться h1 != h2. А вот с моей точки зрения объекты равны, потому что у обоих поле data = 3, а других полей нет.
Так что дефолтная реализация вообще не подходит. Надо каждый раз писат свою. И как я уже показал, xor от хешей всех полей не лучшее решение.
Здравствуйте, adontz, Вы писали:
A>Друг, ты хоть с документацией сверяйся, а потом говори, если так не помнишь
XmlSerializer не умеет работать с IDictionary. Только непонятно, при чем тут это...? Возьми BinaryFormatter, он замечательно сериализует твой класс.