Вопрос по сопряжению пользователей по атрибутам. Алгоритм / структура данных - PullRequest
1 голос
/ 11 июня 2011

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

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

Если пользователь не может быть связан, мы должны оставить этого пользователя внепарный набор.

ВОПРОСЫ:

  1. Как эффективно реализовать этот процесс сопоставления ...
  2. КакРеализуем ли мы это, если допустим также приблизительное совпадение атрибутов ...

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

Пожалуйста, предложите вашу идею илиЛюбая новая мысль об этом решении и любезно помочь мне в решении второго вопроса.Я совершенно невежествен во втором вопросе ..

Объяснение с некоторыми примерами кодов или пример будет полезно ..

Спасибо ...

1 Ответ

2 голосов
/ 11 июня 2011

Хеш-таблица всех непарных пользователей, ключ = атрибут пользователя.

Когда использование входит и ему присваивается атрибут, ищите его в хэше.

Если найдено, то он в паре,Удалите 2-е (парное использование пользователя) из хэша.
Не добавляйте только что введенного пользователя в хеш.

Если не найдено, добавьте его в хеш (он ожидает свою пару).

Готово

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...