Структура данных для быстрого поиска по нескольким критериям

Question

У меня есть несколько элементов, которые содержат n свойств. Мне нужно создать структуру данных, которая будет возвращать все соответствующие элементы для данного набора критериев. Поиск должен быть быстрым.

Чтобы сделать его более понятным, представьте себе следующий класс:

class Element {
    let a : Int? // criterion0
    let b : Int? // criterion1
    let c : Int? // criterion2

    let value : String
}

Теперь я заполняю dataStructure 3000 таких элементов:

dataStructure.add(Element(a:1,b:3,c:4, value:"val0")) // insert 1
dataStructure.add(Element(a:nil,b:1000,c:40, value:"val1")) // insert 2
dataStructure.add(Element(a:nil,b:3,c:4, value:"val2")) // insert 3
...
dataStructure.add(Element(a:10,b:3,c:23, value:"val2999")) // insert 3000

И мне придется искать элементы, которые могли бы точно соответствовать тому, что я вставил, но это также могло бы быть другим. Из-за подстановочного знака ноль, может быть много совпадений для каждого поиска. Мне нужно, чтобы эти поиски были быстрыми:

dataStructure.getAllMatching(a:4, b:30, c:4)

, где аргумент nil во вставленном элементе означает, что любое значение соответствует.

Например, dataStructure.getAllMatching(a:1, b:3, c:4) вернет [ «val0», «val1»] по крайней мере, учитывая то, что я вставил выше.

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

Answer 1

Для фиксированного числа полей (3 в вашем примере), существует простой способ сделать это, который позволяет добавлять, удалять и запрашивать операции всего за O (1) времени. Он использует O (n) памяти, но с относительно большим постоянным коэффициентом; Это нормально, если у вас мало ограничений на память. Я напишу без указания языка программирования c, поскольку я не использую Swift.

Ведение словаря, в котором каждая комбинация полей, включая символы подстановки, сопоставляется с набором Element объекты. Это, вероятно, проще всего описать на примере: предположим, что элементы:

X = (a=1, b=2, c=3)
Y = (a=1, b=3, c=4)
Z = (a=2, b=3, c=4)

Тогда ваш словарь выглядит так:

{
    // just a
    (1, nil, nil): {X, Y}, (2, nil, nil): {Z},
    // just b
    (nil, 2, nil): {X}, (nil, 3, nil): {Y, Z},
    // just c
    (nil, nil, 3): {X}, (nil, nil, 4): {Y, Z}}`.
    // a and b
    (1, 2, nil): {X}, (1, 3, nil): {Y}, (2, 3, nil): {Z},
    // a and c
    (1, nil, 3): {X}, (1, nil, 4): {Y}, (2, nil, 4): {Z},
    // b and c
    (nil, 2, 3): {X}, (nil, 3, 4): {Y, Z},
    // a, b, c
    (1, 2, 3): {X}, (1, 3, 4): {Y}, (2, 3, 4): {Z}
}

По сути, структура данных просто хранит ответ на каждый возможный запрос (кроме тех, которые не дают результатов).

Чтобы добавить или удалить элемент, необходимо обновить наборы, принадлежащие 2 ^ 3 - 1 = 7 ключей, и, возможно, добавить новый ключ с новым набором или удалить ключ. Если для словаря и наборов используются хеш-таблицы, все соответствующие операции словаря / набора занимают O (1) времени, а количество таких операций, которое необходимо выполнить, составляет O (1), поэтому добавление или удаление из структуры данных занимает O (1) раз.

Чтобы выполнить запрос по некоторой комбинации значений полей, просто найдите запрос в словаре и верните соответствующий набор (или верните неизменяемое представление).

---

Все это говорит о том, что только для 300 элементов стоит сравнить «наивное» решение, в котором вы просто сохраняете элементы в списке и проверяете весь список для каждого запроса. 300 не является большим числом, возможно, недостаточно большим, чтобы значение O (1) и O (n) имело значение. В зависимости от языка программирования другие детали, такие как прогнозирование ветвлений и кэш-память ЦП, могут оказывать большее влияние, чем теоретическая сложность Я бы рекомендовал сравнить оба варианта.