Генерация уникального идентификатора в c ++

Question

Каков наилучший способ создания уникального идентификатора из двух (или более) коротких целых в C ++? Я пытаюсь однозначно идентифицировать вершины в графе. Вершины содержат от двух до четырех коротких вставок в качестве данных, и в идеале идентификатор должен быть своего рода хэшем. Предпочитают мобильность и уникальность по скорости или легкости.

Здесь много хороших ответов, сегодня вечером я попробую их все, чтобы понять, что лучше всего подходит для моей проблемы. Еще несколько слов о том, что я делаю.

График представляет собой набор образцов из аудиофайла. Я использую график в качестве цепи Маркова для создания нового аудиофайла из старого файла. Поскольку каждая вершина хранит несколько выборок и указывает на другую выборку, а все выборки являются короткими целыми числами, казалось естественным генерировать идентификатор из данных. Объединение их в длинные и длинные звучит хорошо, но, может быть, все, что мне нужно, - это просто 0 1 2 3 generateID. Не знаете, сколько места необходимо для обеспечения уникальности, если в каждой вершине хранятся 2 16-битных выборки, существует ли 2 ^ 32 возможных правильных комбинаций? и так, если каждая вершина хранит 4 выборки, есть 2 ^ 64 возможных комбинаций?

Решения для конкретных библиотек и платформ, не относящиеся к данному вопросу. Я не хочу, чтобы кому-то другому, кто мог бы скомпилировать мою программу, пришлось загружать дополнительные библиотеки или изменять код в соответствии с их ОС.

Answer 1

Иногда самые простые вещи работают лучше всего.

Можете ли вы просто добавить поле id в объект Vertex и назначить ему номер в порядке построения?

static int sNextId = 0;
int getNextId() { return ++sNextId; }

Answer 2

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

Итак, вот какой-то наполовину код для этого. Надеюсь, у меня все получилось.

uint64_t generateId( uint16_t v1, uint16_t v2, uint16_t v3, uint16_t v4)
{ 
   uint64_t id;
   id = v1 | (((uint64_t)v2) << 16) | (((uint64_t)v3) << 32) | (((uint64_t)v4) << 48);
   return id;
}

При желании это можно сделать с помощью союза (отличная идея от Леона Тиммерманса, см. Комментарий). Очень чисто так:

struct vertex
{
    uint16_t v1;
    uint16_t v2;
    uint16_t v3;
    uint16_t v4;
};

union vertexWithId
{
    vertex v;
    uint64_t id;
};

int main()
{
    vertexWithId vWithId;
    // Setup your vertices
    vWithId.v.v1 = 2;
    vWithId.v.v2 = 5;

    // Your id is automatically setup for you!
    std::cout << "Id is " << vWithId.id << std::endl;
    return 0;
}

Answer 3

Если вы создаете хеш-таблицу для хранения своих вершин, я могу придумать несколько способов избежать коллизий:

1. Генерируйте идентификаторы непосредственно из входных данных, не выбрасывая биты, и используйте хеш-таблицу, которая достаточно велика, чтобы вместить все возможные идентификаторы. С 64-битными идентификаторами последнее будет чрезвычайно проблематичным: вам придется использовать таблицу, которая меньше вашего диапазона идентификаторов, поэтому вам придется иметь дело с коллизиями. Даже с 32-разрядными идентификаторами вам потребуется более 4 ГБ ОЗУ, чтобы справиться с этим без коллизий.
2. Генерация идентификаторов последовательно, как вы читаете в вершинах. К сожалению, это делает очень дорогим поиск ранее прочитанных вершин для обновления их вероятностей, поскольку генератор последовательных идентификаторов не является хеш-функцией. Если объем данных, используемых для построения цепочки Маркова, значительно меньше, чем объем данных, которые используются для цепочки Маркова (или если они оба малы), это может не быть проблемой.

В качестве альтернативы вы можете использовать реализацию хеш-таблицы, которая обрабатывает коллизии для вас (например, unordered_map / hash_map ), и сосредоточиться на остальной части вашего приложения.

