1. Forum
  2. Usenet
  3. COMP.LANG.TCL

  • Sorting a sorted list is inexpensive?

    From Cecil Westerhof@21:1/5 to All on Fri Apr 21 06:53:12 2023
    I have a variable history that is filled like:
    {{#1682051497} {emacsclient --create-frame org/dummy.org &}}
    {{#1682051113} {time thinHistory.tcl}}
    {{#1682051041} ll}
    .
    .
    .

    I use:
    return [lsort -decreasing -index 0 ${history}]

    to return it sorted decreasing on the first element of the containing
    lists.
    It seems that when the sort is not necessary that the sort does not
    take much time. Can I count on this, or could it be that it is not
    always the case and is it better to add code to make sure it is only
    sorted when it is necessary?

    --
    Cecil Westerhof
    Senior Software Engineer
    LinkedIn: http://www.linkedin.com/in/cecilwesterhof

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Ralf Fassel@21:1/5 to All on Fri Apr 21 10:50:05 2023
    * Cecil Westerhof <Cecil@decebal.nl>
    | I use:
    | return [lsort -decreasing -index 0 ${history}]

    | to return it sorted decreasing on the first element of the containing
    | lists.
    | It seems that when the sort is not necessary that the sort does not
    | take much time. Can I count on this, or could it be that it is not
    | always the case and is it better to add code to make sure it is only
    | sorted when it is necessary?

    man lsort(n)
    The implementation of the lsort command uses the merge-sort
    algorithm which is a stable sort that has O(n log n) performance
    characteristics.

    I read that merge-sort on an almost sorted list has good performance.
    So as long as the algorithm of lsort is not changed...

    But.
    How much time max is it allowed to take before sorting becomes
    noticeable? 1 second? 1 millisecond?

    A history list sounds useful only if it does *not* contain zillions of
    entries, and for anything less than say some hundred entries the time
    for sorting it once should not be noticeable.

    R'

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Cecil Westerhof@21:1/5 to Ralf Fassel on Fri Apr 21 11:35:43 2023
    Ralf Fassel <ralfixx@gmx.de> writes:

    * Cecil Westerhof <Cecil@decebal.nl>
    | I use:
    | return [lsort -decreasing -index 0 ${history}]

    | to return it sorted decreasing on the first element of the containing
    | lists.
    | It seems that when the sort is not necessary that the sort does not
    | take much time. Can I count on this, or could it be that it is not
    | always the case and is it better to add code to make sure it is only
    | sorted when it is necessary?

    man lsort(n)
    The implementation of the lsort command uses the merge-sort
    algorithm which is a stable sort that has O(n log n) performance
    characteristics.

    I read that merge-sort on an almost sorted list has good performance.
    So as long as the algorithm of lsort is not changed...

    Well, when only one element was out of order, the program took about
    three times as long to execute. But when none where out of order it
    took about the same time with, or without sort.


    But.
    How much time max is it allowed to take before sorting becomes
    noticeable? 1 second? 1 millisecond?

    In this case it is not something to worry about, but I like to learn
    things I do not need right away. :-D


    A history list sounds useful only if it does *not* contain zillions of entries, and for anything less than say some hundred entries the time
    for sorting it once should not be noticeable.

    The one I tested it on had about 150. I know that thousands are not
    uncommon and that there are people who use tens of thousands.


    Thanks. I keep it without extra code.

    --
    Cecil Westerhof
    Senior Software Engineer
    LinkedIn: http://www.linkedin.com/in/cecilwesterhof

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)