How should tie-breaking be done when finding winning columns



Please review:

I have two questions:

  1. How should these ties be broken?
  2. How are our implementations actually doing it today?


I’ve answered these questions in the issue here (at least for the Python imp.).


My confusion stems from @cogmission’s comment that the C++ version does tie-breaking differently. I know there have been changes to tie-breaking logic in the not-so-distant past. I just want to ensure that we agree what the method should be, and that it is implemented in that way for all implementations we control.

Seems like one method is for winning columns to be inserted in the front of the tie queue and a line is drawn in the queue based on how many winning columns are needed. Is that the method we want to use everywhere? Is that what is happening in python and java as well?

Thanks for helping me clarify. This may be a non-issue, but I just want to make sure that we are using the same logic in all places. I think my confusion may just be that is a duplicate of


It looks like while they go about it very differently, they are in fact doing the same thing, which is sorting the indexes of where the overlaps are found, in descending order (indexes of highest to lowest overlap scores). The Java version (with the new PR), does exactly the same thing - although yet again differently - which is not a big deal due to language best practices.

The questions that still remain are:

  1. I think everyone agrees on this, but it is still hanging around - and that is, should the old unused tie-breaker code be removed?

  2. Should there be some ancillary code to make tie-breaking more determinate? @alavin made the comment that Python’s argsort may not handle ties gracefully (i.e. indeterminate unpredictable tie resolution?)

  3. If the consensus for #2 is “Yes”, then how should the ancillary tie code be implemented? Should we use @alavin’s suggested code here?
    Alex, I have some questions about the code you proposed, but that’s another topic for discussion once we get this far.


Yes it should. is ready for work, and I’m going to mark as a duplicate.


It’s determinate, always preferring the later indices, e.g.:

>>> import numpy as np
>>> values = np.array([3, 0, 0, 1, 3, 7, 0, 3])
>>> np.argsort(values)[::-1]
array([5, 7, 4, 0, 3, 6, 2, 1])  # ties between the values 3 are handled by using the reverse order

The mechanism I suggested breaks ties randomly:

>>> randomValues = numpy.random.random(len(overlaps))
>>> np.lexsort((randomValues, values))[::-1]
array([5, 4, 7, 0, 3, 2, 1, 6])  # compare to the argsort example



Even if we don’t use this solution due to Subutai’s comments on the PR - this was still a very nice suggestion and very good “teaching moment” for me being a Python noob! Thank you, Alex! :wink:

(…and yes, I’ve upgraded my status from Python despiser, to Python noob, I’m actually starting to like it a bit!) :smile:


I’m glad you enjoy my pythonic preaching @cogmission.
For more great tips and tricks I highly recommend “Effective Python”.