私は現在、キーをハッシュし、map::count を使用してその一意性をチェックするアルゴリズムを持っています。これをどのように最適化できますか? また、これがスレッド化されていることを忘れていました。
int coll = 0;
map<long, bool> mymap;
#pragma omp parallel for
for (int i = 0; i < 256; i++)
for (int j = 0; j < 256; j++)
for (int k = 0; k < 256; k++)
{
string temp;
temp = i;
temp += j;
temp += k;
temp += temp;
long myhash = hash(temp.c_str());
if (mymap.count(myhash))
{
#pragma omp atomic
coll++;
cout << "Collision at " << i << " " << j << " " << k << endl;
}
else
{
#pragma omp critical
mymap[myhash] = true;
}
}
cout << "Number of collisions: " << coll << endl;
cout << "Map size: " << mymap.size() << endl;
多くの試行錯誤の末、1GB の RAM を使用して 82.5 秒で 4294967296 個のキーを生成する、私が作成できる最良のバージョンがここにあります。
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <sys/time.h>
#include <iomanip>
#include <omp.h>
#include <vector>
#include <fstream>
#include <ios>
#include <unistd.h>
using namespace std;
class Timer
{
private:
timeval startTime;
public:
void start()
{
gettimeofday(&startTime, NULL);
}
double stop()
{
timeval endTime;
long seconds, useconds;
double duration;
gettimeofday(&endTime, NULL);
seconds = endTime.tv_sec - startTime.tv_sec;
useconds = endTime.tv_usec - startTime.tv_usec;
duration = seconds + useconds/1000000.0;
return duration;
}
static void printTime(double duration)
{
cout << setprecision(10) << fixed << duration << " seconds" << endl;
}
};
static inline long hash(const char* str)
{
return (*(long*)str)>> 0;
}
int coll;
vector<bool> test;
void process_mem_usage(double& vm_usage, double& resident_set)
{
using std::ios_base;
using std::ifstream;
using std::string;
vm_usage = 0.0;
resident_set = 0.0;
// 'file' stat seems to give the most reliable results
//
ifstream stat_stream("/proc/self/stat",ios_base::in);
// dummy vars for leading entries in stat that we don't care about
//
string pid, comm, state, ppid, pgrp, session, tty_nr;
string tpgid, flags, minflt, cminflt, majflt, cmajflt;
string utime, stime, cutime, cstime, priority, nice;
string O, itrealvalue, starttime;
// the two fields we want
//
unsigned long vsize;
long rss;
stat_stream >> pid >> comm >> state >> ppid >> pgrp >> session >> tty_nr
>> tpgid >> flags >> minflt >> cminflt >> majflt >> cmajflt
>> utime >> stime >> cutime >> cstime >> priority >> nice
>> O >> itrealvalue >> starttime >> vsize >> rss; // don't care about the rest
stat_stream.close();
long page_size_kb = sysconf(_SC_PAGE_SIZE) / 1024; // in case x86-64 is configured to use 2MB pages
vm_usage = vsize / 1024.0;
resident_set = rss * page_size_kb;
}
Timer timer;
void signal_handlerkill(int sig)
{
cout << "Number of collisions: " << coll << endl;
//cout << test.size() << endl;
double vm, rss;
process_mem_usage(vm, rss);
vm /= 1024.0;
rss /= 1024.0;
cout << "VM: " << vm << "MB" << endl;
timer.printTime(timer.stop());
exit(1);
}
int main()
{
signal(SIGINT, signal_handlerkill);
timer = Timer();
timer.start();
coll = 0;
for (long i = 0; i < 4294967296+1; i++)
{
test.push_back(0); //Set up the vector
}
#pragma omp parallel for
for (int i = 0; i < 256; i++)
for (int j = 0; j < 256; j++)
for (int k = 0; k < 256; k++)
for (int l = 0; l < 256; l++)
{
const char temp[4] = {i, j, k, l};
long myhash = (*(long*)temp);
if(test.at(myhash))
{
#pragma omp atomic
coll++;
}
else
{
test[myhash].flip();
}
}
cout << "Number of collisions: " << coll << endl;
double vm, rss;
process_mem_usage(vm, rss);
vm /= 1024.0;
rss /= 1024.0;
cout << "VM: " << vm << "MB" << endl;
timer.printTime(timer.stop());
return 0;
}