Эффективный алгоритм сопоставления

Question

У меня есть проблема, чтобы определить, содержит ли объект подмножество заданных свойств.Например, я хочу найти объект, обладающий свойством a, b, c, d .. M в пределах N числа объектов.

, например

search a,b,c,d    object A - e,g,a,c
                  object B - a,b,c
                  object C - d,c,b
                  object D - a,b,c,d,e

вернет объект B и объект C.

Самое простое решение - проверить каждый отдельный объект и посмотреть, имеет ли оно свойство a,б, c..M.В худшем случае будет O (mn), так как мне нужно пройти через весь объект и проверить все свойства a, b, c..M.Вы можете предположить, что N довольно велико, и время работы будет сильно увеличиваться, если M увеличится.Есть ли другой эффективный способ решить эту проблему?Спасибо

Answer 1

1. Сначала преобразуйте тестируемый набор в словарь.

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

Для этого требуется время O (n + m), где n - количество элементов в первом наборе, а m - общее количество элементов во всех других наборах.

Вот решение на python:

def list_sets(search, objects):
    d = dict( [ (x, True) for x in search ] )
    return [ x for x in objects if all( [ y in d for y in x  ] ) ]

Пример ввода:

print list_sets( [ 'a', 'b', 'c', 'd' ],
    [   [ 'e', 'g', 'a', 'c' ],
        [ 'a', 'b', 'c' ],
        [ 'd', 'c', 'b' ],
        [ 'a', 'b', 'c', 'd', 'e' ] ] )

Результат:

[['a', 'b',' c '], [' d ',' c ',' b ']]

Answer 2

Маловероятно, что можно сделать что-то быстрее, чем O (MN).

Проблема в том, что для того, чтобы найти ответ, мы должны проанализировать все объекты и [потенциально] все их свойства.

OTOH может быть (не уверен) возможно сделать некоторую предварительную обработку в O (MN) или немного больше, и тогда быть в состоянии ответить быстрее ...

Answer 3

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

Это не улучшит производительность в худшем случае, но может улучшить реальную производительность в зависимости от ваших данных.