Review Request 113485: Speed up natural sorting by first sorting the items according to KFileItem::text() with QString::operator<()

[Emmanuel Pescosta]

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/113485/#review42636
-----------------------------------------------------------

Ship it!


A "Ship It" from my side.

Great idea btw.

Another great thing about this patch is, that we can make use of these sequences of already "sorted" items
to speed up the sorting, when we use Timsort in future (maybe?).

- Emmanuel Pescosta


On Oct. 28, 2013, 7:46 p.m., Frank Reininghaus wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://git.reviewboard.kde.org/r/113485/
> -----------------------------------------------------------
> 
> (Updated Oct. 28, 2013, 7:46 p.m.)
> 
> 
> Review request for Dolphin.
> 
> 
> Repository: kde-baseapps
> 
> 
> Description
> -------
> 
> We all know now that natural sorting can be very slow. There are two ways to improve this:
> 
> 1. Make the "natural comparison" of two items faster. We might be able to do this when we can use QCollator from Qt5.
> 
> 2. Reduce the number of (expensive) comparisons.
> 
> This patch implements option 2 by first doing a very fast non-natural sorting of the items according to their name. The resulting sequence of items is partially sorted even according to the "natural" comparison, and this makes it possible to do the final sorting with a far lower number of comparisons.
> 
> 
> Diffs
> -----
> 
>   dolphin/src/kitemviews/kfileitemmodel.h d005705 
>   dolphin/src/kitemviews/kfileitemmodel.cpp f21edbf 
> 
> Diff: http://git.reviewboard.kde.org/r/113485/diff/
> 
> 
> Testing
> -------
> 
> Loaded a folder with 100,000 items with the names "a1.txt", ..., "a100000.txt". I guess that this is also one of the worst cases with respect to "difference between natural and non-natural sort order".
> 
> This patch reduces the time needed to sort in a release build (commented out the profiling output in insertItems()) from 1940 ms to 714 ms, which is a saving of about 63%.
> 
> 
> Thanks,
> 
> Frank Reininghaus
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.kde.org/mailman/private/kfm-devel/attachments/20131029/41062939/attachment.htm>