Необходимо найти N самых длинных строк в файле и вывести их в другой файл в обратном порядке.
Как это можно сделать наиболее эффективно по скорости работы и потреблению памяти?
Необходимо найти N самых длинных строк в файле и вывести их в другой файл в обратном порядке.
Как это можно сделать наиболее эффективно по скорости работы и потреблению памяти?
Разбейте задачу на подзадачи.
После 1-2 часов внимательной работы с поисковиком по этим пунктам у вас будет хорошая база знаний для решения этой задачи. Обязательно пишите небольшие кусочки кода самостоятельно, не берите готовые примеры - это убивает творчество.
UPD. Вопрос был изменен автором, поэтому обновляю и ответ
Чтобы узнать самые длинные строки в файле, придется прочитать весь файл. Если вы не прочитаете хотя бы одну строку - возможно она и была самой длинной. Проще всего использовать std::fstream + std::list + std::getline
std::list<std::string> list; // Хранилище строк
std::ifstream file("тут ваш путь"); // Файл для чтения
std::string line; // Одна строка для обработки
while (std::getline(file, line))
{
// обработайте строку
// например, добавьте её в список строк
list.push_back(line);
}
Теперь у нас есть список из строк. Нам нужно взять оттуда N самых длинных строк. Сортируем по длине строки! Нам поможет std::list::sort()
Необходимо определить функцию для сравнения двух элементов списка
bool compare_by_length (const std::string& first, const std::string& second)
{
return ( first.length() < second.length() );
}
Теперь мы можем использовать эту функцию для сортировки
// Сортируем список
list.sort(compare_by_length);
// Нам нужно взять первые N элементов
std::list<std::string>::const_iterator i;
int index = 0;
int N = 5;
// Выводим строки из списка до тех пор, пока есть строки в списке
// и выведено менее N строк
for (i = list.begin(); (i != list.end()) && (count < N;) ++i) {
++count; // Увеличиваем количество взятых строк
std::cout << index << ": " << (*i) << std::endl;
}
В итоге мы получим первые N самых длинных строк из файла
Для решения этой задачи, прямо-таки напрашивается очередь с приоритетом, реализация которой есть в стандартной библиотеке - std::priority_queue<>.
Все что нужно - определить соответствующий компаратор и следить за размером очереди.
#include <functional>
#include <queue>
#include <vector>
#include <iostream>
#include <string>
#include <fstream>
template<typename T>
void print_queue(T& q)
{
while(!q.empty())
{
std::cout << q.top() << '\n';
q.pop();
}
}
int main()
{
using S = std::string;
auto cmp = [](const S &a,const S &b)
{
return a.size() > b.size();
};
std::priority_queue<S, std::vector<S>,decltype(cmp)> q(cmp);
std::ifstream file("test.cpp");
std::string line;
std::size_t N = 5;
while (std::getline(file, line))
{
if (q.size()>N)
q.pop();
q.push(line);
}
if (q.size()>N)
q.pop();
print_queue(q);
}
Вам потребуется выполнить ровно два прохода по файлу:
Нет необходимости явно хранить номера строк и сортировать по ним, так как смещения от начала файла до начала очередной строки (которое мы уже храним для извлечения и копирования в новый файл) также монотонно возрастают.
И ещё. Так как из всего списка, создаваемого на первом проходе, нам потребуется только N первых элементов, то нет необходимости хранить весь список. Вместо этого будем хранить только N строк, наиболее длинных на текущий момент и при необходимости вставлять в него новые элементы с вытеснением старых.
#include <algorithm>
#include <fstream>
#include <limits>
static const char inFile[] = "in.txt"; // Входной файл
static const char outFile[] = "out.txt"; // Выходной файл
enum {N = 7}; // Сколько самых длинных строк надо вывести?
struct LineInfo
{
std::streampos begin;
std::streamsize length;
};
static bool lengthLessComparator(const LineInfo& a, const LineInfo& b)
{
// Знак сравнения поменян, потому что нам необходим обратный порядок
// Также учитываем случай строк с одинаковыми длинами
return a.length > b.length || (a.length == b.length && a.begin > b.begin);
}
template<class T, size_t N>
static T* end(T (&array)[N])
{
return array + N;
}
int main()
{
// Список N самых длинных строк. Сортированность поддерживаем вручную
LineInfo longest[N];
LineInfo* longestListEnd = longest;
// Начинаем построчное чтение
std::fstream in(inFile, std::ios_base::in);
bool hasMoreLines = true;
while(hasMoreLines)
{
const std::streampos stringBegin = in.tellg();
const size_t stringLength = in.gcount();
// Разделитель также считывается
in.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
// Первая часть условия не даёт пропустить последнюю строку.
// Вторая часть не даёт завершиться на пустой строке.
if(stringLength > 0 && in)
{
// Ищем, куда именно надо вставить новый элемент в список (и надо ли вообще)
LineInfo potentialLine;
potentialLine.begin = stringBegin;
potentialLine.length = stringLength;
LineInfo* const newPosition = std::lower_bound(
longest,
longestListEnd,
potentialLine,
lengthLessComparator
);
// Если элемент должен быть вставлен в хвосте списка, проверяем возможность этого
if(newPosition != longestListEnd || longestListEnd != end(longest))
{
*(++longestListEnd) = potentialLine;
std::sort(longest, longestListEnd, lengthLessComparator);
}
}
else
hasMoreLines = false;
}
// Теперь выводим строки в новый файл
std::fstream out(outFile, std::ios_base::out);
for(LineInfo* line = longest; line != longestListEnd; ++line)
{
in.seekg(line->begin);
in.get(*out.rdbuf(), '\n');
out << '\n';
}
}