Как отсортировать 52 млн строк? / Общее / Форум / Программирование игр / GameDev.ru

Добрый день
Как можно сделать сортировку большого числа строк (до 52 миллионов)? . Строки сохранены в тестовые файлы, примерно 1100 файлов (можно сохранить в один фаил, около 15 ГБ), в каждой строке ровно по 900 символов, в строках только символы 0-9, некоторые строки повторяются много раз, а некоторое только один раз. Нужно пройти по всем строкам и подсчитать, какие из них сколько раз повторяются.
Как это сделать не понятно, массивов на 52 млн нет, каждый раз преобходить все файлы очень долго. В процессе можно было бы сохранять каждую строку в виде файла, чтоб повторы отсеивались, но у меня виндовс 10 почему-то не поддерживает длинные имена.

lalka
Удалён

#1
9:15, 1 мая 2023

генеришь файл как-то так

base64 /dev/urandom | head -c 4e9 > big.txt

Это задача на external merge sort.

MetalHeart
Постоялец

#2
9:23, 1 мая 2023

Руками можно написать скрипт:
1. Отсортировать содержимое файлов отдельно по возрастанию. Лучше распараллелить этот шаг.
2. Завести массив курсоров к файлам. Размер массива - кол-во файлов, курсор - номер строки.
3. Выставить все курсоры в 0, т.е. они указывают на первую строку.
4. Теперь пройтись в цикле по всем строкам на которые указывают курсоры и найти наименьшую.
5. Записать эту строчку в итоговый файл или пометить как +1. Курсор сместить на след строчку.
6. Повторять шаги 4-5 пока все курсоры не будут указывать в конец файлов.

Но лучше использовать консольные утилиты если их знаешь. Наверняка они есть, но я, увы, их не знаю.

Имбирная Ведьмочка
Участник

#3
12:10, 1 мая 2023

SELECT line, count(*) FROM lines GROUP BY line ORDER BY line;

std::variant
Удалён

#4
13:49, 1 мая 2023

igalinov1
Для подсчета количества повторений каждой строки можно использовать хэш-таблицу. Ключом в хэш-таблице может быть сама строка, а значением - количество ее повторений. При проходе по каждой строке файла, мы можем проверять, есть ли она уже в хэш-таблице. Если да, то увеличиваем значение на единицу. Если нет, то добавляем строку в таблицу со значением

+ Sage

− Скрыть

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <thread>
#include <mutex>

using namespace std;

// Определяем количество строк, которые могут быть загружены в память
const size_t CHUNK_SIZE = 1000000;

// Определяем количество потоков
const size_t NUM_THREADS = thread::hardware_concurrency();

// Определяем функцию хеширования для строк
size_t get_hash(const string& s)
{
    return hash<string>{}(s);
}

// Определяем функцию для записи результатов подсчета повторений строк
void write_counts(const unordered_map<size_t, size_t>& counts, const string& output_file)
{
    ofstream out(output_file);
    for (const auto& [key, value] : counts) {
        out << key << '\t' << value << '\n';
    }
}

// Функция для подсчета повторений строк в одной части файла
void count_lines_chunk(const string& input_file, const size_t chunk_start, const size_t chunk_end, unordered_map<size_t, size_t>& counts, mutex& m)
{
    ifstream in(input_file);
    in.seekg(chunk_start);
    string line;

    while (in.tellg() < chunk_end && getline(in, line)) {
        if (line.empty()) {
            continue;
        }
        const auto hash = get_hash(line);
        lock_guard<mutex> lock(m);
        if (auto it = counts.find(hash); it != counts.end()) {
            it->second++;
        } else {
            counts.emplace(hash, 1);
        }
    }
}

