Алгоритмическая задача на поиск по составному ключу

Question

[Александр]

Добрый день.

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

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

Что имеется тогда.
user1.id, user2.id и временная метка в момент инициации инвайта, назовём time.

Нужно иметь возможность сделать поиск по user1.id И user2.id вне зависимости от порядка этих аргументов. Первое что приходит на ум это нечто вроде ключа, значение которого формируется из user1.id + user2.id, не завися от порядка слагаемых. Если сделать побитовое сложение значений id, то вроде всё круто получится, но есть риск получить коллизию. Проверить актуальность предложения далее уже тривиально, взяв значение из массива по найденному ключу.

Я знаю, что это можно решить через два массива или даже БД, но это не интересно.
Можно сделать символьное сложение идентификаторов с разделителем и перебирать на каждой итерации два варианта для сравнения, но неужели лучше решения нет?

Comments

[Александр]

Пока лучшее решение даже для символьных id выглядит так.
Сравниваем id1 и id2 побитово, чтобы вычислить больший и меньший. Соответственно, ключ для массива формируется user1.id + разделитель + user2.id , если user1.id меньше чем user2.id. И аналогично, если наоборот. Тогда поиск будет своидиться к формированию слепка по алгоритму выше и проверке на существование данного ключа в массиве.

Answer 1

[Макс]

Сделать одним полем ключ конкатенации массива userId1 и userId2 предварительно их отсортировав по алфавиту ?

Comments

[Александр]

Спасибо. В принципе к похожему решению мы с другом и пришли, но сортировка по алфавиту несколько более тяжелая операция, чем функция strcmp.

[Rsa97]

@kryoz ??? А что, по вашему, делает strcmp и чем она отличается от сортировки двух строк если их всего две?

[Александр]

@Rsa97 я всегда считал, что сортировка заключается в сопоставлении с некоторой весовой метрикой элементов.

[Александр]

@Rsa97 php.net/manual/ru/function.strcmp.php

[Rsa97]

@kryoz Вообще-то сортировка - упорядочение списка/массива согласно некой функции сравнения двух элементов так, чтобы предыдущий элемент отсортированного списка всегда был не больше (или не меньше) предыдущего. Для алфавитной сортировки строк как раз и используются функции strcmp/strcasecmp.