Way to represent a top 10 list with tie breakers as a single numerical value_问答_开发者

I have a top 10 list with a score (highest score wins) and a timestamp.

The timestamp is used in the case of a tie score, in which case the tied score with the lowest timestamp wins (first person to achieve the score places higher).

Sorted data set example:

20 102906755
15 102910755
14 102890755
14 102890756
13 102890756

Notice the tie on score 14, the one with the smaller timestamp is placed higher.

I need to represent with proper ordering both the score and timestamp as a single 32bit value.

Assume the maximum score is 1 million.

I have reduced the timestamp value by subtracting the first valid date score.

How might this be accomplis开发者_StackOverflowhed in C?

First thing is that if there are more than 2^32 different combinations of score with timestamp that you need to represent then it's game over - can't be done.

With that in mind:

how many bits do you really need for the score? If the max score is 1 million you need 20 bits for that, which allowing for an even distribution leaves only 12 for the timestamp. This is going to be very tight, especially if it's possible to have more than 2^12 = 4000 list entries tied on a single score, although score distribution presumably isn't even.
how many bits do you really need for the timestamp?
can you discard most-significant bits from the timestamp? For example, if you know that all times will be after 2001 then you could base the timestamp from 2001 instead of 1970, which gains you 1 bit. [Edit: you seem to have changed the timestamps, they no longer look like seconds since 1970 as they originally did]
can you discard less-significant bits from the timestamp? In your example data you have timestamps which are only 1s apart, but is this realistic? What if you have two lines where the score and the timestamp are both equal? Presumably it's not the end of the world: if a 1s gap is possible then I imagine a 0s gap is possible. Then for example, if you round all timestamps to the nearest 32s then you can gain 5 bits, at the cost of introducing more dead ties.
for the timestamp, can you use a value that's incremented once each time a score comes in, instead of an actual time in seconds since epoch? If so then you can potentially save a lot of bits. Can you use a different incrementing value for each possible score, transforming your example data into (20, 0), (15, 0), (14, 0), (14, 1), (13, 0)?
can you use a >32 bit value?

If the answers to any of those are good, then perhaps it's possible. If the answers are all bad, then it's simply not possible to do what you want.

[Edit: the answer to your new question, taking into account the comment below, is:

double value = (double) score - ((double)timestamp) / (((long long)1) << 33);

Much easier. It's good until 2242AD.

This assuming double is 64 bits on your implementation, which is almost universal.]

Let's say you were going to use unsigned values, and your maximum score was 31.

You could use the top 5 bits for the score, and the lower 27 for the timestamp.

Note that this constrains the limits of both values, so you must consider the possible values and what you will do if you try to use values outside of that range.

To store...

composite = ~(score << 27) | timestamp;

And to later get the values:

#define TIMESTAMP_BITS ((1 << 27) - 1)
score = composite >> 27;
timestamp = composite & TIMESTAMP_BITS;

Please note though that you want to check the score and timestamp before using them, and probably apply masks to be sure the values do not overlap.

Edit

Riderchap makes a good point. The timestamps you give as an example would be too large to use with a 32 bit integer. My answer is more of a demonstration of how to do this in principle.

Although you've subsquently said that you actually have a double available to store the information, I thought I might still share some thoughts on doing this with a 32 bit integer.

Firstly, in order to have these numbers sort in score order first and time order second, you want the score to occupy the higher value places and the timestamp to occupy the lower. To place the score in the higher value places, we must pick a multiply it by some constant factor. The largest number that can be represented by an unsigned 32 bit integer is 4,294,967,295 , and we we have a score range of 0 to 1,000,000. This gives us a multiplier of 4,294.

We then have the lower-value positions occupied by the timestamp - just need to add that in. This gives us:

N = SCORE * 4294 + TIMESTAMP;

The reverse conversions are:

SCORE = N / 4294;
TIMESTAMP = N % 4294;

However, note that the range this allows for the TIMESTAMP is 0 to 4293 inclusive. Anything higher would overflow into the parts of N occupied by the SCORE. If TIMESTAMP is simply a number of seconds (starting at 4293 for the earliest score and counting down), this only gives us a maximum time of just over 71 minutes from the earliest score to the latest - probably insufficient.

This is simply a limit on the number of different buckets you can represent with a 32 bit integer - to be able to represent more distinct timestamps with this model, you need to reduce the number of distinct scores you can represent.

However, note that we don't really want the timestamp as a timestamp - we just want it as a monotonic ordering on the scores. As an alternative, we can keep a counter. Initialise the counter to 4293. When a new score comes in, store it with the current value of the counter as its "timestamp", then decrement the counter. This will allow 4294 distinct highscores to be stored before the counter runs out.

As a further refinement, we can note that we only care about the ordering within the same SCORE value. This suggests another alternative: when a new high score comes in, find the current lowest TIMESTAMP value for that score. Decrement it by 1, and use that for the "timestamp" of the new score (if this is the first time that this SCORE has been submitted, use 4293 as the timestamp). This will allow 4294 high scores per individual score value.

Depending upon the high score, you would need to switch the number of bits to shift. Lets assume a max score of 255, which gives us a shift of 8 bits.

unsigned int combined = ~(score << 32-8) | (time & 0x0FFF);

That might cut off the MSB of time, but unless you're expecting a tie with a few years difference, you'll be fine. It inverts the score and places it in the top 8 bits, then it combines it with the time in the lower 24. The smallest value will be the top score (inverted high score=lowest score and lowest timestamp).