| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Общие вопросы по .NET и C# > Коллекции... Теоретический вопрос |
| Автор: nucer 2.1.2005, 00:57 |
| Решил вот чисто для общего развития сделать структуру для хранения данных... Вспомнил дискретку и СДЕЛАЛ ДЕРЕВО )) Типа там ключ - строка, до фига ветвей, в каждой ветви ещё до фига ветвей... Думаю типа добавлятся элементы будут довольно долго и памяти это дело будет занимать не мало, но зато доступ к элементам будет офигенно быстрый... Протестил... Сравнивал с SortedList и Hashtable Время добавления элементов практически одинаково для всех 3-х. По скорости доступа SortedList сделал где то в 5 раз. А вот по сравнению с Hashtable моё дерево где то в 3 раза медленнее... Как вообще устроен этот ихний Hashtable? Я до этого считал, что деревья самые быстрые по скорости доступа... )) |
| Автор: Domestic Cat 2.1.2005, 02:13 |
| Хаштейбл- это пары ключ - значение. Хранятся они в массиве - массив дает самый быстрый доступ. Суть же в том, чтобы на основании ключа, используя хешфункцию, вычислить номер элемента массива, в который помещается значение. Например, если ты ложишь туда пару "дата"- DateTime, то будет вычислен хешкод слова "дата" (скажем, 55); тогда объект и будет помещен в 55 ячейку. Более подробно - тут http://www.sparknotes.com/cs/searching/hashtables/section1.html |
| Автор: nucer 2.1.2005, 04:35 |
| Что то странно... А если хэш-код > 100000 (у строк реально такие)), то одна таблица займёт всю память что ли? А там чё то всё по аглицки, не понятно ни фига... |
| Автор: Domestic Cat 2.1.2005, 05:43 | ||
хештейбл имеет начальную мощность, естественно не такую большую; маппинг на целочисленные индексы этого массива определяетя хешфункцией.
ну так кто виноват, поищи на на русском, наверняка есть |
| Автор: [Last]Wizard 3.1.2005, 13:29 |
| Кстати о скоростях доступа. Самая быстрая скорость доступа - у массивов, то есть когда все элементы расположены в памяти по-порядку. Тогда скорость доступа к любому элементу приблизительно постоянна и не зависит от длины массива. Но массив имеет кучу недостаков. Например для удаления/вставки элементов необходимо сдвигать все остальные, а скорость этой операции уже зависит от числа элементов. Совершенно иная картина у списков (ArrayList и др). Вставка/удаление элементов происходит за фиксированое время, а вот скорость произвольного доступа зависит от количества элементов. Хотя частично проблема решается путем последовательного обхода списка (foreach работает быстрее чем for + индексатор). Это так сказать два крайних случая. Хэштаблица - есть нечто среднее между массивом и списком. Как говорил Domestic Cat хэштаблица - это массив, каждый элемент которого список, а в этом списке хранятся те элементы, у которых значения хэш-функции ключа одинаковы. Таким образом мы получаем скорость доступа в N раз меньшую, чем у обычного списка, где N - мощность хэштаблицы. В то же время операции вставки/удаления элементов происходят за фиксированое время. Насчет дерева. Скорость произвольного доступа в отсортированом бинарном дереве равна O(log2 N), где N - число элементов дерева. То есть дерево быстрее хэштаблицы только при очень большом N. Дерево имеет очень много других достоинств, например возможность быстрого добавления с сортировкой, и др. Еще следует отметить, что скорость работы хэштаблицы и дерева сильно зависит от иных факторов. Например для хэштаблицы необходимо выбрать такую хэш-функцию, чтобы она РАВНОМЕРНО распределяла хэши ключей в заданый интервал. Для дерева очень важна входная последовательность. Если она уже отсортирована (хотя бы частично), то все преимущества дерева сводятся на нет. |
| Автор: nucer 4.1.2005, 20:05 |
| гы )) Дерево то было не бинарным. Почитав на algolist.ru, я пришёл к выводу что та херовина которуя сделал - StringBTree )) И ещё я так понял, что в хэш-таблице возможен случай, когда два разных ключа будут иметь одинаковое размещение? |
| Автор: Domestic Cat 4.1.2005, 20:09 | ||
Дa, тогда скорость ухудшится. |
| Автор: nucer 5.1.2005, 00:07 |
| Так, теперь я решил сделать хэш таблицу )) Предварительно сделал сортированный список с бинарным поиском... Создал массив из этих самых списков... Получилось быстро, но при большом количестве элементов MS-овский хэш лист всё равно обгоняет мой раза в 1,5... Какие списки (да и списки ли) они там используют.... |
| Автор: Domestic Cat 5.1.2005, 00:14 | ||
Понятия нe имею. Если тебe так нужно устройство хештейбла, посмотри в сорцы Java'вского HashMap. Если сорца нет, могу прицепить; толькo попозже. |
| Автор: Domestic Cat 5.1.2005, 07:51 |
| Ну я сорец прицепил. Хотя это и Java, разобраться думаю будет несложно. |
| Автор: [Last]Wizard 5.1.2005, 12:12 |
| Хэштаблица в .NET реализована на МАССИВЕ, поэтому у неё такая высокая скорость. А внутреняя реализация приблизительно такова: Есть один большой массив длина которого - простое число. Элементы в нем располагаются не по-порядку а в определенные места в массиве, определяемые хэшем ключа. Периодически производится т.н. Rehash, то есть увеличение длины массива и перераспределение элементов в нем. Если хочешь узнать подробнее, скачай http://www.aisto.com/roeder/dotnet/, и сам посмотри реализацию. Более того, в классах .NET Framework 1.1 я не нашел ни одного класса, который бы реализовывал связный список, стек или очередь... Все на массивах... Вот в .NET Framework 2.0 есть LinkedList<T>, который действительно реализован как двусвязный список. ЗЫ. А чем тебя не устраивает стандартный Hashtable? |
| Автор: Domestic Cat 5.1.2005, 18:36 | ||
Да что-то 1.1 вообще бедновата на коллекции. |
| Автор: [Last]Wizard 5.1.2005, 19:15 |
Не, наврал я вам в своем предыдущем посте.  Есть! Есть класс с реализацией однонаправленого списка. Это System.Collections.Specialized.ListDictionary Там хранятся элементы в виде пар ключ/значение, доступ к элементам производится путем линейного обхода списка, в общем классический связный список. |
| Автор: nucer 5.1.2005, 22:59 |
| Да не, меня устраивает, просто хочется самому разобраться в алгоритмах... .net приходит и уходит, а алгоритмы остаются )) За java сорс спасибо, правда разбираться в чужом коде не особо благодарное занятие, тем более написано там как то странно на мой взгляд... (( |
| Автор: Domestic Cat 5.1.2005, 23:08 | ||
в каком смыслe странно ?  Я посмотрел - хаштейбл таm реализован через массив объектов Entry, причем сами эти Entry - односвязные списки, нa случай если в одну ячейку попадут nесколько записей. |
| Автор: sergejzr 5.1.2005, 23:27 | ||
Domestic Cat, как я понял из сорса, вот функция по которой расчитывается индекс в массиве:
Осталось заглянуть в фунуцию hashCode() самого обьекта (интересен конечно же String ) |
| Автор: Domestic Cat 6.1.2005, 00:34 | ||
Хеш код стринга можно найти в доках :
/// Извиняюсь что развел такой Java оффтоп, что поделать - родственная технология Тем более /// что существовать буду теперь на обеих форумах. |
| Автор: [Last]Wizard 6.1.2005, 13:15 | ||
| Если никто не против, то немного о .NET расскажу Алгоритмы хэш-кодов: String: алгоритм строго не определен, в MSDN пишут так:
Int32: хэш целого числа равен самому числу. Int16: (((Int32) X) | (X << 0x10)); Int64: (((Int32) X) ^ ((Int32) (X >> 0x20))); Char: (X | (X << 0x10)); Boolean: 1 если true и 0 если false; DateTime: ticks.GetHashCode(); Single: Адрес памяти, приведенный к Int32; Double: Хэш адреса в памяти (Int64); Guid: ((a ^ ((b << 0x10) | ((ushort) c))) ^ ((f << 0x18) | k)); |