Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, _FRED_, Вы писали:
S>Создаем индексы Б+ деревья http://rsdn.org/article/alg/tlsd.xmlАвтор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.
S>А по индексам создаем новый файл.
S>индекс= Строка,смещение. Сортировка по строка.
В теории многие так "решили" задачу, а на практике — никто.
S> Ну или можно держать ограниченную длину строки, а при сравнении если сроки одинаковы уже лезть в файл по смещению.
Это плохо работает. Проверил, даже код есть.
S>А проще для этого БД какую нибудь использовать
С этим тоже успехов что-то не видно.
Здравствуйте, gandjustas, Вы писали:
S>>Здравствуйте, _FRED_, Вы писали:
S>>Создаем индексы Б+ деревья http://rsdn.org/article/alg/tlsd.xmlАвтор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.
S>>А по индексам создаем новый файл.
S>>индекс= Строка,смещение. Сортировка по строка.
G>В теории многие так "решили" задачу, а на практике — никто.
В БД это все решено
S>> Ну или можно держать ограниченную длину строки, а при сравнении если сроки одинаковы уже лезть в файл по смещению.
G>Это плохо работает. Проверил, даже код есть.
И на какой длине строки проверял? Стандартный Б+ индекс 8 кб.
Сделай свой в 64 кб. Это если памяти не хватает. А по моему длины даже в 500 байт достаточно.
И это если памяти не хватает. Когда речь идет о 1ГБ это даже не смешно.
Вот когда файлы действительно огромные которые не вмещаются в память, Б+ деревья ооочень эффективны.
Особенно если используются SSD.
Причем можно создавать страницы с переменной длиной строки.
То есть страница загружается в память, выбираются данные в память, а потом двоичным поиском уже идет поиск.
Так или иначе нужно будет обращение к диску если страница незакэширована в памяти.
Обращение же к диску если строки равны и длина их больше чем половина страницы, то будет обращение к диску.
Скорость чтения SSD для 4 кб 500 тыщ в секунду. Вполне себе быстро.
S>>А проще для этого БД какую нибудь использовать
G>С этим тоже успехов что-то не видно.
Да ну? А как же они работают то БД?
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, gandjustas, Вы писали:
S>>>Здравствуйте, _FRED_, Вы писали:
S>>>Создаем индексы Б+ деревья http://rsdn.org/article/alg/tlsd.xmlАвтор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.
S>>>А по индексам создаем новый файл.
S>>>индекс= Строка,смещение. Сортировка по строка.
G>>В теории многие так "решили" задачу, а на практике — никто.
S> В БД это все решено
Нужно не теоретическое решение задачи сортировки большого файла, а практическое.
S>Скорость чтения SSD для 4 кб 500 тыщ в секунду. Вполне себе быстро.
А если не SSD?
S>>>А проще для этого БД какую нибудь использовать
G>>С этим тоже успехов что-то не видно.
S> Да ну? А как же они работают то БД?
БД отлично работают, а пока никто ен отсортировал файл в 100гб с помощью БД за разумное время.
Здравствуйте, gandjustas, Вы писали:
S>>>>Здравствуйте, _FRED_, Вы писали:
S>>>>Создаем индексы Б+ деревья http://rsdn.org/article/alg/tlsd.xmlАвтор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.
S>>>>А по индексам создаем новый файл.
S>>>>индекс= Строка,смещение. Сортировка по строка.
G>>>В теории многие так "решили" задачу, а на практике — никто.
S>> В БД это все решено
G>Нужно не теоретическое решение задачи сортировки большого файла, а практическое.
Ну сделать то недолго. Вот есть решение Б+ дерева в памяти.
http://rsdn.org/article/alg/tlsd.xmlАвтор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.
Там кстати сравнение по скорости есть при работе в памяти
Число слов в тексте=528124
Количество слов 20359
Заполнение QuickDictionary (прямой доступ) 0.08363381379477
Заполнение TLSD (прямой доступ) 0.368364694395517
Заполнение Б+-дерева (прямой доступ) 0.461643030049909
Сортировка слиянием кстати совсем немного уступает QuikSort.
https://rsdn.org/forum/philosophy/577195.1Автор: Serginio1
Дата: 22.03.04
А вот результаты сортировки 25 миллионного массива на Delphi
QuickSort 5.5 сек
MergeSort 5.8 сек.
Было это почти 20 лет тому назад!
Но интересно посмотреть при работе с диском.
На основании его можно сделать дерево с хранением на диске. Причем верхние уровни можно хранить в памяти.
При этом как и писал на странице хранить строки по их длине без лишнего места.
То есть длина строки, строка, смещение в файле, реальная длина строки.
Все это упаковано последовательно на странице.
S>>Скорость чтения SSD для 4 кб 500 тыщ в секунду. Вполне себе быстро.
G>А если не SSD?
А если не SSD, то сортировкой слияния от чтения диска не обойтись.
S>>>>А проще для этого БД какую нибудь использовать
G>>>С этим тоже успехов что-то не видно.
S>> Да ну? А как же они работают то БД?
G>БД отлично работают, а пока никто ен отсортировал файл в 100гб с помощью БД за разумное время.
Это зависит от свободной памяти. Сейчас сервера и с терробайтами памяти реальная вещь и еще с SSD.
Но вот чем тебе мое решение не нравится с переменной длиной строки? Индексы будут содержать больше полезной информации, а значит и высота дерева будет меньше и меньше чтения диска.
Хотя скорее всего сортировка слиянием будет быстрее.
