Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Какой-от не очень рандомный рандом / 25 сообщений из 38, страница 1 из 2
23.04.2013, 12:58
    #38236435
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Стали замечать проблему, что часты коллизии.
Написал функцию по подобию используемой в проекте (в частности диапазон тот же).

Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
        for($j=0; $j<100; $j++)
        {
            $a = array();
            for($i=0; $i < 10000; $i++)
            {
                $rnd =  rand(0x10000,0xfffff);

                if(isset($a[$rnd])) {
                    echo "Collision: {$rnd}\n";
                }
                $a[$rnd] = true;
            }
        }



На локальном компьютере она не дает коллизий даже если использую для теста массивы длиной 10000.
На боевом же сервере коллизии так и прут. В тестовой функции их множество, даже если брать длину массива 1000.

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


Функцию переписал так, но не на много лучше стало:

Код: php
1.
2.
3.
4.
    public static function uniqid()
    {
        return dechex(date('U')) . dechex(rand(0x10000,0xfffff));
    }
...
Рейтинг: 0 / 0
23.04.2013, 13:04
    #38236447
phpz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Hett,

mt_rand() ?
...
Рейтинг: 0 / 0
23.04.2013, 13:46
    #38236553
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
На локальном компьютере mt_rand ведет себя значительно хуже. А на сервере я при подобном тесте не ощутил разницы.
...
Рейтинг: 0 / 0
23.04.2013, 14:01
    #38236581
r u
r u
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Hett,

опишите исходную задачу. зачем вам так часто вызывать рандом?
чего хотите добиться
...
Рейтинг: 0 / 0
23.04.2013, 15:00
    #38236715
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Есть поток данных, которые записываются в БД (хранится примерно 2кк записей последних сейчас).
Ну записи добавляются постоянно, старые удаляются. Нужен уникальный ключ для записей, да такой, чтобы пользователи не могли на основании его знать сколько данных было добавлено. Собстна использовался uniqueid, но он стал лажать когда поток данных немножко возрос. Переписал вот как выше, по началу вроде лучше стало (хотя может стечение обстоятельств), а потом опять та же картина.

Вообще если так поглядеть на алгоритм, то шансов коллизий должно быть очень мало. Но за день проскакивает таких штук по 10.
...
Рейтинг: 0 / 0
23.04.2013, 15:30
    #38236783
phpz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Hett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)
...
Рейтинг: 0 / 0
23.04.2013, 15:45
    #38236821
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Hett
Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
        for($j=0; $j<100; $j++)
        {
            $a = array();
            for($i=0; $i < 10000; $i++)
            {
                $rnd =  rand(0x10000,0xfffff);

                if(isset($a[$rnd])) {
                    echo "Collision: {$rnd}\n";
                }
                $a[$rnd] = true;
            }
        }


У вас несколько меньше миллиона возможных значений, и вы хотите отсутствия коллизий для десяти тысяч выбранных значений? http://ru.wikipedia.org/wiki/Парадокс_дней_рождения#.D0.9E.D0.B1.D0.BE.D0.B1.D1.89.D0.B5.D0.BD.D0.B8.D1.8F
...
Рейтинг: 0 / 0
23.04.2013, 16:05
    #38236866
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Если не осилите статью, можно примерно так прикинуть:
чтобы вероятность коллизий N чисел не превышала p, надо выбирать числа из диапазона N^2/p. Например, хотите чтобы в выборке из 10000 чисел вероятность коллизии была не больше 1% - выбирайте из 10000*10000/0.01 - миллиарда возможных значений.
...
Рейтинг: 0 / 0
23.04.2013, 16:50
    #38236972
SmeL_md
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Hett,
У меня была похожая ситуация на 2 разных серверах тогда я генерировал ключ длиной 32 символа от 0 до F.
Ну думал ну как могут быть коллизии :) хотя проверку коллизии делал. Так вот на двух серверах с нагрузкой образно говоря с разницей в 100 раз (почти в одно и тоже время разница месяц). механизм перестал генерировать уникальные ключи, т.е. генерировал то что уже когда то было.
Тогда я поступил так strtoupper(dechex(time())) и конкатенировал с оставшейся длинной ключа.
...
Рейтинг: 0 / 0
23.04.2013, 17:51
    #38237104
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
?Если не осилите статью, можно примерно так прикинуть:
чтобы вероятность коллизий N чисел не превышала p, надо выбирать числа из диапазона N^2/p. Например, хотите чтобы в выборке из 10000 чисел вероятность коллизии была не больше 1% - выбирайте из 10000*10000/0.01 - миллиарда возможных значений.

Дело в том, что это всего лишь тестовая функция и она не дает коллизий (по крайней мере мне не попались при многократном запуске) на моем локальном копьютере.
А вот на сервере из 100 тестов по 1000 рандомных значений получается примерно 15 коллизий.
В проекте же вообще они получаются из 10 записей и относительно очень часто.
...
Рейтинг: 0 / 0
23.04.2013, 17:52
    #38237110
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
phpzHett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)

