Какой самый быстрый способ поиска последовательности чисел в двумерном векторе?

Question

Учитывая 2d массив ( массив может быть больше чем 10k * 10k ) с целочисленными значениями, как быстрее найти данную последовательность чисел в массиве?

Предположим, что двумерный массив, который находится в файле, читается в большой 1d вектор и доступен как big_matrix (строка * x + ширина).Есть 3 типа поиска, которые я хотел бы сделать в одном и том же массиве.Это поиск по заказу, поиск по порядку, поиск лучшего соответствия.Вот мой подход к каждой из функций поиска.

Упорядоченный поиск : Эта функция находит все строки, в которых присутствует данная числовая последовательность (порядок чисел имеет значение).Вот метод KMP для поиска заданной числовой последовательности, которую я реализовал:

void searchPattern(std::vector<int> const &pattern, std::vector<int> const &big_matrix, int begin, int finish,
                         int width, std::vector<int> &searchResult) {

    auto M = (int) pattern.size();
    auto N = width; // size of one row

    while (begin < finish) {
        int i = 0;
        int j = 0;
        while (i < N) {
            if (pattern[j] == big_matrix[(begin * width) + i]) {
                j++;
                i++;
            }
            if (j == M) {
                searchResult[begin] = begin;
                begin++;
                break;
            } else if (i < N && pattern[j] != big_matrix[(begin * width) + i]) {
                if (j != 0)
                    j = lps[j - 1]; // lookup table as in KMP
                else
                    i = i + 1;
            }
        }
        if (j != M) {
            searchResult[begin] = -1;
            begin++;
        }
    }
}

Сложность: O (m * n);m - количество строк, n - количество столбцов

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

void SearchUnordered/BestMatch(std::vector<int> const &match, std::vector<int> const &big_matrix_sorted, int begin, int finish,
                     int width, std::vector<int> &searchResult) {
    std::vector<int>::iterator it;
    std::vector<int> v(match.size() + width);
    while (begin < finish) {
        it = std::set_intersection(match.begin(), match.end(), big_matrix_sorted.begin() + begin * width,
                                   big_matrix_sorted.begin() + begin * width + width, v.begin());
        v.resize(it - v.begin());
        if (v.size() == subseq.size())
        searchResult[begin] = begin;
        else
        searchResult[begin] = -1;
        begin++;
        /* For search best match the last few lines will change as follows:
      searchResult[begin] = (int) v.size();
      begin++; and largest in searchResult will be the result */
    }
}

Сложность: O (m * (l + n));l - длина шаблона, m - количество строк, n - количество столбцов.

Предварительная обработка big_matrix (Построение таблицы поиска, сохранение отсортированной версии.разрешено выполнять любые предварительные операции.) не учитывается .Как я могу улучшить сложность (до O (log (m * n) )) этих функций поиска?

Answer 1

При поиске точного соответствия вы можете сделать это достаточно эффективно, используя то, что я назову « moving hash ».

При поиске вы вычисляете хеш в строке поиска и в то же время продолжаете вычислять движущийся хеш для данных, которые вы ищете.При сравнении вы сначала сравниваете хеш, и только если это совпадение, вы затем продолжаете и сравниваете фактические данные.

Теперь галочка состоит в том, чтобы выбрать алгоритм хеширования, который может легко обновляться каждый раз, когда вы перемещаетесь на одно место, вместо того, чтобы все пересчитывать.Примером такого хэша является, например,.сумма всех цифр.

Если у меня есть следующий массив: 012345678901234567890, и я хочу найти 34567 в этом массиве, я мог бы определить хэш как сумму всех цифр в поискестрока.Это даст хэш 25 (3 + 4 + 5 + 6 + 7).Затем я бы провел поиск в массиве и продолжал обновлять работающий хэш в массиве.Первый хэш в массиве будет 10 (0 + 1 + 2 + 3 + 4), а второй хэш будет 15 (1 + 2 + 3 + 4 + 5).Но вместо того, чтобы пересчитать второй хеш, я могу просто обновить предыдущий хеш, добавив 5 (новая цифра) и вычтя 0 (старая цифра).

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

Answer 2

Если вы хотите сделать это быстрее, но у вас уже есть правильный алгоритм.Вы можете добиться некоторой производительности, просто оптимизировав код (распределение памяти, удаление дублирующих операций, если компилятор этого не сделал и т. Д.).Например, может получить усиление, удалив два big_matrix[(row * width) + i] и присвоив его локальной переменной.Будьте внимательны, чтобы составить профиль и измерить реалистичные случаи.

Для большего усиления можно выбрать темы.Здесь вы можете обрабатывать по одной строке за раз, поэтому должно быть примерно линейное ускорение с количеством ядер.C ++ 11 имеет std::async, который может выполнять часть работы по запуску потоков и получению результатов, вместо того, чтобы иметь дело с std::thread самостоятельно или с механизмами, специфичными для платформы.Есть и другие новшества, которые также могут быть полезны в новых версиях C ++.

void searchPatternRow(std::vector<int> const &pattern, std::vector<int> const &big_matrix, int row, int width, std::vector<int> &searchResult);
void searchPattern(std::vector<int> const &pattern, std::vector<int> const &big_matrix, int begin, int finish, int width, std::vector<int> &searchResult)
{
    std::vector<std::future<void>> futures;
    for (int row = begin; row < finish; ++row)
        std::async([&, row]() { searchPatternRow(pattern, big_matrix, row, width, searchResult);  });
    for (auto &future : futures) future.wait(); // Note, also implicit when the future from async gets destructed
}

Для повышения эффективности работы с потоками вы можете выполнить пакетную обработку и выполнить поиск, скажем, по 10 строкам.Есть также некоторые соображения относительно потоков, записывающих в одну и ту же строку кэша для searchResult.