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

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

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

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


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

Откуда: Зеленоград, Москва, Россия
Сообщений: 21178
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

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

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

Гугл по запросу "внешняя сортировка" выдаёт достаточно материалов
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

Откуда: Зеленоград, Москва, Россия
Сообщений: 21178
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

Откуда:
Сообщений: 15796
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

Откуда:
Сообщений: 15796
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

Откуда: Зеленоград, Москва, Россия
Сообщений: 21178
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]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
S.G.
Member

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

а что за файл, какая структура? в смысле - текст, или блоки данных - одинаковые?
файл строго последовательного доступа, или можно организовать произвольный?
7 сен 16, 22:10    [19639734]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
x1ca4064
Member

Откуда:
Сообщений: 1269
wadman
Уже есть.


Не может быть :), но если уж такая проблема возникла (т.е. сущность==байт) то решение элементарно: заводим 256 счетчиков достаточной размерности, последовательно читаем байты, инкрементируем соответствующий счетчик, после выдаем отсортированную последовательность. Для реализации под 10ТБ данных хватит пары килобайт.
7 сен 16, 22:12    [19639738]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
x1ca4064
wadman
Уже есть.


Не может быть :), но если уж такая проблема возникла (т.е. сущность==байт) то решение элементарно: заводим 256 счетчиков достаточной размерности, последовательно читаем байты, инкрементируем соответствующий счетчик, после выдаем отсортированную последовательность. Для реализации под 10ТБ данных хватит пары килобайт.

Сущность = любая последовательность байт. Никаких счетчиков не хватит.
Уже было. Повторяемся?
7 сен 16, 22:14    [19639744]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Akina
Member

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

wadman
Все можно/нужно делать побайтно.
Так и не нашёл...

И вообще - это я не ТС пишу, а тебе, в ответ на огульное утверждение, что внешнее сравнение возможно в любом случае.
7 сен 16, 22:18    [19639756]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21178
x1ca4064
если уж такая проблема возникла (т.е. сущность==байт) то решение элементарно: заводим 256 счетчиков достаточной размерности, последовательно читаем байты, инкрементируем соответствующий счетчик, после выдаем отсортированную последовательность.
Это т.н. "Сортировка подсчётом".
7 сен 16, 22:20    [19639757]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
x1ca4064
Member

Откуда:
Сообщений: 1269
wadman
Сущность = любая последовательность байт. Никаких счетчиков не хватит.
Уже было. Повторяемся?


Вероятно, я не понимаю, о чем Вы говорите: сообщите, какая операция отношения у Вас определена на множестве "любая последовательность байт"? Пример, хотя бы. Ответ любая не принимается, т.к. не бывает задачи отсортировать "любую последовтельность байт" ... ах да, уже повторяюсь :)
Бывает только задача отсортировать последовательность сущностей. (New!)
7 сен 16, 22:30    [19639780]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
x1ca4064
Member

Откуда:
Сообщений: 1269
Akina
Это т.н. "Сортировка подсчётом".


А я то все гадал, как она называется :)
7 сен 16, 22:31    [19639783]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Изопропил
Member

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

какова структура файла? (сортируемых записей)
7 сен 16, 23:03    [19639859]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
x1ca4064
Member

Откуда:
Сообщений: 1269
Akina
Это т.н. "Сортировка подсчётом".


А я то все гадал, как она называется :)
8 сен 16, 02:16    [19640132]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
mayton
Member

Откуда: loopback
Сообщений: 51396
interweb
3) Можно использовать apache spark, но из того примера, что я видел, данные из файла должны быть все считанны в память - это не представляется возможным.

Ну ты даешь чувак! Чтоб приготовить яичницу ты пойдешь разогревать адронный коллайдер?

Да в 1990-е такие сортировки студенты делали на любой рабочей станции с оперативкой в 512 килобайт
на Borland C++.

Поищи "сортировка слиянием" и еще до кучи "B+дерево" как альтернативный вариант
8 сен 16, 08:47    [19640363]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

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

Это так и есть. Любая сущность - это байты.
Если вся сущность не влазит в оперативку, то байт влезет.
x1ca4064
Ответ любая не принимается, т.к. не бывает задачи отсортировать "любую последовтельность байт"

Ок, пусть будут строки любой длины. Они, как известно, состоят из байт.
И бывает так, что вся строка не влазит в оперативку.
Достаточно "дочитывать" данные в процессе сравнения.
8 сен 16, 09:32    [19640483]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21178
wadman
Это так и есть. Любая сущность - это байты.
Если вся сущность не влазит в оперативку, то байт влезет.
Похоже, ты даже не читаешь моих слов.
8 сен 16, 09:39    [19640524]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

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

Не, я не ищу причин не делать, просто делаю.
Объект состоит из байт? Да.
Объект сравнивается с другим объектом? Да.
Другой объект из байт? Да.
Код объекта в памяти, данные объекта на диске - читай по байтам и сравнивай.
Собственно это всё, что нужно знать для решения задачи.
8 сен 16, 09:43    [19640548]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
S.G.
Member

Откуда: cartoon network
Сообщений: 30611
wadman
Akina
пропущено...
Похоже, ты даже не читаешь моих слов.

Не, я не ищу причин не делать, просто делаю.
Объект состоит из байт? Да.
Объект сравнивается с другим объектом? Да.
Другой объект из байт? Да.
Код объекта в памяти, данные объекта на диске - читай по байтам и сравнивай.
Собственно это всё, что нужно знать для решения задачи.
Это совершенно не так.
Вот например объект, состоящийся из:
{
- строка номер 1
- строка номер 2
- порядковый номер
- дата
- картинка закодированниая в каком- нибудь base64
}
Сортировать надо сначала по дате, потом по порядковому номеру /там где даты одинаковы/.

Из примера видно, что предложение сортировать какие-то абстрактные байты, совершенно не в кассу. Поскольку "объект" и "ключ сортировки", совершенно разные вещи.
8 сен 16, 16:16    [19643498]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
S.G.
Member

Откуда: cartoon network
Сообщений: 30611
* сортировать список таких объектов, конечно же.
8 сен 16, 16:18    [19643509]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
wadman
Member

Откуда: Санкт-Петербург
Сообщений: 27104
S.G.
Из примера видно, что предложение сортировать какие-то абстрактные байты, совершенно не в кассу. Поскольку "объект" и "ключ сортировки", совершенно разные вещи.

Не увидел противоречия моему описанию.
8 сен 16, 16:23    [19643545]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 11020
Извините, что встреваю в высокоинтеллектуальную беседу ...
При побайтовом сравнении требуется найти пару отличающихся байт.
Для принятия решения "больше-меньше" нужны только эти два байта. И не нужно хранить просмотренные совпадающие блоки.
8 сен 16, 16:23    [19643548]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
kealon(Ruslan)
Member

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


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

с чего вдруг, на каждом этапе сливаются два отсортированных ряда
что мешает разделить на серию небольших блоков, вмещающихся в памяти, отсортировать внутри блока например QSort и сохранить в файл, а потом сливать эти блоки?
15 сен 16, 20:09    [19670660]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка больших данных при малой RAM  [new]
MasterZiv
Member

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

внешняя сортировка слиянием.
17 сен 16, 08:44    [19676451]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / Программирование Ответить