Сортировка вектор с фиксированным числом целых чисел

Question

Векторный список vl имеет длину 100000000 с max. 101 различное целочисленное значение. Какой был бы лучший и быстрый алгоритм сортировки?

Я попробовал его с подсчетом сортировки (сортировка ковша), ..., но они недостаточно быстры. Каждый Integer (+ -) действителен. 100000000, 101 различных Целых генерируются случайным образом. Спасибо за ваш ответ! Мой лучший алгоритм составляет около 0,620s.

Answer 1

Используйте unorder_set, чтобы найти уникальные значения, затем поместите эти уникальные значения в vector и отсортируйте их; а затем поместить оригиналы в unorder_multiset рассчитывать значения, что-то вроде:

vector<int> v; 
// fill v with values 
unordered_set<int> s(begin(v), end(v)); 
vector<int> sorted_v(begin(s), end(s)); 
sort(begin(sorted_v), end(sorted_v)); 
unordered_multiset<int> v_count(begin(v), end(v)); 
for (size_t i = 0; i < sorted_v.size(); ++i) 
    cout << "For the " << i << "th value == " << sorted_v[i] << " there are " << v_count.count(v[i]) << " of them." << endl; 

Answer 2

Я считаю, что для решения этой задачи подсчета сортировки является наиболее подходящим. Однако, если все, что вам нужно, это просто скопировать отсортированный список целых чисел как можно быстрее, подумайте о том, чтобы не сохранять целые числа вообще, а только их счетчики на карте.

Answer 3

Согласно wiki (см. Таблицу сравнения алгоритмов), мы должны использовать сортировку подсчета, потому что у нас не так много разных значений.
Во-первых, я полагал, что наши ценности Интс 0-100, и используется следующий код:

void sort(std::vector<int>& v) 
{ 
    double start = std::clock(); 
    int* table = new int[MAX]; 
    for (int i = 0; i < MAX; ++i) 
    { 
     table[i] = 0; 
    } 
    for (int i = 0; i < size; ++i) 
    { 
     ++table[v[i]]; 
    } 
    int cur = 0; 
    for (int i = 0; i < MAX; ++i) 
    { 
     for (int j = 0; j < table[i]; ++j) 
     { 
      v[cur++] = i; 
     } 
    } 
    delete[] table; 
    std::cout << "count sort over char array took " << (std::clock() - start)/CLOCKS_PER_SEC << " s" << std::endl; 
} 

Этот код принял 0.149s на моем компьютере против 3.002s используется std::sort.

Это классическая реализация подсчета рода, но теперь пытаются ускорить его, удалить некоторые избыточные вычисления:

void sort6(int* v, int size) 
{ 
    double start = std::clock(); 
    int* table = new int[MAX]; 
    for (int i = 0; i < MAX; ++i) 
    { 
     table[i] = 0; 
    } 
    int* end = v + size; 
    for (int* vi = v; vi < end; ++vi) 
    { 
     ++table[*vi]; 
    } 
    int* cur = v; 
    for (int i = 0; i < MAX; ++i) 
    { 
     int count = table[i]; 
     for (int j = 0; j < count; ++j) 
     { 
      *(cur++) = i; 
     } 
    } 
    std::cout << "count sort with pointers over char array took " << (std::clock() - start)/CLOCKS_PER_SEC << " s" << std::endl; 
    delete[] v; 
    delete[] table; 
} 

Это дает примерно 0.076s.

Во-вторых, учитывая, что наши ценности не Интс 0-100, я использую следующий алгоритм:

• Найти все 101 различных номеров (с учетом равномерного распределения).
• Отсортируйте эти цифры.
• Поиск каждого из наших номеров 100000000 в этом массиве при выполнении сортировки.

К сожалению, на данный момент у меня нет времени для реализации этого и проверки, но я уверен, что ответ есть.

Answer 4

Вот полная реализация алгоритма, описанного некоторыми другими пользователями выше. Общая сложность алгоритма O (n).

#include <vector> 
#include <unordered_map> 
#include <algorithm> 
#include <cstdint> 

void special_sort(std::vector<int>& v, const size_t nExpectedMaxDifferentValues) 
{ 
    typedef int_fast32_t Value; 
    typedef size_t Count; 
    static_assert(sizeof(Value) >= sizeof(int), "please define Value to int on this platform"); 

    struct ValHash 
    { 
     inline std::size_t operator()(const Value k) const 
     { 
      return k; 
     } 
    }; 

    std::unordered_map<Value, Count, ValHash> counts; 

    counts.reserve(nExpectedMaxDifferentValues * 100); 
    for (const auto x : v) 
     ++counts[x]; 

    std::vector<Value> sorted_numbers; 
    sorted_numbers.reserve(counts.size()); 
    for (const auto& p : counts) 
     sorted_numbers.push_back(p.first); 

    std::sort(std::begin(sorted_numbers), std::end(sorted_numbers)); 

    // fill vector with sorted data: 
    int* p = v.data(); 
    for (const auto x : sorted_numbers) 
    { 
     for (Count i = counts[x]; i > 0; --i) 
     { 
      *p++ = x; 
     } 
    } 
} 

Основная функция для проверки скорости:

#include <random> 
#include <limits> 
#include <time.h> 
#include <iostream> 

int main() 
{ 
    std::cout << "Initialize..." << std::endl; 
    const size_t N = 100000000; 
    const size_t M = 101; 

    std::mt19937 gen(5); // use constant to easily reproduce the test 
    std::uniform_int_distribution<int> disInt(std::numeric_limits<int>::min(), std::numeric_limits<int>::max()); 
    std::vector<int> v1; 
    v1.reserve(M); 

    for (size_t i = 0; i < M; ++i) 
     v1.push_back(disInt(gen)); 

    std::uniform_int_distribution<size_t> disIndex(0, M-1); 
    std::vector<int> v2; 
    v2.reserve(N); 

    for (size_t i = 0; i < N; ++i) 
     v2.push_back(v1[disIndex(gen)]); 

    std::cout << "Sort..." << std::endl; 
    const clock_t begin_time = clock(); 

    special_sort(v2, M); 

    const double seconds = double(clock() - begin_time)/CLOCKS_PER_SEC; 
    std::cout << "Sorting took " << int(seconds * 1000) << " ms" << std::endl; 
    return 0; 
} 

выход программы из моего ноутбука (составитель MSVC 2013 Update 5 для x86_64, побежал на ядро ​​i7-4700MQ CPU @ 2.40ГГц):

Initialize... 
Sort... 
Sorting took 374 ms 

Есть целый ряд магических и наполовину волшебных оптимизаций, чтобы получить этот результат:

• Использование собственных тривиального хэш-функции: -50%
• Использование 100 в качестве множителя для хеш Количество ковша: -50%
• компиляции в x64 вместо 32-битного кода (x86): -25%
• Используйте C++ 11 Еогеаспа вместо эквивалента с итераторами: -33%

Answer 5

В дополнение к answer Сергею вы можете запустить счет параллельно с помощью нескольких потоков, что ускоряет процесс не менее 2 раз.

Таким образом, вместо:

std::unordered_map<int, size_t> counts; 
counts.reserve(nExpectedMaxDifferentValues * 100); 
for (const auto x : v) 
    ++counts[x]; 

мы могли бы породить несколько потоков, которые все делают часть работы (с использованием Windows, нарезание резьбы только для демонстрационных целей):

// Spawn 8 threads and spread the work 
const int numberOfThreads = 8; 
PartialResult partialResults[numberOfThreads]; 
HANDLE threadHandles[numberOfThreads]; 
const size_t partialSize = v.size()/numberOfThreads; 
std::vector<int>::iterator it = v.begin(); 
for (auto i = 0; i < numberOfThreads; i++) 
{ 
    partialResults[i].reserve = nExpectedMaxDifferentValues * 100; 
    partialResults[i].begin = it; 
    it += partialSize; 
    partialResults[i].end = (i == numberOfThreads - 1) ? v.end() : it; 
    threadHandles[i] = ::CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)partial_count, (LPVOID)&partialResults[i], 0, NULL); 
} 

// Wait for all threads to finish 
::WaitForMultipleObjects(numberOfThreads, threadHandles, TRUE, INFINITE); 
for (auto i = 0; i < numberOfThreads; i++) 
    ::CloseHandle(threadHandles[i]); 

// Aggregate counts (this could also be done in parallel) 
std::unordered_map<int, size_t> counts; 
counts.reserve(nExpectedMaxDifferentValues * 100); 
for (auto i = 0; i < numberOfThreads; i++) 
    for (const auto x : partialResults[i].counts) 
     counts[x.first] += x.second; 

Где PartialResult и partial_count является :

struct PartialResult { 
    std::unordered_map<int, size_t> counts; 
    std::vector<int>::iterator begin; 
    std::vector<int>::iterator end; 
    size_t reserve; 
}; 

DWORD WINAPI partial_count(_In_ LPVOID lpParameter) 
{ 
    auto partialResult = (PartialResult*)lpParameter; 
    partialResult->counts.reserve(partialResult->reserve); 
    for (auto it = partialResult->begin; it < partialResult->end; it++) 
     ++partialResult->counts[*it]; 
    return 0; 
} 

Выше кода приводит к выполнению время 390 мс вместо 860 мс на моей установке и может быть улучшено путем одновременного объединения частичных отсчетов.