Сет против Мультисета
Я хотел бы хранить (от 100 до 1000) различные отношения типа <Object A, Relation R, Object B> в комплекте или мультимножество. Я хотел бы иметь возможность искать A а также (A,R), но не для (A,R,B) (и будет всего несколько (<5) отношения с такими же A а также Rтак что линейный поиск, если хорошо, то).
Лучше ли хранить отношения в наборе (по заказу A, R а также B) или хранить их в мультимножестве, заказанном A а также R?
Редактировать:
Я изучил хеш-таблицы, но их итерация не такая быстрая, как (упорядоченная) итерация множества, и сопоставление с образцом также требует много итераций.
(Он должен будет искать один раз, чтобы найти начало итерации, а затем повторять до тех пор, пока не будут выполнены все отношения с одним и тем же объектом A.)
Спасибо,
Рагнар
Решение
Из комментариев я понял, что вы должны искать точные совпадения, либо для A, либо для пары (A, R).
Если это правильно, лучшее, что вы можете сделать, это использовать две хеш-таблицы: одну с A в качестве ключей, другую с (A, R) в качестве ключей. Сами отношения могут быть сохранены в несортированном векторе, а индексы для них вставлены в две хеш-таблицы. Это единственный способ получить O (1) сложность для вашей задачи поиска.
Для производительности крайне важно иметь две независимые структуры индекса: если вы используете только A в качестве ключей, вы получите списки объектов, по которым вам нужно искать подходящий R при поиске пары (A, R). В противном случае, если у вас есть только клавиши (A, R), вы не сможете искать только определенную букву A за O (1).
Другие решения
Других решений пока нет …