Универсальный короткий id
 

Возникла ситуация:

нужно создавать максимально короткие id к данным. Причем делать это нужно как можно более экономично (в плане ресурсов).

id имеет малый период жизни, а количество одновременно живущих id может достигать 1000-3000






Как я думаю это сделать:

Решил использовать base36 в качестве генерации уникальных id.
Значения id будет от 1 до 4-х символов (то есть короткие!), при этом диапазон значений весьма неплохой - 1679615 !

// возвращает уникальный короткий ID в заданном числовом диапазоне
function getRandomID(min, max) {
  var int = Math.floor(Math.random() * (max - min + 1)) + min;

  return int.toString(36);
}

var id = getRandomID(0, 1679615);

alert(id);

Конечно данный id может оказаться уже задействованным (среди тех активных 1000-3000 айдишников), поэтому нужно проверять перед использованием! Но такая вероятность ничтожна в случае с 3000 id - вероятность 1 на 559




А как бы вы это делали?

dmitry111,
а если сгенерировать 1 раз 5000 уникальных и потом пользоваться ?

dmitry111,
А тупо инкрементировать старый id?

забыл уточнить, они (айдишники) то появляются то удаляются

3000 айдишников перебирать каждый раз - это затратно!

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

Если предположить, что игроков 20, а пули вылетают у каждого игрока примерно 30 пуль в секунду, получается 600 id в секунду

Каждая пуля (id) имеет время жизни, например 3 секунды, то есть 1800 id - одновременно активны!

dmitry111,
зачем перебирать ? берёшь всегда первый id из 5000 -- возвращаешь на последнее место

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

function getId() {
        var i = 0;
        return function () {
          i += 1;
          return 'id' + i;
        }
      }
      var newId = getId();
      alert (newId());
      alert (newId());

Poznakomlus,
вот и я говорю нужно инкрементировать, или вообще

var nonce = Date.now()
alert(nonce)

а я 5400 насчитал :)

alert(Date.now() === Date.now());

[quote=nerv_;316696]а я 5400 насчитал :)

да, на ходу писал, забыл на три умножить)

да, Date.now() - то что нужно!

Poznakomlus,

за 3 cекунды эта функция будет возвращать id с индексом более 5000! Нужно либо обнулять, либо уменьшать.

Важны именно короткие id!

ну эт смотря для какой задачи) (про пули не прочитал прост)

а как ты хотел, если у тебя
элементов может находится?

<script>
  function next() {
    var max = 9999,
      i = -1;
    return function () {
      i = i < max ? i + 1 : 0;
      return i;
    }
  }
  var new_id = next();
  alert(new_id());
  alert(new_id());
</script>

после 9999, отсчет с нуля начнется

вот это вот как-то озадачило)

По логике должен быть false!
Есть ли вероятность того, что будет true если использовать Date.now() не в прямом сравнении?

забыл почему меня этот вариант не устроил)

у меня по такому принципу игроки создаются, а пули почему-то так делать не захотел))





Вот почему:
Я просто не хочу привязывать данные к относительным величинам!
То есть игроков может быть 20, а может быть и 10, а может быть и 50))

Я даже для игроков не ограничивал лимит и выставлял первый свободный номер:

// подбирает gameID
  function getGameID() {
    var gameID = 0;

    while (this._users[gameID]) {
      gameID += 1;
    }

    return gameID;
  }

Тот вариант, который я изложил в начале (с base 36), меня тоже не устраивает, кстати!

Пересмотри реализацию логики в этом случае. Или описывай детально, что где и как, вплоть до серверного обеспечения
php spl_object_hash

Почему ты просто не создашь переменную равную 0, и тупо не будешь ее постоянно инкрементировать каждый раз присваивая пуле id
так всех зайцев убьешь, и на тебе плюхи от Date.now() и нет проблемы с сравнением и в конце можно пули выстрелленые посчитать и тд

нафига какое то ограничение? закончилась сессия обнулил, и усе

Ну да рандом не нужен. К моменту когда будут использованы последние айдишники - первые уже по любом должны освободиться.

getId = function(id){
    return function(){
        return (++id[0]).toString(36)
    }
}(new Uint16Array(0))

65536 значений))

у меня node.js

а если сессия будет полчаса))

Aetae,
да, как вариант.


Но не хотел бы использовать какие-то лишние данные - это может в будущем создать проблемы! Значения 1679615, 65536, 9999 - делают код нелогичным, не хотелось бы так делать)

Тебе же понравилась дата)) там большие числа

60 * 60 = 3600 если одна пуля в секунду за час, соответсвенно 360000 если каждый из 100 человек выстрелит в секунду.... это много что ли?))

"65536 хватит на всех", ага.)
Ну можно впихнуть Uint32 - 4294967295 то точно хватит, только тут 4мя символами не ограничишься.)
Только вот подход с рандом не имеет ни малейшего преимущества перед подобными итераторами.

С чем связано ограничение по длине id? Скорость доступа к id = a111 меньше, чем к id=a999938? На сколько?

Похоже на экономию на спичках. Видится мне, что тормоза в игре будут связаны с чем-то другим, но не с генерацией id или их длинной. Хотя мне не понятно зачем генерить id, если можно брать их из диапазона?

Это связано с весом данных, которые передаются по сети.
Думаю, максимальная длина id не должна превышать 3-х символов!

В base 36 3 символа дают 1679616 различный айдишников

а юзать точно так же итерацию. например есть idшки:
999111
999112
999113
999114
999115

Возьми допустим из этого большого числа 9991 и отправь на сервер как префикс,
а потом мелкими пачками посылай
15 16 17 18 19... 99
потом отправляешь новый 9992 и заного
00 01 02 03 04 05
Все будет удобно упорядчено

Хотя я кажется упорот

l-liava-l,

зачем так усложнять? )

Гораздо проще:

999111 .toString(36) // 'lex3'
999112 .toString(36) // 'lex4'
999113 .toString(36) // 'lex5'
999114 .toString(36) // 'lex6'

Массив пуль, добавляем в конец, берем с конца. Никаких переборов, никакого поиска и рандомной генерации. Пули генерятся в начале боя в массив.

Скорость работы с концом массива не знаю. Стек
Увеличиваем стек, увеличивается количество игроков.