ну да, можно взять еще микротайм+рандом. Просто думал может кто сталкивался с этим и знает еще какие-то решения.
...
Рейтинг: 0 / 0
23.04.2013, 17:53
    #38237114
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
HettВ проекте же вообще они получаются из 10 записей и относительно очень часто.
Хотя 10 это вообще максимум который бывает очень редко. В среднем там 2-5 записей в секунду.
...
Рейтинг: 0 / 0
23.04.2013, 18:07
    #38237149
ScareCrow
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
автор Просто думал может кто сталкивался с этим и знает еще какие-то решения.
GUID?
...
Рейтинг: 0 / 0
23.04.2013, 18:16
    #38237159
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
HettНа боевом же сервере коллизии так и прут.Гипотеза с потолка - процессор, случаем, не AMD?
...
Рейтинг: 0 / 0
23.04.2013, 18:23
    #38237167
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
miksoftHettНа боевом же сервере коллизии так и прут.Гипотеза с потолка - процессор, случаем, не AMD?
Два процессора Intel(R) Xeon(R) CPU E3-1270 V2 @ 3.50GHz
...
Рейтинг: 0 / 0
23.04.2013, 19:02
    #38237222
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Корочи на линуксе (в частносте убунте) такое странное поведение.
Я попробовал на домашнем компе,

Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
$i1 = 0;
for($j=0; $j<100; $j++)
{
    $a = array();
    for($i=0; $i < 10000; $i++)
    {
        $rnd = rand(0x10000,0xfffff);

        if(isset($a[$rnd])) {
//            echo "Collision: {$rnd}<br>";
            $i1++;
        }
        $a[$rnd] = true;
    }
}
echo ($i1 / count($a) * 100);


Показало 0.
А на вритуалке на этом же железе ~50.
...
Рейтинг: 0 / 0
23.04.2013, 22:58
    #38237428
phpz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Hett,

Я бы этой строке кода сильно не доверял:
Код: php
1.
echo ($i1 / count($a) * 100);
...
Рейтинг: 0 / 0
24.04.2013, 07:32
    #38237541
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
HettДело в том, что это всего лишь тестовая функция и она не дает коллизий (по крайней мере мне не попались при многократном запуске) на моем локальном копьютере.
А вот на сервере из 100 тестов по 1000 рандомных значений получается примерно 15 коллизий.
В проекте же вообще они получаются из 10 записей и относительно очень часто.На винде тестируете? Ну это как раз на винде random в php не рандомный - выдает фиксированную последовательность из 32768 разных значений, которая потом повторяется по циклу. А для случайных чисел коллизии должны быть.
...
Рейтинг: 0 / 0
24.04.2013, 07:46
    #38237547
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
В статье на wiki обоснование. На пальцах - десять тысяч чисел - это сто миллионов пар. Сто миллионов раз берете пару случайных значений из одного миллиона возможных и проверяете что они не совпали.
Да, и числа выдаваемые функциями rand, mt_rand и т.п. - в любом случае не случайные :)
...
Рейтинг: 0 / 0
24.04.2013, 08:32
    #38237563
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
phpzHett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)Если отрезать 5 символов, то на 10000 значений коллизии будут - я вам гарантирую.
...
Рейтинг: 0 / 0
24.04.2013, 08:34
    #38237566
r u
r u
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
HettНужен уникальный ключ для записей, да такой, чтобы пользователи не могли на основании его знать сколько данных было добавлено.
ну и зачем тогда так заморачиваться?
имеем в таблице PK id автоинкремент
на его основе делаем суррогатный ключ равный md5( $id.$SALT )
и непаримся
коллизии почти исключены, юзеры ничего угадать несмогут.
длинноват - но думаю это непроблема
...
Рейтинг: 0 / 0
24.04.2013, 08:36
    #38237567
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
HettphpzHett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)

ну да, можно взять еще микротайм+рандом. Просто думал может кто сталкивался с этим и знает еще какие-то решения.Вообще-то для гарантированного отсутствия коллизий только одно решение - брать автоинкрементный счетчик. Шифровать его значение. В результатах шифрования ни в коем случае ничего не обрезать!
...
Рейтинг: 0 / 0
24.04.2013, 09:43
    #38237611
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
Я хотел посвятить топик скорее вопросу рандома, придумать другой вариант без коллизий в общем-то не проблема)
...
Рейтинг: 0 / 0
24.04.2013, 09:44
    #38237613
phpz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
?phpzHett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)Если отрезать 5 символов, то на 10000 значений коллизии будут - я вам гарантирую.
Монстр:
Код: php
1.
$rnd = hexdec(substr(md5(microtime(true).rand()),rand(0,23),8));  // так делать не надо xD


А вообще-то может стОит /dev/urandom заюзать
Код: php
1.
$rand_bytes = mcrypt_create_iv(4, MCRYPT_DEV_URANDOM)
...
Рейтинг: 0 / 0
24.04.2013, 10:38
    #38237693
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Какой-от не очень рандомный рандом
HettЯ хотел посвятить топик скорее вопросу рандома, придумать другой вариант без коллизий в общем-то не проблема)
Ну тогда еще раз читайте http://ru.wikipedia.org/wiki/Парадокс_дней_рождения и http://ru.wikipedia.org/wiki/Атака_«дней_рождения» до просветления. С выбранными вами диапазонами коллизии обязательно будут.
...
Рейтинг: 0 / 0
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Какой-от не очень рандомный рандом / 25 сообщений из 38, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]