#1 2024-09-11 10:42:54

okoba
Member
Registered: 2019-09-29
Posts: 113

Multi thread sort

I am looking for different ways of achieving this, and I was wondering if people here have any insight or code.
PasMP and OmniThread have samples for it, but I am hoping for other info.

Offline

#2 2024-09-11 13:40:19

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 14,548
Website

Re: Multi thread sort

I have never needed this, because when sorting becomes a bottleneck, I usually change the algorithm, e.g. to store indexes instead of values, or use hashing, or use self-sorted structures.

What is your use case?
When are our QuickSort###() functions or TDynArray.Sort becoming too slow in practice?

Offline

#3 2024-09-11 13:52:50

okoba
Member
Registered: 2019-09-29
Posts: 113

Re: Multi thread sort

I have a list of log values (that I can not insert into SQLite, always changing and takes to much time to insert) and I want to query them using SQLite VTab, but as you know it can not use SQLite Index. So I thought about sorting them for xFilter to speedup order and group by. But for 100 million, it takes 8s to use the QuickSortInteger and more for string values.

Offline

#4 2024-09-11 15:36:26

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 14,548
Website

Re: Multi thread sort

If your result sets are not in the range of millions entries, I guess you could tune your algorithm.

You certainly don't need to sort all entries before getting the results.

For instance, a map/reduce/sort pattern may be better suited.
It would become a O(n) algorithm, not a O(log(n)), thanks to the "map/reduce" step.

Offline

#5 2024-09-11 15:41:41

okoba
Member
Registered: 2019-09-29
Posts: 113

Re: Multi thread sort

As I said I like to query the list using SQLite VTab and I can not change the algorithm of VTab if you mean that. SQLite xBestIndex asks for a ordered result to speedup order or group by and that is the reason I asked the question.

Offline

Board footer

Powered by FluxBB