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

а что за файл, какая структура? в смысле - текст, или блоки данных - одинаковые?
файл строго последовательного доступа, или можно организовать произвольный?
...
Рейтинг: 0 / 0
07.09.2016, 22:10
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305532
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
x1ca4064
Участник
wadmanУже есть.


Не может быть :), но если уж такая проблема возникла (т.е. сущность==байт) то решение элементарно: заводим 256 счетчиков достаточной размерности, последовательно читаем байты, инкрементируем соответствующий счетчик, после выдаем отсортированную последовательность. Для реализации под 10ТБ данных хватит пары килобайт.
...
Рейтинг: 0 / 0
07.09.2016, 22:12
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305533
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
x1ca4064wadmanУже есть.


Не может быть :), но если уж такая проблема возникла (т.е. сущность==байт) то решение элементарно: заводим 256 счетчиков достаточной размерности, последовательно читаем байты, инкрементируем соответствующий счетчик, после выдаем отсортированную последовательность. Для реализации под 10ТБ данных хватит пары килобайт.
Сущность = любая последовательность байт. Никаких счетчиков не хватит.
Уже было. Повторяемся?
...
Рейтинг: 0 / 0
07.09.2016, 22:14
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305536
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
wadmanЧитай первое сообщение темы и не выдумывай новые условия.Прочитал внимательно все посты ТС.

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

И вообще - это я не ТС пишу, а тебе, в ответ на огульное утверждение, что внешнее сравнение возможно в любом случае.
...
Рейтинг: 0 / 0
07.09.2016, 22:18
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305537
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
x1ca4064если уж такая проблема возникла (т.е. сущность==байт) то решение элементарно: заводим 256 счетчиков достаточной размерности, последовательно читаем байты, инкрементируем соответствующий счетчик, после выдаем отсортированную последовательность.Это т.н. "Сортировка подсчётом".
...
Рейтинг: 0 / 0
07.09.2016, 22:20
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305538
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
x1ca4064
Участник
wadmanСущность = любая последовательность байт. Никаких счетчиков не хватит.
Уже было. Повторяемся?

Вероятно, я не понимаю, о чем Вы говорите: сообщите, какая операция отношения у Вас определена на множестве "любая последовательность байт"? Пример, хотя бы. Ответ любая не принимается, т.к. не бывает задачи отсортировать "любую последовтельность байт" ... ах да, уже повторяюсь :)
Бывает только задача отсортировать последовательность сущностей. (New!)
...
Рейтинг: 0 / 0
07.09.2016, 22:30
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305540
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
x1ca4064
Участник
AkinaЭто т.н. "Сортировка подсчётом".

А я то все гадал, как она называется :)
...
Рейтинг: 0 / 0
07.09.2016, 22:31
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305544
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
interweb,

какова структура файла? (сортируемых записей)
...
Рейтинг: 0 / 0
07.09.2016, 23:03
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305559
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
x1ca4064
Участник
AkinaЭто т.н. "Сортировка подсчётом".

А я то все гадал, как она называется :)
...
Рейтинг: 0 / 0
08.09.2016, 02:16
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305621
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
interweb3) Можно использовать apache spark, но из того примера, что я видел, данные из файла должны быть все считанны в память - это не представляется возможным.
Ну ты даешь чувак! Чтоб приготовить яичницу ты пойдешь разогревать адронный коллайдер?

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

Поищи "сортировка слиянием" и еще до кучи "B+дерево" как альтернативный вариант
...
Рейтинг: 0 / 0
08.09.2016, 08:47
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305629
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
AkinaИ вообще - это я не ТС пишу, а тебе, в ответ на огульное утверждение, что внешнее сравнение возможно в любом случае.
Это так и есть. Любая сущность - это байты.
Если вся сущность не влазит в оперативку, то байт влезет.
x1ca4064Ответ любая не принимается, т.к. не бывает задачи отсортировать "любую последовтельность байт"
Ок, пусть будут строки любой длины. Они, как известно, состоят из байт.
И бывает так, что вся строка не влазит в оперативку.
Достаточно "дочитывать" данные в процессе сравнения.
...
Рейтинг: 0 / 0
08.09.2016, 09:32
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305632
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
wadmanЭто так и есть. Любая сущность - это байты.
Если вся сущность не влазит в оперативку, то байт влезет.Похоже, ты даже не читаешь моих слов.
...
Рейтинг: 0 / 0
08.09.2016, 09:39
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305635
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
AkinawadmanЭто так и есть. Любая сущность - это байты.
Если вся сущность не влазит в оперативку, то байт влезет.Похоже, ты даже не читаешь моих слов.
Не, я не ищу причин не делать, просто делаю.
Объект состоит из байт? Да.
Объект сравнивается с другим объектом? Да.
Другой объект из байт? Да.
Код объекта в памяти, данные объекта на диске - читай по байтам и сравнивай.
Собственно это всё, что нужно знать для решения задачи.
...
Рейтинг: 0 / 0
08.09.2016, 09:43
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39305996
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
wadmanAkinaпропущено...
Похоже, ты даже не читаешь моих слов.
Не, я не ищу причин не делать, просто делаю.
Объект состоит из байт? Да.
Объект сравнивается с другим объектом? Да.
Другой объект из байт? Да.
Код объекта в памяти, данные объекта на диске - читай по байтам и сравнивай.
Собственно это всё, что нужно знать для решения задачи.Это совершенно не так.
Вот например объект, состоящийся из:
{
- строка номер 1
- строка номер 2
- порядковый номер
- дата
- картинка закодированниая в каком- нибудь base64
}
Сортировать надо сначала по дате, потом по порядковому номеру /там где даты одинаковы/.

Из примера видно, что предложение сортировать какие-то абстрактные байты, совершенно не в кассу. Поскольку "объект" и "ключ сортировки", совершенно разные вещи.
...
Рейтинг: 0 / 0
08.09.2016, 16:16
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39306000
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
* сортировать список таких объектов, конечно же.
...
Рейтинг: 0 / 0
08.09.2016, 16:18
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39306006
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
S.G.Из примера видно, что предложение сортировать какие-то абстрактные байты, совершенно не в кассу. Поскольку "объект" и "ключ сортировки", совершенно разные вещи.
Не увидел противоречия моему описанию.
...
Рейтинг: 0 / 0
08.09.2016, 16:23
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39306007
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Извините, что встреваю в высокоинтеллектуальную беседу ...
При побайтовом сравнении требуется найти пару отличающихся байт.
Для принятия решения "больше-меньше" нужны только эти два байта. И не нужно хранить просмотренные совпадающие блоки.
...
Рейтинг: 0 / 0
08.09.2016, 16:23
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39309884
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
interwebAkinaДля случая, когда бОльшая часть данных должна кэшиться на диск, хорошо подходит Сортировка слиянием .

Такой подход я рассматривал, но мне он видится неэффективным: в нем необходимо разбивать данные до байт, а это создаст слишком много временных файлов, и вообще займет много времени.
с чего вдруг, на каждом этапе сливаются два отсортированных ряда
что мешает разделить на серию небольших блоков, вмещающихся в памяти, отсортировать внутри блока например QSort и сохранить в файл, а потом сливать эти блоки?
...
Рейтинг: 0 / 0
15.09.2016, 20:09
| Ответить | Цитировать | Написать  
Сортировка больших данных при малой RAM
    #39310737
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
interweb,

внешняя сортировка слиянием.
...
Рейтинг: 0 / 0
17.09.2016, 08:44
| Ответить | Цитировать | Написать  
19 сообщений из 44, страница 2 из 2
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Сортировка больших данных при малой RAM
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39305538&tid=1340611]:
 0ms
get settings:
 9ms
get forum list:
 18ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 170ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 55ms
get tp. blocked users:
 1ms
others: 230ms
total:  501ms
созд. / загр.: 501ms
x
x
Закрыть


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