时间戳

首页 > 解决方案 > 在向量末尾找到一个周期的最大频率的最快方法？

c++ - 在向量末尾找到一个周期的最大频率的最快方法？

问题描述

假设我有向量{ 1, 1, 2, 1, 1, 2 }，我想找出向量末尾一个周期的最大频率。在这种情况下，频率（卷曲）为 2，因为112重复了两次。而且由于任何重复至少两次的周期最多是向量长度的一半，所以我只需要扫描一半向量。

我正在寻找比较同一向量的各个部分的最快方法。根据最近的建议，我使用了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 循环看起来确实很可怕。基本上，它会尝试在向量序列的末尾找到匹配的周期，如果找到重复的周期，它会检查它延长了多长时间。任何关于更好实施或其他更快编写方法的建议都非常受欢迎！

根据要求提供一些示例：

假设向量序列是{ 1, 1, 2, 1, 1, 2 }它开始检查2向量末尾有多少个s，即1。接下来，它检查末尾有多少1, 2个s，即1。接下来，它检查1, 1, 2并发现这是重复的2次。因此，卷曲为 2。

假设向量序列是{ 2, 2, 2, 2 }从它开始2并找到其中的 4 个。接下来，它检查2, 2并找到其中的 2 个。因此，卷曲为 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).

标签： c++vector

解决方案

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.

我实现了多线程。使用了 1,000,000 ints 的向量，“最坏情况”全为零（因此每次比较都会运行子向量的全长）。单线程版本花了将近 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;
}

推荐阅读