Fastest way to find the largest frequency of a period at the end of a vector?

user_14695150 0
Viewed 132

Say I have the vector { 1, 1, 2, 1, 1, 2 }, I want to find out the largest frequency of a period at the end of the vector. In this case, the frequency (curl) is 2, since 112 is repeated twice. And since any period that is repeated at least twice is at most half the vector length, I only need to scan through half the vector.

I am looking for the fastest way to compare parts of the same vector. On recent suggestion, I went over to use std::equal(), but I don't know whether this is the best function or if I used it in the fastest possible way.

This is my function currently:

vector<int> sequence = someVec;
int curl = 1;
for (int length = 1; length <= sequence.size()/2); ++length) {
    int freq = 1;
    while ((freq + 1) * length <= sequence.size() and std::equal(sequence.end() - (freq + 1) * length, sequence.end() - freq * length, sequence.end() - length)) {
        ++freq;
        if (freq > curl) {
            curl = freq;
        }
    }
}

The while-loop does look quite horrendous. Basically, it tries to find matching periods in the end of the vector sequence, and if it finds a repeated period, it checks for how long it is extended. Any suggestions on better implementation or other, faster ways of writing this are really welcome!!

As requested some examples:

Say the vector sequence is { 1, 1, 2, 1, 1, 2 } it starts checking how many 2s are at the end of the vector, which is 1. Next, it checks how many 1, 2s are at the end, which is 1. Next, it checks 1, 1, 2 and finds that this is repeated 2 times. Thus, the curl is 2.

Say the vector sequence is { 2, 2, 2, 2 } it starts with 2 and finds 4 of these. Next, it checks 2, 2 and finds 2 of these. Thus, the curl is 4.

Since I have to find these curls for sequences up to about a length of 100 million, I really want to squeeze the most out of it. (I do use some mathematical approximation, but this part of the program still takes up about most of the time so I skipped that part).

vector c++
1 Answers

Now (as you no longer make copies of sub-vectors), almost all the time is spent in comparing values.

I see two independent ways to speed this up: vectorize the compare operation (if your compiler doesn't do it) and parallelize processing of different length.

I implemented the multi-threading. Used a vector with 1,000,000 ints, the "worst case" with all zeroes (so every compare runs the full length of the sub-vector). A single threaded version took almost 3 minutes, the 12-threads (on my 6-core) - under 30 seconds. Vectorization should save you at least 50% (based on my past experiments). See this for implementation: https://community.intel.com/t5/Intel-ISA-Extensions/Q-on-memory-comparison-optimization/td-p/1041997

Here is my code (I used globals for simplicity):

#include <iostream>
#include <vector>
#include <mutex>
#include <thread>
#include <atomic>
#include <chrono>

// worst case scenario - all zeroes
std::vector<int> s(1'000'000);
std::mutex m_curl;
unsigned int curl = 1;
std::atomic<int> length;

unsigned int get_curl(int length)
{
  unsigned int local_curl = 1;
  unsigned int freq = 1;
  while ((freq + 1) * length <= s.size() and std::equal(s.end() - (freq + 1) * length, s.end() - freq * length, s.end() - length)) {
    ++freq;
    if (freq > local_curl) {
      local_curl = freq;
    }
  }
  return local_curl;

}

void worker()
{
  unsigned int thread_curl = 1;
  while (true)
  {
    int current_length = length.fetch_sub(1);
    if (current_length <= 0)
      break;
    int local_curl = get_curl(current_length);
    if (local_curl > thread_curl) {
      thread_curl = local_curl;
    }
  }
  // sync access to the curl
  {
    std::lock_guard<std::mutex> l(m_curl);
    if (thread_curl > curl) {
      curl = thread_curl;
    }
  }
}

int main() {
  auto t1 = std::chrono::high_resolution_clock::now();
  length = s.size() / 2;
  // create reasonable number of threads
  static const int n = std::thread::hardware_concurrency();
  std::vector<std::thread> threads;
  for (int i = 0; i < n; ++i)
    threads.emplace_back(std::thread(worker));
  // wait for all of them to finish
  for (int i = 0; i < n; ++i)
    threads[i].join();

  auto t2 = std::chrono::high_resolution_clock::now();
  std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() << std::endl;
  return curl;
}
user_43941690
Related