У меня есть код, который применяет алгоритм Дейкстры для списка смежности.
Данные берутся из файла. В файле первая строка содержит количество вершин и ребер, а остальные строки содержат по три элемента каждая (первые 2 — это номера вершин, а 3-я — вес ребер).
Вывод записывается в другой файл. Основная проблема — долгое чтение (добавление в список) элементов — 8 секунд против 2 по правилам правильного теста. В файле для чтения таких строк 400 000. Как мне ускорить чтение?
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
using namespace std;
# define INF 0x3f3f3f3f
typedef pair<int, int> iPair;
class Graph
{
int V;
list< pair<int, int> >* adj;
public:
Graph(int V);
void addEdge(int u, int v, int w);
void shortestPath(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<iPair>[V];
}
void Graph::addEdge(int u, int v, int w)
{
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
void Graph::shortestPath(int src)
{
priority_queue< iPair, vector <iPair>, greater<iPair> > pq;
vector<int> dist(V, INF);
pq.push(make_pair(0, src));
dist[src] = 0;
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
list< pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = (*i).first;
int weight = (*i).second;
if (dist[v] > dist[u] + weight)
{
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
ofstream file1("C:\Tests\123.txt");
for (int i = 0; i < V; ++i)
cout << dist[i] << " ";
file1.close();
}
int main()
{
ifstream file("C:\Tests\21");
int number_of_veretexes, edges;
file >> number_of_veretexes >> edges;
Graph g(number_of_veretexes);
int _first_, _second_, _third_;
for (int i = 0; i < edges; i++) {
file >> _first_ >> _second_ >> _third_;
g.addEdge( _first_ - 1, _second_ - 1, _third_);
}
g.shortestPath(0);
file.close();
}
3 ответа
Избегать using namespace std
Избегать using namespace std, это считается плохой практикой. Это позволяет сэкономить лишь немного времени на вводе текста, но вы можете столкнуться с проблемами, если имена локальных классов и переменных конфликтуют с именами, определенными в стандартной библиотеке.
Использовать INT_MAX вместо INF
Не надо #define INF к некоторому произвольному значению, просто установите его на максимально возможное значение int может иметь. Это уже определено как INT_MAX в <climits>.
Создать struct Edge
С помощью std::pair<int, int> это удобно, тем более что их можно сортировать, но у него есть некоторые недостатки. Просто взглянув на определение этого типа, неясно, является ли первый элемент номером узла, а второй — весом или наоборот. Фактически вы используете оба соглашения в своем коде: список смежности имеет номер вершины первой, тогда как очередь с приоритетом имеет номер вершины второй. Создайте правильный struct чтобы устранить двусмысленность и повысить безопасность типов. Кроме того, поскольку ребро является свойством графа, определите struct Edge внутри class Graph, вот так:
class Graph {
struct Edge {
int vertex;
int weight;
};
std::list<Edge>* adj;
...
};
Вместо звонка adj[u].push_back(std::make_pair(v, w)), теперь вы должны написать:
adj[u].push_back({v, w});
Для приоритетной очереди вы также хотите создать отдельный struct для элементов. Поскольку только Graph::shortestPath() использует это, вы можете определить это внутри этой функции. Чтобы его можно было сортировать, определите operator<() в этой структуре, вот так:
void Graph::shortestPath(int src) {
struct VertexDistance {
int vertex;
int distance;
bool operator<(const VertexDistance &other) {
if (distance != other.distance)
return distance > other.distance;
else
return vertex > other.vertex;
}
};
std::priority_queue<VertexDistance> pq;
...
}
Избегайте ручного выделения памяти
Немного странно видеть, что вы используете контейнеры STL, такие как std::list и std::vector и std::priority_queue, но затем используйте new выделить массив adj. Почему бы не использовать std::vector для этого тоже? Например, вот так:
std::vector<std::list<Edge>> adj;
Это позволяет избежать необходимости new, и исправляет утечку памяти, которая у вас есть, потому что вы никогда не вызываете delete. Он также позволяет удалить переменную-член V, поскольку вектор уже отслеживает свой размер.
Вы можете облегчить чтение, создав псевдоним для списка ребер:
using AdjacencyList = std::list<Edge>;
std::vector<AdjacencyList> adj;
Использовать std::vector вместо std::list
std::vector и std::list оба могут хранить список элементов, но имеют разные компромиссы в производительности, требованиях к памяти и других аспектах. В вашем коде вы всегда добавляете элементы только в конец списка смежности, вы никогда не вставляете или не удаляете элементы из середины. В этом случае std::vector — это гораздо более эффективная структура данных, поэтому я бы просто написал:
using AdjacencyList = std::vector<Edge>;
std::vector<AdjacencyList> adj;
Использовать на основе диапазона for петли
Если вы не можете использовать какие-либо функции из C ++ 11 или новее, я настоятельно рекомендую вам начать использовать на основе диапазона for-петли. Они экономят набор текста, делают код более читабельным и уменьшают вероятность ошибок. Например, при переборе списка смежности в Graph::shortestPath(), ты можешь написать:
for (auto &edge: adj[u]) {
int v = edge.vertex;
int weight = edge.weight;
...
}
То же самое касается печати содержимого dist:
for (auto &distance: dist)
file << distance << " ";
Проверить на наличие ошибок при чтении и записи файлов
Многие вещи могут пойти не так при чтении и записи в файлы: файлы могут не существовать, быть поврежденными, у вас может не быть разрешений на чтение и / или запись, диск может быть заполнен на полпути при записи файла и т. Д. Поэтому вы должны убедиться, что вы полностью прочитали и записали файлы без ошибок.
Вам не нужно проверять каждую операцию ввода-вывода; файловые объекты будут помнить, возникала ли в прошлом ошибка. Таким образом, самый простой способ получить правильную проверку ошибок — это сделать это после чтения или записи всего файла. Это можно сделать, проверив Биты состояния ввода / вывода. В вашем случае просто проверяю, что good() возвращается true должно быть достаточно, например, для входного файла:
int main() {
ifstream file("...");
...
if (!file.good()) {
std::cerr << "An error occured while reading the input!n";
return 1;
}
g.shortestPath(0);
}
И вот так для выходного файла:
void Graph::shortestPath(int src) {
...
ofstream file("...");
...
file.close();
if (!file.good()) {
std::cerr << "An error occured while writing the output!n";
// TODO: ensure the error propagates to main, or call exit(1)
}
}
Важно позвонить close() сначала здесь, поскольку закрытие потока гарантирует, что его выходной буфер будет полностью очищен.
Когда вы обнаруживаете ошибку, важно, чтобы вы не продолжали использовать какие-либо неверные данные, которые вы могли получить, чтобы вы распечатали полезное сообщение об ошибке для std::cerr, и это если ваша программа возвращает ненулевой код выхода. Последнее важно в том случае, если ваша программа вызывается, например, из сценария, поэтому сценарий не будет продолжать работу с поддельными данными.
Переместить вывод файла из Graph::shortestPath()
Следуя принципу разделение проблем, вам следует удалить функцию вывода файлов из shortestPath(). Вместо этого сделайте эту функцию return кратчайший путь, и позвольте вызывающему абоненту записать его на диск. Это можно просто сделать так:
std::vector<int> Graph::shortestPath(int src)
{
...
while (...) {
...
}
return dist;
}
int main()
{
...
auto path = g.shortestPath(0);
std::ofstream file1(...);
for (auto &distance: path)
file1 << distance < " ";
file1.close();
if (!file1.good()) {
std::cerr << "An error occured while writing the output!n";
return 1;
}
}
Вы также можете рассмотреть возможность переноса ввода и вывода файла в отдельные функции, чтобы main() упрощается до примерно такого:
int main() {
auto graph = readGraph("C:\Tests\21");
auto path = graph.shortestPath(0);
writePath(path, "C:\Tests123.txt");
}
Все @G. — сказал Слипен.
Небольшое изменение в алгоритме.
Ваш исходный алгоритм был Dijkstra нравиться. Но разница означала, что вы потенциально расширили намного больше узлов, чем вам нужно. Это будет означать, что вы добавили больше элементов в приоритетную очередь, что требует времени и места и может быть недостаточно эффективным.
Ниже представлена более традиционная реализация Дейкстры.
vector<int> Graph::shortestPath(int src)
{
priority_queue< iPair, vector <iPair>, greater<iPair> > pq;
vector<int> dist(V, INT_MAX);
pq.push(make_pair(0, src));
while (!pq.empty())
{
int u = pq.top().second;
int d2u = pq.top().first;
pq.pop();
// You were missing this first test.
// And the following update to `dist[u]`
if (dist[u] != INT_MAX) {
// Already done this node we can ignore.
continue;
}
// First time we made it to this node.
// Record the distance (it must be the shortest as pq is priority based).
dist[u] = d2u;
// Loop over all edges from this node.
for (auto const& item: adj[u])
{
int v = item.first;
int weight = item.second;
// Optimization. Don't need this as pq is priority based.
// May or may not help.
if (dist[v] != INT_MAX)
{
pq.push({d2u + weight, v});
}
}
}
return dist;
}
Я подозреваю что push_back намного дороже, чем push. (Или, может быть, наоборот?) (Я предполагаю, что это включает в себя массив (вектор), и дешевле прикрепить его к концу, чем сдвинуть все содержимое, чтобы освободить место в начале.)
Итак, вместо того, чтобы делать push_back, делать push. Затем, когда закончите, переверните содержимое вектора.