Login | Register
My pages Projects Community openCollabNet

Discussions > users > Re: [Ada-Comment] AI95-00302-03/03

charles
Discussion topic

Back to topic list

Re: [Ada-Comment] AI95-00302-03/03

Reply

Author Matthew Heaney <mheaney at on2 dot com>
Full name Matthew Heaney <mheaney at on2 dot com>
Date 2004-05-18 07:50:42 PDT
Message Pascal Obry wrote [on ada-comment]:
> Randy,
>
> > Because Matt is very tied (in his mind) to a particular implementation. The
> > containers as described in AI-302-03 are much more abstract, and do not have
> > a prescribed implementation.
>
> This is not true for the map. The name is Indefinite_Hashed_Maps. This state
> cleary that the implementation uses an hash table. I have found that if an
> hash table is very fast for small set of data (< 10000) it is quite slower
> than an AVL for very large set of data (> 100_000). Maybe this is the current
> reference implementation but that's what I have experienced. FYI, the AVL
> implementation I'm talking about is Table_Of_*_And_Dynamic_Data_G from the
> LGL.
>
> Pascal.

Did you Resize the hashed map first, prior to inserting? Remember that
when the buckets array becomes full (really, Length (M) = Size (M)),
then the buckets array is expanded, which means you have to rehash all
of the existing elements onto the new buckets array.

The resizing is very likely going to throw off your comparison of hashed
map and avl tree. Resize the map to the maximum number of elements (or
some suitably large number) prior to any insertions, and then insert the
elements into the map. My hunch is that that will drastically increase
the performance of the map.

The other test you could perform is to use the ordered set and its
nested generic Generic_Keys, which gives you what is essentially a map
but implemented using a red-black tree. This will give you a more close
comparison (red-black tree vs. avl tree).

Of course you could use the sorted map in Charles directly.

-Matt

--------------------​--------------------​--------------------​---------
To unsubscribe, e-mail: users-unsubscribe@ch​arles.tigris.org
For additional commands, e-mail: users-help at charles dot tigris dot org

« Previous message in topic | 1 of 20 | Next message in topic »

Messages

Show all messages in topic

Re: [Ada-Comment] AI95-00302-03/03 Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-18 07:50:42 PDT
     Re: [Ada-Comment] AI95-00302-03/03 Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-18 08:27:30 PDT
         Re: [Ada-Comment] AI95-00302-03/03 Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-18 08:32:18 PDT
             Re: [Ada-Comment] AI95-00302-03/03 Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-18 10:23:01 PDT
                 Re: [Ada-Comment] AI95-00302-03/03 Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-18 11:17:16 PDT
                     Re: [Ada-Comment] AI95-00302-03/03 Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-19 00:31:12 PDT
                         RE: [Ada-Comment] AI95-00302-03/03 matthewjheaney Matthew Heaney 2004-05-19 07:56:10 PDT
                             RE: [Ada-Comment] AI95-00302-03/03 Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-19 06:12:11 PDT
                         Re: [Ada-Comment] AI95-00302-03/03 Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-19 07:29:12 PDT
                             Re: [Ada-Comment] AI95-00302-03/03 Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-19 10:33:37 PDT
                                 Re: [Ada-Comment] AI95-00302-03/03 Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-19 11:15:04 PDT
                                     Re: [Ada-Comment] AI95-00302-03/03 Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-20 06:11:55 PDT
                                         Re: [Ada-Comment] AI95-00302-03/03 Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-20 07:27:34 PDT
                                             Re: [Ada-Comment] AI95-00302-03/03 Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-20 08:08:47 PDT
                                                 Re: [Ada-Comment] AI95-00302-03/03 Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-20 08:24:20 PDT
                                         Re: [Ada-Comment] AI95-00302-03/03 Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-20 08:09:39 PDT
                                         Re: [Ada-Comment] AI95-00302-03/03 fw Florian Weimer 2004-05-22 02:26:20 PDT
                                             Re: [Ada-Comment] AI95-00302-03/03 Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-22 02:40:40 PDT
                                                 Re: [Ada-Comment] AI95-00302-03/03 fw Florian Weimer 2004-05-22 08:14:36 PDT
                                                     Re: [Ada-Comment] AI95-00302-03/03 Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-22 08:34:06 PDT
Messages per page: