D11282: less expensive findByUrl in KCoreDirListerCache
Stefan BrĂ¼ns
noreply at phabricator.kde.org
Thu May 17 18:06:34 UTC 2018
bruns added inline comments.
INLINE COMMENTS
> dfaure wrote in kcoredirlister.cpp:852
> That was the case already.... hmm but not in my version of kio. It looks like this patch is on top of other patches.
D10742 <https://phabricator.kde.org/D10742> - this makes it even harder to review ...
> mwolff wrote in kcoredirlister.cpp:1970
> O(N) iteration over a large hash is extremely slow, is this done elsewhere? if so, then you may need to find an alternative approach - potentially via multiple containers or by using a sorted vector after all like you proposed initially
My proposal:
A few lines earlier, a `KFileItemList` (~`QList<KFileItem`) is created.
Sort this list by name.
Use a ordered container (e.g. `QMap`) instead of `QHash`.
You can iterate the `QMap` and the `KFileItemList` in parallel, which makes erasing an O(m + n) iteration, instead of O(m * n). (Of course, on top you have sorting of the KFileItemList - O(n log n) - and the overhead when inserting into the QMap<QUrl, KFileItem>)
REPOSITORY
R241 KIO
REVISION DETAIL
https://phabricator.kde.org/D11282
To: jtamate, #frameworks, dfaure
Cc: kde-frameworks-devel, bruns, mwolff, michaelh, ngraham
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-frameworks-devel/attachments/20180517/e41a1e9e/attachment.html>
More information about the Kde-frameworks-devel
mailing list