किसी वेक्टर के अंत में किसी अवधि की सबसे बड़ी आवृत्ति ज्ञात करने का सबसे तेज़ तरीका?

Nov 26 2020

कहो कि मेरे पास वेक्टर है { 1, 1, 2, 1, 1, 2 }, मैं वेक्टर के अंत में एक अवधि की सबसे बड़ी आवृत्ति का पता लगाना चाहता हूं। इस मामले में, आवृत्ति (कर्ल) 2 है, चूंकि 112दो बार दोहराया जाता है। और चूंकि किसी भी अवधि को कम से कम दो बार दोहराया जाता है, इसलिए यह सबसे अधिक आधा वेक्टर लंबाई है, मुझे केवल आधा वेक्टर के माध्यम से स्कैन करने की आवश्यकता है।

मैं उसी वेक्टर के हिस्सों की तुलना करने के लिए सबसे तेज़ तरीका ढूंढ रहा हूं। हाल के सुझाव पर, मैं उपयोग करने के लिए चला गया 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;
        }
    }
}

जबकि लूप काफी भयावह दिखता है। मूल रूप से, यह वेक्टर अनुक्रम के अंत में मिलान अवधि खोजने की कोशिश करता है, और यदि यह एक दोहराया अवधि पाता है, तो यह जांच करता है कि यह कितनी देर तक बढ़ाया गया है। बेहतर कार्यान्वयन या अन्य पर कोई सुझाव, यह लिखने के तेज़ तरीके वास्तव में स्वागत योग्य हैं !!

कुछ उदाहरणों का अनुरोध किया:

वेक्टर अनुक्रम कहो कि { 1, 1, 2, 1, 1, 2 }यह जाँचना शुरू 2कर रहा है कि वेक्टर के अंत में कितने s हैं, जो 1. है। अगला, यह जाँचता है कि कितने 1, 2s अंत में हैं, जो कि 1. अगला है, यह जाँचता है 1, 1, 2और पाता है कि यह दोहराया गया है 2 बार। इस प्रकार, कर्ल 2 है।

सदिश अनुक्रम कहो कि { 2, 2, 2, 2 }यह 24 से शुरू होता है और इनमें से 4 को खोजता है इसके बाद, यह जाँच करता है 2, 2और इनमें से 2 पाता है। इस प्रकार, कर्ल 4 है।

चूंकि मुझे लगभग 100 मिलियन की लंबाई तक अनुक्रमों के लिए इन कर्ल को ढूंढना है, मैं वास्तव में इसका सबसे अधिक निचोड़ करना चाहता हूं। (मैं कुछ गणितीय सन्निकटन का उपयोग करता हूं, लेकिन कार्यक्रम के इस भाग में अभी भी अधिकांश समय लगता है इसलिए मैंने उस भाग को छोड़ दिया)।

जवाब

1 VladFeinstein Nov 26 2020 at 05:21

अब (जैसा कि आप अब उप-वैक्टर की प्रतियां नहीं बनाते हैं), लगभग हर समय मूल्यों की तुलना करने में खर्च होता है।

मुझे इसे गति देने के दो स्वतंत्र तरीके दिखाई देते हैं: तुलनात्मक ऑपरेशन (यदि आपका कंपाइलर ऐसा नहीं करता है) को अलग करें और अलग-अलग प्रोसेसिंग को समानांतर करें length

मैंने मल्टी-थ्रेडिंग लागू किया। 1,000,000 के साथ एक वेक्टर का उपयोग किया गया int, सभी शून्य के साथ "सबसे खराब स्थिति" (इसलिए हर तुलना उप-वेक्टर की पूरी लंबाई को चलाता है)। एक एकल थ्रेडेड संस्करण को लगभग 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;
}