\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#217: Getting Sorted Indices out of Lsort}
\date{August 26, 2004}
\author{James P. Salsman}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#217}&\textbf{Getting Sorted Indices out of Lsort}\\\hline
Author&

James P. Salsman \tipmail{james}{bovik.org}
\\
Created&Thursday, \(\text{26}^{\text{th}}\) August 2004\\
Type&Project\\
Tcl Version&\(8.5\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.20 $\\
Keywords&Tcl, lsort, parallel lists\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

An \textbf{-indices} option is proposed for the \textbf{lsort} command, returning the indices of the given list's elements in the order that they would have otherwise been sorted.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

When corresponding parallel lists must be simultaneously sorted or accessed in the order given by sorting them all according to one used as a list of keys, it is necessary to obtain the indices of the key list's elements in the order that they would be sorted, without actually sorting the list. For example, a list of first names and a corresponding list of last names can be displayed in side-by-side Tk listboxes, in which case we may want to sort both lists by either one used as the sorting key, or we may want to simultaneously iterate over both in either order. To do so, merely sorting a list is unhelpful; we need to obtain the indices of the key list in the order that its corresponding elements would be sorted.

Tk listboxes, database I/O, and statistics applications often involve heavy use of parallel lists. For this and other reasons, many programming languages starting at least as early as APL, up to present-day, numerics-oriented languages such as MATLAB, have included the ability to directly obtain the indices required to access a list (or ``vector'') in sorted order. As shown below, the fastest known pure Tcl solution to this problem takes about five times as long as the given reference implementation, which adds virtually no overhead when it is not invoked.

\section{Specification}

The \textbf{lsort} command may accept a new option, \textbf{-indices}. When \textbf{lsort} is invoked with this option, it will return a list of integer indices of the elements of the list given as the final argument to \textbf{lsort}, in the order that the elements would have been sorted had the \textbf{-indices} option not been specified.

This means an alternative (though less efficient for single lists) mechanism for producing a sorted list could be:
\begingroup\small\begin{verbatim}
  set resultList [list]
  foreach idx [lsort -indices $sourceList] {
    lappend resultList [lindex $sourceList $idx]
  }
\end{verbatim}
\endgroup

\section{Reference Implementation}

The reference implementation is available from SourceForge [\url{http://sourceforge.net/tracker/index.php?func=detail&aid=1017532&group_id=10894&atid=310894}] It may need to be applied with \textbf{patch -l} or \textbf{patch -{}-ignore-whitespace} or it may not apply entirely.

That reference implementation is a 109-line context diff, involving adding 20 lines of code to \textit{tclCmdIL.c}, a single auto int of new variable memory overhead, and no more than three additional integer comparisons and one integer assignment per use of \textbf{lsort} if the new option is not invoked.

Compared to the following pure Tcl implementation, the reference implementation is 2.4 to 6.7 times faster. This very efficient Tcl implementation was provided by Lars Hellström:
\begingroup\small\begin{verbatim}
  proc lsort-indices {itemL} {
    set pairL [list]
    foreach item $itemL {
      lappend pairL [list $item [llength $pairL]]
    }
    set indexL [list]
    foreach pair [lsort -index 0 -real $pairL] {
      lappend indexL [lindex $pair 1]
    }
    set indexL
  } 
\end{verbatim}
\endgroup

The following timing data are the mean \textbf{time} returned from 20 different lists of random reals, with 10 iterations each:
\begingroup\small\begin{verbatim}
  List size  Ref. Imp.  Pure Tcl  Speedup
  ---------  ---------  --------  -------   
      100       13.1      47.9      3.7
      200       33.9     224.1      6.6
      300       45.0     303.1      6.7
      400       62.0     360.6      5.8
      800      142.3     655.0      4.6
     1600      486.2    1150.0      2.4
     5000     1582.5    4847.6      3.1 
\end{verbatim}
\endgroup

At present, the Reference Implementation does not file the \textbf{-indices} switch alphabetically in the C list of \textbf{lsort} switches, or the C switch statement that interprets them. This simple needs to be corrected before final check-in.

\section{Suggested Documentation}

In the \textbf{lsort} man page, under \textbf{DESCRIPTION}, change the first sentence:

\begin{quote}
``This command sorts the elements of list, returning a new list in sorted order.''
\end{quote}

... to read:

\begin{quote}
``This command sorts the elements of list, and returns a new list in sorted order, unless the -indices option is specified, in which case a list of integers is returned, corresponding to the indices of the given list's elements in the order that they otherwise would have been sorted.''
\end{quote}

Under \textbf{EXAMPLES}, at the end of the section, include the following lines:
\begingroup\small\begin{verbatim}
 Obtaining ordered indices:

  % lsort -indices [list a c b]
  0 2 1
  % lsort -indices -unique -decreasing -real -index 0 \
          {{1.2 a} {34.5 b} {34.5 c} {5.6 d}}
  2 3 0
\end{verbatim}
\endgroup

\section{Tcl-core Discussion}

Here are some highlights from the discussion of this TIP on the Tcl-core mailing list. No assurance is given that the discussion is either completely or impartially represented here.

Lars Hellström [\url{http://sourceforge.net/mailarchive/message.php?msg_id=9346824}] described a pure Tcl solution virtually identical to the one shown above, ``which could be complicated enough to warrent a special [lsort] option.'' He also suggested a \textbf{-keycommand} option for sorting on keys generated on-the-fly. Finally, he pointed out a flaw concerning the example in the Rationale from the original version of this TIP, which has since been corrected.

In reply to Lars, James Salsman [\url{http://sourceforge.net/mailarchive/message.php?msg_id=9348381}] provided timing data and an efficient alternative to the \textbf{-keycommand} idea using this TIP's \textbf{-indices} proposal.

\section{Acknowledgements}

Thanks also to George Peter Staplin and Richard Suchenwirth for their kind help and good ideas at the genesis of this TIP.

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
