-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 を超えるリスト エントリが 1 つのスコアに関連付けられる可能性がある場合、非常にタイトになります。ただし、スコアの分布はおそらく均等ではありません。
  • タイムスタンプに実際に必要なビット数は?
  • タイムスタンプから最上位ビットを破棄できますか? たとえば、すべての時間が 2001 年以降になることがわかっている場合は、タイムスタンプを 1970 年ではなく 2001 年に基づいて作成すると、1 ビット増加します。[編集: タイムスタンプを変更したようです。元のように 1970 年以降の秒のようには見えなくなりました]
  • タイムスタンプから重要度の低いビットを破棄できますか? サンプル データでは、1 秒しか離れていないタイムスタンプがありますが、これは現実的ですか? スコアとタイムスタンプが両方とも等しい 2 つの行がある場合はどうなるでしょうか。おそらくそれは世界の終わりではありません。1 秒のギャップが可能であれば、0 秒のギャップも可能だと思います。次に、たとえば、すべてのタイムスタンプを最も近い 32 秒に丸めると、5 ビットを得ることができますが、デッド タイが増えるという犠牲を払います。
  • タイムスタンプには、エポックからの実際の時間 (秒単位) の代わりに、スコアが入るたびに 1 ずつ増加する値を使用できますか? もしそうなら、潜在的に多くのビットを節約できます。サンプル データを (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 ビット整数でこれを行うことについて、いくつかの考えを共有できると思いました。

まず、これらの数値を最初にスコア順、2 番目に時間順に並べ替えるには、スコアが高い値の場所を占め、タイムスタンプが低い場所を占めるようにします。スコアをより高い値の場所に配置するには、一定の係数を掛ける必要があります。符号なし 32 ビット整数で表現できる最大数は 4,294,967,295 で、スコア範囲は 0 から 1,000,000 です。これにより、乗数は 4,294 になります。

次に、タイムスタンプが占有する値の小さい位置を取得します - それを追加するだけです。これにより、次のようになります。

N = SCORE * 4294 + TIMESTAMP;

逆変換は次のとおりです。

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

ただし、これが許容する範囲TIMESTAMPは 0 ～ 4293 であることに注意してください。Nそれ以上のものは、 によって占有されている の部分にオーバーフローしSCOREます。を単純な秒数 (最も古いスコアの4293TIMESTAMPからカウントダウン) とすると、最も古いスコアから最新のスコアまでの最大時間は 71 分強しかなく、おそらく不十分です。

これは、32 ビット整数で表現できるさまざまなバケットの数の制限にすぎません。このモデルでより明確なタイムスタンプを表現できるようにするには、表現できる個別のスコアの数を減らす必要があります。

ただし、タイムスタンプをタイムスタンプとして実際に必要としているわけではないことに注意してください。スコアの単調な順序としてのみ必要です。別の方法として、カウンターを保持することもできます。カウンターを 4293 に初期化します。新しいスコアが入ってきたら、カウンターの現在の値を「タイムスタンプ」として保存し、カウンターをデクリメントします。これにより、カウンターがなくなる前に 4294 の異なるハイスコアを保存できます。

さらなる改良として、同じSCORE値内の順序のみを気にすることに注意してください。これは、別の代替案を示唆しています。新しいハイ スコアが表示されたら、そのスコアの現在の最低 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 に答える