Решил вот чисто для общего развития сделать структуру для хранения данных... Вспомнил дискретку и СДЕЛАЛ ДЕРЕВО ))
Типа там ключ - строка, до фига ветвей, в каждой ветви ещё до фига ветвей... Думаю типа добавлятся элементы будут довольно долго и памяти это дело будет занимать не мало, но зато доступ к элементам будет офигенно быстрый...
Протестил... Сравнивал с SortedList и Hashtable
Время добавления элементов практически одинаково для всех 3-х.
По скорости доступа SortedList сделал где то в 5 раз. А вот по сравнению с Hashtable моё дерево где то в 3 раза медленнее...
Как вообще устроен этот ихний Hashtable? Я до этого считал, что деревья самые быстрые по скорости доступа... ))

Хаштейбл- это пары ключ - значение. Хранятся они в массиве - массив дает самый быстрый доступ. Суть же в том, чтобы на основании ключа, используя хешфункцию, вычислить номер элемента массива, в который помещается значение. Например, если ты ложишь туда пару "дата"- DateTime, то будет вычислен хешкод слова "дата" (скажем, 55); тогда объект и будет помещен в 55 ячейку.

Более подробно - тут
http://www.sparknotes.com/cs/searching/has...s/section1.html

Что то странно... А если хэш-код > 100000 (у строк реально такие)), то одна таблица займёт всю память что ли?

А там чё то всё по аглицки, не понятно ни фига...

хештейбл имеет начальную мощность, естественно не такую большую; маппинг на целочисленные индексы этого массива определяетя хешфункцией.

Цитата(nucer @ 1.1.2005, 19:35)

А там чё то всё по аглицки, не понятно ни фига...

ну так кто виноват, поищи на на русском, наверняка есть

Кстати о скоростях доступа.

Самая быстрая скорость доступа - у массивов, то есть когда все элементы расположены в памяти по-порядку. Тогда скорость доступа к любому элементу приблизительно постоянна и не зависит от длины массива. Но массив имеет кучу недостаков. Например для удаления/вставки элементов необходимо сдвигать все остальные, а скорость этой операции уже зависит от числа элементов.

Совершенно иная картина у списков (ArrayList и др). Вставка/удаление элементов происходит за фиксированое время, а вот скорость произвольного доступа зависит от количества элементов. Хотя частично проблема решается путем последовательного обхода списка (foreach работает быстрее чем for + индексатор).

Это так сказать два крайних случая. Хэштаблица - есть нечто среднее между массивом и списком. Как говорил Domestic Cat хэштаблица - это массив, каждый элемент которого список, а в этом списке хранятся те элементы, у которых значения хэш-функции ключа одинаковы. Таким образом мы получаем скорость доступа в N раз меньшую, чем у обычного списка, где N - мощность хэштаблицы. В то же время операции вставки/удаления элементов происходят за фиксированое время.

Насчет дерева. Скорость произвольного доступа в отсортированом бинарном дереве равна O(log2 N), где N - число элементов дерева. То есть дерево быстрее хэштаблицы только при очень большом N. Дерево имеет очень много других достоинств, например возможность быстрого добавления с сортировкой, и др.

Еще следует отметить, что скорость работы хэштаблицы и дерева сильно зависит от иных факторов. Например для хэштаблицы необходимо выбрать такую хэш-функцию, чтобы она РАВНОМЕРНО распределяла хэши ключей в заданый интервал. Для дерева очень важна входная последовательность. Если она уже отсортирована (хотя бы частично), то все преимущества дерева сводятся на нет.

гы )) Дерево то было не бинарным. Почитав на algolist.ru, я пришёл к выводу что та херовина которуя сделал - StringBTree ))
И ещё я так понял, что в хэш-таблице возможен случай, когда два разных ключа будут иметь одинаковое размещение?

Цитата

И ещё я так понял, что в хэш-таблице возможен случай, когда два разных ключа будут иметь одинаковое размещение?

Дa, тогда скорость ухудшится.

Так, теперь я решил сделать хэш таблицу ))
Предварительно сделал сортированный список с бинарным поиском... Создал массив из этих самых списков... Получилось быстро, но при большом количестве элементов MS-овский хэш лист всё равно обгоняет мой раза в 1,5... Какие списки (да и списки ли) они там используют....

Цитата

Какие списки (да и списки ли) они там используют....

Понятия нe имею. Если тебe так нужно устройство хештейбла, посмотри в сорцы Java'вского HashMap. Если сорца нет, могу прицепить; толькo попозже.

Ну я сорец прицепил. Хотя это и Java, разобраться думаю будет несложно.


Присоединённый файл ( Кол-во скачиваний: 14 )
 Hashtable.java

Хэштаблица в .NET реализована на МАССИВЕ, поэтому у неё такая высокая скорость.

А внутреняя реализация приблизительно такова:
Есть один большой массив длина которого - простое число. Элементы в нем располагаются не по-порядку а в определенные места в массиве, определяемые хэшем ключа. Периодически производится т.н. Rehash, то есть увеличение длины массива и перераспределение элементов в нем. Если хочешь узнать подробнее, скачай .NET Reflector, и сам посмотри реализацию.

Более того, в классах .NET Framework 1.1 я не нашел ни одного класса, который бы реализовывал связный список, стек или очередь... Все на массивах... Вот в .NET Framework 2.0 есть LinkedList<T>, который действительно реализован как двусвязный список.

ЗЫ. А чем тебя не устраивает стандартный Hashtable?

Цитата

Wizard, 5.1.2005,  03:12]Более того, в классах .NET Framework 1.1 я не нашел ни одного класса, который бы реализовывал связный список, стек или очередь... Все на массивах... Вот в .NET Framework 2.0 есть LinkedList<T>, который действительно реализован как двусвязный список.

Да что-то 1.1 вообще бедновата на коллекции.

Не, наврал я вам в своем предыдущем посте.
Есть! Есть класс с реализацией однонаправленого списка. Это System.Collections.Specialized.ListDictionary
Там хранятся элементы в виде пар ключ/значение, доступ к элементам производится путем линейного обхода списка, в общем классический связный список.

Да не, меня устраивает, просто хочется самому разобраться в алгоритмах... .net приходит и уходит, а алгоритмы остаются ))
За java сорс спасибо, правда разбираться в чужом коде не особо благодарное занятие, тем более написано там как то странно на мой взгляд... ((

Цитата

тем более написано там как то странно на мой взгляд...

в каком смыслe странно ?

Я посмотрел - хаштейбл таm реализован через массив объектов Entry, причем сами эти Entry - односвязные списки, нa случай если в одну ячейку попадут nесколько записей.