Re: associative array

[Francesco Potortì]

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:
>> https://octave.org/doc/v5.2.0/containers_002eMap.html
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
table.

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:    http://fly.isti.cnr.it