Member 14549747 Ответов: 4

Как я могу отсортировать 100 ГБ в памяти объемом 1 ГБ ?

У меня есть проект, в котором меня просят отсортировать файл размером 100 ГБ в памяти объемом 1 ГБ . Я новичок в этом деле
информатика и я не могу понять концепцию сортировки 100 ГБ в 1 ГБ, и я хотел бы получить вашу помощь в решении этой конкретной проблемы.
Спасибо, что уделили мне время .

Что я уже пробовал:

В сортировке mergesort-это самый быстрый метод сортировки со сложностью O(nlogn), а деревья b+ хороши для сортировки больших объемов данных, поэтому я думаю, что это должен быть один из этих 2 методов . Однако я не могу отменить концепцию, которую я объяснил выше .

4 Ответов

Рейтинг:
2

Patrice T

Цитата:
Я новичок в этом деле
информатика и я не могу понять концепцию сортировки 100 ГБ в 1 ГБ, и я хотел бы получить вашу помощь в решении этой конкретной проблемы.

Наверное, потому, что нет такого понятия.
Жесткий диск и память-это, по сути, одно и то же, разница в том, что объем памяти меньше, а память быстрее.
Поскольку память является естественным рабочим местом процессора, а файл-нет, средства чтения и записи отличаются в коде, но они похожи в принципе.
Главное отличие, которое я вижу, заключается в том, что последовательное чтение/запись в файле более эффективно, чем случайное чтение/запись.
Цитата:
В сортировке mergesort-это самый быстрый метод сортировки со сложностью O(nlogn), а деревья b+ хороши для сортировки больших объемов данных, поэтому я думаю, что это должен быть один из этих 2 методов .

Существует гораздо больше методов сортировки, и каждый из них имеет свое преимущество.
Обратите внимание, что метод сортировки не связан с размером данных, некоторые из них просто более эффективны, чем другие в определенных ситуациях.
Так что сортировка слиянием-это хороший вариант. Помните, что вы сравниваете только 2 значения одновременно.
Вы можете использовать гибридный метод, объединять сортировку небольших кусков (менее половины объема памяти) в памяти и больших щелей в файле.

Совет: изучите алгоритмы сортировки
Алгоритм сортировки - Википедия[^]
Алгоритмы Сортировки - GeeksforGeeks[^]

Рейтинг:
18

RickZeeland

Здесь вы можете найти примеры на разных языках: внешняя сортировка · темы GitHub · GitHub[^]

Рейтинг:
0

phil.o

Концепция, которая вам нужна для выполнения вашей задачи, называется Внешняя сортировка[^].

Рейтинг:
0

OriginalGriff

Первое, что нужно сделать, это начать с того, что вы должны отсортировать: что содержит файл, который нуждается в сортировке? По чему его нужно сортировать?

Подумайте об этом: если у вас на столе лежит стопка смешанных банкнот, существует множество способов их сортировки: по номиналу, по цвету, по размеру, по серийному номеру. Что из этого важно?
При выборе "свойства сортировки" для банкнот вы можете эффективно игнорировать все остальные свойства: например, номинал означает, что вам не важен размер или цвет.

Ваш файл, вероятно, организован примерно так же: он будет содержать информацию в строках, которые должны быть отсортированы по определенному столбцу (или набору столбцов, возможно), и вы можете - для целей сортировки - игнорировать все остальные столбцы.
Когда вы знаете, по чему сортировать, вы можете начать рассматривать возможность сортировки прямо сейчас - но обратите внимание, что если вы начнете фактически разбивать входные данные на отдельные файлы, вы будете смотреть на множество больших файлов: вероятно, потребуется намного больше 100 ГБ.

Я бы построил "индексный файл", который содержит смещение начала каждой строки в главном файле, и отсортировал его, используя любой метод, который вы предпочитаете. Когда он будет отсортирован, создайте новый файл и скопируйте в него строки данных в новом порядке.