Najszybszy sposób na znalezienie największej częstotliwości okresu na końcu wektora?

Question

Powiedzmy, że mam wektor { 1, 1, 2, 1, 1, 2 }, chcę znaleźć największą częstotliwość okresu na końcu wektora. W tym przypadku częstotliwość (zwijanie) wynosi 2, ponieważ 112jest powtarzana dwukrotnie. A ponieważ każdy okres, który jest powtarzany co najmniej dwa razy, stanowi co najwyżej połowę długości wektora, potrzebuję tylko przeskanować połowę wektora.

Szukam najszybszego sposobu na porównanie części tego samego wektora. Zgodnie z ostatnią sugestią przeszedłem do użycia std::equal(), ale nie wiem, czy jest to najlepsza funkcja, czy też użyłem jej w najszybszy możliwy sposób.

To jest obecnie moja funkcja:

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

Pętla while wygląda dość przerażająco. Zasadniczo próbuje znaleźć pasujące okresy na końcu sekwencji wektora, a jeśli znajdzie powtarzający się okres, sprawdza, jak długo jest wydłużony. Wszelkie sugestie dotyczące lepszej implementacji lub innych, szybszych sposobów pisania tego są naprawdę mile widziane!

Zgodnie z prośbą o kilka przykładów:

Powiedzmy, że sekwencja wektora { 1, 1, 2, 1, 1, 2 }zaczyna sprawdzać, ile 2s znajduje się na końcu wektora, czyli 1. Następnie sprawdza, ile 1, 2s znajduje się na końcu, czyli 1. Następnie sprawdza 1, 1, 2i stwierdza, że ​​to się powtarza 2 czasy. Zatem skręt wynosi 2.

Powiedzmy, że sekwencja wektorów { 2, 2, 2, 2 }zaczyna się od 2i znajduje 4 z nich. Następnie sprawdza 2, 2i znajduje 2 z nich. Zatem skręt wynosi 4.

Ponieważ muszę znaleźć te loki dla sekwencji o długości do około 100 milionów, naprawdę chcę wycisnąć z nich jak najwięcej. (Używam matematycznego przybliżenia, ale ta część programu nadal zajmuje większość czasu, więc ją pominąłem).

Answer 1

Teraz (ponieważ nie tworzysz już kopii wektorów podrzędnych), prawie cały czas spędzasz na porównywaniu wartości.

Widzę dwa niezależne sposoby, aby to przyspieszyć: wektoryzację operacji porównania (jeśli twój kompilator tego nie robi) i równoległe przetwarzanie różnych length.

Zaimplementowałem wielowątkowość. Użyto wektora z 1 000 000 ints, „najgorszego przypadku” ze wszystkimi zerami (więc każde porównanie obejmuje całą długość wektora podrzędnego). Wersja jednowątkowa zajęła prawie 3 minuty, 12 wątków (na moim 6-rdzeniowym) - poniżej 30 sekund. Wektoryzacja powinna zaoszczędzić co najmniej 50% (na podstawie moich wcześniejszych eksperymentów). Zobacz to do realizacji:https://community.intel.com/t5/Intel-ISA-Extensions/Q-on-memory-comparison-optimization/td-p/1041997

Oto mój kod (użyłem globali dla uproszczenia):

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