// Считаем строки из файла и подсчитываем количество повторений в несколько потоков
void count_lines(const string& input_file, const string& output_file)
{
    // Вычисляем размер файла
    ifstream in(input_file, ios::binary | ios::ate);
    const size_t file_size = in.tellg();
    in.close();

    // Разбиваем файл на части для каждого потока
    vector<pair<size_t, size_t>> chunks;
    const size_t chunk_size = file_size / NUM_THREADS;
    for (size_t i = 0; i < NUM_THREADS - 1; i++) {
        chunks.emplace_back(i * chunk_size, (i + 1) * chunk_size);
    }
    chunks.emplace_back((NUM_THREADS - 1) * chunk_size, file_size);

    // Создаем потоки и запускаем обработку каждой части файла
    vector<thread> threads;
    vector<unordered_map<size_t, size_t>> thread_counts(NUM_THREADS);
    mutex m;
    for (size_t i = 0; i < NUM_THREADS; i++) {
        threads.emplace_back(count_lines_chunk, input_file, chunks[i].first, chunks[i].second, ref(thread_counts[i]), ref(m));
    }

    // Дожидаемся завершения работы всех потоков
    for (auto& t : threads) {
        t.join();
    }

    // Объединяем результаты из всех хэш-таблиц в одну
    unordered_map<size_t, size_t> counts;
    for (const auto& thread_count : thread_counts) {
        for (const auto& [key, value] : thread_count) {
            if (auto it = counts.find(key); it != counts.end()) {
                it->second += value;
            } else {
                counts.emplace(key, value);
            }
        }
    }

    // Записываем результаты в выходной файл
    write_counts(counts, output_file);
}

int main()
{
    const string input_file = "input.txt";
    const string output_file = "output.txt";
    count_lines(input_file, output_file);
    return 0;
}

entryway
Участник

#5
14:11, 1 мая 2023

Если это не наперегонки, то может попробовать просто взять и отсортировать? У меня нет места на 15 гигабайт, но 7 гигабайт данных ниже сортируются ~8 минут:

cat 7g | sort | uniq -c | sort -rn > xxx

+ Показать

ronniko
Участник

#6
15:18, 1 мая 2023

7 гигабайт данных ниже сортируются ~8 минут

И кто считает что современные компы крутые девайсы ?
Ведро с болтами.
Полное разочарование в компьютерах.

entryway ты сам писал тест сортировки семи гиг ? На с++ писал ?

entryway
Участник

#7
15:46, 1 мая 2023

ronniko
> entryway ты сам писал тест сортировки семи гиг ? На с++ писал ?
Нет, просто вызывал стандартные утилиты OS.

NitroHub
Постоялец

#8
17:26, 1 мая 2023

> большого числа строк (до 52 миллионов)

большое будет когда миллиарды

а так второй пост

Aslan
Постоялец

#9
19:16, 1 мая 2023

igalinov1
Если только повторы считать, то самое простое - сортировать по какому-то хэшу, разбить на части, уже влезающие в оперативку, а там уж пройтись точным сравнением для повторяющихся значений хэш.

Еще дерево строк можно использовать, вроде может сильно сократить обьем за счет повторяющихся частей.

Или MergeSort (уже предлагали) - читаешь по строке с двух файлов, пишешь в третий (дофига чтений винта и репозицонирований головки).

Skvoznjak
Постоялец

#10
20:21, 1 мая 2023

Извращаться нужно только если в системе не хватает памяти, а так, делаешь несколько массивов и функцию прослойку между ними и счётчиком. Если же памяти не хватает, а тебе нужно убрать все повторы, то разделяешь свои данные на массивы по ~4Гб, обрабатываешь каждый поштучно и пересохраняшь - это первичная обработка. Затем занимаешься вторичной - если не можешь выделить на работу 8Гб, то дробишь свои файлы вдвое, после сравниваешь каждый по очереди с каждым из других и обрабатываешь. На паскале это элементарная задача запрограммировать самому (с гото конечно, потому-что без него - дикий ужас и пляска на граблях), без всяких утилит - пока будешь их изучать, уже свою уже почти допишешь.