Der schnellste Weg, um die größte Frequenz einer Periode am Ende eines Vektors zu finden?

Nov 26 2020

Angenommen, ich habe den Vektor { 1, 1, 2, 1, 1, 2 }, ich möchte die größte Häufigkeit einer Periode am Ende des Vektors herausfinden. In diesem Fall beträgt die Frequenz (Curl) 2, da 112sie zweimal wiederholt wird. Und da jede Periode, die mindestens zweimal wiederholt wird, höchstens die Hälfte der Vektorlänge beträgt, muss ich nur die Hälfte des Vektors durchsuchen.

Ich suche nach dem schnellsten Weg, um Teile desselben Vektors zu vergleichen. Auf jüngsten Vorschlag habe ich mich für die Verwendung entschieden std::equal(), aber ich weiß nicht, ob dies die beste Funktion ist oder ob ich sie auf die schnellstmögliche Weise verwendet habe.

Dies ist derzeit meine Funktion:

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

Die while-Schleife sieht ziemlich schrecklich aus. Grundsätzlich wird versucht, übereinstimmende Perioden am Ende der Vektorsequenz zu finden, und wenn eine wiederholte Periode gefunden wird, wird überprüft, wie lange sie verlängert wird. Vorschläge für eine bessere Implementierung oder andere, schnellere Schreibweisen sind herzlich willkommen !!

Wie gewünscht einige Beispiele:

Angenommen, die Vektorsequenz { 1, 1, 2, 1, 1, 2 }beginnt zu prüfen, wie viele 2s sich am Ende des Vektors befinden, nämlich 1. Als nächstes prüft sie, wie viele 1, 2s sich am Ende befinden, dh 1. Als nächstes prüft sie 1, 1, 2und stellt fest, dass dies wiederholt wird 2 mal. Somit beträgt die Locke 2.

Angenommen, die Vektorsequenz { 2, 2, 2, 2 }beginnt mit 2und findet 4 davon. Als nächstes prüft 2, 2und findet es 2 davon. Somit beträgt die Locke 4.

Da ich diese Locken für Sequenzen bis zu einer Länge von etwa 100 Millionen finden muss, möchte ich wirklich das Beste daraus machen. (Ich verwende eine mathematische Näherung, aber dieser Teil des Programms nimmt immer noch ungefähr die meiste Zeit in Anspruch, so dass ich diesen Teil übersprungen habe).

Antworten

1 VladFeinstein Nov 26 2020 at 05:21

Jetzt (da Sie keine Kopien von Untervektoren mehr erstellen) wird fast die gesamte Zeit für den Vergleich von Werten aufgewendet.

Ich sehe zwei unabhängige Möglichkeiten, um dies zu beschleunigen: Vektorisieren Sie die Vergleichsoperation (wenn Ihr Compiler dies nicht tut) und parallelisieren Sie die Verarbeitung verschiedener length.

Ich habe das Multithreading implementiert. Verwendet einen Vektor mit 1.000.000 ints, den "schlimmsten Fall" mit allen Nullen (so läuft jeder Vergleich über die gesamte Länge des Untervektors). Eine Single-Threaded-Version dauerte fast 3 Minuten, die 12-Threads (auf meinem 6-Core) - unter 30 Sekunden. Durch die Vektorisierung sollten Sie mindestens 50% einsparen (basierend auf meinen früheren Experimenten). Siehe dies für die Implementierung:https://community.intel.com/t5/Intel-ISA-Extensions/Q-on-memory-comparison-optimization/td-p/1041997

Hier ist mein Code (der Einfachheit halber habe ich Globals verwendet):

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