before it would be useful to include in the stdlib, along with some motivating use cases

One example would be a continuous auction, like a stock exchange order book. In that case, efficient enumeration is desirable by all of account ID, order ID, or (price, time). book = IndexedList() book.add_unique_index('order_id', lambda o: o.id) book.add_index('account_id', lambda o: o.account_id) book.add_index('price_time', lambda o: (o.price, o.time)) def add_order(order): book.append(order) def del_order(order): del book.indices['order_id'][order.id] def close_account(account_id): del book.indices['account_id'][account_id] def iter_matches(limit_price): for (price, time), order in book.indices['price_time']: if price > limit_price: break yield order Again it's not very clear how the magical 'indices' object slices would work. David

On Mon, Dec 1, 2014 at 3:13 PM, Chris Angelico wrote:

On Tue, Dec 2, 2014 at 2:03 AM, David Wilson wrote:

...

...

before it would be useful to include in the stdlib, along with some motivating use cases

One example would be a continuous auction, like a stock exchange order book. In that case, efficient enumeration is desirable by all of account ID, order ID, or (price, time).

For small numbers of entries, it'd be simpler to just sort and filter on demand; for large numbers of entries, you should probably be using a database, which will have these sorts of facilities. Is there a mid-range where it's better to keep it all in memory, but it's too slow to sort on demand?

My current work project keeps ~8 GB of data in RAM (and looking at 64-128GB servers to get us through the next 3 years). Sorting on demand would be way too slow but it doesn't need to be in a database either - it can be reconstructed from an event stream, and running a DB server is extra ops. Using an in-memory DB like SQLite is an unnecessary extra layer. Currently it just has maps as needed to speed up queries, and I don't think it fits the use case for an MI container, but other projects might. With the amount of RAM in modern machines "keep it all in memory" is viable for lots of use cases with otherwise large values of N. - Jeff

FWIW, a couple of years ago I wrote an implementation of a multi-index container with an ORM-ish interface ( http://norman.readthedocs.org/en/latest/), more for my own amusement than any practical purposes. However, I found that in my work the applications were actually rather limited and generally better served by sqlalchemy + appropriate db, or pandas (depending on use case). I haven't touched the code in quite a while and there may be some bugs that I never discovered, but it might still be of some use. David On Wed, Dec 3, 2014 at 3:10 PM, SF Markus Elfring < elfring@users.sourceforge.net> wrote:

...

Sorting on demand would be way too slow but it doesn't need to be in a database either - it can be reconstructed from an event stream, and running a DB server is extra ops.

I am looking also for ways to omit persistent storage for a specific data processing task. How often will simple index management be sufficient for some software applications?

...

Using an in-memory DB like SQLite is an unnecessary extra layer.

How many in-memory data bases can be reused by the Python software infrastructure? Would you like to point any more class libraries out?

Regards, Markus _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

...

http://www.boost.org/doc/libs/1_57_0/libs/multi_index/doc/index.html

This came up on #python just last week, and I've personally encountered a desire for something similar a bunch of times.

How challenging is it to map powerful Boost classes to the Python programming language?

Probably, though, the ideal interface to something like this would need some time to evolve before it would be useful to include in the stdlib,

I am curious on how this could happen ...

along with some motivating use cases

Would you like to look at any more examples I could show?

-- at least, it would be nice if there were one or two third party implementations to compare before settling on an interface. I can't think of any existing implementations that operate on purely in-memory structures.

Thanks for your feedback.

Boost::multiindex is pretty awesome, but its interface is also somewhat complicated, and a 1:1 translation wouldn't make for a pretty Python experience.

Will this story become another promising software development adventure? Regards, Markus

Is this what pandas MultiIndex does (in Cython)? * http://pandas.pydata.org/pandas-docs/dev/api.html#reshaping-sorting * http://toolz.readthedocs.org/en/latest/api.html On Mon, Dec 1, 2014 at 8:24 AM, David Wilson wrote:

On Mon, Dec 01, 2014 at 01:13:41PM +0100, SF Markus Elfring wrote:

...

Hello,

I find a data structure like it is provided by the "Boost Multi-index Containers Library" interesting for efficient data processing. http://www.boost.org/doc/libs/1_57_0/libs/multi_index/doc/index.html

This came up on #python just last week, and I've personally encountered a desire for something similar a bunch of times. Probably, though, the ideal interface to something like this would need some time to evolve before it would be useful to include in the stdlib, along with some motivating use cases -- at least, it would be nice if there were one or two third party implementations to compare before settling on an interface. I can't think of any existing implementations that operate on purely in-memory structures.

Boost::multiindex is pretty awesome, but its interface is also somewhat complicated, and a 1:1 translation wouldn't make for a pretty Python experience.

I thought about this a little bit last week, initially starting with a "MultiSet" type interface, where the "default" interface for the container emulated a regular set object. But that would prevent having sets of things unless they were hashable (instead of, say, merely having properties that were orderable). In applications where I'd like to use a structure like this, often the element type is mutable.

My second idea was for something like an "IndexedList" type, where the default interface mimicked the built-in list. This would allow generic use of the container with code that wasn't expecting it, and avoid the hashability issue from before.

Perhaps something like:

lst = IndexedList() lst.add_unique_index('id', lambda o: o['id']) lst.add_index('age', lambda o: o['age'])

lst.append({'id': 1, 'age': 50}) lst.append({'id': 1, 'age': 50}) # KeyError

lst.append({'id': 2, 'age': 51})

assert lst.indices['id'][1]['age'] == 50

slice = lst.indices['age'][40:50] # No idea what would be returned here, some kind of view perhaps. assert len(slice) == 2

Following on from the blist thread a few months back, this is another example of a container that would be easy to construct if Python had some kind of built-in ordered mapping type.

David

...

How are the chances to integrate a class library with similar

functionality into the Python software infrastructure?

...

https://bugs.python.org/issue22957

Regards, Markus _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

---

Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

I don't know the first thing about Boost, but this sounds like a database.

The summary mentions it also. http://www.boost.org/doc/libs/1_57_0/libs/multi_index/doc/index.html "... The concept of multi-indexing over the same collection of elements is borrowed from relational database terminology and allows for the specification of complex data structures in the spirit of multiply indexed relational tables where simple sets and maps are not enough. ..."

Perhaps you can use sqlite?

I am reusing this software already as you can see here: Determination for the number of named function parameters (with SmPL) https://lkml.org/lkml/2014/12/1/184 Regards, Markus