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

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

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

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

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

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