Нахождение пар векторов, где ни один элемент первого не меньше, чем этот элемент во втором - PullRequest
Новая
       14

Нахождение пар векторов, где ни один элемент первого не меньше, чем этот элемент во втором

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

Это обобщение Как сравнить каждый элемент в двух массивах с временной сложностью меньше, чем O (n ^ 2) . Скажем, у нас есть две матрицы A и B размером nxk и mxk, адресуемые как A[row][col] и B[row][col]. Пусть пара (i, j) будет приемлемой, если для каждого r, A[i][r] >= B[j][r]. Есть ли способ определить каждую приемлемую пару быстрее, чем наивный O (nmk) 

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        bool accept = true;
        for (int r = 0; r < k && accept; ++r) {
            accept &= (A[i][r] >= B[j][r]);
        }
        if (accept) { std::cout << i << ", " << j << "\n"; }
    }
}

Если k = 1, тогда я могу использовать решение, вытекающее из связанного вопроса, чтобы выполнить задачу за n log n раз. Однако, когда k> 1, это становится более сложным из-за таких матриц: 

A[0] = {1, 1}
A[1] = {3, 1}
A[2] = {3, 5}
A[3] = {5, 3}
A[4] = {5, 5}

B[0] = {2, 4}
B[1] = {4, 2}

Допустимые пары: (2, 0), (4, 0), (3, 1) и (4, 1). Сортировка по первому элементу дает порядок выше, где то, что приемлемо для B = 1, является смежным (A = 3 и A = 4), но то, что приемлемо для B = 0, нет. Сортировка по второму элементу аналогичным образом делает то, что приемлемо для B = 0, смежным, а то, что приемлемо для B = 1, нет. Выполнение одного прохода сортировки и считывания смежных диапазонов, например, решение k = 1, похоже, не работает.

Конкретный параметр, который я имею в виду для этой проблемы, имеет n и m порядка миллионов, а k порядка тысячи, поэтому время nmk не очень практично.

1 Ответ

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

Размер вывода может быть nm, поэтому алгоритм не может иметь лучшую производительность, чем O (нм). Улучшение среднего случая, безусловно, возможно, но во многом зависит от ваших данных и распределения. Вот несколько общих советов:

Если вы можете позволить себе m * k памяти, вы можете хранить отсортированный список индексов B, упорядоченный по значению первого столбца. То же самое для второго столбца и так далее. С помощью этой структуры + бинарный поиск вы можете ответить на вопрос о том, задан ли фиксированный столбец c и фиксированное число x, сколько B [j] [c] <= x в O (log m). </p>

Затем для каждого значения x в A [i] вы можете проверить, сколько B [j] [c] <= x. Сортировать их по этому количеству. Первое значение (назовем его L1) будет самым низким числом, поэтому вы будете сравнивать с B из отсортированного списка по этому столбцу. Используя бинарный поиск, вы можете пропустить начало и сравнить только с массивами L1 из B. </p>

Вместо сравнения столбец за столбцом в любом порядке, вы можете сравнить порядок, который мы сохранили из расчетов B [j] [c] <= x. Это будет означать, что второе значение, которое мы используем из A, будет иметь наименьший шанс по сравнению с остальными столбцами быть ниже, чем значения в B. Это поможет минимизировать сравнения для пар, которые не удовлетворяют условиям. </p>

...