Объясните временную сложность этих функций группировки

Question

Здесь у меня есть 800 производных классов Base и список из 8000000 объектов этих типов, которые могут быть любого порядка. Цель состоит в том, чтобы максимально эффективно отнести список к 800 типам. Здесь я написал две функции для этого. Первый предположительно находится в O (M * logN) времени, где M - размер списка, а N = число конкретных производных классов Base, а второе, предположительно, в O (M) времени. Но когда я выхожу на выход, второй явно не log800 раз быстрее, чем первый. У меня была сложная временная сложность? Еще лучше, есть ли более быстрая функция, которая делает это целое сравнение спорным?

#include <iostream> 
#include <list> 
#include <unordered_map> 
#include <array> 
#include <ctime> 

class Base { 
public: 
    virtual std::size_t ID() const = 0; 
}; 

template <std::size_t N> class Derived : public Base { 
    virtual std::size_t ID() const override {return N;} 
}; 

const std::size_t NumDerivedTypes = 800; 

template <typename Iterator> 
std::unordered_map<std::size_t, std::list<typename Iterator::value_type>> separateWithMap (Iterator first, Iterator last) { 
    std::unordered_map<std::size_t, std::list<typename Iterator::value_type>> map; 
    while (first != last) { 
     const auto it = map.find ((*first)->ID()); 
     if (it != map.end()) { 
      it->second.emplace_back(*first); 
     } 
     else { 
      std::list<typename Iterator::value_type> newGroup = {*first}; 
      map.emplace ((*first)->ID(), newGroup); 
     } 
     first++; 
    } 
    return map; 
} 

template <typename Iterator> 
std::array<std::list<typename Iterator::value_type>, NumDerivedTypes> separateWithArray (Iterator first, Iterator last) { 
    std::array<std::list<typename Iterator::value_type>, NumDerivedTypes> array; 
    while (first != last) { 
     array[(*first)->ID()].emplace_back(*first); 
     ++first; 
    } 
    return array; 
} 

// ------------------------------- Testing ------------------------------- 
template <std::size_t N> 
void build (std::list<Base*>& weapons) { 
    weapons.emplace_back(new Derived<N>); 
    build<N+1>(weapons); 
} 

template <> 
void build<NumDerivedTypes> (std::list<Base*>&) {} // End of recursion. 

struct Timer { 
    const std::clock_t begin = std::clock(); 
    ~Timer() { 
     auto end = std::clock(); 
     std::cout << double(end - begin)/CLOCKS_PER_SEC << " seconds.\n"; 
    }; 
}; 

int main() { 
    // M = scrambled.size(), N = number of concrete derived classes of Base. 
    std::list<Base*> scrambled; 
    for (std::size_t i = 0; i < 10000; i++) 
     build<0>(scrambled); // Assume 'scrambled' has many, many elements in some unknown order. 
    std::cout << "scrambled.size() = " << scrambled.size() << '\n'; // 8000000 

    { 
     std::cout << "\nseparateWithMap started:\n"; // O(M*logN) time 
     Timer timer; 
     const std::unordered_map<std::size_t, std::list<Base*>> separated = separateWithMap (scrambled.begin(), scrambled.end()); 
     std::cout << "separateWithMap ended:\n"; 
    } 
    { 
     std::cout << "\nseparateWithArray started:\n"; // O(M) time    
     Timer timer; 
     const std::array<std::list<Base*>, NumDerivedTypes> partitioned = separateWithArray (scrambled.begin(), scrambled.end()); 
     std::cout << "separateWithArray ended:\n"; 
    } 
} 

Выход:

scrambled.size() = 8000000 

separateWithMap started. 
separateWithMap ended. 
30.318 seconds. 

separateWithArray started. 
separateWithArray ended. 
22.869 seconds. 

Кстати, обе эти функции успешно отделить объекты в их соответствующих типов (проверено), но я не показывают, что в выходных данных, по понятным причинам.

Answer 1

Первый предположительно в O (M * LogN) раз, где М является размер списка, и N = число конкретных полученных классов базы

Это не хотя. unordered_map - хэш-таблица, lookup и insertion имеют среднюю постоянную сложность. Итак, первый по-прежнему O(M). Просто с большим количеством работы, чем с простой версией массива.

В качестве побочного сведению, используя operator[] упростило бы логика немного:

for (; first != last; ++first) { 
    map[(*first)->ID()].emplace_back(*first); 
} 

Точно так же как версии массива.