[Octave-bug-tracker] [bug #49559] Implementation of containers.Map

[Guillaume]

Follow-up Comment #14, bug #49559 (project octave):

Many thanks for the review, Kai.

I attach a new version fixing a), b), and d). For the performance issue c), it
seems that most of the time is spent in ordering the keys (a call of
orderfields()). I replaced it with a call to sort() before encoding the keys:


>> n = 2e3; t1=tic; mapObj = containers.Map(num2cell(1:n),1:n); toc(t1),
t2=tic; mapObj(n-5), toc(t2)
Elapsed time is 0.196254 seconds.
ans =  1995
Elapsed time is 0.00353098 seconds.


This makes me notice that orderfields() is slow because of the loop at the end
of this function; there might be a faster way to implement it by using
cell2struct(). I also tried to use sortrows() but came across bug #42523;
contrary to the comments there, I think the issue is not with sort() itself
but that sortrows() should call cell2mat() before sort() if the input is a
cell.

Now, with current implementation, keys will be automatically sorted
appropriately (and relatively quickly) when using the constructor. Ordering
using orderfields() will still be called when a new key/value pair is added to
the map, and this will be slow for large maps:


n = 2e3;
tic; mapObj = containers.Map(num2cell(1:n),1:n); toc
Elapsed time is 0.195531 seconds.
tic; mapObj(n+1) = 0; toc
Elapsed time is 3.00148 seconds.


Hopefully this can be fixed by improving orderfields().

Finally, I looked at how to fix the ordering of keys when they are numeric and
contain negative values. Currently:


>> m = containers.Map([-2 -1 0 1 2],{'a','b','c','d','e'});
>> keys(m) ## keys have been sorted according to [-2 -1 0 1 2]
ans =
{
  [1,1] = -2
  [1,2] = -1
  [1,3] = 0
  [1,4] =  1
  [1,5] =  2
}
>> m = containers.Map('KeyType','double','ValueType','char');
>> m(-2)='a';
>> m(-1)='b';
>> m(0)='c';
>> m(1)='d';
>> m(2)='e';
>> keys(m) ## keys have been sorted according to num2hex'ed [-2 -1 0 1 2]
ans =
{
  [1,1] = 0
  [1,2] =  1
  [1,3] =  2
  [1,4] = -1
  [1,5] = -2
}


It seems that using something along the lines of the following would work
(taking the negative of positive values, and the complement of negative
values):


X = [-2 -1 0 1 2];
hex2num(sort(cellstr(num2hex(X))))

i = X >= 0; j = X < 0;
X = typecast(X,'int64');
X(i) = bitset(X(i),64,1);
X(j) = bitcmp(X(j),'int64');
X = typecast(X,'double');

K = sort(cellstr(num2hex(X)))

Y = hex2num(K);
i = Y <= 0; j = Y > 0;
Y = typecast(Y,'int64');
Y(i) = bitset(Y(i),64,0);
Y(j) = bitcmp(Y(j),'int64');
Y = typecast(Y,'double')


The code above works in Matlab but not Octave as there seems to be
compatibility issues with bitset().

(file #40196)
    _______________________________________________________

Additional Item Attachment:

File name: Map.m                          Size:19 KB


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?49559>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/