벡터 끝에서주기의 가장 큰 주파수를 찾는 가장 빠른 방법은 무엇입니까?

Question

벡터가 있다고 가정하면 벡터 { 1, 1, 2, 1, 1, 2 }끝에서 기간의 가장 큰 빈도를 찾고 싶습니다. 이 경우 112두 번 반복 되므로 빈도 (컬)는 2 입니다. 그리고 적어도 두 번 반복되는 기간은 최대 벡터 길이의 절반이므로 벡터의 절반 만 스캔하면됩니다.

동일한 벡터의 부분을 비교하는 가장 빠른 방법을 찾고 있습니다. 최근 제안으로을 사용 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-loop는 꽤 끔찍해 보입니다. 기본적으로 벡터 시퀀스의 끝에서 일치하는 기간을 찾으려고 시도하고 반복되는 기간을 찾으면 연장 된 기간을 확인합니다. 더 나은 구현이나 다른 빠른 작성 방법에 대한 제안은 정말 환영합니다!

요청 된 몇 가지 예 :

벡터 시퀀스가 ​​벡터 의 끝에있는 s가 1 { 1, 1, 2, 1, 1, 2 }인지 확인하기 시작 한다고 가정 해 보겠습니다 2. 다음으로, 1, 2끝에있는 s가 1인지 확인합니다. 다음으로, 이것이 1, 1, 2반복되는 것을 확인 하고 찾습니다. 2 타임스. 따라서 컬은 2입니다.

벡터 시퀀스가 { 2, 2, 2, 2 }로 시작하여 24 개를 찾습니다. 다음 2, 2으로이 중 2 개를 확인 하고 찾습니다. 따라서 컬은 4입니다.

최대 약 1 억 길이의 시퀀스에 대해 이러한 컬을 찾아야하므로 최대한 활용하고 싶습니다. (나는 약간의 수학적 근사치를 사용하지만 프로그램의이 부분은 여전히 ​​대부분의 시간을 차지하므로 그 부분을 건너 뛰었습니다).

Answer 1

이제 (더 이상 하위 벡터의 복사본을 만들지 않으므로) 거의 모든 시간이 값을 비교하는 데 소비됩니다.

속도를 높이는 두 가지 독립적 인 방법이 있습니다 : 비교 작업을 벡터화 (컴파일러가 수행하지 않는 경우)하고 다른 처리를 병렬화 length합니다.

멀티 스레딩을 구현했습니다. 1,000,000 int초의 벡터를 사용했습니다 . "최악의 경우"는 모두 0입니다 (따라서 모든 비교는 하위 벡터의 전체 길이를 실행합니다). 단일 스레드 버전은 거의 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;
}