Какое элегантное решение существует для этого шаблона? Многоуровневый поиск

Question

Предположим, что у нас есть несколько массивов целых чисел. Вы можете рассматривать каждый массив как уровень. Мы пытаемся найти последовательность элементов, ровно по одному элементу из каждого массива, и переходим к следующему массиву с тем же предикатом. Например, у нас есть v1, v2, v3 в качестве массивов:

v1  | v2  | v3
-----------------
1   | 4   | 16
2   | 5   | 81
3   | 16  | 100
4   | 64  | 121

Я мог бы сказать, что предикат: next_element == previous_element^2
Допустимая последовательность из приведенного выше примера: 2 -> 4 -> 16
На самом деле, в этом примере нет другой допустимой последовательности. Я мог бы написать три цикла для грубой силы в упомянутом примере, , но что если число массивов будет переменным , но, конечно, с известным порядком, как бы вы решили эту проблему?

Подсказки, или ссылки на скороговорки очень приветствуются. Я сделаю это на C ++, но мне просто нужна идея.

Спасибо

Answer 1

(Шаблоны проектирования применяются для разработки классов и API для улучшения качества кода, но не для решения вычислительных задач.)

В зависимости от случаев:

1. Если массивы располагаются в случайном порядке, и у вас есть конечное требование к пространству, то единственным решением является грубая сила. O (N ^k ) время (k = 3), O (1) пробел.
2. Если предикат не является обратимым (например, SHA1(next_elem) xor SHA1(prev_elem) == 0x1234), то грубая сила также является единственным решением.
3. Если вы можете расходовать пространство, то создайте хэш-наборы для v2 и v3, чтобы вы могли быстро найти следующий элемент, который удовлетворяет предикату. O (N + b ^k ) время, O (кН) пространство. (b = максимальное количество next_elem, которые удовлетворяют предикату, заданному prev_elem)
4. Если массивы отсортированы и ограничены, вы также можете использовать бинарный поиск вместо хеш-таблицы, чтобы избежать использования пробела. O (N (log N) ^k-1 + b ^k ) время, O (1) пробел.

(Количество мест не учитывает использование стека из-за рекурсии.)

Общий способ, который потребляет до O (Nb ^k ) пространства, заключается в построении решения путем последовательной фильтрации, например,

solutions = [[1], [2], ... [N]]

filterSolution (Predicate, curSols, nextElems) {
   nextSols = []
   for each curSol in curSols:
      find elem in nextElems that satisfy the Predicate
      append elem into a copy of curSol, then push into nextSols
   return nextSols
}

for each levels:
  solutions = filterSolution(Predicate, solutions, all elems in this level)
return solutions

Answer 2

Если вы заранее упорядочите свои массивы, поиск может быть выполнен намного быстрее. Вы можете начать с меньшего массива, а затем выполнить двоичный поиск ожидаемых чисел на каждом из них. Это будет O (n k logM), n - размер наименьшего массива, k - номера массивов, M - размер большего массива

Это может быть сделано даже быстрее, если вы используете Hashmaps вместо массивов. Это позволит вам искать в O (n * k).

Если использование обратных функций (для поиска в более ранних массивах) не вариант, то вы должны начать с первого массива, а n = размер первого массива.

Для простоты я начну с первого массива

//note the 1-based arrays
for (i : 1 until allArrays[1].size()) {
  baseNumber = allArrays[1][i];
  for (j: 2 until allArrays.size()) {
    expectedNumber = function(baseNumber);
    if (!find(expectedNumber, allArrays[j]))
        break;
    baseNumber = expectedNumber;
  }
}

Вы, вероятно, можете сделать несколько нулевых проверок и добавить туда некоторые логические значения, чтобы узнать, существует последовательность или нет

Answer 3

Если предикаты сохраняют порядок в массивах (например, в вашем примере, если все значения гарантированно неотрицательны), вы можете адаптировать алгоритм слияния. Рассмотрим ключ для каждого массива как конечное значение (то, что вы получите после применения предиката столько раз, сколько необходимо для всех массивов).

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

В основном, проверьте, равно ли следующее конечное значение для всех массивов. Если нет, перешагните через самое низкое (только в одном массиве) и повторите. Если все три равны, то это (возможное) решение - перешагните через все три, прежде чем искать следующий.

«Возможное» решение, потому что вам может потребоваться выполнить проверку - если функция предиката может сопоставить более одного входного значения с одним и тем же выходным значением, может возникнуть случай, когда значение найдено в некоторых массивах (но не в первом или последнее) неправильно.

EDIT - могут быть большие проблемы, когда предикат не сопоставляет каждый вход с уникальным выходом - в данный момент не может думать. По сути, подход слияния может работать хорошо, но только для определенных типов предикатов.

Answer 4

Я бы оставил все векторы как heaps , чтобы у меня была сложность O(log n) при поиске элемента. Таким образом, в общей сложности k векторов вы получите сложность, такую ​​как O(k * log n)

Answer 5

Вы можете создать отдельный индекс, который отобразит индекс из одного массива в индекс другого. Из индекса вы можете быстро увидеть, существует решение или нет.

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