4 ms·
For what it's worth, this is quite easy to compute in a way that works with any number of ties, and doesn't require computing the whole list in order. Your rank
by btrask 16y ago
For what it's worth, this is quite easy to compute in a way that works with any number of ties, and doesn't require computing the whole list in order. Your rank is the number of people above you plus one.
- Retric 16y agoI must be missing something. That's a N^2 operation on an unsorted list. ~N Log N if you sort it first. And N to insert a new entry to a sorted list.
- btrask 16y agoYes, it requires a sorted list, but so does the naïve implementation. The performance is equivalent to binary search to find the entry, although you then have to scan backwards to make sure you have the first entry with the same value. Since performance is probably not an issue for most rankings, the biggest benefit is a clear, easy to remember definition, which should reduce the chances of making the same mistake landhar did.
- Retric 16y agoIf you are inserting 3 into an indexed and sorted list (1,2,4,5) you can calculate the index of 3 in O(Log N). But you also need to update the index of 4, and 5 which is an O(N) operation.
- deleted 16y ago[deleted]