Здравствуйте, 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.
Но интересно посмотреть при работе с диском.

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

S>>Скорость чтения SSD для 4 кб 500 тыщ в секунду. Вполне себе быстро.
G>А если не SSD?
А если не SSD, то сортировкой слияния от чтения диска не обойтись.

S>>>>А проще для этого БД какую нибудь использовать
G>>>С этим тоже успехов что-то не видно.
S>> Да ну? А как же они работают то БД?
G>БД отлично работают, а пока никто ен отсортировал файл в 100гб с помощью БД за разумное время.
Это зависит от свободной памяти. Сейчас сервера и с терробайтами памяти реальная вещь и еще с SSD.

Но вот чем тебе мое решение не нравится с переменной длиной строки? Индексы будут содержать больше полезной информации, а значит и высота дерева будет меньше и меньше чтения диска.

Здравствуйте, 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.

Но вот чем тебе мое решение не нравится с переменной длиной строки? Индексы будут содержать больше полезной информации, а значит и высота дерева будет меньше и меньше чтения диска.