Maneira mais rápida de encontrar a maior frequência de um período no final de um vetor?

Nov 26 2020

Digamos que eu tenha o vetor { 1, 1, 2, 1, 1, 2 }, quero descobrir a maior frequência de um período no final do vetor. Neste caso, a frequência (curl) é 2, pois 112é repetido duas vezes. E uma vez que qualquer período que se repete pelo menos duas vezes tem no máximo metade do comprimento do vetor, eu só preciso examinar a metade do vetor.

Estou procurando a maneira mais rápida de comparar partes do mesmo vetor. Por sugestão recente, passei a usar std::equal(), mas não sei se essa é a melhor função ou se usei da maneira mais rápida possível.

Esta é minha função atualmente:

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

O loop while parece realmente horrível. Basicamente, ele tenta encontrar períodos coincidentes no final da seqüência vetorial e, se encontrar um período repetido, verifica por quanto tempo ele está estendido. Quaisquer sugestões sobre uma implementação melhor ou outras maneiras mais rápidas de escrever isso são realmente bem-vindas !!

Conforme solicitado, alguns exemplos:

Digamos que a sequência do vetor { 1, 1, 2, 1, 1, 2 }comece a verificar quantos 2s estão no final do vetor, que é 1. Em seguida, verifica quantos 1, 2s estão no final, que é 1. Em seguida, verifica 1, 1, 2e descobre que isso se repete 2 vezes. Portanto, o curl é 2.

Digamos que a seqüência de vetores { 2, 2, 2, 2 }comece com 2e encontre 4 deles. Em seguida, ele verifica 2, 2e encontra 2 deles. Portanto, o cacho é 4.

Já que preciso encontrar esses cachos para sequências de até 100 milhões de comprimento, eu realmente quero extrair o máximo deles. (Eu uso algumas aproximações matemáticas, mas esta parte do programa ainda ocupa a maior parte do tempo, então eu pulei essa parte).

Respostas

1 VladFeinstein Nov 26 2020 at 05:21

Agora (como você não faz mais cópias de subvetores), quase todo o tempo é gasto na comparação de valores.

Vejo duas maneiras independentes de acelerar isso: vetorizar a operação de comparação (se o seu compilador não fizer isso) e paralelizar o processamento de diferentes length.

Implementei o multi-threading. Usou um vetor com 1.000.000 ints, o "pior caso" com todos os zeros (portanto, cada comparação executa o comprimento total do subvetor). Uma única versão encadeada levou quase 3 minutos, os 12 encadeamentos (no meu 6-core) - menos de 30 segundos. A vetorização deve economizar pelo menos 50% (com base em minhas experiências anteriores). Veja isto para implementação:https://community.intel.com/t5/Intel-ISA-Extensions/Q-on-memory-comparison-optimization/td-p/1041997

Aqui está meu código (usei globais para simplificar):

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