|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 29 Nov 2001 03:38:43
To : Aleksey V Vaneev
Subject : Re: Кеш для узлов дерева, хранимого в файле
--------------------------------------------------------------------------------
Привет! "Aleksey V. Vaneev" <Aleksey.V.Vaneev@p1.f15.n5003.z2.fidonet.org>
сообщил(а) нам:
> Так это не проблема и дерево сбалансировано... Проблема-то возникает
тогда,
> когда в дерево из 38000 тысяч элементов хочется добавить элемент или
произвести
> в нем поиск. Приходится очень много читать из файла.
Предположим, что у нас 64-ричное дерево. Тогда у каждого узла (кроме корня)
не менее 32 потомков. Следовательно для поиска в 38e6 записях придется
просмотреть ln(38e6)/ln(32)+1 - примерно 7 узлов. В каждом узле производится
двоичный поиск - по 5 сравнений (вероятно будет 6). Итого 7 обращений к
индексному файлу и 42 сравнения. ЭТО МHОГО???
С уважением, Андрей.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
