3 ms·

A somewhat related question: Why can't you add an index to a simple in-memory list? It would be great if you could have a std::vector or Python list of plain ol

A somewhat related question: Why can't you add an index to a simple in-memory list? It would be great if you could have a std::vector or Python list of plain old objects, and then tell it to add an index (using a hashtable for example) on one or two of the fields. I played with something like that in Python a couple of years ago, but never made it production-ready. I think in many simple cases it could replace a dedicated (SQL) database.

layer8 4y ago
Because, at least in C++ and Python that you mention, you can mutate (a field of) an element of the list without the list noticing, and hence without the index being updated. In the general case, you’d not only have to wrap the list, but also its elements, and wire the element wrappers up with the list. So it’s better to have the application do that because it knows when the index needs updating for a given element (and its old & new value). The other reason is that most often you only need an index on one field, and don’t need the elements to be in a particular order, so you just use a map/dict with the value of that field, instead of a list.
nikita 4y ago
This is awesome idea! I'm sure there is an implementation somewhere.
- runekaagaard 4y ago
  Here you go :) https://zodb.org/en/latest/ https://zodb.org/en/latest/
ElectricalUnion 4y ago
> Why can't you add an index to a simple in-memory list? The index is already a "simple in-memory list", sorted. That's why it is expensive to mantain. > It would be great if you could have a std::vector or Python list of plain old objects Sort said Python list by the columns in your index. > and then tell it to add an index (using a hashtable for example) on one or two of the fields. Hashtable is another thing entirely, and designed for fast key retrieval at very high memory and CPU cost. If you can't afford a index you can't afford a Hashtable/dict either.
- bshipp 4y ago
  Every time I've found myself heading down this rabbit hole of creating a faster Python list sort/search, I've inevitably realized that using an in-memory sqlite database is orders of magnitude faster and more flexible, especially once you start trying to mangle lists or sets with millions of elements. The added benefit is that you can also dump it to the drive if you have to prematurely end your task and resume it from the same place later. And it also supports indexes, both traditional and full-text searching. It's a lot easier to use a tool designed for the task instead of building one from scratch.
ignoramous 4y ago
> It would be great if you could have a std::vector or Python list of plain old objects, and then tell it to add an index (using a hashtable for example) on one or two of the fields. This is what a LinkedHashMap (1 index) and HashBasedTable (2 indices) do in the jvm-land. Admittedly, there isn't a convenience api to convert a given collection/vector to a map/table (but hey, if you're like me and write a lot of golang, then the current jvm-land status quo is already heaven!). https://guava.dev/releases/snapshot-jre/api/docs/com/google/common/collect/HashBasedTable.html https://guava.dev/releases/snapshot-jre/api/docs/com/google/...
tracnar 4y ago
This talk explored a bit that idea, you could have a (full) programming language which is more like SQL so you get good enough datastructures (and indexing- without manual tuning: https://www.youtube.com/watch?v=gC295d3V9gE https://www.youtube.com/watch?v=gC295d3V9gE I think Prolog (another commenter pointed it out) and datalog do this to some extend.
chakkepolja 4y ago
Boost has something called MultiIndex.
mywittyname 4y ago
Honest question: how many applications are using in-memory lists that are large enough to warrant indexing but are also too small to put in a database? That's probably why such a library doesn't exist. Sorting & search is good enough for one field. Full scans aren't that bad for small/medium datasets. And databases aren't that difficult to integrate into an application. Also, pandas exists in the Python world.
- bshipp 4y ago
  Usually laziness, in my experience. that internal "fine, I guess I'll open the SqlAlchemy docs and spin up a database instance for this instead of monkeying around with python sets and lists" argument developers have with themselves. Pandas is also very powerful, but everytime I go to use it I feel I have to learn the API all over again.

layer8 4y ago

Because, at least in C++ and Python that you mention, you can mutate (a field of) an element of the list without the list noticing, and hence without the index being updated. In the general case, you’d not only have to wrap the list, but also its elements, and wire the element wrappers up with the list. So it’s better to have the application do that because it knows when the index needs updating for a given element (and its old & new value). The other reason is that most often you only need an index on one field, and don’t need the elements to be in a particular order, so you just use a map/dict with the value of that field, instead of a list.

nikita 4y ago

This is awesome idea! I'm sure there is an implementation somewhere.

runekaagaard 4y ago
Here you go :) https://zodb.org/en/latest/ https://zodb.org/en/latest/

ElectricalUnion 4y ago

> Why can't you add an index to a simple in-memory list? The index is already a "simple in-memory list", sorted. That's why it is expensive to mantain. > It would be great if you could have a std::vector or Python list of plain old objects Sort said Python list by the columns in your index. > and then tell it to add an index (using a hashtable for example) on one or two of the fields. Hashtable is another thing entirely, and designed for fast key retrieval at very high memory and CPU cost. If you can't afford a index you can't afford a Hashtable/dict either.

bshipp 4y ago
Every time I've found myself heading down this rabbit hole of creating a faster Python list sort/search, I've inevitably realized that using an in-memory sqlite database is orders of magnitude faster and more flexible, especially once you start trying to mangle lists or sets with millions of elements. The added benefit is that you can also dump it to the drive if you have to prematurely end your task and resume it from the same place later. And it also supports indexes, both traditional and full-text searching. It's a lot easier to use a tool designed for the task instead of building one from scratch.

ignoramous 4y ago

> It would be great if you could have a std::vector or Python list of plain old objects, and then tell it to add an index (using a hashtable for example) on one or two of the fields. This is what a LinkedHashMap (1 index) and HashBasedTable (2 indices) do in the jvm-land. Admittedly, there isn't a convenience api to convert a given collection/vector to a map/table (but hey, if you're like me and write a lot of golang, then the current jvm-land status quo is already heaven!). https://guava.dev/releases/snapshot-jre/api/docs/com/google/common/collect/HashBasedTable.html https://guava.dev/releases/snapshot-jre/api/docs/com/google/...

tracnar 4y ago

This talk explored a bit that idea, you could have a (full) programming language which is more like SQL so you get good enough datastructures (and indexing- without manual tuning: https://www.youtube.com/watch?v=gC295d3V9gE https://www.youtube.com/watch?v=gC295d3V9gE I think Prolog (another commenter pointed it out) and datalog do this to some extend.

chakkepolja 4y ago

Boost has something called MultiIndex.

mywittyname 4y ago

Honest question: how many applications are using in-memory lists that are large enough to warrant indexing but are also too small to put in a database? That's probably why such a library doesn't exist. Sorting & search is good enough for one field. Full scans aren't that bad for small/medium datasets. And databases aren't that difficult to integrate into an application. Also, pandas exists in the Python world.

bshipp 4y ago
Usually laziness, in my experience. that internal "fine, I guess I'll open the SqlAlchemy docs and spin up a database instance for this instead of monkeying around with python sets and lists" argument developers have with themselves. Pandas is also very powerful, but everytime I go to use it I feel I have to learn the API all over again.