Способ представления списка топ-10 с прерывателями связей в виде единого числового значения

Question

У меня есть список 10 лучших с оценкой (наибольшее количество побед) и отметкой времени.

Отметка времени используется в случае ничейной оценки, и в этом случае выигрывает связанный результат с наименьшей отметкой времени.(первый человек, получивший более высокий балл).

Пример набора отсортированных данных:

20 102906755
15 102910755
14 102890755
14 102890756
13 102890756

Обратите внимание на связь с результатом 14, тот, который имеет меньшую временную метку, размещается выше.

Мне нужно представить в правильном порядке и счет, и метку времени как одно 32-битное значение.

Допустим, максимальный балл составляет 1 миллион.

Я уменьшил значение метки времени, вычтяпервая действительная оценка даты.

Как это может быть достигнуто в C?

Answer 1

Во-первых, если вам нужно представить более 2 ^ 32 различных комбинаций очков с отметкой времени, значит, игра окончена - это невозможно.

С учетом этого:

• сколько битов вам действительно нужно для оценки?Если максимальный балл составляет 1 миллион, вам понадобится 20 бит для этого, что для равномерного распределения оставляет только 12 для метки времени.Это будет очень сложно, особенно , если возможно иметь более 2 ^ 12 = 4000 записей в списке, привязанных к одному баллу, хотя распределение баллов предположительно даже не .
• сколько битов вам действительно нужно для метки времени?
• можете ли вы отбросить наиболее значимые биты из метки времени?Например, если вы знаете, что все время будет после 2001 года, вы можете использовать временную метку с 2001 года вместо 1970 года, что дает вам 1 бит.[Редактировать: вы, кажется, изменили метки времени, они больше не выглядят как секунды с 1970 года, как они изначально делали]
• Можете ли вы отбросить менее значимые биты из метки времени?В вашем примере данных у вас есть временные метки, которые разнесены всего на 1 с, но это реально?Что если у вас есть две строки, в которых оценка и отметка времени равны?Предположительно, это не конец света: если возможен разрыв в 1 с, то я думаю, что возможен разрыв в 0.Затем, например, если вы округлите все метки времени до ближайших 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 бита в вашей реализации, что почти универсально.]

Answer 2

Несмотря на то, что вы впоследствии говорили, что на самом деле у вас есть 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 включительно.Все, что выше, переполнилось бы частями N, занятыми SCORE.Если TIMESTAMP - это просто число секунд (начиная с 4293 для самого раннего счета и обратного отсчета), это дает нам максимальное время, составляющее чуть более 71 минуты от самого раннего счета до самого последнего - вероятно, недостаточно.

Это просто ограничение на количество различных сегментов, которые вы можете представить с помощью 32-битного целого числа - чтобы иметь возможность представлять более четкие временные метки с помощью этой модели, вам нужно уменьшить количество отдельных показателей, которые вы можете представить.

Однако, обратите внимание, что мы не хотим, чтобы временная метка была временной меткой - мы просто хотим, чтобы она была монотонной, упорядоченной по счетам.В качестве альтернативы мы можем сохранить счетчик.Инициализируйте счетчик 4293. Когда появится новый счет, сохраните его с текущим значением счетчика в качестве его «метки времени», затем уменьшите счетчик.Это позволит сохранить 4294 различных рекорда до того, как счетчик закончится.

В качестве дальнейшего уточнения, мы можем отметить, что нас интересует только порядок в пределах того же значения SCORE .Это предлагает другую альтернативу: когда приходит новый высокий балл, найдите текущее самое низкое значение TIMESTAMP для этого балла.Уменьшите его на 1 и используйте для «отметки времени» нового счета (если это первый раз, когда было отправлено это SCORE, используйте 4293 в качестве отметки времени).Это позволит получить 4294 балла за отдельное значение.

Answer 3

Допустим, вы собирались использовать значения без знака, и ваш максимальный балл был 31.

Вы можете использовать верхние 5 бит для оценки и младшие 27 для отметки времени.

Обратите внимание, что это ограничивает пределы обоих значений, поэтому вы должны учитывать возможные значения и то, что вы будете делать, если попытаетесь использовать значения вне этого диапазона.

В магазин ...

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

А чтобы позже получить значения:

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

Обратите внимание, что вы хотите проверить счет и отметку времени перед их использованием и, возможно, применить маски, чтобы убедиться, что значения не перекрываются.

Редактировать

Riderchap делает хорошую мысль. Метки времени, которые вы приводите в качестве примера, были бы слишком большими, чтобы использовать их с 32-битным целым числом. Мой ответ - скорее демонстрация того, как это сделать в принципе.

Answer 4

В зависимости от старшей оценки вам нужно будет переключать количество бит для сдвига.Давайте предположим, что максимальная оценка 255, что дает нам сдвиг в 8 бит.

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

Это может отрезать MSB времени, но если вы не ожидаете связи сразница в несколько лет, ты будешь в порядке.Он инвертирует счет и размещает его в старших 8 битах, затем объединяет его со временем в младших 24-х. Наименьшим значением будет максимальный балл (инвертированный высокий балл = самый низкий балл и самая низкая временная метка).