Скажем, у меня есть большой набор массивов (может быть размером до миллионов), и я хочу определить (желательно точно, хотя и приблизительно нормально) массив в этом наборе с наибольшим размером пересечения с входом, чтобудет самый эффективный способ сделать это?Я перечислю некоторые решения, которые приходили мне в голову, сводя это к другой проблеме, но я не уверен, что они обязательно являются лучшими.
Этот набор массивов может храниться в любой структуре данных, имассивы могут быть отсортированы и сохранены любым способом.Идея состоит в том, чтобы оптимизировать время запроса здесь.
Пример: скажем, мой набор массивов (отсортирован по принципу радиуса для удобства, можно отсортировать любым выбранным способом):
[('a', 'b'), ('a', 'e', 'f'), ('b', 'f', 'g'), ('b', 'j', 'z'), ('d', 'l', 'f'), ('x', 'y', 'z')]
и мой входной массив:
('a', 'f')
Тогда соответствующие пересечения:
[('a'), ('a', 'f'), ('f'), (), ('f'), ()]
Таким образом, на выходе будет ('a', 'f')
, имеющее самое большое пересечение размера 2. В качестве бонусабыло бы даже лучше иметь наибольшее K
из них, поэтому здесь, если K = 3, результат будет (в любом порядке):
[('a', 'f'), ('f'), ('a')]
Некоторые возможные решения, о которых я думал:
- Размер моего домена ограничен (например, это может быть az или числа 1-70 и т. Д.), Поэтому потенциально я могу представить их как двоичные строки, и теперь задача состоит в том, чтобы найтиминимальное расстояние Хэммингтона, которое я теперь могу сделать с чем-то вроде хеширования локальности?Например,
('a', 'f')
можно представить как 10000100000000000000000000
- . Также используя тот факт, что домен ограничен, я могу создать некоторый инвертированный индекс с элементами в домене, указывающими на различные массивы в наборе, изатем пересечь (хотя бы некоторые из) эти результаты для каждого элемента во входном массиве - хотя я чувствую, что это было бы невероятно неэффективно (особенно, если пересечение оказалось небольшим) - подобно тому, как работает поиск в Google, хотя я и неНе знаю всех подробностей их алгоритма
Спасибо за любые ответы или указатели в правильном направлении!