Форум программистов, компьютерный форум CyberForum.ru

Быстрый способ получение уникального ID - C++

Восстановить пароль Регистрация
 
-NEURON-
Заблокирован
27.08.2014, 18:34     Быстрый способ получение уникального ID #1
Есть какой - то список уже существующих уникальных ID, нужно наибыстрейшим способом создать новый уникальный для этого списка ID. (пусть тип ID будет допустим unsigned int)
1. В каком виде лучше хранить список переменной длинны всех уникальных ID ? std::map ?
2. Каким наибыстрейшим способом можно сгенерить уникальный ID ? Если map - ну там всё просто, но сдаётся мне, что это не наибыстрейший способ... Может хранить всё в std::vector, а во время генерации проверять std::binary_search-ем наличие ID в списке и если такого нет - добавлять, если есть - генерить заново ...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
27.08.2014, 18:42     Быстрый способ получение уникального ID #2
Завести счётчик, скажем, unsigned int. Каждый раз, когда нужен новый ID, брать его значение и увеличивать на единицу. Первые 4 миллиарда ID, выданных таким счётчиком, будут уникальными. Если "малавата будет", есть long long, это ещё в 4 миллиарда раз больше. Если изначально докрутить его до числа, на 1 большего из всех существующих ID, можно как-то к ним приспособиться.
В смысле поиска самым быстрым будет unordered_map, у binary_search и map эквивалентная сложность поиска O(log N).
DrOffset
6423 / 3797 / 878
Регистрация: 30.01.2014
Сообщений: 6,585
27.08.2014, 18:49     Быстрый способ получение уникального ID #3
Цитата Сообщение от -NEURON- Посмотреть сообщение
список уже существующих уникальных ID, нужно наибыстрейшим способом создать новый уникальный для этого списка ID
Т.е. задача получить список уникальных ID исходя из другого списка уникальных ID?
y = f(x), где x старый ID, а y - новый? Так?

Цитата Сообщение от -NEURON- Посмотреть сообщение
1. В каком виде лучше хранить список переменной длинны всех уникальных ID ? std::map ?
Зависит от задачи. Как планируется этот список использовать?
Цитата Сообщение от -NEURON- Посмотреть сообщение
2. Каким наибыстрейшим способом можно сгенерить уникальный ID ? Если map - ну там всё просто, но сдаётся мне, что это не наибыстрейший способ...
Разве std::map что-то генерирует? std::map - это хранение и доступ, а не генерация.

Добавлено через 7 минут
Цитата Сообщение от Nick Alte Посмотреть сообщение
В смысле поиска самым быстрым будет unordered_map
Это зависит от характера данных. Если у нас ключи какие-нибудь длинные строки, для которых нет достаточно хорошей хэш-функции, то он запросто может оказаться не лучшим решением.

