Резюме
Учитывая набор ребер (от 3 до 1 000 000), эффективно собирайте замкнутые петли (я называю их кругами для простоты).Я выполняю это как часть более крупного проекта Python, поэтому я ожидаю, что лучшее решение будет написано на C ++ / CUDA с привязками Python (что я и пробовал).
Проблема
Соберите кольца, учитывая набор ребер (определяемых двумя индексами вершин), которые удовлетворяют следующему:
- нет блуждающих ребер (все ребра используются для создания окружностей),
- все кольца закрываются (например, если есть ребро 1-2, то есть ребро n-1, которое закроет его),
- ребра имеют неупорядоченные индексы (например, ребро можетбыть 1-2 или 2-1).
Мой общий подход
- выбрать край в конце списка и установить одну вершину в началенового кольца (
pStart) и другой вершины к следующей точке в цепочке (pEnd), добавив оба к новому списку колец, - поиск
pEnd в списке ребер, - как только ребро найдено, обновите
pEnd до вершины, которая не равна pEnd и добавьте это в список звонков, - повторяйте два вышеупомянутых шага до тех пор, пока
pStart==pEnd, - , если больше не останавливаются ребра, в противном случае повторите выше.
Моя реализация
В C ++ яреализована последовательная и параллельная версия.Я протестировал его, используя набор из 45 000 ребер, и получил следующие результаты:
- серийный (105 секунд)
- параллельный - CUDA Thrust (28 секунд)
Serial:
#include <algorithm>
#include <vector>
#include <string>
#include <boost/algorithm/string.hpp>
#include <fstream>
#include <iostream>
#include <chrono>
std::vector< std::vector<int> > rings_from_edges(std::vector<std::vector<int>> edges)
{
int pStart, pEnd;
std::vector<int> temp;
std::vector<std::vector<int>> rings;
temp = edges.back();
edges.pop_back();
pStart = temp[0];
pEnd = temp[1];
int p1, p2;
while(not edges.empty())
// Scan edges list until pEnd is found.
for(auto const& pts: edges)
{
p1 = pts[0];
p2 = pts[1];
// Check if the start of the edge corresponds with the end of the ring.
if(p1 == pEnd)
{
temp.push_back(p2);
pEnd = p2;
edges.erase(std::remove(edges.begin(), edges.end(), pts), edges.end());
// Check if the beginning of the ring is the same as the end of the newly appended edge.
if (p2 == pStart)
{
// Add the newly created ring to the rings list.
rings.push_back(temp);
temp.clear();
// If the edges list contains more edges, reset the starting and end points to search for a new ring.
if(not edges.empty())
{
temp = edges.back();
edges.pop_back();
pStart = temp[0];
pEnd = temp[1];
}
}
break;
}
// Check if the end of the edge corresponds with the end of the ring.
else if(p2 == pEnd)
{
temp.push_back(p1);
pEnd = p1;
edges.erase(std::remove(edges.begin(), edges.end(), pts), edges.end());
// Check if the beginning of the ring is the same as the end of the newly appended edge.
if (p1 == pStart)
{
// Add the newly created ring to the rings list.
rings.push_back(temp);
temp.clear();
// If the edges list contains more edges, reset the starting and end points to search for a new ring.
if(not edges.empty())
{
temp = edges.back();
edges.pop_back();
pStart = temp[0];
pEnd = temp[1];
}
}
break;
}
}
return rings;
}
int main() {
std::chrono::steady_clock::time_point t1 = std::chrono::steady_clock::now();
std::vector< std::vector<int> > vectIN, vectOUT;
std::string fileName = "PATH TO CSV FILE";
std::string delimeter = ",";
std::ifstream file(fileName);
std::string line = "";
while (getline(file, line))
{
std::vector<std::string> vec;
boost::algorithm::split(vec, line, boost::is_any_of(delimeter));
std::vector<int> vec2;
vec2.emplace_back(std::stoi(vec.data()[0]));
vec2.emplace_back(std::stoi(vec.data()[1]));
vectIN.push_back(vec2);
}
file.close();
std::chrono::steady_clock::time_point t2 = std::chrono::steady_clock::now();
vectOUT = rings_from_edges(vectIN);
std::chrono::steady_clock::time_point t3 = std::chrono::steady_clock::now();
for (auto const& ring:vectOUT)
{
for(auto const& pt:ring)
{
if(pt>=0)
std::cout << pt << " ";
}
std::cout << std::endl;
}
std::chrono::steady_clock::time_point t4 = std::chrono::steady_clock::now();
long t1_t2 = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
long t2_t3 = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();
long t3_t4 = std::chrono::duration_cast<std::chrono::milliseconds>(t4 - t3).count();
std::cout << "Load csv: " << t1_t2 << std::endl;
std::cout << "Ring assembly: " << t2_t3 << std::endl;
std::cout << "Output: " << t3_t4 << std::endl;
std::cout << "----------------- THAT'S ALL FOLKS!!! -----------------" << std::endl;
return 0;
}
CUDA Thrust версии выше:
#include <thrust/remove.h>
#include <thrust/device_vector.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/tuple.h>
#include <thrust/copy.h>
#include <thrust/sort.h>
#include <thrust/find.h>
#include <thrust/functional.h>
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/string.hpp>
#include <chrono>
#include <thrust/binary_search.h>
#include <thrust/uninitialized_copy.h>
#include <thrust/device_malloc.h>
#include <thrust/device_vector.h>
int main(){
std::chrono::steady_clock::time_point t1 = std::chrono::steady_clock::now();
std::string fileName = "PATH TO CSV HERE";
std::string delimeter = ",";
std::ifstream file(fileName);
std::vector<std::vector<int>> vectIN;
std::string line = "";
while (getline(file, line))
{
std::vector<std::string> vec;
boost::algorithm::split(vec, line, boost::is_any_of(delimeter));
std::vector<int> vec2;
vec2.emplace_back(std::stoi(vec.data()[0]));
vec2.emplace_back(std::stoi(vec.data()[1]));
vectIN.push_back(vec2);
}
file.close();
std::chrono::steady_clock::time_point t2 = std::chrono::steady_clock::now();
std::vector<int> h_edge1, h_edge2;
h_edge1.reserve(vectIN.size());
h_edge2.reserve(vectIN.size());
for(auto const& pts: vectIN)
{
h_edge1.emplace_back(pts[0]);
h_edge2.emplace_back(pts[1]);
}
std::chrono::steady_clock::time_point t3 = std::chrono::steady_clock::now();
thrust::device_vector<int> d_pStart(1);
thrust::device_vector<int> d_pEnd(1);
thrust::host_vector<int> h_rings;
thrust::device_vector<int> d_rings;
// Initialize edge vectors / pStart / pEnd / while minimizing copying with CudaMalloc
thrust::device_vector<int> d_edge1(vectIN.size());
thrust::device_vector<int> d_edge2(vectIN.size());
thrust::copy(thrust::make_zip_iterator(thrust::make_tuple(h_edge1.begin(), h_edge2.begin())),
thrust::make_zip_iterator(thrust::make_tuple(h_edge1.end(), h_edge2.end())),
thrust::make_zip_iterator(thrust::make_tuple(d_edge1.begin(), d_edge2.begin())));
// Arrange edges with edge1 as key and edge2 as value
thrust::sort_by_key(d_edge1.begin(), d_edge1.end(), d_edge2.begin());
d_rings.push_back(d_edge1.back());
d_rings.push_back(d_edge2.back());
d_edge1.pop_back();
d_edge2.pop_back();
d_pStart[0] = d_rings[0];
d_pEnd[0] = d_rings[1];
thrust::device_vector<int> element(1), p1(1), p2(1);
while(not d_edge1.empty())
{
element.clear();
int temp = d_pEnd[0];
auto iter1 = thrust::equal_range(thrust::device, d_edge1.begin(), d_edge1.end(), temp);
if(iter1.first != iter1.second)
{
element[0] = thrust::distance(d_edge1.begin(), iter1.first);
}
else
{
auto iter2 = thrust::find(thrust::device, d_edge2.begin(), d_edge2.end(), d_pEnd[0]);
element[0] = thrust::distance(d_edge2.begin(), iter2);
}
// EDGE START INDEX (P1) AND END INDEX (P2)
p1[0] = d_edge1[element[0]];
p2[0] = d_edge2[element[0]];
// ERASE THE EDGE FROM DEVICE LIST
d_edge1.erase(d_edge1.begin()+element[0]);
d_edge2.erase(d_edge2.begin()+element[0]);
if(p1[0] == d_pEnd[0])
{
d_pEnd[0] = p2[0];
if( d_pStart[0] == d_pEnd[0])
{
d_rings.push_back(-p2[0]);
if(not d_edge1.empty())
{
d_pStart[0] = d_edge1.back();
d_pEnd[0] = d_edge2.back();
d_rings.push_back(d_pStart[0]);
d_rings.push_back(d_pEnd[0]);
d_edge1.pop_back();
d_edge2.pop_back();
}
}
else
{
d_rings.push_back(p2[0]);
}
}
else if(p2[0] == d_pEnd[0])
{
d_pEnd[0] = p1[0];
if(d_pStart[0] == d_pEnd[0])
{
d_rings.push_back(-p1[0]);
if(not d_edge1.empty())
{
d_pStart[0] = d_edge1.back();
d_pEnd[0] = d_edge2.back();
d_rings.push_back(d_pStart[0]);
d_rings.push_back(d_pEnd[0]);
d_edge1.pop_back();
d_edge2.pop_back();
}
}
else
{
d_rings.push_back(p1[0]);
}
}
}
std::chrono::steady_clock::time_point t4 = std::chrono::steady_clock::now();
// Copy rings to host and print them.
h_rings = d_rings;
for(auto const& pt:h_rings)
{
if(pt>=0)
std::cout << pt << " ";
else
std::cout << -pt << std::endl;
}
std::cout << std::endl;
long t1_t2 = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
long t2_t3 = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();
long t3_t4 = std::chrono::duration_cast<std::chrono::milliseconds>(t4 - t3).count();
std::cout << "Load csv: " << t1_t2 << std::endl;
std::cout << "Create vector: " << t2_t3 << std::endl;
std::cout << "Ring assembly: " << t3_t4 << std::endl;
std::cout << "----------------- THAT'S ALL FOLKS!!! -----------------" << std::endl;
return 0;
}
Other
Я реализовал нечто похожее на код CUDA выше, но организовал данные в сегментытак что поиск должен быть сделан только на ограниченном количестве данных.К сожалению, я пока не получил его полноценную работу.
Недавно я изучал графические библиотеки, чтобы посмотреть, смогу ли я сделать это таким образом, но мне не удалось заставить этот способ работать.пока тоже.Я знаю, что в инструментарии CUDA есть один, а также буст.
Заключительные замечания
Я хотел бы запустить его как минимум менее чем за 10 секунд, но в идеале я бы хотел, чтобысекунду до миллиона ребер.Я не знаю, является ли это реалистичным, но я надеюсь, что ускорение с помощью Cuda могло бы достичь этого или найти другой алгоритм все вместе.Я пытаюсь понять, может ли кто-нибудь помочь мне в этом.