Databases
StackOverflow2013
Postsdbo
POOptimizing an algorithm using map::count
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POOptimizing an algorithm using map::count
    text
    copied!<p>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.</p> <pre><code>int coll = 0; map&lt;long, bool&gt; mymap; #pragma omp parallel for for (int i = 0; i &lt; 256; i++) for (int j = 0; j &lt; 256; j++) for (int k = 0; k &lt; 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 &lt;&lt; "Collision at " &lt;&lt; i &lt;&lt; " " &lt;&lt; j &lt;&lt; " " &lt;&lt; k &lt;&lt; endl; } else { #pragma omp critical mymap[myhash] = true; } } cout &lt;&lt; "Number of collisions: " &lt;&lt; coll &lt;&lt; endl; cout &lt;&lt; "Map size: " &lt;&lt; mymap.size() &lt;&lt; endl; </code></pre> <p>After much trial and error, here is the best version I could produce, generating 4294967296 keys in 82.5 seconds using 1GB of RAM.</p> <pre><code>#include &lt;iostream&gt; #include &lt;string&gt; #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;signal.h&gt; #include &lt;sys/time.h&gt; #include &lt;iomanip&gt; #include &lt;omp.h&gt; #include &lt;vector&gt; #include &lt;fstream&gt; #include &lt;ios&gt; #include &lt;unistd.h&gt; using namespace std; class Timer { private: timeval startTime; public: void start() { gettimeofday(&amp;startTime, NULL); } double stop() { timeval endTime; long seconds, useconds; double duration; gettimeofday(&amp;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 &lt;&lt; setprecision(10) &lt;&lt; fixed &lt;&lt; duration &lt;&lt; " seconds" &lt;&lt; endl; } }; static inline long hash(const char* str) { return (*(long*)str)&gt;&gt; 0; } int coll; vector&lt;bool&gt; test; void process_mem_usage(double&amp; vm_usage, double&amp; 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 &gt;&gt; pid &gt;&gt; comm &gt;&gt; state &gt;&gt; ppid &gt;&gt; pgrp &gt;&gt; session &gt;&gt; tty_nr &gt;&gt; tpgid &gt;&gt; flags &gt;&gt; minflt &gt;&gt; cminflt &gt;&gt; majflt &gt;&gt; cmajflt &gt;&gt; utime &gt;&gt; stime &gt;&gt; cutime &gt;&gt; cstime &gt;&gt; priority &gt;&gt; nice &gt;&gt; O &gt;&gt; itrealvalue &gt;&gt; starttime &gt;&gt; vsize &gt;&gt; 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 &lt;&lt; "Number of collisions: " &lt;&lt; coll &lt;&lt; endl; //cout &lt;&lt; test.size() &lt;&lt; endl; double vm, rss; process_mem_usage(vm, rss); vm /= 1024.0; rss /= 1024.0; cout &lt;&lt; "VM: " &lt;&lt; vm &lt;&lt; "MB" &lt;&lt; endl; timer.printTime(timer.stop()); exit(1); } int main() { signal(SIGINT, signal_handlerkill); timer = Timer(); timer.start(); coll = 0; for (long i = 0; i &lt; 4294967296+1; i++) { test.push_back(0); //Set up the vector } #pragma omp parallel for for (int i = 0; i &lt; 256; i++) for (int j = 0; j &lt; 256; j++) for (int k = 0; k &lt; 256; k++) for (int l = 0; l &lt; 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 &lt;&lt; "Number of collisions: " &lt;&lt; coll &lt;&lt; endl; double vm, rss; process_mem_usage(vm, rss); vm /= 1024.0; rss /= 1024.0; cout &lt;&lt; "VM: " &lt;&lt; vm &lt;&lt; "MB" &lt;&lt; endl; timer.printTime(timer.stop()); return 0; } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload