<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
On 07/01/2012 12:17, Christoph Breitkopf wrote:
<blockquote
cite="mid:CAPTT2bYvYtcoORxRL85=jpbWtGCHZ_owNqy+QRk8aUPte86T2A@mail.gmail.com"
type="cite">Hello,<br>
<br>
I wonder why Data.Map provides the indexed access functions:<br>
<br>
<a moz-do-not-send="true"
href="http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Map.html#g:21">http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Map.html#g:21</a><br>
<br>
These functions seem rather out-of-place to me in the map api. The
only use case I could think of so far would be to find the median,
or in general n-th smallest key, but that does not seem sufficient
reason (also, I think there are faster methods for that). Anything
else?<br>
<br>
</blockquote>
I don't know the motivation in Data.Map, but here's some thoughts
from a C++ home-rolled data structures perspective...<br>
<br>
Somewhere around a decade ago, I started an in-memory C++ multiway
tree library, initially an experiment seeing if I could improve
sequential access performance. This half-worked, but I still use the
data structure primarily because it's a bit safer in some cases than
the STL containers, and also has some extra functionality that makes
it more convenient.<br>
<br>
Features include...<br>
<ol>
<li> "cursor maintenance" (when I insert/delete, cursors/iterators
are not invalidated except in the special case that the cursor
references an item that is deleted. There are two tricks for
this case - the cursor will at least know that the item is
deleted, plus there are special cursors that can defer deletion
(mainly for delete-the-current-item within loops).</li>
<li>Searching based on custom "comparisons" - mainly searching
based on a partial key (certain fields), so you can find the
first/last item equal to a partial key, ignoring less
significant fields.</li>
<li>Finding the first key that is *not* in the container (for
unsigned integer keys only).<br>
</li>
<li>Subscripted access - finding a given index, determining the
index to an item referenced by a cursor, stepping
forward/backward by a given number of items.</li>
</ol>
The subscripted access isn't massively useful - it was implemented
because I was curious how to handle it efficiently. However, cases
do come up from time to time in strange places. For example,
sometimes it's more convenient to store an index (into a container
that won't change) than a cursor or a full key. And using an ordered
container does tend to imply, after all, that you're interested
somehow in the order (or else why not use a hash table?).<br>
<br>
One case, I guess, relates to DSL-generated data structures. The
point there is that when the generated code runs, the map instance
is long dead. Within the generated code, ranges etc tend to be
identified by subscript - so the DSL needs to be able to translate
from key to subscript, and (maybe) back again. OTOH, don't forget
that laziness thing - if the code generator was working from a
sorted array it would know the subscripts anyway.<br>
<br>
A particularly surprising side-effect - along with the map,
multimap, set and multiset wrappers, I have a vector wrapper. When
you have a huge array and do lots of inserts and deletes within that
array, a multiway tree (with subscripted access) turns out to be a
good trade-off. Some accesses are more awkward (because the items
aren't all contiguous in memory), but the log-time inserts and
deletes can be worth it.<br>
<br>
The first-key-not-in-the-container stuff was mostly a side-effect of
the data structure augmentation I did for subscripted access. That
is very convenient, but with costs.<br>
<br>
The no. 1 killer feature that keeps me using and maintaining this
library is the partial-key search thing. This is so useful, I even
added a feature to a DSL (used mainly for AST nodes and multiple
dispatch - originally based on treecc) to make it more convenient to
generate partial-key classes.<br>
<br>
The cursor maintenance makes it a lot easier to write algorithms
that update the container, but it's perhaps surprising how rare
that's necessary.<br>
<br>
The issue with all this is of course partly overhead, but also
because I got lazy - keeping these things hanging around throughout
whole program runs like cheap second-rate databases. They are quite
convenient to work with, but for a long time I stopped even
considering pulling all the data out into a flat array, processing
it there, then rebuilding a new indexed data structure only if I
really needed it, or keeping data mostly in an array and sorting it
ready for binary searches just at the key point where that's needed.<br>
<br>
Some programs I've written using them are maybe an order of
magnitude slower than they should be, and in quite a few cases
there's an asymptotic difference, not just a constant factor - a lot
of algorithms are O(n log n) where without the convenience
containers they could be O(n).<br>
<br>
Very little of this would be relevant in a pure functional
programming world, of course, but anyway - yes, subscripting can be
(occasionally) useful. It's just hard to give specific examples,
because they're buried in all the technicalities of quite large
programs.<br>
<br>
</body>
</html>