Форумы портала PHP.SU :: Версия для печати :: уникальный хеш из двух чисел

Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770
Форумы портала PHP.SU :: Версия для печати :: уникальный хеш из двух чисел

Форумы портала PHP.SU » » Вопросы новичков » уникальный хеш из двух чисел

Страниц (1): [1]

1. OrmaJever - 25 Октября, 2014 - 21:14:45 - перейти к сообщению

Задача на миллион! Есть 2 любые числа, нужно получить такое число (хеш) что бы оно было уникальным для любой пары, но не зависело от расположения этих чисел. Например
есть 2 числа 1 и 2, нужна формула по который для 1 и 2 будет такой же хеш как и для 2 и 1, но уникальный для другой пары.
То есть
1 * 2 = 2
2 * 1 = 2
но в этой формуле слишком много колизий, например 2*10 = 20 5*4 тоже = 20, а нужны уникальные значения для каждой пары.
Простой код для проверки коллизий

PHP:
скопировать код в буфер обмена

$arr = array();
for( $y=1; $y<50; ++$y) {
    for( $x = 1; $x<50; ++$x) {
        $arr[] = ($y / $x) + ($x / $y); // формула
    }
}
sort($arr);
var_dump(count($arr) == count(array_unique($arr)));
var_dump($arr)

2. dcc0 - 25 Октября, 2014 - 21:50:11 - перейти к сообщению

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

3. OrmaJever - 25 Октября, 2014 - 22:03:55 - перейти к сообщению

упорядочивать нельзя, есть просто 2 числа и нужно получить одинаковый хеш или число по формуле вне зависимости от их расположения.

4. Мелкий - 25 Октября, 2014 - 22:12:25 - перейти к сообщению

xor?

5. OrmaJever - 25 Октября, 2014 - 22:19:34 - перейти к сообщению

Мелкий, а что xor? сам по себе он возвращает bool, а битовый ^ даёт очень много повторений
(Добавление)
Вот более правильный скрипт проверки колизий

PHP:
скопировать код в буфер обмена

$arr = array();
for( $y=1; $y<100; ++$y) {
    for( $x = 1; $x<100; ++$x) {
        if( $x == $y ) continue;
        $arr[] = $y / $x + $x / $y; // <- формула
    }
}
asort($arr);
$count = count($arr);
$coll = $count - count(arraY_unique($arr));
echo round($coll * 100 / $count, 1), '% коллизий';

6. OrmaJever - 26 Октября, 2014 - 10:31:25 - перейти к сообщению

ладно, раз в предложениями туго тогда опишу идея по другому.
Есть таблица сообщений в бд с полями from_id (от кого) и to_id (кому)
Дак вот, все эти сообщения нужно групировать и выводить в виде беседы, то есть
from_id = 5 AND to_id = 10
это одна беседа с
from_id = 10 AND to_id = 5
То есть мне для вывода списка бесед нужно сгрупировать по этим двум полям, но как если они могут быть в разной последовательности?
Вариант создать другую таблицу "conversation" где будет id беседы - не предлагать Улыбка

Я могу создать отдельное поле в котором хранить id или хеш беседы, но как его генерировать?

7. Мелкий - 26 Октября, 2014 - 11:08:35 - перейти к сообщению

Я-то думал задача сугубо математическая.

Берёте поле в 2 раза превышающее по размеру from_id и to_id, bigint, видимо, и пишете туда (для 64-битной версии PHP, для 32-битной лучше со строками и str_pad сделать):

PHP:
скопировать код в буфер обмена

$iMaxDigitsCount = 10; // я не помню, сколько десятичных знаков в int'е.
if ($x > $y) $hash = $x*pow(10, $iMaxDigitsCount) + $y;
else $hash = $y*pow(10, $iMaxDigitsCount) + $x;

8. OrmaJever - 26 Октября, 2014 - 11:19:41 - перейти к сообщению

тут как оказалось - "а слона то я и не заметил". Я изначально хотел сугубо математическое решение что бы делать его прямо в запросе аля

CODE (SQL):
скопировать код в буфер обмена

GROUP BY (from_id + to_id)

но сейчас вот подумал, я ведь могу в php сортировать from_id и to_id от меньшего до большего и делать из них хеш который буду записывать в отдельное поле. Это же банально просто Растерялся

9. Мелкий - 26 Октября, 2014 - 11:31:26 - перейти к сообщению

Можно и на sql, if есть, возведение в степень тоже.

CODE (SQL):
скопировать код в буфер обмена

GROUP BY IF (from_id>to_id, from_id*pow(10,10)+to_id, to_id*pow(10,10)+from_id)

Операторами бинарного сдвига будет компактнее, да только я их не помню Закатив глазки

10. OrmaJever - 26 Октября, 2014 - 13:03:38 - перейти к сообщению

так, окей, это работает! Но теперь главный вопрос, насколько эти вычисления в group by ресурсоёмкие? Может всё такие лучше создать отдельное поле и результат вот этих вычислений (на php) записывать туда и группировать по уже готовому результату?

11. snikers987 - 26 Октября, 2014 - 13:26:27 - перейти к сообщению

Может я чего то не понял, а что мешает взять 2 числа и конкатенировать их, предварительно отсортировав, например по формуле, $min_id.$max_id ?

Для

CODE (SQL):
скопировать код в буфер обмена

 
from_id = 5 AND to_id = 10
from_id = 10 AND to_id = 5

хеш будет 510.

Псевдокод:

PHP:
скопировать код в буфер обмена

 
$ids = array($from_id, $to_id);
sort($ids);
echo $hash = join('', $ids);
 

Такой вариант будет правильно работать и в случае, если в беседе более 2 участников.

Можно прямо в SQL:

CODE (SQL):
скопировать код в буфер обмена

 
GROUP BY IF(from_id>to_id, CONCAT(to_id, from_id), CONCAT(from_id, to_id))
 

12. OrmaJever - 26 Октября, 2014 - 14:05:29 - перейти к сообщению

snikers987 пишет:

а что мешает взять 2 числа и конкатенировать их

по сути ничего, только нужно добавить сепаратор потому что 311 и 415 совпадёт с 31 и 1415, и тут уже вопрос в производительности, мне кажется что математически операции быстрее чем обьединение строк
(Добавление)
В общем решено, отдельное поле с индефикатором переписки в любом случае нужно создавать, что бы потом его в ссылку писать для отображения самой переписки. В каком формате делать уже по ходу решу.