Форум PHP

Какой алгоритм для этого используется?

Например, мне для каждого нового урла надо создать случайную последовательность размером 6 символов вида /^[a-z0-9]{6}$/, при этом не повторяя уже созданные урлы, которые сохраняются в БД.

Создать случайную последовательность не трудно, а вот как обеспечить уникальность...?

Создать массив всех возможных значений и вычесть из него все уже использованные и выбрать случайную запись - не самый оптимальный вариант, учитывая, что всего вариантов 33^6 = 1291467969, а если расширить алфавит (скажем, включив и заглавные буковки), то и того больше

Была идея (если брать длину строки в 5 символов) - сгенерить все варианты и положить один за одним в файл, тогда получим файл размером 33^5/1024/1024 ~ 37Мб (что в общем-то приемлимо). Тогда можно в качестве случайного значения читать 5 байт из этого файла со смещением == rand(общее кол-во вариантов - кол-во уже использованных). Единственное, что придется как-то пересобирать файл каждый раз, удаляя использованное значение. Да и при большем кол-во вариантов размер файла будет расти очень быстро

В общем, похоже не по тому пути я пошел в поисках решения этой проблемы =) Есть идеи?

Может попробовать псевдослучайность на openssl_random_pseudo_bytes.

Можно еще так попробовать:

весь диапазон допустимый это случайное число от K до N. С каждой генерацией нового значение K увеличивается на 1, то есть сгенерированное число в следующей выборке не будет принимать участие. А чтобы не подцеплять большие файлы, массив всех слов, в которых будет выбор по генерируемому числу, разбить на несколько массивов, а какой из них будет служить для выбора может указывать сгенерированное число деленное по модулю.

В общем, да. Задача сводится к выбору случайного числа из N возможных значений. Это число потом можно перевести в Xричную систему счисления, чтобы получить символьный код, где X-кол-во знаков используемого алфавита.

По поводу вашего предложения с разделением всего массива на M подмассивов:
у меня возникала такая идея, но довести её до ума я не смог.
Возьмем простой пример - двухсимвольный код, каждый символ - 0-2. Получаем общий массив

00 10 20
01 11 21
02 12 22

Этот общий массив я разбил на M=3 частей. Генерируем случайное число от K..M (1..9 в нашем примере). Допустим, получаем 5.
5%M == 2. И... дальше что? Непонятно

Возникла другая идея, как продолжение идеи с файлом. Только вместо того, чтобы хранить готовые значения, будем хранить только флаг использовано значение или нет. Т.е. имеем последовательность бит 1..N. Для алфавита /^[a-z0-9]{5}$/ получаем 36^5 возможных вариантов (36 а не 33, как я ошибочно в первом комменте написал. 26 букв + 10 цифр). Итого 60466176 вариантов/бит, а значит 60466176/8/1024/1024 ~ 7Мб.
Выборка тогда будет происходить следующим образом:
1. генерим случайное число R от 1..N
2. проверяем "свободен" ли бит под номером R, если да - меняем его состояние, иначе читаем последующие биты, пока не будет найден первый свободный (возвращаемся на начало файла, если потребуется).
3. Генерируем символьный код на основе полученного порядкового номера

7Мб можно держать в разделяемой памяти, для быстрого доступа. В случае крэша системы, восстановить эту последовательность можно из базы, проведя обратные преобразования

Пока что такое решение мне кажется наиболее удачным. Хотелось бы увидеть ваши комментарии

>Допустим, получаем 5. 5%M == 2. И... дальше что? Непонятно

Ну что не понятного, есть у вас 100 значений, разбили вы их на банки по 20 штук, если теперь генерировать число от 1 до 100 и делить его по модулю 20, то результат деления покажет в каком банке находится искомое значение. Это для того чтобы не грузить большие объемы.

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

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

> сгенерировали весь возможный набор случайно его размещая по банкам
т.е. в итоге мы храним все возможные варианты где-то во внешней памяти? Так?

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

Не разбивайте, если размеры вас не лимитируют. Изначально вы пишите о больших объемах. Собственно зачем грузить сразу все, если выбрать нужно всего лишь одно значение. Банк на сотню КБ, для file() превратить в массив не проблема, и в нем же под первым индексом счетчик. И если я знаю что получить надо из банка М, то что выгоднее - все сразу или только часть необходимая?

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

>весь диапазон допустимый это случайное число от K до N. С каждой генерацией нового значение K увеличивается на 1, то есть сгенерированное число в следующей выборке не будет принимать участие.

ну допустим диапазон от 1 до 1679616, К = 1, N = 1679616, геренируется случайное число 10145, K увеличивается на 1 до 2, диапазон становится от 2 до 1679616, почему же опять не сгенерируется 10145? или я что-то не правильно понял? тогда зачем вообще генерировать, просто перебирать по порядку )

>Создать массив всех возможных значений...

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

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

6 символов вида /^[a-z0-9]{6}$/ это далеко не 1000000 значений, это 36 ^ 6 = 2 176 782 336 значений и какова же вероятность повторения? да даже 5 символов вероятность 1 к 60 млн.... даже если у вас в базе будет 999999 url-ов, вероятность повторения будет 0,016 т.е. из 100 генераций, в 1 или 2 случаях придется пройти по базе более одного раза, при том что у вас уже там 1 млн. url-ов

я к тому, что вероятность коллизии возрастает с каждым новым добавленным значением. вполне возможно, что длина строки будет ограничена 4мя символами, тогда 36^4 даст нам 1679616, что не так уж много.
Вообще, задача в большей степени в роде "прокачать" скилы. Попробовать разные методы. А вообще ваш вариант конечно вполне жизнеспособен, но я его не рассматриваю, хотя бы потому, что мы не ищем легких путей)))

>Например, мне для каждого нового урла надо создать случайную последовательность...

Прошу прощения, а какой прок от того, что сгенерированная строка - случайна?

Это добавляет изрядно хлопот, по сравнению с простейшим вариантом, если бы сохранялся простой порядковый номер url.
Собственно, все рассуждения в этой ветви о том, как эти хлопоты преодолеть.
Может их создавать не нужно?
PS. в соседней ветке родилось вот такое сообщение 21.12.2014 18:46 (абсолютно в тему, как мне представляется).