Answer 4

Если вы работаете в Windows, вы можете использовать CoCreateGUID API, в Linux вы можете использовать / proc / sys / kernel / random / uuid, вы также можете посмотреть 'libuuid'.

Answer 5

Определение «ID» в вопросе не совсем понятно: нужно ли его использовать в качестве ключа для быстрого поиска по вершинам? Вы можете определить компаратор для std::map (см. Пример ниже)

Вам нужно уметь различать два объекта Vertex с одинаковыми координатами (но разными в другом поле)? Определите некоторую «фабрику идентификаторов» (см. Шаблон синглтона), которая генерирует, например, последовательность целых чисел, не связанная со значениями объектов Vertex. - Многое из того, что предлагает Fire Lancer (но остерегайтесь вопросов безопасности потоков!)

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

Как только вы определили ' строгий слабый порядок ' для этого типа, вы можете использовать его в качестве ключа, например, std::map,

struct Vertex {
  typedef short int Value;
  Value v1, v2;

  bool operator<( const Vertex& other ) const {
    return v1 < other.v1 || ( v1 == other.v1 && v2 < other.v2 ) ;
};

Vertex x1 = { 1, 2 };
Vertex x2 = { 1, 3 };
Vertex y1 = { 1, 2 }; // too!

typedef std::set<Vertex> t_vertices;

t_vertices vertices;
vertices.insert( x1 );
vertices.insert( x2 );
vertices.insert( y1 ); // won't do a thing since { 1, 2 } is already in the set.

typedef std::map<Vertex, int> t_vertex_to_counter;
t_vertex_to_counter count;
count[ x1 ]++;
assert( count[x1] == 1 );
assert( count[y1] == 1 );
count[ x2 ]++;
count[ y1 ]++; 
assert( count[x1] == 2 );
assert( count[y1] == 2 );

Answer 6

Если вы предпочитаете переносимость, то boost :: tuple это хорошо:

Вы хотите кортеж из 4 предметов:

typedef boost::tuple<uint16,uint16,uint16,uint16> VertexID;

Вы можете назначить так:

VertexID id = boost::make_tuple(1,2,3,4);

У буст-кортежа уже есть поддержка сравнения, равенства и т. Д., Поэтому его легко использовать в контейнерах и алгоритмах.

Answer 7

с манжеты, я бы сказал, использовать простые числа,

id = 3 * value1 + 5 * value2 + .... + somePrime * valueN

Убедитесь, что вы не переполняете свое пространство идентификаторов (долго? Долго?). Поскольку у вас есть фиксированное количество значений, просто обоснуйте несколько случайных простых чисел. Не беспокойтесь о создании их, в списках их достаточно, чтобы вы могли работать некоторое время.

Я немного отрывочен в доказательстве, хотя, может быть, кто-то более математический может меня зацепить. Вероятно, имеет отношение к уникальной простой факторизации числа.

Answer 8

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

((long long) shortNumberX) << 0, 4, 8 или 12 </p>

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

Редактировать: забыли добавить, вы должны ИЛИ их вместе.

Answer 9

Ну, единственный способ гарантировать, что идентификатор уникален, это сделать так, чтобы у вас было больше комбинаций идентификаторов, чем у ваших идентификаторов, полученных из

например, для 2 шорт (при условии 16 бит), вы должны использовать 32-битный int

int ID = ((int)short1 << 16) | short2;

и для 4-х шорт вам понадобится 64-битное int и т. Д. *

Практически все остальные коллизии (несколько вещей могут получить один и тот же идентификатор) в значительной степени гарантированы.

Однако другой подход (который, я думаю, был бы лучше) для получения идентификаторов заключался бы в выдаче их при вставке вершин:

unsigned LastId = 0;//global

unsigned GetNewId(){return ++LastId;}

Это также позволяет вам добавлять больше / разные данные к каждой вершине. Однако, если вы ожидаете создать более 2 ^ 32 вершин без сброса, это, вероятно, не самый лучший метод.