Calculating the Smith set: an optimization

[Steve Eppley]

This message isn't intended to provoke further discussion of Smith 
algorithms.  I just want to post an enhancement over my previous 
algorithm in case programmers are interested.

As before, the algorithm assumes the pairwise votes have already
been tallied so it's known, for any two candidates, whether one
pairwise-beat the other.

  Find the candidate(s) with the fewest pairwise defeats.  
  /* These candidate(s) are guaranteed to be in the Smith set. */
  Initialize a list named Smith with just these candidate(s).

  Initialize another list named NotYetSmith with the remainder 
  of the candidates.
  Optional: initialize NotYetSmith so it's sorted by number of
  pairwise defeats (ascending order).
  
  for each candidate Ci in the (growing) Smith list
     for each candidate Cj in the (shrinking) NotYetSmith list
        if Ci did not pairwise-beat Cj
           move Cj from NotYetSmith to the end of Smith
        endif
     endfor
  endfor

The "move Cj" instruction just needs to rewrite three pointers. This
is only one more than merely appending Cj to Smith, and should pay
for itself many times over since each future traversal of NotYetSmith
will traverse fewer elements.

If the optional sort step is performed, then NotYetSmith will shrink
early and maybe save more time than the sorting requires.

- -

[The rest of this message can be skipped.  It duplicates some 
explanatory commentary from a previous message.]

To a programmer, "list", "append", and "move" have meanings which may
not be apparent to everyone.  Lists are ordered, and have a first
element and a last element.  When an element is appended to a
list, it is appended at the end and becomes the new last element.  
When an element is moved from one list to another list, it is 
appended to the second list and deleted from the first list.

Another property of lists is that the pointer (a.k.a. address) to a
list's first element can always be obtained.  Another property is
that given a pointer to an element of a list there is a way to find
the pointer to the next element.  (Attempting to find the pointer to
the next element after the last element returns a special "null"
pointer.)  So lists can be traversed from first to last.

The line "for each candidate Ci in the (growing) Smith list" implies
that the Smith list would be traversed from the first candidate in the
Smith list, in list order, until the "null" pointer is returned by the
attempt to find the next candidate. 

--Steve