我正在處理一個應該準確地對此類代碼的時間復雜度進行基準測驗的練習。
我正在處理的資料由這樣的字串對組成hbFvMF,PZLmRb，每個字串在資料集中出現兩次，一次在位置1上，一次在位置2上。所以第一個字串將指向zvEcqe,hbFvMF例如并且串列繼續......
50k 對的示例資料集
我已經能夠生成代碼，將這些資料集排序到 50k 對時沒有太大問題，這大約需要 4-5 分鐘。10k 在幾秒鐘內得到排序。
問題是我的代碼應該處理多達 500 萬對的資料集。所以我想看看我還能做些什么。我將發布我的兩個最佳嘗試，最初的一個帶有向量，我認為我可以通過替換來升級它vector，unsorted_map因為搜索時的時間復雜度更高，但令我驚訝的是，當我測驗它時，兩個容器之間幾乎沒有區別。我不確定我解決問題的方法或我選擇的容器是否會導致分揀時間過長......
嘗試使用向量：
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <map>
#include <unordered_map>
#include <stdio.h>
#include <vector>
#include <iterator>
#include <utility>
#include <functional>
#include <algorithm>
using namespace std;
template<typename T>
void search_bricks_backwards(string resume, vector<T>& vec, vector<string>& vec2) {
int index = 0;
int temp_index = 0;
while (true) {
if (index == vec.size()) {
vec2.insert(vec2.begin(), vec[temp_index].first);
cout << "end of backward search, exitting..." << endl;
break;
}
if (vec[index].second == resume) {
vec2.insert(vec2.begin(), resume);
resume = vec[index].first;
//vec.erase(vec.begin() index);
temp_index = index;
index = 0;
}
index ;
}
}
template<typename T>
void search_bricks(string start, vector<T>& vec, vector<string>& vec2) {
int index = 0;
int temp_index = 0;
while (true) {
//cout << "iteration " << index << endl;
if (index == vec.size()) {
vec2.push_back(vec[temp_index].second);
cout << "all forward bricks sorted" << endl;
break;
}
if (vec[index].first == start) {
vec2.push_back(vec[index].first);
start = vec[index].second;
//vec.erase(vec.begin() index);
temp_index = index;
index = 0;
}
index ;
}
search_bricks_backwards(vec[0].first, vec, vec2);
}
template<typename T>
void search_bricks_recursion(string start, vector<T>& vec, vector<string>& vec2) {
int index = 0;
for (const auto& pair : vec) {
//cout << "iteration " << index << endl;
if (pair.first == start) {
vec2.push_back(start);
cout << "found " << start << " and " << pair.first << endl;
search_bricks(pair.second, vec, vec2);
}
if (index 1 == vec.size()) {
search_bricks_backwards(start, vec, vec2);
}
index ;
}
}
template<typename T>
void printVectorElements(vector<T>& vec)
{
for (auto i = 0; i < vec.size(); i) {
cout << "(" << vec.at(i).first << ","
<< vec.at(i).second << ")" << " ";
}
cout << endl;
}
vector<string> split(string s, string delimiter) {
size_t pos_start = 0, pos_end, delim_len = delimiter.length();
string token;
vector<string> res;
while ((pos_end = s.find(delimiter, pos_start)) != string::npos) {
token = s.substr(pos_start, pos_end - pos_start);
pos_start = pos_end delim_len;
res.push_back(token);
}
res.push_back(s.substr(pos_start));
return res;
}
unordered_map<string, string> brick_to_map(string const& s)
{
unordered_map<string, string> m;
string key, val;
istringstream iss(s);
while (getline(getline(iss, key, ',') >> ws, val))
m[key] = val;
return m;
}
int main()
{
vector<pair<string, string>> bricks;
vector<string> sorted_bricks;
ifstream inFile;
inFile.open("input-pairs-50K.txt"); //open the input file
stringstream strStream;
strStream << inFile.rdbuf(); //read the file
string str = strStream.str(); //str holds the content of the file
//cout << str << endl;
istringstream iss(str);
for (string line; getline(iss, line); )
{
string delimiter = ",";
string s = line;
vector<string> v = split(s, delimiter);
string s1 = v.at(0);
string s2 = v.at(1);
bricks.push_back(make_pair(s1, s2));
}
search_bricks(bricks[0].second, bricks, sorted_bricks);
//display the results
for (auto i = sorted_bricks.begin(); i != sorted_bricks.end(); i)
cout << *i << " ";
}
嘗試unsorted map：
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <map>
#include <unordered_map>
#include <stdio.h>
#include <vector>
#include <iterator>
#include <utility>
#include <functional>
#include <algorithm>
using namespace std;
void search_bricks_backwards(string resume, unordered_map<string, string> brick_map, vector<string>& vec2) {
typedef unordered_map<string, string>::value_type map_value_type;
while (true) {
unordered_map<string, string>::const_iterator got = find_if(brick_map.begin(), brick_map.end(), [&resume](const map_value_type& vt)
{ return vt.second == resume; }
);
if (got == brick_map.end()) {
vec2.insert(vec2.begin(), resume);
cout << "end of backward search, exitting..." << endl;
break;
}
//cout << "iteration " << index << endl;
else if (got->second == resume) {
vec2.insert(vec2.begin(), resume);
resume = got->first;
}
}
}
void search_bricks(string start, unordered_map<string, string> brick_map, vector<string>& vec2) {
typedef unordered_map<string, string>::value_type map_value_type;
while (true) {
unordered_map<string, string>::const_iterator got = find_if(brick_map.begin(), brick_map.end(), [&start](const map_value_type& vt)
{ return vt.first == start; }
);
if (got == brick_map.end()) {
vec2.push_back(start);
cout << "all forward bricks sorted" << endl;
break;
}
else if (got->first == start) {
vec2.push_back(start);
//cout << "found " << start << " and " << vec[index].first << endl;
start = got->second;
}
}
auto it = brick_map.begin();
search_bricks_backwards(it->first, brick_map, vec2);
}
template<typename T>
void printVectorElements(vector<T>& vec)
{
for (auto i = 0; i < vec.size(); i) {
cout << "(" << vec.at(i).first << ","
<< vec.at(i).second << ")" << " ";
}
cout << endl;
}
vector<string> split(string s, string delimiter) {
size_t pos_start = 0, pos_end, delim_len = delimiter.length();
string token;
vector<string> res;
while ((pos_end = s.find(delimiter, pos_start)) != string::npos) {
token = s.substr(pos_start, pos_end - pos_start);
pos_start = pos_end delim_len;
res.push_back(token);
}
res.push_back(s.substr(pos_start));
return res;
}
int main()
{
unordered_map<string, string> bricks;
vector<string> sorted_bricks;
ifstream inFile;
inFile.open("input-pairs-50K.txt"); //open the input file
for (string line; getline(inFile, line); )
{
string delimiter = ",";
string s = line;
vector<string> v = split(s, delimiter);
string s1 = v.at(0);
string s2 = v.at(1);
bricks.insert(make_pair(s1, s2));
}
/*for (auto& x : bricks)
std::cout << x.first << "," << x.second << " ";*/
auto it = bricks.begin();
search_bricks(it->second, bricks, sorted_bricks);
// display results
for (auto i = sorted_bricks.begin(); i != sorted_bricks.end(); i)
cout << *i << " ";
}
我希望提高我的代碼的時間復雜度，以便能夠更有效地處理資料，如果有人能建議我的代碼或容器中需要改進的地方，我將非常感激。
uj5u.com熱心網友回復：
演算法中最大的殺手是那些序列掃描。地圖提供關鍵查找操作。他們的find成員是什么讓他們打勾（和閃耀）。如果你想發出這種尖叫，你需要使用鍵控來做到這一點。緊隨其后的是預先等待 a 的高昂費用std::vector，這可能會很快變得非常昂貴。
在我繼續之前，有一件事。我掃描了您提供的源測驗。資料中實際上有 49999 行，而不是 50000 行。經過一些試驗、錯誤、撓頭等，我發現了這一點：
EZkYGM在檔案中只出現一次，作為右側bWyUVV僅出現一次，作為左側。
我懷疑這些是排序串列的“終端”？結果似乎表明情況確實如此。但是，嘿，我很高興我終于明白了你在這個資料集背景關系中“排序”的意思（你只花了兩天時間就把它敲到我的腦海里，它終于點擊了）。
反正...
全方位的性能改進
在保持基本前提的同時從中剝離大量代碼，請考慮以下內容：
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <unordered_map>
#include <deque>
#include <algorithm>
#include <chrono>
void search_bricks_backwards
(
std::string resume,
std::unordered_map<std::string, std::string>& rbricks,
std::deque<std::string>& dst
)
{
while (true)
{
auto it = rbricks.find(resume);
dst.emplace_front(std::move(resume));
if (it == rbricks.end())
break;
resume = it->second;
rbricks.erase(it);
}
}
void search_bricks
(
std::unordered_map<std::string, std::string>& bricks,
std::unordered_map<std::string, std::string>& rbricks,
std::deque<std::string>& dst
)
{
// remember these
std::string start = bricks.begin()->second;
std::string resume = bricks.begin()->first;
while (true)
{
auto it = bricks.find(start);
dst.emplace_back(std::move(start));
if (it == bricks.end())
break;
start = it->second;
bricks.erase(it);
}
// same search, but different keyed map
search_bricks_backwards(resume, rbricks, dst);
}
int main()
{
using namespace std::chrono;
std::unordered_map<std::string, std::string> bricks, rbricks;
std::deque<std::string> sorted_bricks;
std::ifstream inFile("input-pairs-50K.txt");
if (inFile.is_open())
{
for (std::string line; std::getline(inFile, line);)
{
// make damn sure we get two keys
std::istringstream iss(line);
std::string s1, s2;
if (std::getline(iss, s1, ',') &&
std::getline(iss, s2) &&
!s1.empty() &&
!s2.empty())
{
bricks.emplace(std::make_pair(s1, s2));
rbricks.emplace(std::make_pair(s2, s1));
}
}
auto tp0 = high_resolution_clock::now();
search_bricks(bricks, rbricks, sorted_bricks);
auto tp1 = high_resolution_clock::now();
std::cout << duration_cast<milliseconds>(tp1-tp0).count() << "ms\n";
// display results
int n = 0;
for (auto i = sorted_bricks.begin(); i != sorted_bricks.end(); i)
std::cout << n << ". " << *i << '\n';
}
}
最顯著的區別：
用作
std::deque<std::string>排序結果。您為這些矢量展示位置付出了高昂的代價。你所有的向量操作要么在后面推進（對于保留向量來說還可以），要么在前面推進（向量中的可怕性能）。專門用于非常快速的std::deque前后插入和修剪。我們不是在做后者，而是在大力做前者。兩個映射，分別鍵控 s1==>s2 和 s2==>s1。有第三方容器可以為您執行此操作（通常參考的容器是boost::bimap）。然而，為此，考慮到密鑰大小，只存盤兩個映射很容易。
在適當的地方使用移動語意（雖然不多）
在搜索程序中，每個發現的鍵都會從剛剛搜索的地圖中洗掉。這可以確保我們在應該停止的時候停止，并且相當快地恢復記憶體占用。
適用時參考引數。這些容器在構建結果集時被有效地破壞了，但這沒關系（實際上保證在一端或另一端正確檢測終端）。
雙鍵使世界變得與眾不同。使用您的測驗資料集在一臺 4 歲的小型 macbook pro 筆記本電腦上進行發布構建會產生以下結果（您可以通過已知答案測驗來驗證）。
所有代碼均使用 -O2 優化構建，運行 Apple clang 版本 13.0.0 (clang-1300.0.29.30)
std::unordered_map
34ms
1. bWyUVV
2. mPBGRC
3. WfkvWy
4. vjWNHY
5. HudtyD
6. DhxjdV
7. kdWhGX
8. tIsDXh
9. eMVeMX
10. fVQoeG
... 49980 lines omitted ...
49990. YfBDnP
49991. sHKVrT
49992. ZzhoZV
49993. Dyunmj
49994. KCQbpj
49995. rbMSgD
49996. WKOksU
49997. qqMTnq
49998. llrqUI
49999. XYpBnk
50000. EZkYGM
盡管在我的測驗中存在高達 42 毫秒和低至 28 毫秒的例外值，但該時間數字相當一致。使用常規的相同線束std::map導致：
std::map
92ms
1. bWyUVV
2. mPBGRC
3. WfkvWy
4. vjWNHY
5. HudtyD
6. DhxjdV
7. kdWhGX
8. tIsDXh
9. eMVeMX
10. fVQoeG
... 49980 lines omitted ...
49990. YfBDnP
49991. sHKVrT
49992. ZzhoZV
49993. Dyunmj
49994. KCQbpj
49995. rbMSgD
49996. WKOksU
49997. qqMTnq
49998. llrqUI
49999. XYpBnk
50000. EZkYGM
因此，您肯定使用了具有無序鍵控的正確容器，您實際上并沒有使用鍵控，這使得容器基本上不比順序掃描好。這與您的評估相吻合，它確實不比矢量順序掃描解決方案好。無論如何，您基本上都是這樣做的。
我懷疑上面顯示的性能應該能夠運行您預期的 500 萬對，只要您可以將其全部保存在記憶體中（兩次，對此感到抱歉，但結果非常坦率地表明它物有所值）。
對記憶體更友好（至少一點點）
下面做同樣的事情，但沒有所有添加的輸出，并使用一個呼叫函式，地圖在飛行中轉置。這減輕了從一開始就需要兩張地圖。整體性能與上面的代碼比較；只是一個不同的，對記憶體更友好的實作。
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <sstream>
#include <deque>
#include <unordered_map>
#include <chrono>
using map_type = std::unordered_map<std::string, std::string>;
std::deque<std::string> sort_bricks( map_type& bricks )
{
std::deque<std::string> dst;
// remember these
std::string start = bricks.begin()->second;
std::string resume = bricks.begin()->first;
// process by append
while (true)
{
auto it = bricks.find(start);
dst.emplace_back(std::move(start));
if (it == bricks.end())
break;
start = std::move(it->second);
bricks.erase(it);
}
// invert the remaining map
{
map_type mres;
for (auto& pr : bricks)
mres.emplace(std::move(pr.second), pr.first);
std::swap(bricks, mres);
}
// process by prepend
while (true)
{
auto it = bricks.find(resume);
dst.emplace_front(std::move(resume));
if (it == bricks.end())
break;
resume = std::move(it->second);
bricks.erase(it);
}
return dst;
}
int main()
{
using namespace std::chrono;
std::ifstream inFile("input-pairs-50K.txt");
if (inFile.is_open())
{
map_type bricks;
for (std::string line; std::getline(inFile, line);)
{
std::istringstream iss(line);
std::string s1, s2;
if (std::getline(iss, s1, ',') &&
std::getline(iss, s2) &&
!s1.empty() &&
!s2.empty())
{
bricks.emplace(std::make_pair(s1, s2));
}
}
auto tp0 = high_resolution_clock::now();
auto sorted_bricks = sort_bricks(bricks);
auto tp1 = high_resolution_clock::now();
std::cout << "Size: " << sorted_bricks.size() << '\n';
std::cout << "Time: " << duration_cast<milliseconds>(tp1-tp0).count() << "ms\n";
}
}
uj5u.com熱心網友回復：
您可以使用 trie 資料結構，這是一篇解釋演算法的論文：https ://people.eng.unimelb.edu.au/jzobel/fulltext/acsc03sz.pdf
但是你必須從頭開始實作 trie，因為據我所知，c 中沒有默認的 trie 實作。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/431387.html
上一篇：文本匹配的啟發式排序