-NEURON-, нельзя выбирать быстрейшее решение абстрактно. Оно всегда привязано к задаче.
-NEURON-
Заблокирован
27.08.2014, 18:52  [ТС]     Быстрый способ получение уникального ID #4
Цитата Сообщение от DrOffset Посмотреть сообщение
Т.е. задача получить список уникальных ID исходя из другого списка уникальных ID?
нее - задача сгеннерить один новый id, которого ещё нет в списке уникальных id.
Цитата Сообщение от DrOffset Посмотреть сообщение
Разве std::map что-то генерирует?
ну у него ключ то уникален, чиста ради этого. Ну типа map .... count() > 1 - значит уже есть ...ну да не суть.
Цитата Сообщение от Nick Alte Посмотреть сообщение
Завести счётчик, скажем, unsigned int. Каждый раз, когда нужен новый ID, брать его значение и увеличивать на единицу.
Да, именно об это я конечно же сразу и подумал. Но в моём случае речь идёт и крутой клиент серверной системе, работающей нон стоп 10-и летиями. А самая засада в том, что вот есть этот список элементов, у каждого свой уникальный ID, я спокойно добавляю туда новые элементы инкрементом последнего ID как бы, но, из этого списка элементы могут удаляться (по одному, по несколько), то есть получается что освобождаются потенциальные номера для новых id и я подумал, может их тоже использовать ... Т.к. лет за 10 даже unsigned long long может исчерпаться, учитывая то, что в день может добавляться по 1000 новых id в систему ... Хотя я не считал - ща проверю на сколько хватит Просто сама мысль о том, что когда - то они закончатся - как то меня тревожит ...
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
27.08.2014, 18:58     Быстрый способ получение уникального ID #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от -NEURON- Посмотреть сообщение
Просто сама мысль о том, что когда - то они закончатся - как то меня тревожит ...
Тогда рекомендую сразу за компанию посчитать, когда закончатся 16 квинтиллионов чисел (1.6e19, на минуточку), выражаемых long long, при пиковой скорости выдачи ID.
-NEURON-
Заблокирован
27.08.2014, 18:58  [ТС]     Быстрый способ получение уникального ID #6
Хотя я тут подсчитал, даже если по миллиону новых ID в день добавлять, размера unsigned long long хватить больше чем на 50 миллиардов лет ))))))))))))))))))))))
Единственных косяк, программа x86, по этому на каждую операцию будет намного больше времени тратится, нежели на x64... Ща подсчитаю, на сколько мне unsigned int хватить
DrOffset
6423 / 3797 / 878
Регистрация: 30.01.2014
Сообщений: 6,585
27.08.2014, 19:05     Быстрый способ получение уникального ID #7
Цитата Сообщение от -NEURON- Посмотреть сообщение
Хотя я не считал - ща проверю на сколько хватит
При условии 64 разрядного счетчика это будет 50539024859478 лет, если считать, что в год добавляется 365000 записей.

Добавлено через 6 минут
Цитата Сообщение от -NEURON- Посмотреть сообщение
намного больше времени тратится, нежели на x64
Не придумывай
С целыми числами, даже если они в один регистр не помещаются, все равно операции очень быстрые. Тем более инкремент/декремент.
-NEURON-
Заблокирован
27.08.2014, 19:06  [ТС]     Быстрый способ получение уникального ID #8
Вот думал тут не гемороиться с инкрементами и всякими проверками ну уникальность, просто брать уникальный в каждую микросекунду ID, основывая на тайм штампе каком - нибуть, скажем 1970-го года... Ну считать, cколько микросекунд прошло с того года... Но тут дело в том, что на компе могут перевести время и привет
DrOffset
6423 / 3797 / 878
Регистрация: 30.01.2014
Сообщений: 6,585
27.08.2014, 19:15     Быстрый способ получение уникального ID #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от -NEURON- Посмотреть сообщение
Вот думал тут не гемороиться с инкрементами и всякими проверками ну уникальность
Ничего себе не геморроится. Так-то unix time (дада, тот, который с 1970) - это тоже целое число.

Добавлено через 7 минут
Цитата Сообщение от -NEURON- Посмотреть сообщение
ну у него ключ то уникален, чиста ради этого. Ну типа map .... count() > 1 - значит уже есть ...ну да не суть.
Если ты действительно собираешься хранить миллиарды значений, то любой контейнер и любой алгоритм будут сильно проседать при таком подходе (т.к. все они зависят от N).
Счетчик - это лучшее решение. Если он контролируется из одного места, скажем какой-нибудь менеджер соединений. Появился клиент, выдали ему следующий ID увеличив счетчик и т.д.
uptime 10 лет - это редкость невероятная, но допустим. За 10 лет ты не исчерпаешь возможностей, как ни крути. Там скорее уже железо на сервере будут менять, чем эти ID кончатся
-NEURON-
Заблокирован
27.08.2014, 19:19  [ТС]     Быстрый способ получение уникального ID #10
Вообще то, если говорить более конкретно, у меня в списке уникальных элементов - строки юникода, длинной до 100 символов максимум. Я просто думал дать каждой строке уникальный ID, и всю работу с элементами в системе вести по этому ID для уменьшения расхода памяти и увеличения скорости обработки (ну там сравнивание строк - тот или не тот элемент и тд)... Думаю забить на ID и ключом оставлять строку ...
DrOffset
6423 / 3797 / 878
Регистрация: 30.01.2014
Сообщений: 6,585
27.08.2014, 19:30     Быстрый способ получение уникального ID #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от -NEURON- Посмотреть сообщение
Я просто думал дать каждой строке уникальный ID, и всю работу с элементами в системе вести по этому ID для уменьшения расхода памяти и увеличения скорости обработки (ну там сравнивание строк - тот или не тот элемент и тд)... Думаю забить на ID и ключом оставлять строку ...
Эм, а куда делись миллиарды значений?
А вообще для строк - можно использовать хэширование. Тем более если известна максимальная длина, то есть надежда найти хорошую хэш-функцию и дело в шляпе. Как раз упомянутый выше unordered_set/map подойдет.

