使用map :: count优化算法 [英] Optimizing an algorithm using map::count

问题描述

我目前有一个算法，它使用map :: count来检索一个关键字的唯一性。怎么可以优化？我也忘了提到这是线程。

  int coll = 0; 
 map< long，bool> MyMap中;对于（int i = 0; i <256; i ++）
 #pragma omp并行
（int j = 0; j <256; j ++）
 
 （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<<< 碰撞在< i< < j< < k < ENDL; 
} 
 else 
 {
 #pragma omp critical 
 mymap [myhash] = true; 
} 
} 
 
 cout<< 碰撞次数：< coll< ENDL; 
 cout<<< 地图大小：<< mymap.size（）<< ENDL; 
  

经过多次尝试和错误，这里是我可以制作的最佳版本，在82.5秒内生成4294967296个键使用1GB的RAM。

  #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> 
使用命名空间std; 
 
 class Timer 
 {
 private：
 timeval startTime; 
 
 public：
 
 void start（）
 {
 gettimeofday（& startTime，NULL）; 
} 
 
 double stop（）
 {
 timeval endTime; 
长秒，useconds; 
双持续时间; 
 
 gettimeofday（& endTime，NULL）; 
 
秒= endTime.tv_sec  -  startTime.tv_sec; 
 useconds = endTime.tv_usec  -  startTime.tv_usec; 
 
持续时间=秒+ useconds / 1000000.0; 
 
返回时间; 
} 
 
 static void printTime（double duration）
 {
 cout<<< setprecision（10）<固定的<持续时间<< 秒<< ENDL; 
} 
}; 
 
 static inline long hash（const char * str）
 {
 return（*（long *）str）>> 0; 
} 
 int coll; 
 vector< bool>测试; 
 
 void process_mem_usage（double& vm_usage，double& resident_set）
 {
 using std :: ios_base; 
使用std :: ifstream; 
使用std :: string; 
 
 vm_usage = 0.0; 
 resident_set = 0.0; 
 
 //'file'stat似乎给出最可靠的结果
 // 
 ifstream stat_stream（/ proc / self / stat，ios_base :: in）; 
 
 //对于stat中的主要条目，我们不关心
 // 
 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; 
 
 //我们要的两个字段
 // 
 unsigned long vsize; 
 long rss; 
 
 stat_stream>> pid>>通信>>状态>>> ppid>> pgrp>>会话>> tty_nr 
>> tpgid>>标志>> minflt>> cminflt>> majflt>> cmajflt 
>> utime>> stime>> cutime>> >>优先>>不错
>> O> itrealvalue>>开始时间>> vsize>> RSS; //不要在乎休息
 
 stat_stream.close（）; 
 
 long page_size_kb = sysconf（_SC_PAGE_SIZE）/ 1024; //如果x86-64配置为使用2MB页面
 vm_usage = vsize / 1024.0; 
 resident_set = rss * page_size_kb; 
} 
定时器定时器; 
 void signal_handlerkill（int sig）
 {
 cout<< 碰撞次数：< 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（）
 {
信号（SIGINT，signal_handlerkill）; 
 timer = Timer（）; 
 timer.start（）; 
 coll = 0; （long i = 0; i< 4294967296 + 1; i ++）
 $ b {
 test.push_back（0）; 
 
 //设置向量
} 
 
 #pragma omp并行为
 for（int i = 0; i< 256; i ++）
 for（int j （int k = 0; k <256; k ++）
（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<<< 碰撞次数：< 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; 
} 
  

解决方案

在空间方面可以使用 set 而不是映射，因为 bool 值是无用的。

另外，如果你使用C ++ 11， unordered_set 可能会给更好的表现。

另外，

  temp = 
 temp + = j; 
 temp + = k; 
 temp + = temp; 
  

可能比使用 stringstream 甚至是char数组。

I currently have an algorithm that hashes a key and checks for it's uniqueness using map::count. How could this be optimized? I also forgot to mention that this is threaded.

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;

After much trial and error, here is the best version I could produce, generating 4294967296 keys in 82.5 seconds using 1GB of RAM.

#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;
}

解决方案

In terms of space, you could use a set instead of a map, since the bool value is useless.

Also, if you're using C++11, an unordered_set will probably give better performance.

Also,

temp = i;
temp += j;
temp += k;
temp += temp;

probably has a bigger overhead than using a stringstream or even char arrays.

这篇关于使用map :: count优化算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！