On 7/18/14 4:41 PM, David M. Lloyd wrote:
On 07/18/2014 06:36 PM, Stuart Marks wrote:
Map.of()
.add(k0, v0)
.add(k1, v1)
...
.add(kN, vN);
this would result in O(N^2) performance and space allocation, though
most of the allocated space is garbage.
Adding another alternative, instead of producing intermediate maps which are
copied at each step for the sake of maintaining O(1) lookup, this approach could
instead create a linked-list-of-pairs which would be O(n) for lookups, but also
O(n) for space - you could then efficiently feed that to a "real" map
constructor, especially if each "map" also implemented Map.Entry, which would
make an iterator particularly lightweight, making the overall cost for, say, a
HashMap be O(n).
Not sure it's the "right" approach, just throwing it out there as a random
Friday thought.
... now being analyzed in the cold, harsh light of a Monday morning. Er,
afternoon. :-)
The main difficulty here is if the type returned by add() is a Map, it has to
obey all the requirements of the Map contract. That means that somebody has to
enforce the uniqueness constraint of the keys. This will affect things like
iterating over the map or asking for its size, and so forth. Either the extra
work is done at addition time or later when certain results require respecting
uniqueness.
If add() returns something other than a Map, such as a temporary data structure
later used to construct a Map, then pushing the items onto a linked list is
quite a sensible idea. (Maybe a linked list of arrays, to reduce per-element
overhead.) We don't care if the keys are unique when they're being added, since
that'll be taken care of later at map construction time. But this is essentially
a builder, not incremental additions to a Map.
s'marks