Добавлено через 2 минуты
Вот, ознакомься.

Добавлено через 1 минуту
И вот, практика.
-NEURON-
Заблокирован
27.08.2014, 19:34  [ТС]     Быстрый способ получение уникального ID #12
Ща покурю мануал по - поводу unordered map-а, т.к. в повседневных задачах кроме vecot-а и простого map-а (ну не считая всяких стрингов) особо ничего не приходилось использовать, вот реально - хватало.
DrOffset
6423 / 3797 / 878
Регистрация: 30.01.2014
Сообщений: 6,585
27.08.2014, 19:37     Быстрый способ получение уникального ID #13
-NEURON-, если хочется еще производительность, то можно вместо unordered_set\map использовать одноименный контейнеры из boost.intrusive. Если про задачу известны какие-то детали, например, до начала добавления в контейнер можно сказать сколько всего будет вставок, то можно очень сильно поднять производительность, исключив перехеширование таблицы и создав ее заранее нужного размера. Ну и т.д.
Название как бы намекает
-NEURON-
Заблокирован
27.08.2014, 19:38  [ТС]     Быстрый способ получение уникального ID #14
Нее...буст не хочу тащить за собой, вот когда его официально включать в С++17, тогда возможно. Пока что всё на Qt
DrOffset
6423 / 3797 / 878
Регистрация: 30.01.2014
Сообщений: 6,585
27.08.2014, 19:43     Быстрый способ получение уникального ID #15
-NEURON-, А если например нужен словарный поиск или частичный поиск строк (особенно длинных строк), то тут еще лучше подойдет ternary tree и его вариации.
Короче, всегда задача на первом месте. Без изучения предметной области задачи ничего оптимизировать не надо. Иначе можно сильно сесть в лужу. Серебряной пули на все времена - нет.

Добавлено через 1 минуту
Цитата Сообщение от -NEURON- Посмотреть сообщение
Нее...буст не хочу тащить за собой, вот когда его официально включать в С++17, тогда возможно. Пока что всё на Qt
А, религия. Ну понятно
-NEURON-
Заблокирован
27.08.2014, 19:49  [ТС]     Быстрый способ получение уникального ID #16
Цитата Сообщение от DrOffset Посмотреть сообщение
А, религия. Ну понятно
Ехехе...Да не... Не люблю с собой лишнюю тележку библиотек таскать
Кстати, может я отстал от жизни уже, но нет ли в стандартном STL C++11 какого - то контейнера, для хранения уникальных значений в одинарном списке, ну то есть если мне нужен контейнер, куда бы я мог бы просто вставлять уникальные строки... Ну вот std::map<std::wstring,int> например, мне для уникальных значений нужен только std:wstring, второе поле пары мне не нужно, есть какой - унарный контейнер типа мапа ?
DrOffset
6423 / 3797 / 878
Регистрация: 30.01.2014
Сообщений: 6,585
27.08.2014, 19:54     Быстрый способ получение уникального ID #17
-NEURON-, ну std::unordered_set/std::set же
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.08.2014, 19:55     Быстрый способ получение уникального ID
Еще ссылки по теме:

Быстрый способ сравнить содержимое двух файлов C++
C++ Memory shift или самый быстрый способ перемещения блока памяти
C++ Самый быстрый способ решения задачи a+b

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
-NEURON-
Заблокирован
27.08.2014, 19:55  [ТС]     Быстрый способ получение уникального ID #18
Цитата Сообщение от DrOffset Посмотреть сообщение
ну std::unordered_set/std::set же
А, ну ок, мне просто лень было весь текст про них прочитать
Yandex
Объявления
27.08.2014, 19:55     Быстрый способ получение уникального ID
Ответ Создать тему
Опции темы

Текущее время: 04:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru