c++ - 在 vector 末尾找到周期的最大频率的最快方法？

Question

假设我有 vector { 1, 1, 2, 1, 1, 2 } ，我想找出 vector 末尾的一个周期的最大频率。在本例中，频率 (curl) 为 2，因为 112 重复了两次。并且由于至少重复两次的任何周期最多是 vector 长度的一半，所以我只需要扫描一半的 vector 。

我正在寻找比较同一 vector 各部分的最快方法。根据最近的建议，我转而使用 std::equal()，但我不知道这是否是最好的功能，或者我是否以最快的方式使用它。

这是我目前的功能:

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;
        }
    }
}

while 循环看起来确实很可怕。基本上，它会尝试在 vector 序列的末尾找到匹配的周期，如果找到重复的周期，它会检查它延长了多长时间。非常欢迎任何关于更好的实现或其他更快的编写方法的建议!!

根据要求的一些例子:

假设 vector 序列是 { 1, 1, 2, 1, 1, 2 } 它开始检查 vector 末尾有多少个 2，即1。接下来，它检查最后有多少个1, 2，即1。接下来，它检查1, 1, 2，发现这个重复 2 次。因此，旋度为 2。

假设 vector 序列是 { 2, 2, 2, 2 } 它以 2 开头并找到其中的 4 个。接下来，它检查 2, 2 并找到其中的 2 个。因此，旋度为 4。

由于我必须为长达 1 亿左右的序列找到这些 curl ，所以我真的很想从中获得最大的 yield 。 (我确实使用了一些数学近似，但是这部分程序仍然占用了大部分时间，所以我跳过了那部分)。

Answer 1

现在(因为您不再复制子 vector )，几乎所有时间都花在比较值上。

我看到有两种独立的方法可以加快速度:矢量化比较操作(如果您的编译器不这样做)和并行处理不同的长度。

我实现了多线程。使用了一个包含 1,000,000 个 int 的 vector ，这是全零的“最坏情况”(因此每次比较都会运行子 vector 的全长)。单线程版本花费了将近 3 分钟，12 线程(在我的 6 核上)- 不到 30 秒。矢量化应该至少为您节省 50%(根据我过去的实验)。看到这个实现:https://community.intel.com/t5/Intel-ISA-Extensions/Q-on-memory-comparison-optimization/td-p/1041997

这是我的代码(为简单起见，我使用了全局变量):

#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;
}