[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting men
From: |
Mathieu Desnoyers |
Subject: |
Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items |
Date: |
Thu, 19 May 2022 16:21:59 -0400 (EDT) |
----- On May 3, 2022, at 1:15 PM, Mihai Moldovan ionic@ionic.de wrote:
> Just a nit, feel free to ignore it...
>
>
> * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote:
>> How does the following paragraph sound ?
>>
>> ^^^^^^^^
>> Here is the improved algorithm proposed:
>>
>> - Prepare a list with all the relevant information for ordering by a single
>> sort(1) execution. This is done by renaming ".old" suffixes by " 1" and
>> by suffixing all other files with " 2", thus making sure the ".old" entries
>> will follow the non-old entries in reverse-sorted-order.
>> - Call version_reverse_sort on the list (sort -r -V): A single execution of
>> sort(1) will reverse-sort the list in O(n*log(n)) with a merge sort.
>
> This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of
> SUS/POSIX here) mandates that the sort utility must either use merge sort or
> have O(n*log(n)) time complexity.
>
> Given that you're using version sort, which is a GNU extension, it probably
> can't be anything than GNU sort anyway, though, so the point still holds by
> implicity.
I'm using the same sort already used in version_sort(). It uses sort -V if
available,
but there is a fallback to sort if -V is not available. Therefore, nothing
implies
a version sort, so nothing implies a GNU extension. So your point about other
sort
not necessarily being O(nlog(n)) merge sort is valid. I will remove this
statement
from the next patch version commit message.
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com