Эффективный способ найти массив с наибольшим пересечением к входному массиву - PullRequest
Новая
       24

Эффективный способ найти массив с наибольшим пересечением к входному массиву

1 голос
/ 04 июня 2019

Скажем, у меня есть большой набор массивов (может быть размером до миллионов), и я хочу определить (желательно точно, хотя и приблизительно нормально) массив в этом наборе с наибольшим размером пересечения с входом, чтобудет самый эффективный способ сделать это?Я перечислю некоторые решения, которые приходили мне в голову, сводя это к другой проблеме, но я не уверен, что они обязательно являются лучшими.

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

Пример: скажем, мой набор массивов (отсортирован по принципу радиуса для удобства, можно отсортировать любым выбранным способом): 

[('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, хотя я и неНе знаю всех подробностей их алгоритма

Спасибо за любые ответы или указатели в правильном направлении!

Ответы [ 2 ]

2 голосов
/ 04 июня 2019

Заранее некоторые вопросы, которые я не смог задать через комментарий из-за отсутствия репутации:

  1. Все массивы уникальны, но каждый ли это массив сам по себе?
  2. Если более одногомассив имеет наибольший размер пересечения, вам нужно перечислить их все?
  3. Ваш ввод может быть длиннее самого длинного заданного массива?

Итерация

Без хэш-кода Iотсортирует массивы по длине и начнёт с самых длинных массивов, чтобы, возможно, пропустить более короткие массивы в конце, найдя размер пересечения, который просто больше или равен размеру более коротких массивов.

Если вы также сортируете массивыСами по себе вы можете использовать расстояние Хэммингтона, но вам не нужно сортировать и преобразовывать все массивы одновременно, а начинать только с их доли.Если вы не используете Hammington, имейте в виду, что, если вы сравниваете свои входные данные с массивом, который является вашим входом с размером +1, вам нужно будет сравнивать только до первого сравнения, где последний элемент вашего входного сигнала меньше текущего массиваelement.

af

ackz // поскольку k> f нам не нужно сравнивать f и z

Я думаю, что таксводится к сложности O (n lg n), так как сортировка массивов по размеру будет O (n lg n), вычисление размера n * O (1) и выполнение внутренней сортировки по осям O (n).Само сравнение будет O (n lg n) (не слишком уверенный в этом), поэтому итоговое значение будет O (n lg n) * 2 + 2 * O (n) => O (n lg n).

Дерево

Просто грубая идея: вы можете отсортировать все массивы с помощью Radix и преобразовать их в Хеммингтон, а оттуда заполнить ими дерево и проходить по нему, пока дальнейшее перемещение не приведет к меньшему расстоянию.Насколько это эффективно, я понятия не имею.

https://stackoverflow.com/a/6390606/9758920

0 голосов
/ 04 июня 2019

Я бы предложил простой подход с использованием хэш-наборов.
Если хэш-набор хорошо реализован, с хорошей хеш-функцией, то мы можем считать, что проверка, является ли элемент частью этого набора, может быть сделана в O(1).
Затем мы можем сделать следующее: 

function find_closest_arrays(A, B_1, ..., B_n) {
    result = [0, ..., 0] // array of size n
    for elem in A {
        for i in 1 ... n {
            if elem is in B_i {
                result[i] ++
            }
        }
    }
    return result
}

Эта функция возвращает массив result. result[i] содержит общее количество элементов между входным массивом A и B_i.
Отсюда получение k лучшего происходит довольно быстро, все, что вам нужно сделать, это получить индексы самого большого числа k в result.
Временная сложность этого алгоритма составляет O(n * m), с m размером входного массива и n размером набора массивов.

...