Review Request 108824: New sorting algorithm for Dolphin
Emmanuel Pescosta
emmanuelpescosta099 at gmail.com
Sat Feb 16 18:19:36 GMT 2013
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/108824/
-----------------------------------------------------------
(Updated Feb. 16, 2013, 6:19 p.m.)
Review request for Dolphin and Frank Reininghaus.
Changes
-------
Avoid some unnecessary lessThan calls (Use compare return value [int] instead)
Description
-------
Implemented a new sorting algorithm called Tim Sort which is a modified Merge Sort algorithm (http://svn.python.org/projects/python/trunk/Objects/listsort.txt) - Default sorting algorithm in Python and Java
Tim Sort is really fast for already sorted lists (Great for inserting new items, sort role changes - see benchmark 2, ...)
Some benchmarks (200k folders and files):
# Sort Type: Name => TimSort: 1755 ms - Parallel MergeSort: 1547 ms
# Sort Type: Name (Reorder descending) => TimSort: 163 ms - Parallel MergeSort: 434 ms
# Sort Type: Size => TimSort: 259 ms - Parallel MergeSort: 516 ms
# Sort Type: Type => TimSort: 269 ms - Parallel MergeSort: 594 ms
Btw.: Tim Sort uses only 1 core!
ToDo: Write a benchmark for sorting algorithms
Diffs (updated)
-----
dolphin/src/kitemviews/kfileitemmodel.h 903291a
dolphin/src/kitemviews/kfileitemmodel.cpp a763b3f
dolphin/src/kitemviews/private/kfileitemmodelsortalgorithm.h 1d56894
Diff: http://git.reviewboard.kde.org/r/108824/diff/
Testing
-------
Sorting works fine for me
Thanks,
Emmanuel Pescosta
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.kde.org/mailman/private/kfm-devel/attachments/20130216/b764dc33/attachment.htm>
More information about the kfm-devel
mailing list