Алгоритм генерации номера карточки

[JohnK]

Интересует как "правильно" сгенерировать 14 значные номера? Таких номеров нужно, скажем 100 000. Карточки нужны для пополнения счета в нашей локальной сети, которую мы внедряем.
Под словом "правильно" подразумеваю то, как это делаю, скажем, теже операторы мобильной связи.
На данный момент использую Randomize + Rnd.

[CodeName33]

Тут ИМХО правильнее использовать 2 части:
Одна часть должна содержать некий каунтер, который будет увеличиваться на 1 у каждой новой карточки, чтобы избежать случайного повтора номера.
Вторая часть будет содержать случайные данные, чтобы было не подделать просто так.
Лучше перемешивать первую часть среди второй, или кодировать, чтобы каунтер не был виден явным образом.

[JohnK]

Я генерирую следующим образом:
00 0000 0000 0000 - каждый элемент ( разделенный пробелом) случайно генерируется, затем полученное 14х значное число проверяется на повторение.
Мне кажется это слишком просто, хотя с другой стороны попробуй подбери с 3 попыток!

[JohnK]

Было бы хорошо услышать ваши идеи, может у кого был опыт генерирования кодов пополнения?

[CodeName33]

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

Теоретически, это может вызвать зависание программы на неопределённое время, если он будет много раз генерировать уже имеющиеся коды. Чтобы этого избежать, как раз каунтер и вводится.

[JohnK]

У меня 100 000 номеров генерятся приблизительно 2-3 минуты. На форме разместил прогрессбар, так что на зависание стало меньше похоже

[Хакер]

Я надеюсь не надо говорит, что проверку на повторение нужно делать не тупым сравнением текущего ключа со всеми ранее сгенерированными ключами?

[JohnK]

А как еще можно?
P.s. Именно так и делаю

[Хакер]

Ужас. Сейчас, генерируя 100000-ный ключ, тебе нужно произвести 99999 x 14 сравнений. Не много ли? Есть техника, позволяющая произвести максимум 14 сравнений. Выигрышь: в 99999 раз меньше лишних действий.

Найди мой топик о Krm и Dfa, где мой подход раскртиковали.

[Хакер]

Да куда там Krm, его использование будет оправдано когда каждому ключу сопоставлены ещё-какие то данные, и надо, имея ключ, за минимальное время найти и получить сопоставленные данные.

А так пойдёт обычный массив.

[JohnK]

Почитал твои выкладки, и решил, что лучше я подожду лишних 3-5 минут, чем разбираться и отлаживать описанную методу

[CodeName33]

Почитал твои выкладки, и решил, что лучше я подожду лишних 3-5 минут, чем разбираться и отлаживать описанную методу

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

Ну или индексировать массив и бинарным поиском искать.

[JohnK]

Ребята! Вопрос не о том как перебрать массив. Вопрос, как генерировать номера наиболее грамотно.

[alibek]

Наиболее грамотно — генерировать все возможные значения (10^14), после чего из полученного набора извлекать нужное количество случайных записей.
Также можно генерировать численные последовательности на основе GUID и использовать их.
Генерировать ключ и проверять, что он уникален (а в случае неуникальности генерировать еще раз) можно, но только в том случае, когда число нужных значений значительно меньше числа возможных значений.

[JohnK]

Так я и делаю...

[Debugger]

Можно совместить случайное число с уникальным номером. Ну, например, старшие 24 бита обозначают случайное число, все остальное - нормер карточки.

[JohnK]

CodeName33 уже предлагал такой вариант, вариант интересный.

[awl100Alex]

На данный момент использую Randomize + Rnd.

http://bbs.vbstreets.ru/viewtopic.php?p=6715278#p6715278

Вопрос, как генерировать номера наиболее грамотно.

Если копнуть теорию...

"...К каким же выводам пришел Д. Кнут? Проанализировав огромный фактический материал, он показывает, что алгоритм или закон, заложенный в генератор случайных чисел, неизбежно проявит себя в том, что последовательность случайных чисел начнет повторяться циклически, т.е. перестанет быть случайной с некоторого момента. В пределах одного цикла последовательность случайна, но длина любого цикла конечна. Невозможно придумать алгоритм, цикл которого был бы бесконечен. Всегда наступает такой момент времени, после которого числа начнут повторяться.
Таким образом, Д. Кнут подтверждает правоту высказывания Дж. фон Неймана: "Всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений" (1951г)."

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

[Хакер]

По-моему, всё это неактуально в данном случае.

[JohnK]

awl100Alex До этого поста я некоторое время пытался найти алгоритмы, но всякий раз натыкался на программы для развода людей (коды пополнение опрераторов моб связи)

[JohnK]

Вообщем на данный момент своял программу генерации 14 значных чисел, пока пойдет. Дальше планирую RND + Shift bits. Думаю сделать таким образом 5 разных алгоритмов и каждую партию карточек делать одним из них. Но, если у вас есть свежие идеи, с удовольствием послушаю.

[awl100Alex]

JohnK
Свежих идей нет - потому что они все уже давно не свежие, а давно разжеванные и изученные полностью. Поищи инфу в литературе по "Теории вероятности" или "Криптографии".

[JohnK]

awl100Alex "Спасибо" за содержательный ответ.

[awl100Alex]

JohnK
Скачай эту книгу...
http://www.goldbook.ws/2006/04/09/Donald_EH__Knut__Iskusstvo_programmirovanija___.html
Там ниже есть ссылки на deposit.
Цитирую...
"Во втором томе представлена теория получисленных алгоритмов. В отдельные главы вынесено описание процесса генерации случайных чисел и способов работы с ними в вычислительной среде".
Или здесь, третья ссылка через ifolders...
http://itbookz.ru/nodata/nodataprog/4946-.html
Алгоритм Д.Г.Лехмера, например. Этим теоремам и исследованиям уже, как там пишут - 100 лет. Поэтому и говорю тебе, что ничего нового нет. Почитай, изучи, поговори со знакомыми математиками для разьясниния деталей и пиши свой генератор карточек.

[trash]

Интересно, зачем изобретать такие корявые велосипеды, если в mssql есть newid и уникальные ключи?

[Хакер]

Интересно, ты будешь читать тему полностью, прежде чем отвечать?

[JohnK]

Долго читал. Много думал....