Processing long lists

[tusooa]

In the qml example, we see that a count is used for the model of a list view: https://github.com/arximboldi/lager/blob/master/example/todo/qml/main.qml#L123 .

This is viable in most cases, but if we would like to transform the list, we are in trouble. immer operations are generally efficient, but not so if we have to create new containers out of old ones.

This could include transforming individual items:

auto list = someCursor.make(); // some lager::reader<immer::flex_vector<T>>
auto transform = zug::map([](auto item) { return ...; });
auto transformed = list.map([=](auto container) { return intoImmer(..., transform, container); }).make(); // O(len(list)) on every update

This may be worked around by putting the transformations into the delegate of the list view, but also:

Filtering:

auto filter = zug::filter([](auto item) { return wantThisP(item); });
auto transformed = list.map([=](auto container) { return intoImmer(..., filter, container); }).make(); // O(len(list)) on every update

Still, this might be also worked around by using the visible property on the delegate, but if there are too many non-visible items (as in a search operation) this is definitely not ideal. And now there is Sorting:

auto transformed = list.map([=](auto container) { return zug::sorted(container.transient()).persistent(); }); // O(nlogn) on every update where n = len(list)

Maintaining a secondary index (as in https://lily.kazv.moe/kazv/libkazv/-/blob/ba5bbfca67b8b1ae9cf34244dbbccc769b19872b/src/client/clientutil.hpp#L200 combined with https://lily.kazv.moe/kazv/libkazv/-/blob/ba5bbfca67b8b1ae9cf34244dbbccc769b19872b/src/client/room/room-model.cpp#L67 ,r.timeline is a list containing all message ids sorted by their timestamp, while r.messages is a map from id to message) might be useful, but still inconvenient.

Do you have any ideas about this? Thank you very much.

[arximboldi]

Hi @tusooa!

To be clear: this is not so much a Lager question, more of an Immer/Zug question? Why do you need to transform every element?
Isn't that a modelling problem?

For maintaining sorted lists, of things that are manipulated one by one, I use an immer::flex_vector and binary-search to find the right point of insertion, and then use insert at the right place. O(log n). (Seems to be the case in your AddToTimeLineAction?)

[tusooa]

Hi @tusooa!

To be clear: this is not so much a Lager question, more of an Immer/Zug question? Why do you need to transform every element?
Isn't that a modelling problem?

For maintaining sorted lists, of things that are manipulated one by one, I use an immer::flex_vector and binary-search to find the right point of insertion, and then use insert at the right place. O(log n). (Seems to be the case in your AddToTimeLineAction?)

Thank you for the reply.

Several years ago when I was reading lager documentation, I saw it mentioned a diffing algorithm (which is cursors now). At that time I was expecting things like Qt's list models, but I did not see such a thing, so I expressed my concerns here. Feel free to move if this issue belong somewhere else -))

I agree that transforming individual items is not very useful most of the time, and for sorting, making a secondary index is ok. For filtering, however, what would be the best practice in your opinion?