Speed up getSureLosers

[GoogleCodeExporter]

getSureLosers doesn't scale well to large number of candidates

Original issue reported on code.google.com by dan.keshet@gmail.com on 20 Nov 2009 at 8:10

[GoogleCodeExporter]

So, I'm looking into changing this (when using weakTieBreakMethod of "strong", 
this
method alone takes 50% of runtime for the pathological case we've been looking 
at). 
I can try to change it so that it just works one-for-one like it does now, but 
it
might help if I understood better how this method worked better.

Specifically, I'm confused by what nextClusterCount represents, and what the
comparison between s and it means.

Original comment by dan.keshet@gmail.com on 20 Nov 2009 at 10:57

[GoogleCodeExporter]

There's a lot of ways this method could be improved. We don't need to sort all 
the
continuing candidates; we could just successively call a method like
findTiedCandidates to get the next cluster.  

But that's not really necessary.  99% of the time, this method is being called 
from
isSurplusToTransfe(), which really just needs to know if there are any sure 
losers.

So, I suggest the creation of a method hasSureLosers(), which just shortcuts to
answering that question.  I've tried to create it myself, but I'm still a bit
confused as to how to do that.

Original comment by dan.keshet@gmail.com on 21 Nov 2009 at 3:50

[GoogleCodeExporter]

For real elections, the number of votes will be much larger than the number of 
candidates so this optimization is not effective for the typical use case.  Not 
worth complicating the code for the unusual case where the number of candidates 
is large relative to the number of ballots.

Original comment by jeff.oneill on 8 Jan 2011 at 5:00

• Changed state: WontFix

[GoogleCodeExporter]

For real elections, the number of votes will be much larger than the number of 
candidates so this optimization is not effective for the typical use case.  Not 
worth complicating the code for the unusual case where the number of candidates 
is large relative to the number of ballots.

Original comment by jeff.oneill on 8 Jan 2011 at 5:40