Сортировка и слияние данных из разных файлов в один
У меня возникла задача реализовать алгоритм слияние файлов (совместно с сортировкой) в один большой файл. Задача усложняется тем, что каждый файл полностью помещается в памяти, но все сразу — нет. Я решил отсортировать каждый файл по отдельности и затем слить их в один большой, но вот как производить слияние, если все вместе они не помещаются в памяти.
Файлы содержат только числа от min(int64_t) и до max(int64_t), разделенные пробелом, например такая последовательность файлов:
должна быть слита в такой файл:
Какой можно было бы выбрать способ или алгоритм для реализации данной задачи на С++ (готовые ф-ии использовать не буду, хочется самому написать код)?
Для ускорения поможет буфер чтения. Просто читаем несколько чисел и их заносим в двумерный массив. А алгоритм слияния стандартный :
- Находим минимальное число из первых, что хранятся в буфере
- Вычёркиваем этот один элемент из буфера
Вот как реализовал буфера :
Функции в реализации :
читаю первое число, что находится в буфере i-го файла и записываю в указанное место памяти, возвращаю true или false
удаляю первый элемент из буфера i-го файла
нахожу минимальное число из доступных первых, записываю результат в место памяти, удаляю этот элемент из буфера, возвращаю true или возвращаю false
в главной функции просто нахожу минимальное число с помощью findmin , и записываю в файл
Тестировал в Си и плюсах такой код :
К сожалению, я не могу сейчас тестировать такие большие файлы. Но все же решил поделится своей идеей. Так как автор вопроса написал хочется самому написать код я не буду лишать его такой возможности, и по этой же причине прошу не минусовать мой код приведенный на JavaScript поскольку он служит псевдокодом к ответу. Т.е. в данном случае я приведу лишь свою логику, а автор вопроса если она ему понравится сможет доработать ее на плюсах или любом другом языке, который сочтет нужным. Лично мне мое решение нравится как и сам вопрос, хотя решение не идеально (иногда и только в плане размеров файлов) в остальном оно рабочее.
- идея алгоритма родилась из того что командой cat в linux и type в windows можно объединить файлы превышающие объем оперативки (я проверял на linux )
- для демонстрации вместо файлов я использую массивы таким образом алгоритм легко протестировать даже в браузере
- алгоритм гарантирует что левый(первый) файл не содержит числа превышающего любое из чисел в правом(следующем) файле
- минусом алгоритма является то что он не гарантирует размещение в памяти отдельного файла (но частично это настраивается, хотя решение не полное если файл с одинаковыми числами не влезет в память)
- проходим по всем файлам и сортируем их по отдельности
- после того как у нас появилсись минимумы и максимумы в отдельных файлах мы можем найти общий минимум и максимум, а так же запомнить максимальный размер файла
- далее мы создаем какое-то количество файлов (больше чем есть — лучше) в которые будем раскидывать наши числа, куда кидать число мы решаем согласно его величине и количеству файлов, таким образом меньшие числа попадут в первый файл а самые большие в последний
- после того как мы раскидали числа по файлам, файлы нужно снова отсортировать так как первоначальная сортировка была нарушена
- после того как мы отсортировали файлы нам остается только склеить их в один большой.
Как видно при 10000 итерациях произошла 1 ошибка превышения размера файла , это значит что один из файлов оказался больше самого большого первоначального файла но я не измерял на сколько, возможно совсем на чуть-чуть, все дело в данных если к примеру будет идти очень много одинаковых чисел то по алгоритму они должны попасть в 1 файл и соответственно тот разростется в размерах — это единственный видимый мной минус данного подхода, возможно есть и другие которые я не вижу на данный момент, пока не придумал как это обойти.
По большей части я не стремился дать конкретный ответ, это бы заняло куда больше времени чем я уже потратил, просто решил предложить одну из идей для реализации, возможно это подтолкнет автора вопроса к своему решению.
Как склеить (сшить) два кода Python вместе?
Мне интересно, как лучше всего собрать коды из разных файлов Python в новый файл Python. Допустим, первый файл 1.py будет состоять из:
И еще один файл 2.py состоит из:
Теперь предположим, что у вас есть конечный файл final.py , в который вы хотите, чтобы все коды из 1.py и 2.py копировались в него слово в слово в определенном порядке операций, где он выглядит, как показано ниже , Обратите внимание, что я понимаю, что мы можем использовать функцию импорта в Python, но в этом случае я бы хотел, чтобы весь текст некоторых определений был скопирован в новый код Python. Другими словами, склейте коды из разных файлов, чтобы создать новый файл.
Перефразируйте выше: что, если файл 1 имеет 100 определений, а файл 2 имеет 100 определений, но я хочу, чтобы из каждого файла были скопированы конкретные файлы в файл 3 с полным текстом и синтаксисом в указанном порядке.
Как склеить код из разных файлов
В статье вы научитесь создавать программу из нескольких файлов
Содержание
Объявления и определения
Рассмотрим задачу: надо вывести числа от N до 1, при этом для нечётных чисел надо писать odd $
Ради интереса решим задачу с помощью рекурсии:
Увы программа не компилируется. В C++ каждая функция должна быть объявлена или определена до первого использования, но в нашем случае printEvenRecursive использует printOddRecursive, а printOddRecursive использует printEvenRecursive! Мы не можем поместить определение одной функции выше другой так, чтобы каждая функция была объявлена перед использованием.
Но кроме определений функций в C++ есть объявления функций
- Объявление (declaration) — это конструкция, которая зарезервирует идентификатор и опишет для компилятора его тип, но не раскроет деталей работы объявленной сущности.
- Определение (definition) — это конструкция, которая не только зарезервирует идентификатор, но и раскроет реализацию связанной с ним сущности
Объявление функции похоже на определение функции, только вместо тела стоит точка с запятой:
Теперь мы можем переписать рекурсивный пример, просто разместив определения обеих функций в начале файла.
Хорошим стилем считается заранее и в одном месте писать объявления всех функций, кроме main. Вы можете писать объявления в начале cpp-файла или в заголовке. О заголовках читайте ниже.
Пишем свой заголовок
В C/C++ заголовок — это файл с расширением *.h или *.hpp , который включается в другие файлы директивой #include .
- Заголовок может иметь и другое расширение файла, но не стоит нарушать джентльменских соглашений: используйте h или hpp
- В заголовке пишут только объявления функций, а все определения можно и нужно помещать в cpp-файл
Создайте каталог, и разместите в нём файл print.h , в котором будут объявления функций. Скопируйте туда код, приведённый ниже.
Мы могли бы убрать из заголовка printEvenRecursive и printOddRecursive, сделав его чище, но сейчас для примера оставим.
Запомните правила хорошего тона:
- в начале заголовка пишите #pragma once , чтобы не получить ошибки компиляции при ромбовидном include, когда одни и те же сущности объявляются несколько раз (подробнее о pragma once и define guards…)
- заголовок должен быть чистым, ведь он повторно используется многими файлами проекта
- поэтому не пишите в заголовке using namespace . ; , иначе вы замусорите глобальное пространство имён целого проекта
Теперь создайте файл print.cpp , в котором будут реализованы функции из заголовка print.h . Скопируйте туда код, расположенный ниже.
Обратите внимание: #include <iostream> находится в cpp-файле, а не в заголовке, потому что экспортированные из iostream сущности нужны только в реализации функций, но не нужны в объявлении.
В конце создайте файл main.cpp и скопируйте в него код:
Компоновка программы из нескольких файлов
Собирая программу из одного файла с помощью g++, вы на деле выполняли одним махом два действия:
- компиляцию, в ходе которой исходный текст файла превращается в логическую модель (AST) и затем превращается в объектный код, в котором машинные коды смешаны со ссылками на внешние функции
- компоновку, в ходе все внешние ссылки на функции заменяются на машинный код либо превращаются в ссылки на динамические библиотеки (dll/so, также известны как shared libraries)
Сейчас эти же действия мы выполним раздельно. Отройте терминал и введите последовательно две команды:
Если код в обоих cpp-файлах синтаксически правилен, то компилятор создаст два файла: main.o и print.o . Эти файлы называют объектными файлами (object files). Именно они содержат машинный код, смешанный со ссылками на внешние функции.
Вы можете дизассемблировать эти файлы, чтобы посмотреть, во что компилятор превратил ваш код. Для этого выполните команду objdump -d main.o .
Теперь мы вызовем g++ для компоновки объектных файлов. На выходе мы получим исполняемый файл print_executable.exe
На деле компилятор не будет компоновать: он передаст эту задачу утилите ld. Вызывать утилиту ld вручную мы не станем, потому что потребуются дополнительные флаги, которые включают компоновку со стандартной библиотекой C++.
Компоновка программы в CMake
CMake прячет факт раздельной компиляции файлов. Чтобы в CMake скомпоновать программу, состоящую из нескольких частей, просто перечислите эти файлы в add_executable.
Удалите файл print_recursive.exe :
Создайте файл CMakeFiles.txt с одной строкой:
Теперь выполните конфигурирование и сборку программы:
Мы почти закончили! Остался только один вопрос: почему в add_executable мы указали заголовок print.h , если он всё равно не компилируется сам по себе? Дело в том, что при любых изменениях в коде заголовка print.h вся программа должна быть пересобрана, но файл print.h сам по себе не компилируется. Добавление print.h в список исходников в CMake позволяет CMake следить за датой и временем модификации заголовка, чтобы решить, надо ли повторно собирать проект из-за изменений в заголовках.
Зачем это нужно?
Копипаст вручную — это, может, и не самый плохой вариант для небольшого количества файлов.
Но представьте, что вам нужно объединить 100+ файлов… готовы ли вы сделать все вручную? Эта затея весьма утомительна и чревата ошибками.
Для файлов с одинаковой структурой таблицы (те же заголовки и количество столбцов) можно воспользоваться скриптом на Python.
Шаг 1: Импортируйте пакеты и задайте рабочую директорию
Измените “/mydir” на нужную вам директорию.
Шаг 2: Воспользуйтесь glob для сопоставления с шаблоном ‘csv’
Сопоставьте шаблон (‘csv’) и сохраните список имен файлов в переменной ‘all_filenames’. Здесь можно почитать о сопоставлении регулярных выражений.