Le moyen le plus rapide de trouver la plus grande fréquence d'une période à la fin d'un vecteur?

Question

Disons que j'ai le vecteur { 1, 1, 2, 1, 1, 2 }, je veux trouver la plus grande fréquence d'une période à la fin du vecteur. Dans ce cas, la fréquence (curl) est de 2, puisqu'elle 112est répétée deux fois. Et comme toute période répétée au moins deux fois est au plus égale à la moitié de la longueur du vecteur, je n'ai besoin de parcourir que la moitié du vecteur.

Je recherche le moyen le plus rapide de comparer des parties du même vecteur. Sur une suggestion récente, je suis allé utiliser std::equal(), mais je ne sais pas si c'est la meilleure fonction ou si je l'ai utilisée de la manière la plus rapide possible.

C'est ma fonction actuellement:

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

La boucle while semble assez horrible. Fondamentalement, il essaie de trouver des périodes correspondantes à la fin de la séquence vectorielle, et s'il trouve une période répétée, il vérifie pendant combien de temps il est prolongé. Toutes les suggestions sur une meilleure mise en œuvre ou d'autres moyens plus rapides d'écrire ceci sont vraiment les bienvenues !!

Comme demandé quelques exemples:

Disons que la séquence vectorielle { 1, 1, 2, 1, 1, 2 }commence à vérifier combien de 2s sont à la fin du vecteur, qui est 1. Ensuite, il vérifie combien de 1, 2s sont à la fin, qui est 1. Ensuite, il vérifie 1, 1, 2et trouve que cela est répété 2 fois. Ainsi, la boucle est de 2.

Disons que la séquence vectorielle { 2, 2, 2, 2 }commence par 2et en trouve 4. Ensuite, il vérifie 2, 2et en trouve 2. Ainsi, la boucle est de 4.

Puisque je dois trouver ces boucles pour des séquences d'une longueur maximale d'environ 100 millions, je veux vraiment en tirer le meilleur parti. (J'utilise une approximation mathématique, mais cette partie du programme prend encore la plupart du temps, alors j'ai sauté cette partie).

Answer 1

Maintenant (comme vous ne faites plus de copies de sous-vecteurs), presque tout le temps est passé à comparer les valeurs.

Je vois deux façons indépendantes d'accélérer cela: vectoriser l'opération de comparaison (si votre compilateur ne le fait pas) et paralléliser le traitement de différents length.

J'ai implémenté le multi-threading. Utilisé un vecteur avec 1 000 000 ints, le «pire des cas» avec tous les zéros (donc chaque comparaison exécute toute la longueur du sous-vecteur). Une version à un seul thread a pris près de 3 minutes, les 12 threads (sur mon 6-core) - moins de 30 secondes. La vectorisation devrait vous faire économiser au moins 50% (sur la base de mes expériences passées). Voir ceci pour la mise en œuvre:https://community.intel.com/t5/Intel-ISA-Extensions/Q-on-memory-comparison-optimization/td-p/1041997

Voici mon code (j'ai utilisé des globals pour plus de simplicité):

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