Здравствуйте, B0FEE664, Вы писали:

BFE>Если вам не сложно, расскажите, пожалуйста, как будет работать алгоритм bucket sort для файла размером 140GB состоящим из одинаковых записей {"I":1}, если мы пытаемся сортировать этот файл по полю "I"?

BFE>Вот вы взяли запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине одна запись.
BFE>Взяли вторую запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине две записи.
BFE>Взяли третью запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине три записи.
BFE>...

BFE>Я правильно рассказываю начало работы алгоритма?

Затянули сколько влезло в 1 корзину, отсортировали любым библиотечным методом по вкусу в памяти (с comparator по сортируемому полю), выгрузили в выходной файл, запомнили смещение на начало следующей корзины. Затянули следующих в 2 корзину, отсортировали в памяти, выгрузили в выходной файл. Так пока весь входной файл не вычитан. Заключительный проход: создаем временный файл, создаём кольцевой буфер в памяти, создаём поле «смещение следующего элемента в выходном файле, берём fibonacci heap (PriorityQueue), и считываем по 1 записи (смещение записи) + comparator на сортируемое поле, из каждой отсортированной корзины. Достаём 1 элемент из PriorityQueue (т.е. номер корзины и смещение элемента относительно начала корзины, и пытаемся скопировать в выходной файл, пока он не налезает на невытащенный элемент корзины 1, остаток в кольцевой буфер памяти, если туда не влезло- в временный файл. Дальше, из какой корзины элемент ушёл- из нее закидываем ещё элемент в PriorityQueue, и повторяем шаг с выгрузкой из PriorityQueue. Таким образом, в итоге выходной файл окажется отсортирован. Удаляем временный файл (если он в процессе потребовался и был создан).

Здравствуйте, B0FEE664, Вы писали:

BFE>Если вам не сложно, расскажите, пожалуйста, как будет работать алгоритм bucket sort для файла размером 140GB состоящим из одинаковых записей {"I":1}, если мы пытаемся сортировать этот файл по полю "I"?

BFE>Вот вы взяли запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине одна запись.
BFE>Взяли вторую запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине две записи.
BFE>Взяли третью запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине три записи.
BFE>...

BFE>Я правильно рассказываю начало работы алгоритма?

Затянули сколько влезло в 1 корзину, отсортировали любым библиотечным методом по вкусу в памяти (с comparator по сортируемому полю), выгрузили в выходной файл, запомнили смещение на начало следующей корзины. Затянули следующих в 2 корзину, отсортировали в памяти, выгрузили в выходной файл. Так пока весь входной файл не вычитан. Заключительный проход: создаем временный файл, создаём кольцевой буфер в памяти, создаём поле «смещение следующего элемента в выходном файле, берём fibonacci heap (PriorityQueue), (или если в C++ этого не завезли- std::map тоже сойдёт, но чуть медленнее), и считываем по 1 записи (смещение записи) + comparator на сортируемое поле, из каждой отсортированной корзины. Достаём 1 элемент из PriorityQueue (т.е. номер корзины и смещение элемента относительно начала корзины, и пытаемся скопировать в выходной файл, пока он не налезает на невытащенный элемент корзины 1, остаток в кольцевой буфер памяти, если туда не влезло- в временный файл. Дальше, из какой корзины элемент ушёл- из нее закидываем ещё элемент в PriorityQueue, и повторяем шаг с выгрузкой из PriorityQueue. Таким образом, в итоге выходной файл окажется отсортирован. Удаляем временный файл (если он в процессе потребовался и был создан).