|
|
/*
|
|
|
* tree06.cpp
|
|
|
*
|
|
|
* Created on: Apr 28, 2024
|
|
|
* Author: 28032
|
|
|
*/
|
|
|
|
|
|
//#include <iostream>
|
|
|
//#include <fstream>
|
|
|
//#include <vector>
|
|
|
//#include <algorithm>
|
|
|
//#include <chrono>
|
|
|
//
|
|
|
//using namespace std;
|
|
|
//
|
|
|
//class Trie
|
|
|
//{
|
|
|
//public:
|
|
|
// Trie()
|
|
|
// {
|
|
|
// for(int i = 0;i < 26;i++)
|
|
|
// children[i] = NULL;
|
|
|
// wordcount = 0;
|
|
|
// }
|
|
|
// Trie(int cnt)
|
|
|
// {
|
|
|
// for(int i = 0;i < 26;i++)
|
|
|
// children[i] = NULL;
|
|
|
// wordcount = cnt;
|
|
|
// }
|
|
|
// Trie* children[26];
|
|
|
// int wordcount;
|
|
|
//}*trie;
|
|
|
//
|
|
|
//Trie* addWord(Trie* last,int site)
|
|
|
//{
|
|
|
// if(last->children[site])
|
|
|
// return last->children[site];
|
|
|
// else
|
|
|
// return last->children[site] = new Trie();
|
|
|
//}
|
|
|
//
|
|
|
//vector<pair<string,int> > ranking;
|
|
|
//
|
|
|
//void showWord(Trie* root,string w)
|
|
|
//{
|
|
|
// if(root->wordcount)
|
|
|
// ranking.push_back(make_pair(w,root->wordcount));
|
|
|
// for(int i = 0;i < 26;i++)
|
|
|
// {
|
|
|
// if(root->children[i])
|
|
|
// {
|
|
|
// showWord(root->children[i],w+(char)('a'+i));
|
|
|
// }
|
|
|
// }
|
|
|
//}
|
|
|
//
|
|
|
//bool cmp(pair<string,int>& a,pair<string,int>& b)
|
|
|
//{
|
|
|
// if(a.second != b.second)
|
|
|
// return a.second > b.second;
|
|
|
//
|
|
|
// return a.first < b.first;
|
|
|
//}
|
|
|
//int main()
|
|
|
//{
|
|
|
// ifstream fp("in.txt",ios::in);
|
|
|
// trie = new Trie;
|
|
|
//
|
|
|
// string line;
|
|
|
// auto begin = std::chrono::high_resolution_clock::now();
|
|
|
// while(getline(fp,line))
|
|
|
// {
|
|
|
// int l = line.length();
|
|
|
// Trie* current = trie;
|
|
|
// for(int i = 0;i < l;i++)
|
|
|
// {
|
|
|
// if('a'<=line[i] && line[i]<='z')
|
|
|
// {
|
|
|
// current = addWord(current,line[i]-'a');
|
|
|
// }
|
|
|
// else if('A'<=line[i] && line[i]<='Z')
|
|
|
// {
|
|
|
// current = addWord(current,line[i]-'A');
|
|
|
// }
|
|
|
// else
|
|
|
// {
|
|
|
// if(current!=trie)
|
|
|
// current->wordcount++;
|
|
|
// current = trie;
|
|
|
// }
|
|
|
// }
|
|
|
// }
|
|
|
//
|
|
|
// showWord(trie,"");
|
|
|
//
|
|
|
// sort(ranking.begin(),ranking.end(),cmp);
|
|
|
//
|
|
|
// if(ranking.size()<100)
|
|
|
// for(auto it:ranking)
|
|
|
// cout<<it.first<<" "<<it.second<<endl;
|
|
|
// else
|
|
|
// for(auto it = ranking.begin();it!=ranking.begin()+100;it++)
|
|
|
// cout<<it->first<<" "<<it->second<<endl;
|
|
|
//
|
|
|
// auto end = std::chrono::high_resolution_clock::now();
|
|
|
// auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
|
|
|
// printf("Time measured: %.5f seconds.\n", elapsed.count() * 1e-9);
|
|
|
// return 0;
|
|
|
//}
|
|
|
|
|
|
//#include <iostream>
|
|
|
//#include <fstream>
|
|
|
//#include <vector>
|
|
|
//#include <algorithm>
|
|
|
//#include <chrono>
|
|
|
//
|
|
|
//using namespace std;
|
|
|
//
|
|
|
//class Trie
|
|
|
//{
|
|
|
//public:
|
|
|
// Trie()
|
|
|
// {
|
|
|
// children = NULL;
|
|
|
// sibling =NULL;
|
|
|
// wordsite = 28;
|
|
|
// wordcount = 0;
|
|
|
// }
|
|
|
// Trie(int site,int cnt)
|
|
|
// {
|
|
|
// children = NULL;
|
|
|
// sibling = NULL;
|
|
|
// wordsite = site;
|
|
|
// wordcount = cnt;
|
|
|
// }
|
|
|
// Trie* children;
|
|
|
// Trie* sibling;
|
|
|
// int wordsite;
|
|
|
// int wordcount;
|
|
|
//}*trie;
|
|
|
//
|
|
|
//Trie* addWord(Trie* last,int site)
|
|
|
//{
|
|
|
// Trie* current = last->children;
|
|
|
//
|
|
|
// if(current)
|
|
|
// {
|
|
|
// while(current)
|
|
|
// {
|
|
|
// if(current->wordsite == site)
|
|
|
// return current;
|
|
|
// current = current->sibling;
|
|
|
// }
|
|
|
// current = last->children;
|
|
|
// while(current->sibling)
|
|
|
// current = current->sibling;
|
|
|
// return current->sibling = new Trie(site,0);
|
|
|
// }
|
|
|
// else
|
|
|
// {
|
|
|
// return last->children = new Trie(site,0);
|
|
|
// }
|
|
|
//}
|
|
|
//
|
|
|
//vector<pair<string,int> > ranking;
|
|
|
//
|
|
|
//void showWord(Trie* root,string w)
|
|
|
//{
|
|
|
// if(root->wordcount)
|
|
|
// ranking.push_back(make_pair(w,root->wordcount));
|
|
|
//
|
|
|
// for(Trie* i = root->children;i !=NULL;i = i->sibling)
|
|
|
// {
|
|
|
// showWord(i,w+(char)('a'+i->wordsite));
|
|
|
// }
|
|
|
//}
|
|
|
//
|
|
|
//bool cmp(pair<string,int>& a,pair<string,int>& b)
|
|
|
//{
|
|
|
// if(a.second != b.second)
|
|
|
// return a.second > b.second;
|
|
|
//
|
|
|
// return a.first < b.first;
|
|
|
//}
|
|
|
//int main()
|
|
|
//{
|
|
|
// ifstream fp("in.txt",ios::in);
|
|
|
// trie = new Trie;
|
|
|
//
|
|
|
// string line;
|
|
|
// auto begin = std::chrono::high_resolution_clock::now();
|
|
|
// while(getline(fp,line))
|
|
|
// {
|
|
|
// int l = line.length();
|
|
|
// Trie* current = trie;
|
|
|
// for(int i = 0;i < l;i++)
|
|
|
// {
|
|
|
// if('a'<=line[i] && line[i]<='z')
|
|
|
// {
|
|
|
// current = addWord(current,line[i]-'a');
|
|
|
// }
|
|
|
// else if('A'<=line[i] && line[i]<='Z')
|
|
|
// {
|
|
|
// current = addWord(current,line[i]-'A');
|
|
|
// }
|
|
|
// else
|
|
|
// {
|
|
|
// if(current!=trie)
|
|
|
// current->wordcount++;
|
|
|
// current = trie;
|
|
|
// }
|
|
|
// }
|
|
|
// }
|
|
|
//
|
|
|
// showWord(trie,"");
|
|
|
//
|
|
|
// sort(ranking.begin(),ranking.end(),cmp);
|
|
|
//
|
|
|
// if(ranking.size()<100)
|
|
|
// for(auto it:ranking)
|
|
|
// cout<<it.first<<" "<<it.second<<endl;
|
|
|
// else
|
|
|
// for(auto it = ranking.begin();it!=ranking.begin()+100;it++)
|
|
|
// cout<<it->first<<" "<<it->second<<endl;
|
|
|
//
|
|
|
// auto end = std::chrono::high_resolution_clock::now();
|
|
|
// auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
|
|
|
// printf("Time measured: %.5f seconds.\n", elapsed.count() * 1e-9);
|
|
|
// return 0;
|
|
|
//}
|
|
|
|
|
|
//#include <iostream>
|
|
|
//#include <fstream>
|
|
|
//#include <vector>
|
|
|
//#include <algorithm>
|
|
|
//#include <chrono>
|
|
|
//#include <thread>
|
|
|
//#include <mutex>
|
|
|
//
|
|
|
//using namespace std;
|
|
|
//
|
|
|
//mutex mtx;
|
|
|
//
|
|
|
//class Trie
|
|
|
//{
|
|
|
//public:
|
|
|
// Trie()
|
|
|
// {
|
|
|
// children = NULL;
|
|
|
// sibling =NULL;
|
|
|
// wordsite = 28;
|
|
|
// wordcount = 0;
|
|
|
// }
|
|
|
// Trie(int site,int cnt)
|
|
|
// {
|
|
|
// children = NULL;
|
|
|
// sibling = NULL;
|
|
|
// wordsite = site;
|
|
|
// wordcount = cnt;
|
|
|
// }
|
|
|
// Trie* children;
|
|
|
// Trie* sibling;
|
|
|
// int wordsite;
|
|
|
// int wordcount;
|
|
|
//}*trie;
|
|
|
//
|
|
|
//Trie* addWord(Trie* last,int site)
|
|
|
//{
|
|
|
// Trie* current = last->children;
|
|
|
//
|
|
|
// if(current)
|
|
|
// {
|
|
|
// while(current)
|
|
|
// {
|
|
|
// if(current->wordsite == site)
|
|
|
// return current;
|
|
|
// current = current->sibling;
|
|
|
// }
|
|
|
// current = last->children;
|
|
|
// while(current->sibling)
|
|
|
// current = current->sibling;
|
|
|
// return current->sibling = new Trie(site,0);
|
|
|
// }
|
|
|
// else
|
|
|
// {
|
|
|
// return last->children = new Trie(site,0);
|
|
|
// }
|
|
|
//}
|
|
|
//
|
|
|
//vector<pair<string,int> > ranking;
|
|
|
//
|
|
|
//void showWord(Trie* root,string w)
|
|
|
//{
|
|
|
// if(root->wordcount)
|
|
|
// ranking.push_back(make_pair(w,root->wordcount));
|
|
|
//
|
|
|
// for(Trie* i = root->children;i !=NULL;i = i->sibling)
|
|
|
// {
|
|
|
// showWord(i,w+(char)('a'+i->wordsite));
|
|
|
// }
|
|
|
//}
|
|
|
//
|
|
|
//bool cmp(pair<string,int>& a,pair<string,int>& b)
|
|
|
//{
|
|
|
// if(a.second != b.second)
|
|
|
// return a.second > b.second;
|
|
|
//
|
|
|
// return a.first < b.first;
|
|
|
//}
|
|
|
//
|
|
|
//void buildTrie(void)
|
|
|
//{
|
|
|
// ifstream fp("in.txt",ios::in);
|
|
|
// trie = new Trie;
|
|
|
//
|
|
|
// string line;
|
|
|
// while(1)
|
|
|
// {
|
|
|
// lock_guard<mutex> lg(mtx);
|
|
|
// getline(fp,line);
|
|
|
// if(getline(fp,line))
|
|
|
// break;
|
|
|
// int l = line.length();
|
|
|
// Trie* current = trie;
|
|
|
// for(int i = 0;i < l;i++)
|
|
|
// {
|
|
|
// if('a'<=line[i] && line[i]<='z')
|
|
|
// {
|
|
|
// current = addWord(current,line[i]-'a');
|
|
|
// }
|
|
|
// else if('A'<=line[i] && line[i]<='Z')
|
|
|
// {
|
|
|
// current = addWord(current,line[i]-'A');
|
|
|
// }
|
|
|
// else
|
|
|
// {
|
|
|
// if(current!=trie)
|
|
|
// current->wordcount++;
|
|
|
// current = trie;
|
|
|
// }
|
|
|
// }
|
|
|
// }
|
|
|
//}
|
|
|
//int main()
|
|
|
//{
|
|
|
// auto begin = std::chrono::high_resolution_clock::now();
|
|
|
//
|
|
|
// thread t1(buildTrie);
|
|
|
// thread t2(buildTrie);
|
|
|
// thread t3(buildTrie);
|
|
|
// thread t4(buildTrie);
|
|
|
//
|
|
|
// t1.join();
|
|
|
// t2.join();
|
|
|
// t3.join();
|
|
|
// t4.join();
|
|
|
//
|
|
|
// showWord(trie,"");
|
|
|
//
|
|
|
// sort(ranking.begin(),ranking.end(),cmp);
|
|
|
//
|
|
|
// if(ranking.size()<100)
|
|
|
// for(auto it:ranking)
|
|
|
// cout<<it.first<<" "<<it.second<<endl;
|
|
|
// else
|
|
|
// for(auto it = ranking.begin();it!=ranking.begin()+100;it++)
|
|
|
// cout<<it->first<<" "<<it->second<<endl;
|
|
|
//
|
|
|
// auto end = std::chrono::high_resolution_clock::now();
|
|
|
// auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
|
|
|
// printf("Time measured: %.5f seconds.\n", elapsed.count() * 1e-9);
|
|
|
// return 0;
|
|
|
//}
|
|
|
//
|
|
|
//
|
|
|
//
|
|
|
|
|
|
//#include <iostream>
|
|
|
//#include <fstream>
|
|
|
//#include <vector>
|
|
|
//#include <algorithm>
|
|
|
//#include <chrono>
|
|
|
//#include <thread>
|
|
|
//#include <mutex>
|
|
|
//
|
|
|
//using namespace std;
|
|
|
//
|
|
|
//// ... （Trie类的定义保持不变）
|
|
|
//
|
|
|
//class Trie
|
|
|
// {
|
|
|
// public:
|
|
|
// Trie()
|
|
|
// {
|
|
|
// children = NULL;
|
|
|
// sibling =NULL;
|
|
|
// wordsite = 28;
|
|
|
// wordcount = 0;
|
|
|
// }
|
|
|
// Trie(int site,int cnt)
|
|
|
// {
|
|
|
// children = NULL;
|
|
|
// sibling = NULL;
|
|
|
// wordsite = site;
|
|
|
// wordcount = cnt;
|
|
|
// }
|
|
|
// Trie* children;
|
|
|
// Trie* sibling;
|
|
|
// int wordsite;
|
|
|
// int wordcount;
|
|
|
// }*trie;
|
|
|
//mutex trieMutex;
|
|
|
//
|
|
|
//void processLine(Trie* root, const string& line, int offset)
|
|
|
//{
|
|
|
// int l = line.length();
|
|
|
// Trie* current = root;
|
|
|
// for (int i = 0; i < l; i++)
|
|
|
// {
|
|
|
// char ch = line[i];
|
|
|
// int site;
|
|
|
// if ('a' <= ch && ch <= 'z')
|
|
|
// {
|
|
|
// site = ch - 'a';
|
|
|
// }
|
|
|
// else if ('A' <= ch && ch <= 'Z')
|
|
|
// {
|
|
|
// site = ch - 'A';
|
|
|
// }
|
|
|
// else
|
|
|
// {
|
|
|
// lock_guard<mutex> guard(trieMutex); // 锁定以保护Trie树的访问
|
|
|
// if (current != root)
|
|
|
// current->wordcount++;
|
|
|
// current = root;
|
|
|
// continue;
|
|
|
// }
|
|
|
//
|
|
|
// // 锁定以保护Trie树的访问
|
|
|
// lock_guard<mutex> guard(trieMutex);
|
|
|
// current = addWord(current, site);
|
|
|
// }
|
|
|
//}
|
|
|
//
|
|
|
//void showWordThreadSafe(Trie* root, string w, vector<pair<string, int>>& localRanking, mutex& rankingMutex)
|
|
|
//{
|
|
|
// // ... （showWord函数的逻辑保持不变，但需要锁定ranking向量）
|
|
|
//
|
|
|
// if(root->wordcount)
|
|
|
// ranking.push_back(make_pair(w,root->wordcount));
|
|
|
// lock_guard<mutex> guard(rankingMutex);
|
|
|
// for (auto& p : localRanking)
|
|
|
// {
|
|
|
// ranking.push_back(p);
|
|
|
// }
|
|
|
//}
|
|
|
//
|
|
|
//int main()
|
|
|
//{
|
|
|
// // ... （trie初始化代码保持不变）
|
|
|
//
|
|
|
// ifstream fp("in.txt", ios::in);
|
|
|
// vector<thread> threads;
|
|
|
// vector<pair<string, int>> perThreadRanking;
|
|
|
// mutex rankingMutex;
|
|
|
//
|
|
|
// int numThreads = thread::hardware_concurrency(); // 获取硬件支持的线程数
|
|
|
// int linesPerThread = fp.lines() / numThreads; // 假设我们可以这样获取行数
|
|
|
//
|
|
|
// for (int i = 0; i < numThreads; ++i)
|
|
|
// {
|
|
|
// threads.emplace_back([=, &perThreadRanking]() {
|
|
|
// string line;
|
|
|
// int lineCount = 0;
|
|
|
// while (getline(fp, line) && lineCount < linesPerThread)
|
|
|
// {
|
|
|
// processLine(trie, line, i * linesPerThread + lineCount);
|
|
|
// lineCount++;
|
|
|
// }
|
|
|
// showWordThreadSafe(trie, "", perThreadRanking, rankingMutex);
|
|
|
// });
|
|
|
// }
|
|
|
//
|
|
|
// for_each(threads.begin(), threads.end(), mem_fn(&thread::join));
|
|
|
//
|
|
|
// // ... （排名和输出代码保持不变）
|
|
|
//
|
|
|
// return 0;
|
|
|
//}
|
