Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #8466

Re: C Containers Library vs STL

Show all headers | View raw

Le 04/08/11 14:47, Marc a écrit :
> jacob navia  wrote:
>
>> Le 04/08/11 02:34, Ian Collins a écrit :
>>>
>>> Um, I tried both versions with the same optimisations (cc/CC -fast) on
>>> my Solaris box and the run times (over several runs) for a 350K line
>>> file with 214K unique lines were:
>>>
>>> C: 5.027s
>>> CC: 1.835s
>
> Comparing a hash table to a binary tree is not really fair, try with
> hash_set (common extension) or unordered_set (C++0x).
>
>> Did you change the number passed to the Create API?
>>
>> The code as shown is optimized for a file of 500 lines or so.
>>
>> Changing that 500 to (say 135000) would be significantly
>> better but would use much more memory.
>
> Standard C++ hash tables automatically increase their number of buckets
> when the number of objects is large enough.
>

I am thinking about adding such an extension to the Dictionary
container. I have already such an extension for the general hash
table container, it resizes automatically. The Dictionary container
was thought as a light weight hash table, with character keys. The
general hash table can have keys of any type but its usage is
more cumbersome, that is why I splitted it into a dictionary
(good for 80% of applications) and a general hash table
(when you need resisizing, and keys that aren't character data.


Now, I am wondering if that interface is not MORE complicated than
a more capable dictionary... Anyway if the resizing is automatic I can
keep the same interface. The code is bulkier though.


> Why should 135000 buckets use much more memory if there are enough
> objects to fill most buckets?

Because there is more overhead per bucket. In my implementation
we have a table of <n> slots, and each slot with a single linked
list of objects that map to the same hash code.

Space overhead is:
(1) overhead for the linked list: 2*sizeof(void *) for each object
(2) Overhead of the table for the slots: sizeof(void *)/ number of
objects per slot.

You see? The larger the table, the more overhead it makes since the
occupancy decreases (and hence the speed of search increases)

jacob

Back to comp.lang.c++ | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

C Containers Library vs STL jacob navia <jacob@spamsink.net> - 2011-08-03 22:40 +0200
  Re: C Containers Library vs STL Ian Collins <ian-news@hotmail.com> - 2011-08-04 09:13 +1200
    Re: C Containers Library vs STL Robert Wessel <robertwessel2@yahoo.com> - 2011-08-03 17:36 -0500
      Re: C Containers Library vs STL Robert Wessel <robertwessel2@yahoo.com> - 2011-08-03 17:38 -0500
        Re: C Containers Library vs STL jacob navia <jacob@spamsink.net> - 2011-08-04 01:30 +0200
          Re: C Containers Library vs STL Robert Wessel <robertwessel2@yahoo.com> - 2011-08-03 18:40 -0500
            Re: C Containers Library vs STL jacob navia <jacob@spamsink.net> - 2011-08-04 13:42 +0200
          Re: C Containers Library vs STL Ian Collins <ian-news@hotmail.com> - 2011-08-04 12:34 +1200
            Re: C Containers Library vs STL Ian Collins <ian-news@hotmail.com> - 2011-08-04 13:38 +1200
              Re: C Containers Library vs STL Juha Nieminen <nospam@thanks.invalid> - 2011-08-04 07:02 +0000
                Re: C Containers Library vs STL Ian Collins <ian-news@hotmail.com> - 2011-08-04 19:40 +1200
                Re: C Containers Library vs STL Juha Nieminen <nospam@thanks.invalid> - 2011-08-04 14:16 +0000
                Re: C Containers Library vs STL jacob navia <jacob@spamsink.net> - 2011-08-04 16:25 +0200
                Re: C Containers Library vs STL Nobody <nobody@nowhere.com> - 2011-08-04 21:40 +0100
            Re: C Containers Library vs STL jacob navia <jacob@spamsink.net> - 2011-08-04 09:42 +0200
              Re: C Containers Library vs STL Ian Collins <ian-news@hotmail.com> - 2011-08-04 19:59 +1200
              Re: C Containers Library vs STL Marc <marc.glisse@gmail.com> - 2011-08-04 12:47 +0000
                Re: C Containers Library vs STL jacob navia <jacob@spamsink.net> - 2011-08-04 15:17 +0200

csiph-web