ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Сортировка больших данных при малой RAM
25 сообщений из 44, страница 1 из 2
  1  все
Сортировка больших данных при малой RAM
    #39305264
interweb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
interweb
Участник
Интересуют способы сортировки больших данных (порядка 10 ТБ) при наличии лишь 1 GB RAM

Исследованные варианты:
1) Разбить файл на тысячи относительно небольших файлов, отсортировать каждый из них и потом склеить. Но этот вариант работать не будет т.к. скажем в первом файле значения 1-10, в 100м значения от 1-50, поэтому склейка не состоится
2) Можно попробовать использовать некую БД, но не уверен, что это правильный подход
3) Можно использовать apache spark, но из того примера, что я видел, данные из файла должны быть все считанны в память - это не представляется возможным.
...
Рейтинг: 0 / 0
07.09.2016, 15:09
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305269
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Блочная сортировка
...
Рейтинг: 0 / 0
07.09.2016, 15:18
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305286
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Для случая, когда бОльшая часть данных должна кэшиться на диск, хорошо подходит Сортировка слиянием .
...
Рейтинг: 0 / 0
07.09.2016, 15:35
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305302
interweb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
interweb
Участник
AkinaДля случая, когда бОльшая часть данных должна кэшиться на диск, хорошо подходит Сортировка слиянием .

Такой подход я рассматривал, но мне он видится неэффективным: в нем необходимо разбивать данные до байт, а это создаст слишком много временных файлов, и вообще займет много времени.
...
Рейтинг: 0 / 0
07.09.2016, 15:46
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305310
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
interwebмне он видится неэффективным: в нем необходимо разбивать данные до байт, а это создаст слишком много временных файлов, и вообще займет много времени.Да ладно- много файлов! считать научись... если, например, использовать блоки сортировки по 1 Мбайт, то на диске будет максимум 28 файлов, включая исходный и конечный.
...
Рейтинг: 0 / 0
07.09.2016, 15:52
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305315
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
interweb,

первый вариант - рабочий. Недавно реализовал. ;)
...
Рейтинг: 0 / 0
07.09.2016, 15:56
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305317
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Как вариант: если в сортировке участвует небольшая часть данных до 1%, т.е. файл это набор записей например по 1 Кб и каждая содержит ключ 8 байт. Для сортировки перелить ключи в отдельный файл со структурой {ключ, смещение}, где смещение - это расположение записи в исходном файле. Затем сортировать по ключу этот новый файл. Затем по нему и исходному создать файл с результатом.
...
Рейтинг: 0 / 0
07.09.2016, 15:57
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305331
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
И зачем Дональд Кнут книги писал...

Гугл по запросу "внешняя сортировка" выдаёт достаточно материалов
...
Рейтинг: 0 / 0
07.09.2016, 16:14
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305384
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
Имхо все промышленные бд использую велосипеды на тему .
...
Рейтинг: 0 / 0
07.09.2016, 17:27
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305400
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
x1ca4064
Участник
interweb,

А сколько в 10ТБ сущностей для сортировки?
...
Рейтинг: 0 / 0
07.09.2016, 17:40
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305435
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
x1ca4064А сколько в 10ТБ сущностей для сортировки?
Любое случайное количество. Это не имеет значения.
...
Рейтинг: 0 / 0
07.09.2016, 18:25
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305456
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
wadmanЭто не имеет значения.При условии, что 2 комплекта необходимых для сравнения частей сущности поместятся в оперативке... внешнее сравнение двух экземпляров я как-то себе с трудом представляю.
...
Рейтинг: 0 / 0
07.09.2016, 19:14
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305460
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
Akinaвнешнее сравнение двух экземпляров я как-то себе с трудом представляю.
Я это реализовал последовательным чтением.
Оперативки в моем решении нужно 16 мб (можно и меньше), а размер файла не ограничен.
...
Рейтинг: 0 / 0
07.09.2016, 19:22
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305461
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
wadmanAkinaвнешнее сравнение двух экземпляров я как-то себе с трудом представляю.
Я это реализовал последовательным чтением.
Оперативки в моем решении нужно 16 мб (можно и меньше), а размер файла не ограничен.
Соврал. :) Не реализовал, но задумал через буферное упреждающее чтение.
...
Рейтинг: 0 / 0
07.09.2016, 19:29
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305464
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
AkinaПри условии, что 2 комплекта необходимых для сравнения частей сущности поместятся в оперативке...
Как часто надо сравнивать сущности по 0.5+ Гб ? Напомню
interwebпри наличии лишь 1 GB RAM
...
Рейтинг: 0 / 0
07.09.2016, 19:32
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305469
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
Dima TКак часто надо сравнивать сущности по 0.5+ Гб ?
Например, при написании тестового задания.
...
Рейтинг: 0 / 0
07.09.2016, 19:36
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305474
interweb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
interweb
Участник
wadmaninterweb,

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

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

Блок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го блока и не сравниваются с другими блоками.
...
Рейтинг: 0 / 0
07.09.2016, 19:42
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305475
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
interweb, топик внимательно перечитай.
...
Рейтинг: 0 / 0
07.09.2016, 19:49
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305483
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
interwebОн не может быть рабочим. Вот пример:
Как так? У меня же получилось. :)

Есть 4-е отсортированных (ранее разбитых) файла (1, 2, 3, 4).
Читаем по строке из каждого и сортируем их.
1. Первую строку сливаем в общий файл (0).
2. Если эта строка была (например) из 4-го файла, то из него-же и читаем новую строку.
3. Снова сортируем.
4. см п.1.
...
Рейтинг: 0 / 0
07.09.2016, 20:07
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305487
Владимир2012
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир2012
Участник
interwebИнтересуют способы сортировки больших данных (порядка 10 ТБ) при наличии лишь 1 GB RAM

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

"И это пожалуй все!" /Форест Гамп/
...
Рейтинг: 0 / 0
07.09.2016, 20:27
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305502
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
x1ca4064
Участник
wadmanЛюбое случайное количество. Это не имеет значения.

Не согласен, т.к. "дъявол прячется в деталях": если нужно отсортировать 10^12 байт (т.е. каждая сущность занимает 1 байт), это одно, если нужно отсортировать 2 сущности по 5*10^11, это другое. Общее решение либо должно учитывать эти вырожденные случаи (плюс еще какие-либо возможные, порожденные особой статистикой исходных данных), либо будет не эффективным в ряде задач.
...
Рейтинг: 0 / 0
07.09.2016, 21:15
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305506
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
x1ca4064Не согласен, т.к. "дъявол прячется в деталях"
Детали такие, что любая последовательность байт.
Задача такая.
Придется смириться с ТЗ, а не выставлять в обратку свои.
...
Рейтинг: 0 / 0
07.09.2016, 21:22
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305510
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
x1ca4064
Участник
wadmanx1ca4064Не согласен, т.к. "дъявол прячется в деталях"
Детали такие, что любая последовательность байт.
Задача такая.
Придется смириться с ТЗ, а не выставлять в обратку свои.
Не бывает такого, "отсортировать любую последовательность байт" (если не брать вырожденный случай): эти байты описывают какие-то сущности, для которых и определяют операцию отношения. Для сущностей, подчеркиваю, а не для байт.
...
Рейтинг: 0 / 0
07.09.2016, 21:29
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305513
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
wadmanЯ это реализовал последовательным чтением.
wadmanзадумал через буферное упреждающее чтение.
Это ты всё рассказываешь в предположении, что мы сравниваем строки (ну или бин-последовательности), причём строго посимвольно.

А представь себе вариант, когда сравниваемые сущности - это сложные объекты, причём единственный способ сравнить объекты A и B - это вызвать тернарный метод A.Compare(B) (ну либо B.Compare(A) - причём они дадут одинаковый ответ, хотя могут отличаться реализацией). Т.е. надо не только загрузить в память объект А для вызова его метода (и соответственно целиком - а ведь его для этого ещё может потребоваться десериализовать!), но и передать ему (и соответственно опять же полностью загрузить в память) объект B...
...
Рейтинг: 0 / 0
07.09.2016, 21:38
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305529
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
x1ca4064Не бывает такого
Уже есть.
AkinaЭто ты всё рассказываешь в предположении, что мы сравниваем строки (ну или бин-последовательности), причём строго посимвольно.
Нененене. Читай первое сообщение темы и не выдумывай новые условия.
Загружать "объект" полностью нет необходимости. Все можно/нужно делать побайтно.
Важен результат = отсортированный файл (байты!).
...
Рейтинг: 0 / 0
07.09.2016, 22:02
| Ответить | Цитировать | Написать  
25 сообщений из 44, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Сортировка больших данных при малой RAM
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&startmsg=39305264&tid=1340611]:
 0ms
get settings:
 6ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 61ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 56ms
get tp. blocked users:
 1ms
others: 211ms
total:  367ms
созд. / загр.: 367ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]