4 ms·

I get the point, but I rarely find myself in the case I even need an _ordered_ hash map. Despite the fact my language provide one by default. I can't remember

I get the point, but I rarely find myself in the case I even need an _ordered_ hash map. Despite the fact my language provide one by default. I can't remember one time in the last decade where I was in need of a _sorted_ hash map. And if it ever happen I can easily depend install one. I'm unsure of having something even more general like a b+tree would help. It's possible that, because I'm not use to have them handy, I don't think about them when I encounter a problem for which they would be perfect. But I never felt like I missed them. Can you give me a few examples of problems you them for in the past year? Was that with a high or low level language?

fnord123 6y ago
Let's get all the records from 2020-06-28T10:00:00.000Z to 2020-06-29T09:59:59.999Z and sum the quantity field. Or anywhere you would want to group_by. Or anywhere you might use something like an RDD that partitions the data to compute something for each chunk of data (in parallel) (also after a group_by). Also, sparse vectors. You don't have a value to store for each index so you use a BTreeMap. I've done this using sentinel values in an array, but that's gross depending on how sparse and how large the vector is. In Python I would just use a Dataframe (pandas), but in Rust I would use BTreeMap. I wouldn't wish for all languages to have a dataframe type in them since they're such complicated beasts with tricky APIs (pandas and R are such acquired tastes) so I think people can get quite far with B(+)Trees. So that's what I wish was in every stdlib.
- BiteCode_dev 6y ago
  I don't know, wouldn't dumping the data into a db easier? If it fits on sqlite, you already have a solution in most languages to this problem. Technically you would be using a btree, but a higher level interface, like with a fs or hashmap. Which is kinda my point. I dont say it's not a good DS, but having it in all languages stdlib seems overkill given the tool we have today. I'm a python guy, and even without panda it has the heapq module which is a b-tree, yet I never really got a reason to use it.
  - fnord123 6y ago
    Heapq is a priority queue implemented on a binary tree; not a btree. > I dont say it's not a good DS, but having it in all languages stdlib seems overkill given the tool we have today. C++ has map and Java has TreeMap. These are both red black trees (which are equivalent to btrees where k=4). So there's no question of whether there are ordered mapping types in these languages. IMO they'd be better as b(+)rees with a wider fanout. That's all.

fnord123 6y ago

Let's get all the records from 2020-06-28T10:00:00.000Z to 2020-06-29T09:59:59.999Z and sum the quantity field. Or anywhere you would want to group_by. Or anywhere you might use something like an RDD that partitions the data to compute something for each chunk of data (in parallel) (also after a group_by). Also, sparse vectors. You don't have a value to store for each index so you use a BTreeMap. I've done this using sentinel values in an array, but that's gross depending on how sparse and how large the vector is. In Python I would just use a Dataframe (pandas), but in Rust I would use BTreeMap. I wouldn't wish for all languages to have a dataframe type in them since they're such complicated beasts with tricky APIs (pandas and R are such acquired tastes) so I think people can get quite far with B(+)Trees. So that's what I wish was in every stdlib.

BiteCode_dev 6y ago
I don't know, wouldn't dumping the data into a db easier? If it fits on sqlite, you already have a solution in most languages to this problem. Technically you would be using a btree, but a higher level interface, like with a fs or hashmap. Which is kinda my point. I dont say it's not a good DS, but having it in all languages stdlib seems overkill given the tool we have today. I'm a python guy, and even without panda it has the heapq module which is a b-tree, yet I never really got a reason to use it.
- fnord123 6y ago
  Heapq is a priority queue implemented on a binary tree; not a btree. > I dont say it's not a good DS, but having it in all languages stdlib seems overkill given the tool we have today. C++ has map and Java has TreeMap. These are both red black trees (which are equivalent to btrees where k=4). So there's no question of whether there are ordered mapping types in these languages. IMO they'd be better as b(+)rees with a wider fanout. That's all.