Ответ на »сообщение 635« (matvey)
___________________________
>>> Ну в ранкированном дереве доступ к элементу по индексу занимает опять же log(N) операций, что не фатально медленнее...
Хм... Я имел ввиду, что медленнее по сравнению с массивом. Там все же доступ к элементу по смещению получаем сразу же. Что имеет свои плюсы для определенных задач.

>>> Или потестировать готовые деревья??? ;)
Какой смысл тестировать готовое?! Если для интереса, то делать свое. Можно даже и без Кнута. Пусть будет чуток похуже, но зато задача интереснее ;-)


Ответ на »сообщение 636« (Как слышно? Прием!)
___________________________
>>> Ввиду того, что одиночные добавления редки <...>
А TStrings.Add, по-вашему, редко используется?! ;-)

Балансированные деревья хорошо работают при добавлении одного элемента.
А вот если требуется добавить список или массив, тут успехов не видно.
Ввиду того, что одиночные добавления редки, а метод сложен
(в тои числе неустойчив к сбоям) он и непопулярен.

Ответ на »сообщение 634« (Geo)
___________________________

Тут, собственно, все та же ситуация между ссылочным списком и массивом: список модифицируется проще и не требует для себя больших непрерывныз учатсков памяти, а в массиве доступ к произвольному элем6енту быстрее.
Угу... В принципе можно рассматривать бинарное дерево как модифицированный двусвязный список.
Ну в ранкированном дереве доступ к элементу по индексу занимает опять же log(N) операций, что не фатально медленнее...

К тому же, быстродействие сейчас таково, что сдвинуть раз в час полмассива туда или сюда -- жто не проблема. Ну и пусть три порядка: значит сдвинем не за 10 наносекунд, а за 10 микросекунд. Вот никто и не чешется.
На 100 элементах незаметно, но когда речь зашла о 100 000, то стало заметно.

Ну, и в-третьих, готовая библиотеки, в которых была бы реализована поддержка сбаланисрованных бинарных деревьев, ... э-э-э... скажем, не столь распространены ;-)
RB-дерево было в acedutils вроде. AVL-дерево в чистом виде негде не видел, ходя фактор сбалансированности для второго случая выше. Прошитые и ранкированные деревья, также как и трехсвязные списки (а там фишка в том, что можно делать обработку с любой позиции в дереве) - только у Кнута.

А вообще-то, как-нибудь надо будет заняться реализацией балансировки деревьев. Просто так, для души. Задачка интересная.
Или потестировать готовые деревья??? ;)

Сергею:
Потому, что ни кто не удосужился выложить статью с исходниками (или хотя бы ссылку) где, ... вот то, что Вы сказали реализовано :)
Первоисточник всего - Кнут - первый и третий том. В Википедии есть отрывки, но они какие-то недоделанные местами. На РСДН есть статья, но почему-то для итератора предложено использовать стек, а не прошивку дерева, что странно. Я к тому, что лучше кнута почитать...

Ответ на »сообщение 633« (matvey)
___________________________
Да я уж понял, что "порядки" набегают при внеснии изменений.

Тут, собственно, все та же ситуация между ссылочным списком и массивом: список модифицируется проще и не требует для себя больших непрерывныз учатсков памяти, а в массиве доступ к произвольному элем6енту быстрее.

К тому же, быстродействие сейчас таково, что сдвинуть раз в час полмассива туда или сюда -- жто не проблема. Ну и пусть три порядка: значит сдвинем не за 10 наносекунд, а за 10 микросекунд. Вот никто и не чешется.

Ну, и в-третьих, готовая библиотеки, в которых была бы реализована поддержка сбаланисрованных бинарных деревьев, ... э-э-э... скажем, не столь распространены ;-)

А вообще-то, как-нибудь надо будет заняться реализацией балансировки деревьев. Просто так, для души. Задачка интересная.

Ответ на »сообщение 631« (Geo)
___________________________
тот же метод дихотомии работает вполне прилично
Он работает на упорядоченных списках давая сложность в log(N). Но вставка/удаление элемента приводит к переаллокации памяти под массив, а следовательно и копированию, что в конечном итоге приведет к сложности в N операций. Для балансированных деревьев операции вставки/удаления приведет к сложности аккурат в log(N), что и составит выигрыш в два-три порядка для больших объемов данных.

Ответ на »сообщение 630« (matvey)
___________________________
почему народ для упорядоченных списков (массивов) данных практически не использует самобалансирующиеся древовидные структуры Потому, что ни кто не удосужился выложить статью с исходниками (или хотя бы ссылку) где, ... вот то, что Вы сказали реализовано :)))

Ответ на »сообщение 630« (matvey)
___________________________
Мое ИМХО

Во-первых, сложно.

Во-вторых, тот же метод дихотомии работает вполне прилично. Откуда появятся те самые 2-3 порядка?

Тема оптимизации кода у меня вызывает один элементарный вопрос - почему народ для упорядоченных списков (массивов) данных практически не использует самобалансирующиеся древовидные структуры (как вариант прошитые или ранкированные)? Или выигрыш на 1000+ элементов в два-три порядка по быстродействию считается слишком небольшим, чтобы ради этого заморачиваться? Не, ну оверхед в 20-30 байт на элемент будет, но скорость...

Ответ на »сообщение 628« (Мухтар )
___________________________
Мне кажется такой работой должен дефрагментатор заниматься.

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

Об оптимизации можно судить по тому, как сканирование диска С:\ происходит несколько минут, а копирование 20мегабайтного файла - несколько секунд :)