[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: associative array

From: Francesco Potortì
Subject: Re: associative array
Date: Fri, 27 Mar 2020 20:12:35 +0100

Francesco Potortì:
>>> I need an associative array, and I tried with structs, with the field
>>> names as keys.
>>> Unfortunately it clearly slows down with size. I have about 30000 keys,
>>> for each I first check if it's already there, if not I create it, if
>>> it's there I add some data. The number of operations (insertion +
>>> updates) is around 55000. The slowdown appears to be quadratic (but I
>>> have not made any measurement, in fact).
>>> Are there more efficient ways to build and update an associative array?
José Abílio Matos:
>> How about containers.Map:
Andrew Janke:
>That's a reasonable idea, but I'm curious as to why struct itself is
>slow. I would think that struct lookups for get or set would be O(1)
>using a hash on the string key (or some other symbol-level identifier).
>Are structs not hashtables over the string key values?

I read somewhere that they are, that's why I used a struct in the first
place.  I have now profiled my code and it turns out that it spends 91%
of time on isfield, which is what I suspected.  After instrumenting it
to measure time, it turns out that the time grows linearly with struct
size, while it should stay constant.

Then I tried to build a small demo program showing this, but no, here
the time is almost constant with struct size, as expected from a hash

Now the only thing is to take my program and simplify it until I
demonstrate the problem, but that would be a long task :(

Francesco Potortì (ricercatore)        Voice:  +39.050.621.3058
ISTI - Area della ricerca CNR          Mobile: +39.348.8283.107
via G. Moruzzi 1, I-56124 Pisa         Skype:  wnlabisti
(gate 20, 1st floor, room C71)         Web:

reply via email to

[Prev in Thread] Current Thread [Next in Thread]