Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Сортировка больших данных при малой RAM  [new]
interweb
Member [заблокирован]

Откуда:
Сообщений: 97
Интересуют способы сортировки больших данных (порядка 10 ТБ) при наличии лишь 1 GB RAM

Исследованные варианты:
1) Разбить файл на тысячи относительно небольших файлов, отсортировать каждый из них и потом склеить. Но этот вариант работать не будет т.к. скажем в первом файле значения 1-10, в 100м значения от 1-50, поэтому склейка не состоится
2) Можно попробовать использовать некую БД, но не уверен, что это правильный подход
3) Можно использовать apache spark, но из того примера, что я видел, данные из файла должны быть все считанны в память - это не представляется возможным.
7 сен 16, 15:09    [19638061]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Dima T
Member

Откуда:
Сообщений: 15801
Блочная сортировка
7 сен 16, 15:18    [19638106]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21181
Для случая, когда бОльшая часть данных должна кэшиться на диск, хорошо подходит Сортировка слиянием.
7 сен 16, 15:35    [19638197]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
interweb
Member [заблокирован]

Откуда:
Сообщений: 97
Akina
Для случая, когда бОльшая часть данных должна кэшиться на диск, хорошо подходит Сортировка слиянием.


Такой подход я рассматривал, но мне он видится неэффективным: в нем необходимо разбивать данные до байт, а это создаст слишком много временных файлов, и вообще займет много времени.
7 сен 16, 15:46    [19638248]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21181
interweb
мне он видится неэффективным: в нем необходимо разбивать данные до байт, а это создаст слишком много временных файлов, и вообще займет много времени.
Да ладно- много файлов! считать научись... если, например, использовать блоки сортировки по 1 Мбайт, то на диске будет максимум 28 файлов, включая исходный и конечный.
7 сен 16, 15:52    [19638286]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
interweb,

первый вариант - рабочий. Недавно реализовал. ;)
7 сен 16, 15:56    [19638308]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Dima T
Member

Откуда:
Сообщений: 15801
Как вариант: если в сортировке участвует небольшая часть данных до 1%, т.е. файл это набор записей например по 1 Кб и каждая содержит ключ 8 байт. Для сортировки перелить ключи в отдельный файл со структурой {ключ, смещение}, где смещение - это расположение записи в исходном файле. Затем сортировать по ключу этот новый файл. Затем по нему и исходному создать файл с результатом.
7 сен 16, 15:57    [19638315]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Изопропил
Member

Откуда:
Сообщений: 31571
И зачем Дональд Кнут книги писал...

Гугл по запросу "внешняя сортировка" выдаёт достаточно материалов
7 сен 16, 16:14    [19638433]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
д0k
Guest
Имхо все промышленные бд использую велосипеды на тему.
7 сен 16, 17:27    [19638915]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
x1ca4064
Member

Откуда:
Сообщений: 1269
interweb,

А сколько в 10ТБ сущностей для сортировки?
7 сен 16, 17:40    [19638981]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
x1ca4064
А сколько в 10ТБ сущностей для сортировки?

Любое случайное количество. Это не имеет значения.
7 сен 16, 18:25    [19639204]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21181
wadman
Это не имеет значения.
При условии, что 2 комплекта необходимых для сравнения частей сущности поместятся в оперативке... внешнее сравнение двух экземпляров я как-то себе с трудом представляю.
7 сен 16, 19:14    [19639332]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
Akina
внешнее сравнение двух экземпляров я как-то себе с трудом представляю.

Я это реализовал последовательным чтением.
Оперативки в моем решении нужно 16 мб (можно и меньше), а размер файла не ограничен.
7 сен 16, 19:22    [19639347]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
wadman
Akina
внешнее сравнение двух экземпляров я как-то себе с трудом представляю.

Я это реализовал последовательным чтением.
Оперативки в моем решении нужно 16 мб (можно и меньше), а размер файла не ограничен.

Соврал. :) Не реализовал, но задумал через буферное упреждающее чтение.
7 сен 16, 19:29    [19639364]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Dima T
Member

Откуда:
Сообщений: 15801
Akina
При условии, что 2 комплекта необходимых для сравнения частей сущности поместятся в оперативке...

Как часто надо сравнивать сущности по 0.5+ Гб ? Напомню
interweb
при наличии лишь 1 GB RAM
7 сен 16, 19:32    [19639373]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
Dima T
Как часто надо сравнивать сущности по 0.5+ Гб ?

Например, при написании тестового задания.
7 сен 16, 19:36    [19639384]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
interweb
Member [заблокирован]

Откуда:
Сообщений: 97
wadman
interweb,

