Search for rows in a 2D array that contain a given sequence

Question

I have a 2d array of m * n dimension (m and n can vary from 1 to 100000). The following snippet of code checks if the sequence exists in the row and stores the index if it exists. The time taken by the following code on 10000*10000 matrix is 650 milliseconds. The sequential version of the code also takes the same time.

This on Intel Core i7-7560U CPU @ 2.40GHz × 4

#include <iostream>
#include <vector>
#include <future>

std::vector<int> lps;

void ComputeLPSArray(std::vector<int> const &pattern) {

    std::vector<int> lps(pattern.size());
    int len = 0;

    lps[0] = 0;

    int i = 1;
    while (i < (int) pattern.size()) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}


int SearchPattern(std::vector<int> const &pattern, std::vector<int> const &row) {
    auto M = (int) pattern.size();
    auto N = (int) row.size();

    int i = 0;
    int j = 0;
    while (i < N) {

        if (pattern[j] == row[i]) {
            j++;
            i++;
        }
        if (j == M) {
            return 1;
        } else if (i < N && pattern[j] != row[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return -1;
}

std::vector<int> SearchSequence(std::vector<std::vector<int>> const &matrix, std::vector<int> const &sequence) {

    ComputeLPSArray(sequence);
    std::vector<int> result(matrix.size());
    unsigned int length = 0;
    std::vector<std::future<int>> f(matrix.size());

    for (unsigned int i = 0; i < matrix.size(); i++) {
        std::vector<int> row = matrix[i];
        f[i] = async(std::launch::async, [sequence, row] { return SearchPattern(sequence, row); });
    }

    for (unsigned int i = 0; i < f.size(); ++i) {
        if (f[i].get() == 1)
            result[length++] = i;
    }

    result.resize(length);

    return result;
}

int main() {

    int m = 25, n = 20; // assume `m` and `n` can vary.
    std::vector<std::vector<int >> matrix(m, std::vector<int>(n));

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            matrix[i][j] = rand() % 1000;
        }

    }

    std::vector<int> sequence = matrix[24]; // This is purely for testing purpose, actual input(matrix&sequence) is read from files.

    std::vector<int> result;
    result = SearchSequence(matrix, sequence); // This is the ONLY function which needs to be optimised.

    return 0;
}

How do I speed up the search time in this scenario?

Answer 1

I rewrote your SearchSequence function to be as absolutely brain-dead as possible:

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

std::vector<int> SearchSequence(std::vector<std::vector<int>> const &matrix, std::vector<int> const &sequence)
{
    std::vector<int> result;

    for (unsigned int i = 0; i < matrix.size(); i++) {
        auto it = std::search(matrix[i].begin(), matrix[i].end(), sequence.begin(), sequence.end());
        if (it != matrix[i].end()) {
            result.emplace_back(i);
        }
    }
    return result;
}

int main() {

    int m = 25000, n = 25000; // assume `m` and `n` can vary.
    std::vector<std::vector<int >> matrix(m, std::vector<int>(n));

    auto start_time = std::chrono::steady_clock::now();

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            matrix[i][j] = rand() % 1000;
        }
    }

    std::vector<int> sequence = matrix[9999]; // This is purely for testing purpose, actual input(matrix&sequence) is read from files.

    auto initial_time = std::chrono::steady_clock::now();
    std::cout
        << "Initializing the array with rand() took: "
        << std::chrono::duration_cast<std::chrono::milliseconds>(initial_time - start_time).count() << " ms\n";

    std::vector<int> result = SearchSequence(matrix, sequence); // This is the ONLY function which needs to be optimised.

    auto search_time = std::chrono::steady_clock::now();
    std::cout
        << "Executing the actual search took: "
        << std::chrono::duration_cast<std::chrono::milliseconds>(search_time - initial_time).count() << " ms\n";

    return 0;
}

On my laptop, this prints:

$ clang++ -std=c++14 -O3 ./x.cc
$ ./a.out
Initializing the array with rand() took: 5304 ms
Executing the actual search took: 2 ms

$ clang++ -std=c++14 -O0 ./x.cc
$ ./a.out
Initializing the array with rand() took: 7670 ms
Executing the actual search took: 8 ms

This is single-threaded, with absolutely no cleverness to the search at all — I'm just using the $O(n^2)$ std::search algorithm from the standard library.

I suggest that your business with std::vector<std::future<int>> is completely unnecessary, and that if you're measuring any slowness, it's slowness in initializing the matrix with random numbers.