-1

我有一个带有分数（最高分获胜）和时间戳的前 10 名列表。

时间戳用于平分的情况，在这种情况下，时间戳最低的平分获胜（第一个获得分数的人排名更高）。

排序数据集示例：

20 102906755
15 102910755
14 102890755
14 102890756
13 102890756

注意得分 14 的平局，时间戳较小的得分较高。

我需要以正确的顺序将分数和时间戳表示为单个 32 位值。

假设最高分数为 100 万。

我通过减去第一个有效日期分数来减少时间戳值。

这如何在 C 中实现？

4

4 回答 4

2

第一件事是，如果有超过 2^32 种不同的得分和时间戳组合需要表示，那么游戏就结束了 - 无法完成。

考虑到这一点：

  • 你真的需要多少位来得分？如果最高分数为 100 万，则需要 20 位，这允许均匀分布，仅留下 12 位用于时间戳。这将非常紧张，特别是如果可能有超过 2^12 = 4000 个列表条目绑定在一个分数上，尽管分数分布可能不均匀。
  • 时间戳你真的需要多少位？
  • 你能从时间戳中丢弃最重要的位吗？例如，如果您知道所有时间都在 2001 年之后，那么您可以基于 2001 年而不是 1970 年的时间戳，这样可以获得 1 位。[编辑：您似乎已经更改了时间戳，它们不再像 1970 年以来那样看起来像原来那样的秒数]
  • 你能从时间戳中丢弃不太重要的位吗？在您的示例数据中，您的时间戳仅相隔 1 秒，但这是现实的吗？如果你有两行分数和时间戳都相等怎么办？大概这不是世界末日：如果 1s 的差距是可能的，那么我想 0s 的差距是可能的。然后，例如，如果您将所有时间戳四舍五入到最接近的 32 秒，那么您可以获得 5 位，但代价是引入更多死结。
  • 对于时间戳，您是否可以使用每次得分时增加一次的值，而不是自纪元以来的实际时间（以秒为单位）？如果是这样，那么您可能会节省很多位。您能否对每个可能的分数使用不同的递增值，将示例数据转换为 (20, 0)、(15, 0)、(14, 0)、(14, 1)、(13, 0)？
  • 你可以使用 >32 位的值吗？

如果其中任何一个的答案都很好，那么也许这是可能的。如果答案都不好，那么根本不可能做你想做的事。

[编辑：考虑到以下评论，您的新问题的答案是：

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

容易得多。直到公元 2242 年为止都很好。

这个假设double在您的实现中是 64 位，这几乎是通用的。]

于 2010-12-18T01:42:30.800 回答
1

假设您要使用无符号值，而您的最高分是 31。

您可以使用前 5 位作为分数，使用低 27 位作为时间戳。

请注意，这限制了这两个值的限制，因此您必须考虑可能的值以及如果您尝试使用该范围之外的值会做什么。

储藏...

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

稍后获取值：

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

请注意，尽管您想在使用它们之前检查分数和时间戳，并且可能会应用掩码以确保值不重叠。

编辑

Riderchap 提出了一个很好的观点。您作为示例提供的时间戳太大而无法与 32 位整数一起使用。我的回答更多的是在原则上演示如何做到这一点。

于 2010-12-18T01:32:16.377 回答
1

尽管您后来说您实际上有一个double可用的存储信息，但我想我可能仍然会分享一些关于使用 32 位整数执行此操作的想法。

首先，为了让这些数字按得分顺序排列，时间顺序排在第二位，您希望得分占据较高值的位置，而时间戳占据较低的位置。要将分数放在较高值的位置，我们必须选择一个将它乘以某个常数因子。可以用无符号 32 位整数表示的最大数字是 4,294,967,295 ，我们的分数范围是 0 到 1,000,000。这给了我们 4,294 的乘数。

然后我们得到时间戳占据的较低值位置 - 只需将其添加进去。这给了我们：

N = SCORE * 4294 + TIMESTAMP;

反向转换为：

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

但是，请注意，这允许的范围TIMESTAMP是 0 到 4293（包括 0 到 4293）。任何更高的东西都会溢出到N被SCORE. 如果TIMESTAMP只是几秒钟（从 4293 开始的最早得分并倒计时），这只会给我们从最早得分到最新得分的最大时间超过 71 分钟 - 可能不够。

这只是对您可以用 32 位整数表示的不同存储桶数量的限制 - 为了能够使用此模型表示更多不同的时间戳，您需要减少可以表示的不同分数的数量。

但是，请注意，我们并不真正希望时间戳作为时间戳 - 我们只是希望它作为分数的单调排序。作为替代方案，我们可以保留一个柜台。将计数器初始化为 4293。当有新分数进入时，将其与计数器的当前值一起存储为它的“时间戳”，然后递减计数器。这将允许在计数器用完之前存储 4294 个不同的高分。

作为进一步的改进，我们可以注意到我们只关心相同SCOREvalue内的排序。这提出了另一种选择：当出现新的高分时，找到该分数的当前最低 TIMESTAMP 值。将其减 1，并将其用作新分数的“时间戳”（如果这是第一次SCORE提交，则使用 4293 作为时间戳）。这将允许每个个人得分值 4294 高分。

于 2010-12-18T02:31:05.500 回答
0

根据高分，您需要切换要移位的位数。让我们假设最高分数为 255，这给了我们 8 位的移位。

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

这可能会切断 MSB 的时间，但除非你期待一个相差几年的领带，否则你会没事的。它将分数反转并将其放置在前 8 位中，然后将其与低 24 位中的时间相结合。最小值将是最高分数（反转的高分=最低分数和最低时间戳）。

于 2010-12-18T01:35:15.080 回答