Rockbox.org home
release
dev builds
extras
themes manual
wiki
device status forums
mailing lists
IRC bugs
patches
dev guide



Rockbox mail archive

Subject: Re: how is strnatcmp aka "Interpret numbers while sorting" supposed to sort?

Re: how is strnatcmp aka "Interpret numbers while sorting" supposed to sort?

From: Thomas Martitz <thomas.martitz_at_fhtw-berlin.de>
Date: Thu, 19 Mar 2009 18:47:41 +0100

Dominik Riebeling wrote:
> On Thu, Mar 19, 2009 at 4:04 PM, Thomas Martitz
> <thomas.martitz_at_fhtw-berlin.de> wrote:
>
>> Now imagine this for every char in a string, and for every string in a file
>> list (with some 100 files). It's three-times (or even more) more complexity
>> than just.
>> while (is_zero(a))
>> a = next;
>>
>
> This "natural sorting" is more complex than ASCII sorting anyway. And
> what's the added complexity by simply going back by one to get the
> last 0? That's only an added check, and everything else only if you
> hit a digit.
>
> if(is_digit(a)) {
> /* is_digit() had a hit */
> while(is_zero(a))
> a = next;
> /* if current one is not a digit anymore we've just skipped the
> value 0 and need to take that back to not remove that value */
> if(!is_digit(a)) /* no need to check if there is a prev value --
> we skipped at least one 0. If not we still have a digit. */
> a = prev;
> }
>
>
That's how did it now (see FS#10030).
>> We're on embedded, and thus slow systems. Your would surely work well on a
>> desktop app, but for mp3-players we need fast and small code. The gain has
>> to justify the code, and I don't think it does it in this example.
>>
>
> We're talking about high-level functionality here. There's nothing
> timing-critical, and even on the Archos players I'm confident doing
> this properly wouldn't cause a serious slowdown compared to the
> current state, but feel free to measure it and present numbers. We can
> play mp3 files at <45MHz (at least on coldfire, don't have all the
> numbers at hand right now) which is much more calculating-intensive
> than doing a few additional comparisons on a list of maybe some 100
> files.
>
> You're basically saying we shouldn't fix the functionality because
> it's too expensive runtime-wise. If it's really too expensive to have
> a functionality working properly (which I doubt) we shouldn't ship the
> functionality at all.
>
>
> - Dominik
>

The problem with his proposal was, that it looked 3 times at every char.
That's hardly optimal.

The original algorithm looks only once through each char. And the
version you proposed does it too (except in the case where it goes back
1 char). That's why it's not much more expensive than normal strcmp.

And I think that a file-listing is relatively timing critical. I
wouldn't want to have noticeably delay just due to sorting on each
folder I enter.
Received on 2009-03-19


Page was last modified "Jan 10 2012" The Rockbox Crew
aaa