[Development] Faster locale aware string list sorting

Knoll Lars Lars.Knoll at digia.com
Sat Mar 9 20:59:18 CET 2013


There's a QCollator class in Qt already to fix exactly that problem, the
plan is to make it public for Qt 5.1.

Cheers,
Lars

On 3/9/13 8:57 PM, "Zeno Endemann" <zeno.endemann at googlemail.com> wrote:

>I've been playing around with different sorting methods and have noticed
>that the naive way to sort a QStringList with localeAwareCompare is
>atrociously slow on my system (64bit Linux, German locale - up to a
>thousand times slower than using the lessThan-operator). While a
>locale aware sorting is obviously inherently slower than basically a
>memory compare I believe we can do a lot better.
>
>As many desktop application need to sort lists of strings in a
>locale aware fashion, I think Qt should provide something to do this
>efficiently. In fact, there are already two places in Qt that would
>benefit from faster sorting (QDir and QSortFilterProxyModel are
>currently using the slow naive method).
>
>The most simple approach to speed this up is to generate the ICU sort
>keys for all the strings and sort the list with them. But this method
>can be pretty inefficient for longer strings and uses a lot of RAM. A
>more adaptive method would be to generate (and cache) on each string
>comparison only the sort key prefix necessary to distinguish the two
>strings. Or we could go all out - I have an idea for a parallelizable
>bucket/merge sort combination ;)
>
>So my questions: Is there interest in (or even plans for) something like
>this? Also, I can hardly believe I'm the first to do something about
>this. Does anyone know of a library that deals with the problem already?
>
>Anyway, if there is interest, I can upload my small benchmark to the Qt
>bug tracker.
>
>
>Best regards,
>Zeno Endemann
>
>
>_______________________________________________
>Development mailing list
>Development at qt-project.org
>http://lists.qt-project.org/mailman/listinfo/development




More information about the Development mailing list