Databases
StackOverflow2013
Postsdbo
POHow to make a fast dictionary that contains another dictionary?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to make a fast dictionary that contains another dictionary?
    primarykey
    data
    text
    <p>I have a <code>map&lt;size_t, set&lt;size_t&gt;&gt;</code>, which, for better performance, I'm actually representing as a lexicographically-sorted <code>vector&lt;pair&lt;size_t, vector&lt;size_t&gt;&gt;&gt;</code>.</p> <p>What I need is a <code>set&lt;T&gt;</code> with <em>fast</em> insertion times (removal doesn't matter), where <code>T</code> is the data type above, so that I can check for duplicates (my program runs until there are no more unique <code>T</code>'s being generated.).</p> <p>So far, switching from <code>set</code> to <code>unordered_set</code> has turned out to be quite beneficial (it makes my program run > 25% faster), but even now, inserting <code>T</code> still seems to be one of the main bottlenecks.</p> <p>The maximum number of integers in a given <code>T</code> is around ~1000, and each integer is also &lt;= ~1000, so the numbers are quite small (but there are thousands of these <code>T</code>'s being generated).</p> <p>What I have already tried:</p> <ul> <li><p>Using <code>unsigned short</code>. It actually decreases performance slightly.</p></li> <li><p>Using Google's <a href="https://code.google.com/p/cpp-btree/source/browse/btree_map.h" rel="nofollow"><code>btree::btree_map</code></a>.<br> It's actually much slower because I have to work around the iterator invalidation.<br> (I have to copy the keys, and I think that's why it turned out slow. It was at least twice as slow.)</p></li> <li><p>Using a different hash function. I haven't found any measurable difference as long as I use something reasonable, so it seems like this can't be improved.</p></li> </ul> <p>What I have <em>not</em> tried:</p> <ul> <li><p>Storing "fingerprints"/hashes instead of the actual sets.<br> This sounds like the perfect solution, except that the fingerprinting function needs to be <em>fast</em>, and I need to be <em>extremely</em> confident that collisions won't happen, or they'll screw up my program.<br> (It's a deterministic program that needs exact results; collisions render it useless.)</p></li> <li><p>Storing the data in some other compact, CPU-friendly way.<br> I'm not sure how beneficial this would be, because it might involve copying around data, and most of the performance I've gained so far is by (cleverly) avoiding copying data in many situations.</p></li> </ul> <h3>What else can I do to improve the speed, if anything?</h3>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMehrdad
    1. USMehrdad
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to make a fast dictionary that contains another dictionary?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COdo you use reserve() ? if you have a huge data, hash_map need huge dynamic array. that is bottolneck.
      singulars
      1. POHow to make a fast dictionary that contains another dictionary?
      1. USthomas
    2. CO@thomas: Yup I do. :) I use `reserve` for almost everything (including the hashtable), and avoid copying of containers by using moves/swaps.
      singulars
      1. POHow to make a fast dictionary that contains another dictionary?
      1. USMehrdad
    3. COExcuse me, but what type exactly is `T`?
      singulars
      1. POHow to make a fast dictionary that contains another dictionary?
      1. USFred Foo
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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