Re: [OctDev] string dictionary class

[Carnë Draug]

On 13 January 2014 20:31, c. <address@hidden> wrote:
> Hi,
>
> I saw you were discussing what's the purpose of
> @dict in the package general so I looked up the
> orginal message that Jaroslav sent when he created
> that class explaining its purpose.
>
> HTH,
> c.
>
> Begin forwarded message:
>
>> From: Jaroslav Hajek <address@hidden>
>> Subject: [OctDev] string dictionary class
>> Date: 14 August 2009 08:29:24 GMT+2
>> To: octave-forge list <address@hidden>
>> Cc: Octave users list <address@hidden>
>>
>> hi all,
>>
>> I have contributed a simple string dictionary class to the `general'
>> package, which comprises
>>
>> indexing by strings & cell string arrays
>> indexed assignment
>> inserting and deleting elements
>> existence query (has)
>> query with default value (get)
>>
>> it is intended to work with development version of Octave, as it uses
>> some new features. The implementation uses binary lookup in a sorted
>> array.
>> operation complexity, w.r.t. number of existing keys N is:
>> retrieve and query: O(log(N))
>> set existing entry: O(log(N)) with the recent subsasgn optimization
>> (e79470be3ecb), O(N) without it.
>> insert new key / delete existing: O(N)
>>
>> it is therefore not suitable for frequent insertions but good when
>> query is the major operation.
>>
>> Example usage:
>>
>> octave:1> gnusoft = dict
>> gnusoft = dict: {}
>> octave:2> gnusoft("octave") = "www.octave.org"
>> gnusoft =
>>
>> dict: {
>>  octave : www.octave.org
>> }
>> octave:3> gnusoft("gcc") = "gcc.gnu.org"
>> gnusoft =
>>
>> dict: {
>>  gcc : gcc.gnu.org
>>  octave : www.octave.org
>> }
>> octave:4> gnusoft({"octave", "gcc", "octave"})
>> ans =
>>
>> {
>>  [1,1] = www.octave.org
>>  [1,2] = gcc.gnu.org
>>  [1,3] = www.octave.org
>> }
>>
>> octave:5> getgnusoftaddress = @(name) get(gnusoft, name,
>> "directory.fsf.org/GNU")
>> getgnusoftaddress =
>>
>> @(name) get (gnusoft, name, "directory.fsf.org/GNU")
>>
>> octave:6> getgnusoftaddress ("octave")
>> ans = www.octave.org
>> octave:7> getgnusoftaddress ("bison")
>> ans = directory.fsf.org/GNU
>> octave:8> has(gnusoft, {"gcc", "bison"})
>> ans =
>>
>>   1   0
>>
>> octave:9> mathgnusoft = gnusoft
>> mathgnusoft =
>>
>> dict: {
>>  gcc : gcc.gnu.org
>>  octave : www.octave.org
>> }
>> octave:10> mathgnusoft ({"gcc"}) = []
>> mathgnusoft =
>>
>> dict: {
>>  octave : www.octave.org
>> }
>> octave:11> files = dir;
>> octave:12> cache_file_stat = dict ({dir.name}, {dir.statinfo});
>> octave:13> cache_file_stat ("adresamp2.m")
>> ans =
>> {
>>  dev =  2051
>>  ino =  14749998
>>  mode =  33188
>>  modestr = -rw-r--r--
>>  nlink =  1
>>  uid =  1000
>>  gid =  100
>>  rdev = 0
>>  size =  2739
>>  atime =  1.2464e+09
>>  mtime =  1.2403e+09
>>  ctime =  1.2403e+09
>>  blksize =  4096
>>  blocks =  16
>> }
>>
>>
>> I welcome suggestions for improvements and enhancements.
>>
>> enjoy!

I just did a very simple test for that, retrieving values and checking
existence of keys in a dict, versus the equivalent operations in a
struct

a = mat2cell (char (randi ([40 100], [1000 8])), ones (1000, 1), 8);

s = struct (a{:});
d = dict (a(1:2:end), a(2:2:end));

keys = a(1:2:end)';
t = cputime (); for f = keys, s.(f{:}); endfor; cputime () -t
t = cputime (); for f = keys, get (d, f{:}); endfor; cputime () -t

t = cputime (); for f = keys, isfield (s, f{:}); endfor; cputime () -t
t = cputime (); for f = keys, has (d, f{:}); endfor; cputime () -t

For struct:
get value is 0.0080000
has key is 0.10401

For dict:
get value is 0.048003
has key is  0.044003

Carnë