Hi Steve, I've been meaning to take a look at this and get back to you, but just haven't had the chance in the last week. Have you made any progress? Anyway, I'll try to take a look tomorrow.
Cheers, Kevin On Monday, June 23, 2014, <[email protected]> wrote: > Dear Julia colleagues, > > As mentioned in earlier posts, I'm working on a 2-3 tree implementation of > sorted associative arrays (analogous to map and multimap in C++). This is > like Dict in Julia, except that the key/value pairs can be retrieved in > sort-order on the keys. > > For my preliminary implementation, the timing for a sequence of 10^7 > insert and find operations is encouraging: my Julia 2-3 trees: 10 sec; my > Julia 2-3 trees with @inbounds everywhere: 8 sec; my C++ 2-3 trees: 20 sec; > my C++ 2-3 trees with /O2 compilation: 6 sec; native C++ map (red/black > trees) with /O2 compilation: 5 sec. > > I have a few additional questions. > > (1) Iteration: The Julia manual describes a start/next/done formulation > for iteration in which the iterator returns (key,value) pairs. However, > this is not adequate for some uses of maps. In C++ an iterator is like a > pointer to the (key,value) pair or like a subscript of an array. The > usefulness of this approach is that the iterator itself can be stored in > another data structure and then dereferenced much later. I'm wondering > whether there is a convention in Julia for naming and operating with this > kind of iterator. (It could be related to the 'state' data item described > in 2.1.7 of the manual.) > > (2) Related to the above question: if m is the map and i is the iterator, > then a second getindex can be implemented so that m[i] returns the > key-value pair. However, it is a bit confusing to overload [] in this way > because of the resemblance to m[k] where k is a key that returns just the > value. Does Julia offer the possibility of overloading some other > subscript notation besides []? For example, maybe Julia could implement a > syntax like m[. i .] or something that would call getindex2 and setindex2? > it seems to me that there will be other cases when a user has a data > structure that can be indexed in more than one way. I suppose this must > already come up with sparse matrices? > > (3) @inbounds: Is there a way for a user-written data structure to check > whether @inbounds is active, and if so, to use a different faster version > of (user-written) getindex and setindex? > > Thanks, > Steve Vavasis > >
