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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
-NEURON-
Заблокирован
#1

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

27.08.2014, 18:34. Просмотров 843. Ответов 17
Метки нет (Все метки)

Есть какой - то список уже существующих уникальных ID, нужно наибыстрейшим способом создать новый уникальный для этого списка ID. (пусть тип ID будет допустим unsigned int)
1. В каком виде лучше хранить список переменной длинны всех уникальных ID ? std::map ?
2. Каким наибыстрейшим способом можно сгенерить уникальный ID ? Если map - ну там всё просто, но сдаётся мне, что это не наибыстрейший способ... Может хранить всё в std::vector, а во время генерации проверять std::binary_search-ем наличие ID в списке и если такого нет - добавлять, если есть - генерить заново ...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.08.2014, 18:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрый способ получение уникального ID (C++):

Самый быстрый способ решения задачи a+b - C++
несколько раз ходил на олимпиады, во многих из них в пробном туре даётся задача а+б, решаю её стандартным способом: cin >> a >> b; ...

Быстрый способ сравнить содержимое двух файлов - C++
Здравствуйте, подскажите наиболее быстрый способ сравнить содержимое двух текстовых файлов и вывести различия.

Быстрый способ определения цвета пиксела координатам x, y - C++
В общем задача такая , нужен быстрый способ определения цвета пиксела в настоящее время на экране по заданным координатам x, y мне нужно...

Memory shift или самый быстрый способ перемещения блока памяти - C++
int* dataField = new int{0}; for (int i = 0; i < 50; i++) dataField = 777; //тут должен быть memory shift delete dataField;...

Самый быстрый способ посчитать сумма элементов матрицы, находящихся в матрице - C++
Здравствуйте форумчане! Подскажите мне самый быстрый способ нахождении суммы элементов матрицы, находящихся на главной диагонали...

Считать квадратную матрицу. Какой самый быстрый способ это сделать? - C++
Какие самые быстрые способы считывания в с++? Пример : мне надо считать квадратную матрицу. Какой самый быстрый способ это сделать?

17
Nick Alte
Эксперт С++
1639 / 1011 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
27.08.2014, 18:42 #2
Завести счётчик, скажем, unsigned int. Каждый раз, когда нужен новый ID, брать его значение и увеличивать на единицу. Первые 4 миллиарда ID, выданных таким счётчиком, будут уникальными. Если "малавата будет", есть long long, это ещё в 4 миллиарда раз больше. Если изначально докрутить его до числа, на 1 большего из всех существующих ID, можно как-то к ним приспособиться.
В смысле поиска самым быстрым будет unordered_map, у binary_search и map эквивалентная сложность поиска O(log N).
1
DrOffset
7351 / 4451 / 1009
Регистрация: 30.01.2014
Сообщений: 7,293
27.08.2014, 18:49 #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-, нельзя выбирать быстрейшее решение абстрактно. Оно всегда привязано к задаче.
1
-NEURON-
Заблокирован
27.08.2014, 18:52  [ТС] #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 в систему ... Хотя я не считал - ща проверю на сколько хватит Просто сама мысль о том, что когда - то они закончатся - как то меня тревожит ...
0
Nick Alte
Эксперт С++
1639 / 1011 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
27.08.2014, 18:58 #5
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от -NEURON- Посмотреть сообщение
Просто сама мысль о том, что когда - то они закончатся - как то меня тревожит ...
Тогда рекомендую сразу за компанию посчитать, когда закончатся 16 квинтиллионов чисел (1.6e19, на минуточку), выражаемых long long, при пиковой скорости выдачи ID.
0
-NEURON-
Заблокирован
27.08.2014, 18:58  [ТС] #6
Хотя я тут подсчитал, даже если по миллиону новых ID в день добавлять, размера unsigned long long хватить больше чем на 50 миллиардов лет ))))))))))))))))))))))
Единственных косяк, программа x86, по этому на каждую операцию будет намного больше времени тратится, нежели на x64... Ща подсчитаю, на сколько мне unsigned int хватить
0
DrOffset
7351 / 4451 / 1009
Регистрация: 30.01.2014
Сообщений: 7,293
27.08.2014, 19:05 #7
Цитата Сообщение от -NEURON- Посмотреть сообщение
Хотя я не считал - ща проверю на сколько хватит
При условии 64 разрядного счетчика это будет 50539024859478 лет, если считать, что в год добавляется 365000 записей.

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

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

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

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

Добавлено через 1 минуту
Цитата Сообщение от -NEURON- Посмотреть сообщение
Нее...буст не хочу тащить за собой, вот когда его официально включать в С++17, тогда возможно. Пока что всё на Qt
А, религия. Ну понятно
0
27.08.2014, 19:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.08.2014, 19:43
Привет! Вот еще темы с ответами:

Наиболее быстрый способ сравнения двух экземпляров структур на предмет одинаковости их полей - C++
Есть структура, в которой есть несколько int-ов и char-ов, какой имеется наиболее быстрый способ в C/C++ для сравнения двух экземпляров...

Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти - C++
Привет! Какой есть наиболее быстрый способ сортировки файла, содержащего int-ы (по одному int-у на каждой строчке), размером в 1...

Каков самый быстрый способ узнать количество строк в оргомном текстовом файле в Windows? - C++
Есть текстовый файл с кучей строк (размер файла ~ 1Гб). Как можно максимально быстро узнать кол-во строк в этом файле? Если делать тупо...

Напишите функцию для поиска первого уникального символа в строке - C++
Пожалуйста! Напишите функцию для поиска первого уникального символа в строке(с пояснением пожалуйста)))


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru