정렬

Question

내가 좋아하는 정수의 많은 양의 벡터를 정렬하는 빠른 알고리즘을 작성하는 것을 시도하고는 : 159 14 5 97 6 54

지금까지, 내 ​​프로그램은 벡터로 나누기 같은 MSD에 의해 작은 버킷 :

012,356,741,175,816,278,272,381 :

bucket[1]:159 14 
bucket[5]:5 54 
bucket[6]:6 
bucket[9]:97 

지금은 가장 중요한 자리 순서 양동이를 정렬하는 재귀 기수 정렬을 사용하는 데 필요한거야 643,210

이 내가 온라인으로 볼 재귀 기수 코드 : 내 코드로이 비트를 구현하는 방법을 모르는

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit 
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does 
void radixSort(int* input, int size, int digit){ 
    if (size == 0) 
    return; 

    int[10] buckets; // assuming decimal numbers 

    // Sort the array in place while keeping track of bucket starting indices. 
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit), 
    // then let bucket[i+1] = bucket[i] 

    for (int i = 0; i < 10; ++i) 
    { 
    radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1); 
    } 
} 

, 나는 [] 위의 코드에 무엇을 버킷에 대해 확실하지 않다 . 아무도 내가 어떤 변화를 만들어야하는지 설명 할 수 있습니까? 다음은 내가 재귀 적으로 사용하지 않기 때문에 잘 수행되지 않는 멀티 쓰레드 코드입니다. 나는 내 코드에이 비트를 구현하는 방법을 모르는

void sort(unsigned int numCores, std::vector<unsigned int> numbersToSort){ 
// ******************Stage 1**************** 
// Use multithread to seperate numbers into buckets using the most significant digits 
    auto smallbuckets = std::vector<std::shared_ptr<std::vector<std::vector<unsigned int>>>>(); 
    std::mutex mutex; 

    unsigned int workload = numbersToSort.size()/numCores; 

    std::function<void(unsigned int, unsigned int, unsigned int)> put_small_buckets; 
    put_small_buckets = [this, &smallbuckets, &mutex] 
(unsigned int id, unsigned int start, unsigned int end) { 

    auto buckets = std::make_shared<std::vector<std::vector<unsigned int>>>(std::vector<std::vector<unsigned int>>()); 
    for (int j = 0; j < 10; ++j) { 
     buckets->push_back(std::vector<unsigned int>()); 
    } 

    for (unsigned int i = start; i < end; ++i) { 
     unsigned int a = numbersToSort[i]; 
     std::string tmp = std::to_string(a); 
     char c = tmp.at(0); 
     int ia = c - '0'; 
     (*buckets)[ia].push_back(numbersToSort[i]); 
    } 
    std::lock_guard<std::mutex> lock(mutex); 
    smallbuckets.push_back(buckets); 
    }; 

// create a container of threads 
    std::vector<std::shared_ptr<std::thread>> containerOfThreads; 

// create threads and add them to the container. 
    for (unsigned int i = 0; i < numCores; ++i) { 
    // start the thread. 
    unsigned int start = workload * i; 
    unsigned int end = workload * (i + 1); 
    if(i == numCores - 1) end = this->numbersToSort.size() ; 
    containerOfThreads.push_back(std::make_shared<std::thread>(put_small_buckets, i, start, end)); 
    } 

// join all the threads back together. 
    for (auto t : containerOfThreads) t->join(); 

    numbersToSort.clear(); 
// ******************Stage 2**************** 
// Put small multithreaded buckets back to the bucket of radix(10) 

    auto bigbuckets = std::vector<std::shared_ptr<std::vector<unsigned int>>>(); 
    for (int j = 0; j < 10; ++j) { 
    bigbuckets.push_back(std::make_shared<std::vector<unsigned int>>(std::vector<unsigned int>())); 
    } 

int current_index = 10; 

std::function<void()> collect; 
collect = [this, &smallbuckets, &current_index, &mutex, &collect, &bigbuckets]() { 
    mutex.lock(); 
    int index = --current_index; 
    mutex.unlock(); 
    if (index < 0) return; 
    auto mybucket = bigbuckets[index]; 
    for (auto i = smallbuckets.begin(); i != smallbuckets.end(); ++i) { 
     mybucket->insert(mybucket->end(), (*(*i))[index].begin(), (*(*i))[index].end()); 
    } 
    collect(); 
    }; 

// create a container of threads 
    containerOfThreads.clear(); 

// create threads and add them to the container. 
    for (unsigned int i = 0; i < numCores; ++i) { 
    containerOfThreads.push_back(std::make_shared<std::thread>(collect)); 
    } 

// join all the threads back together. 
    for (auto t : containerOfThreads) t->join(); 

// ******************Stage 3**************** 
// Sort big buckets 

    for (int j = 0; j < 10; ++j) { 
    bigbuckets.push_back(std::make_shared<std::vector<unsigned int>>(std::vector<unsigned int>())); 
    } 
    std::function<void(unsigned int, unsigned int)> sort_big_buckets; 
    sort_big_buckets = [this, &bigbuckets, &mutex] 
    (unsigned int start, unsigned int end) { 
    unsigned int curr = start; 
    while(curr < end){ 

     auto mybucket = bigbuckets[curr]; 
     std::sort(mybucket->begin(),mybucket->end(), [](const unsigned int& x, const unsigned int& y){ 
      std::string tmp1 = std::to_string(x); 
      std::string tmp2 = std::to_string(y); 
      return lexicographical_compare(tmp1.begin(), tmp1.end(), tmp2.begin(), tmp2.end()); 
      //return aLessB(x,y,0); 
     }); 
     ++curr; 
    } 
    }; 
// create a container of threads 
    containerOfThreads.clear(); 

    workload = 10/numCores; 
// create threads and add them to the container. 
    for (unsigned int i = 0; i < numCores; ++i) { 
    // start the thread. 
    unsigned int start = workload * i; 
    unsigned int end = workload * (i + 1); 
    if(i == numCores - 1) end = 10 ; 
    containerOfThreads.push_back(std::make_shared<std::thread>(sort_big_buckets, start, end)); 
    } 

// join all the threads back together. 
    for (auto t : containerOfThreads) t->join(); 
// put all elements back to numbersToSort 
    for (auto i = bigbuckets.begin(); i != bigbuckets.end(); ++i) { 
    numbersToSort.insert(numbersToSort.end(), (*i)->begin(), (*i)->end()); 
    } 
} 

Answer 1

, 나는 양동이 [] 위의 코드에서 할 일에 대해 확실하지 않다. 아무도 내가 어떤 변화를 만들어야하는지 설명 할 수 있습니까?

솔직히 말해 버킷 []은 필요하지 않습니다. 아이디어는 버킷 시작 색인을 여기에 보관하는 것이지만 나중에 버킷이 하나씩 동일한 순서로 처리되므로이 배열 대신 몇 가지 추가 변수를 사용할 수 있습니다.

내가 말했듯이 숫자를 문자열로 변환하고 문자열을 정렬해야합니다. 이렇게하면 모든 create-string-> compare-> destroy-string 연산을 수행하지 않고 버킷 당 1 문자를 확인할 수 있습니다. 결국 문자열을 다시 숫자로 변환해야합니다.

이 같을 수 요청 된 코드의 부분 :

void radixSort(std::vector<std::string>::iterator begin, std::vector<std::string>::iterator end, int digit){ 
    if (begin == end) 
     return; 

    // first skip short numbers 
    e = begin; 
    for (auto p = begin; p != end; ++p) 
     if (p->size() <= digit) 
     { 
      if (p != e) 
       std::swap(*p, *e); 
      q++; 
     } 
    if (e == end) 
     return; 

    for (char d = '0'; d <= '9'; ++d) 
    { 
     auto s = e; 
     for (auto p = e; p != end; ++p) 
      if (p->at(digit) == d) 
      { 
       if (p != e) 
        std::swap(*p, *e); 
       e++; 
      } 
     radixSort(s, e, digit+1); 
    } 
} 

는이 같은 것을 할 수있는 문자열 벡터를 정렬하려면 : 귀하의 질문에

radixSort(v.begin(), v.end(), 0);