ベクトルの終わりにあるピリオドの最大頻度を見つける最も速い方法は？
ベクトル{ 1, 1, 2, 1, 1, 2 }があるとしましょう。ベクトルの終わりにあるピリオドの最大頻度を調べたいと思います。この場合、頻度（curl）は2112です。これは、が2回繰り返されるためです。また、少なくとも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ループはかなり恐ろしいように見えます。基本的に、ベクトルシーケンスの最後で一致する期間を見つけようとし、繰り返される期間を見つけた場合は、それが延長されている時間をチェックします。より良い実装やこれを書くための他のより速い方法に関する提案は本当に大歓迎です!!
要求に応じていくつかの例：
ベクトルシーケンスは、ベクトルの最後にあるsの{ 1, 1, 2, 1, 1, 2 }数（1）2のチェックを開始するとします。次に、1, 2最後のsの数（1）をチェックします。次に、1, 1, 2これが繰り返されていることを確認します2回数。したがって、カールは2です。
ベクターシーケンスは、{ 2, 2, 2, 2 }で始まり2、これらのうち4つを見つけると言います。次に、2, 2これらのうち2つをチェックして見つけます。したがって、カールは4です。
約1億の長さまでのシーケンスでこれらのカールを見つける必要があるので、私は本当にそれを最大限に絞りたいと思っています。（私はいくつかの数学的近似を使用しますが、プログラムのこの部分はまだほとんどの時間を占めるので、その部分をスキップしました）。
回答
現在（サブベクトルのコピーを作成しなくなったため）、ほとんどすべての時間が値の比較に費やされています。
これを高速化する2つの独立した方法があります。比較操作をベクトル化する方法（コンパイラーが実行しない場合）と、異なるの処理を並列化する方法lengthです。
マルチスレッドを実装しました。1,000,000int秒のベクトルを使用しました。これは、すべてゼロの「最悪の場合」です（したがって、すべての比較でサブベクトルの全長が実行されます）。シングルスレッドバージョンはほぼ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;
}