первый вариант - рабочий. Недавно реализовал. ;)


Он не может быть рабочим. Вот пример:

Блок1:
2 1 3 20

Блок 2:
7 5 8 10


Блок 50:

2 3 1 30

После сортировки каждого блока и последовательной склейки получим:

1 2 3 20 +5 7 8 10 + … + 1 2 3 30

т.е. данные из 50го блока остаются в позиции 50го блока и не сравниваются с другими блоками.
7 сен 16, 19:42    [19639400]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Dima T
Member

Откуда:
Сообщений: 15801
interweb, топик внимательно перечитай.
7 сен 16, 19:49    [19639404]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
interweb
Он не может быть рабочим. Вот пример:

Как так? У меня же получилось. :)

Есть 4-е отсортированных (ранее разбитых) файла (1, 2, 3, 4).
Читаем по строке из каждого и сортируем их.
1. Первую строку сливаем в общий файл (0).
2. Если эта строка была (например) из 4-го файла, то из него-же и читаем новую строку.
3. Снова сортируем.
4. см п.1.
7 сен 16, 20:07    [19639438]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Владимир2012
Member [заблокирован]

Откуда:
Сообщений: 1460
interweb
Интересуют способы сортировки больших данных (порядка 10 ТБ) при наличии лишь 1 GB RAM

Исследованные варианты:
1) Разбить файл на тысячи относительно небольших файлов, отсортировать каждый из них и потом склеить. Но этот вариант работать не будет т.к. скажем в первом файле значения 1-10, в 100м значения от 1-50, поэтому склейка не состоится
2) Можно попробовать использовать некую БД, но не уверен, что это правильный подход
3) Можно использовать apache spark, но из того примера, что я видел, данные из файла должны быть все считанны в память - это не представляется возможным.
Экспромтом:
- на первом проходе создаем array, каждый item которого содержит "вес ключа";
- на втором проходе строим бинарный индекс

"И это пожалуй все!" /Форест Гамп/
7 сен 16, 20:27    [19639468]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
x1ca4064
Member

Откуда:
Сообщений: 1269
wadman
Любое случайное количество. Это не имеет значения.


Не согласен, т.к. "дъявол прячется в деталях": если нужно отсортировать 10^12 байт (т.е. каждая сущность занимает 1 байт), это одно, если нужно отсортировать 2 сущности по 5*10^11, это другое. Общее решение либо должно учитывать эти вырожденные случаи (плюс еще какие-либо возможные, порожденные особой статистикой исходных данных), либо будет не эффективным в ряде задач.
7 сен 16, 21:15    [19639554]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
x1ca4064
Не согласен, т.к. "дъявол прячется в деталях"

Детали такие, что любая последовательность байт.
Задача такая.
Придется смириться с ТЗ, а не выставлять в обратку свои.
7 сен 16, 21:22    [19639588]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
x1ca4064
Member

Откуда:
Сообщений: 1269
wadman
x1ca4064
Не согласен, т.к. "дъявол прячется в деталях"

Детали такие, что любая последовательность байт.
Задача такая.
Придется смириться с ТЗ, а не выставлять в обратку свои.

Не бывает такого, "отсортировать любую последовательность байт" (если не брать вырожденный случай): эти байты описывают какие-то сущности, для которых и определяют операцию отношения. Для сущностей, подчеркиваю, а не для байт.
7 сен 16, 21:29    [19639611]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21181
wadman
Я это реализовал последовательным чтением.

wadman
задумал через буферное упреждающее чтение.

Это ты всё рассказываешь в предположении, что мы сравниваем строки (ну или бин-последовательности), причём строго посимвольно.

А представь себе вариант, когда сравниваемые сущности - это сложные объекты, причём единственный способ сравнить объекты A и B - это вызвать тернарный метод A.Compare(B) (ну либо B.Compare(A) - причём они дадут одинаковый ответ, хотя могут отличаться реализацией). Т.е. надо не только загрузить в память объект А для вызова его метода (и соответственно целиком - а ведь его для этого ещё может потребоваться десериализовать!), но и передать ему (и соответственно опять же полностью загрузить в память) объект B...
7 сен 16, 21:38    [19639650]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
x1ca4064
Не бывает такого

Уже есть.
Akina
Это ты всё рассказываешь в предположении, что мы сравниваем строки (ну или бин-последовательности), причём строго посимвольно.

Нененене. Читай первое сообщение темы и не выдумывай новые условия.
Загружать "объект" полностью нет необходимости. Все можно/нужно делать побайтно.
Важен результат = отсортированный файл (байты!).
7 сен 16, 22:02    [19639714]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить