4 ms·

Could you explain some examples of what this is useful for? What sort of algorithms or operations do you have in mind where you both want insertion order, and

by tene 7y ago

Could you explain some examples of what this is useful for? What sort of algorithms or operations do you have in mind where you both want insertion order, and also key-based lookup in the same data structure? I've made heavy use of all kinds of maps, and of queues and channels and arrays, but I don't recall ever noticing a situation where I wanted the properties of both mixed into the same data structure. I'd love to learn more about useful tools to add to my toolbox!

ivalm 7y ago
I think there is a lot of counters you might want both. For example, supposed you have a list of ids accessing some system, you may want to count the raw number, but then also have some transformations thereof that are still ordered by count. Example l = getListOfAccessIds() counts = Counter(l) total = np.sum(counts.values()) fractions = {k:v/total for k,v in counts.most_common()} #use the fact new dictionary is still ordered by most common plt.semilogy(fractions.values()) plt.plot(np.cumsum(fractions.values())) #still works like dict print(fractions[id_of_interest])
behindsight 7y ago
I use ordered maps to keep track of state snapshots/patches of redux/mobx-state-tree stores. It allows me to both apply them sequentially as generated, or to "jump to" a particular point in time.
mehrdadn 7y ago
For "algorithms", I mean, some really do care about insertion order. Like idk, if you have a priority queue, then you generally want FIFO ordering when the priority is the same? It like a pretty obvious desire in most cases... imagine a thread scheduler or a packet scheduler or what have you. But generally it's about determinism and avoiding loss of information, not just whether a particular algorithm needs it. For example, you'd want serialize(obj) and serialize(deserialize(serialize(obj))) to produce the same output, otherwise you e.g. might not be able to cache stuf. But for a data structure like a hashtable, it's pretty tough (not logically impossible, but rather pointlessly difficult) to make that happen without preserving insertion order. As another example, it's incredibly handy for a user to see items in the order in which they were inserted. Like say you're parsing command-line arguments, and the command is ./foo --x=y --w. If the user sees {x: y, w: None} then that tells them w was passed after x. That can be extremely useful for debugging; e.g. maybe you expected the caller to specify w earlier, in a different context and for an entirely different reason. Seeing that it came afterward immediately tells you something is wrong. But when such information is lost it's harder to debug code.
- dTal 7y ago
  If --w can be specified in two places for "an entirely different reason", then an unordered data structure is simply inappropriate, full stop. That's not a question of debugging, that's a question of correctness.
wruza 7y ago
console.log(object) { keys in headache less order } I find this use case severely undervalued in this thread and have no idea why. It helps so much in logging and/or debugging.
gwking 7y ago
I notice it most often when it alleviates correctness concerns with text output. I write lots of python scripts, and guaranteed stable iteration order in dicts lets me breeze through little details that I used to put effort into. Most recent example I can think of is: my human client provides a json schema and data. I iterate over the schema items, which are in the client’s desired display order and construct a validated dict from the input data. From then on, the data items are in correct display order. Previously I would need an ordered array of schema keys; now I can just iterate over the items directly. Someone will probably argue that “implicit is bad” but I have been enjoying the benefits since it was an implementation detail :)
pdobsan 7y ago
Working with GraphQL.
nicoburns 7y ago
I wrote a program that read in a proprietary data format, ran a few transformations, then outputted CSVs. Using an ordered map was super-useful, because it gave me deterministic output between runs. Otherwise I ended up with CSVs with differently ordered rows...
kccqzy 7y ago
Say, a simple LRU cache: * Inserting into the cache is just normal insertion. * To delete excessive items, simply iterate to get the first few items' keys, then delete. * To lookup, simply do a key-based lookup, then delete and re-insert.
ben509 7y ago
Very few algorithms really care, rather, it's when you're composing them that maintaining insertion order avoids a lot of boilerplate in having to cart that information around. For the same reason, though, it's potentially a bad idea. All these algorithms that generate dicts generally won't promise to maintain insertion order, they just happen to by chance. Then consumers come to depend on it and be surprised when it inevitably changes.

by tene 7y ago

ivalm 7y ago

I think there is a lot of counters you might want both. For example, supposed you have a list of ids accessing some system, you may want to count the raw number, but then also have some transformations thereof that are still ordered by count. Example l = getListOfAccessIds() counts = Counter(l) total = np.sum(counts.values()) fractions = {k:v/total for k,v in counts.most_common()} #use the fact new dictionary is still ordered by most common plt.semilogy(fractions.values()) plt.plot(np.cumsum(fractions.values())) #still works like dict print(fractions[id_of_interest])

behindsight 7y ago

I use ordered maps to keep track of state snapshots/patches of redux/mobx-state-tree stores. It allows me to both apply them sequentially as generated, or to "jump to" a particular point in time.

mehrdadn 7y ago

For "algorithms", I mean, some really do care about insertion order. Like idk, if you have a priority queue, then you generally want FIFO ordering when the priority is the same? It like a pretty obvious desire in most cases... imagine a thread scheduler or a packet scheduler or what have you. But generally it's about determinism and avoiding loss of information, not just whether a particular algorithm needs it. For example, you'd want serialize(obj) and serialize(deserialize(serialize(obj))) to produce the same output, otherwise you e.g. might not be able to cache stuf. But for a data structure like a hashtable, it's pretty tough (not logically impossible, but rather pointlessly difficult) to make that happen without preserving insertion order. As another example, it's incredibly handy for a user to see items in the order in which they were inserted. Like say you're parsing command-line arguments, and the command is ./foo --x=y --w. If the user sees {x: y, w: None} then that tells them w was passed after x. That can be extremely useful for debugging; e.g. maybe you expected the caller to specify w earlier, in a different context and for an entirely different reason. Seeing that it came afterward immediately tells you something is wrong. But when such information is lost it's harder to debug code.

dTal 7y ago
If --w can be specified in two places for "an entirely different reason", then an unordered data structure is simply inappropriate, full stop. That's not a question of debugging, that's a question of correctness.

wruza 7y ago

console.log(object) { keys in headache less order } I find this use case severely undervalued in this thread and have no idea why. It helps so much in logging and/or debugging.

gwking 7y ago

I notice it most often when it alleviates correctness concerns with text output. I write lots of python scripts, and guaranteed stable iteration order in dicts lets me breeze through little details that I used to put effort into. Most recent example I can think of is: my human client provides a json schema and data. I iterate over the schema items, which are in the client’s desired display order and construct a validated dict from the input data. From then on, the data items are in correct display order. Previously I would need an ordered array of schema keys; now I can just iterate over the items directly. Someone will probably argue that “implicit is bad” but I have been enjoying the benefits since it was an implementation detail :)

pdobsan 7y ago

Working with GraphQL.

nicoburns 7y ago

I wrote a program that read in a proprietary data format, ran a few transformations, then outputted CSVs. Using an ordered map was super-useful, because it gave me deterministic output between runs. Otherwise I ended up with CSVs with differently ordered rows...

kccqzy 7y ago

Say, a simple LRU cache: * Inserting into the cache is just normal insertion. * To delete excessive items, simply iterate to get the first few items' keys, then delete. * To lookup, simply do a key-based lookup, then delete and re-insert.

ben509 7y ago

Very few algorithms really care, rather, it's when you're composing them that maintaining insertion order avoids a lot of boilerplate in having to cart that information around. For the same reason, though, it's potentially a bad idea. All these algorithms that generate dicts generally won't promise to maintain insertion order, they just happen to by chance. Then consumers come to depend on it and be surprised when it inevitably changes.