Упорядоченный контейнер с постоянным временем вставки?

Question

Мне нужна помощь , ассоциативный контейнер со строковыми ключами, оцененный вектором цифр. Кроме того, мне нужно O(1) время вставки.

Мое описание звучит абстрактно, я дам вам сценарий:

Существует онлайн тест. Когда человек принимает этот тест, его имя добавляется в базу данных. Люди могут повторить тест, если захотят. Все их оценки будут записаны под их именем (что уникально). Например, Дэвид, Том, Алиса приходят и сдают экзамен несколько раз. Программа должна иметь возможность распечатать выход в следующем формате:

Alice 65 70 84 
David 98 97 93 
Tom 100 45 
... 

Как вы можете видеть их имена должны быть распечатаны в лексикографическом порядке. Всякий раз, когда кто-то принимает тест, его оценка добавляется в базу данных. Поскольку многие люди придут пройти тест, это должно быть O(1) сложность времени. Однако распечатка базы данных также происходит часто; говорят один раз в секунду. Поэтому было бы выгодно, чтобы не приходилось явно сортировать данные на каждом дисплее.

Какую структуру данных я могу использовать здесь? (STL является предпочтительным.) Я в настоящее время использую unordered_map, так как он дает мне O(1) вставки, но он не может перебирать ключи в лексикографическом порядке.

Answer 1

Учитывая, что реальный O (1) операция в этом случае является очень сложной проблемой, и вы предпочитаете использовать STL, я бы предложил что-то вроде следующих структур данных. Не то чтобы это не удовлетворяло вашим требованиям Big-Oh, и это не самый эффективный способ реализовать его даже с STL, но он прост и эффективен.

Ваша основная структура данных - std::map. Но для того, чтобы ускорить Lookups в O (1), вы можете использовать std::unordered_map так:

using std::map, std::string, std::vector, std::unordered_map; 

typedef map<string, vector<int> > TestTakersMap; 
typedef unordered_map<string, TestTakersMap::iterator> LookupAccelerator; 

Теперь ваши различные операции будут:

• Добавить новый человек: Вы вставляете в карту, но также вы добавляете имя и итератор на карте, где вы вставили новую запись в unordered_map. O (log (N)).
• Поиск человека: Используя unordered_map, вы можете получить итератор и данные для этого человека.ОжидаемыеO (1).
• Добавить новую оценку: Вы найдете человека, использующего unordered_map, а затем используйте итератор, который вы получили, чтобы добавить новый балл. АмортизированныйO (1).
• Распечатка всех имен и оценок: Вы итератор над самой картой и получите имена в лексикографическом порядке без добавления шага сортировки. Можно считать O (S), где S - общее количество баллов для всех участников.

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

ОБНОВЛЕНИЕ: Вы можете выполнять основные операции, такие как следующее. Включения и т. Д. Выглядят так:

#include <map> 
#include <string> 
#include <unordered_map> 
#include <vector> 

using std::map; 
using std::string; 
using std::unordered_map; 
using std::vector; 

Это очень простой класс для выполнения некоторых операций, которые вы хотите. Обратите внимание, что я использую возможности C++ 11 (auto, emplace, ...), но не воспринимайте этот код как особенно хороший стиль программирования; Я не могу ручаться за это.

class TestScores 
{ 
private: 
    typedef int ScoreType; 
    typedef vector<ScoreType> ScoreList; 
    typedef map<string, ScoreList> TestTakersMap; 
    typedef unordered_map<string, TestTakersMap::iterator> LookupAccelerator; 

public: 
    bool hasName (string const & new_name) const 
    { 
     return m_lookup.end() != m_lookup.find (new_name); 
    } 

    // Returns true if the name is really new 
    bool addName (string const & new_name) 
    { 
     if (hasName(new_name)) 
      return false; // name already in there 

     auto i = m_takers.emplace (new_name, vector<int>()).first; 
     m_lookup.emplace (new_name, i); 

     return true; 
    } 

    ScoreList const & getScores (string const & name) const 
    { 
     // This redirects to the private, non-const version 
     return const_cast<TestScores *>(this)->getScores(name); 
    } 

    void addScore (string const & name, ScoreType new_score) 
    { 
     getScores(name).push_back (new_score); 
    } 

private: 
    // If the name doesn't already exist, it is added! 
    ScoreList & getScores (string const & name) 
    { 
     if (!hasName(name)) 
      addName (name); 

     return m_lookup[name]->second; 
    } 

private: 
    TestTakersMap m_takers; 
    LookupAccelerator m_lookup; 
}; 

Answer 2

Контейнер, который может вставить в O(1) и дать упорядоченную итерацию в O(n), может использоваться для сортировки строк в линейном времени.

Мы можем сразу же заключить, что этот контейнер не работает только с компаратором, поскольку сортировка на основе компаратора имеет нижнюю границу O(n log n).

Существует только несколько алгоритмов сортировки, которые сортируются в линейном времени, и они, как правило, нуждаются в знаниях о вашем ключевом пространстве для работы. Инкрементная, «онлайн» версия такого алгоритма может быть вам полезна, и инкрементные внутренние данные, которые он использует, станут вашим контейнером.

Here - обсуждение алгоритмов сортировки по линейному времени.

Answer 3

Если вы действительно серьезно о размере ваших набор данных являются очень большими, и что вы абсолютно необходимы эффективным введение, поиск и лексикографической итерация, вы можете проверить Judy Arrays. Массивы Judy бывают быстрыми, эффективными с точки зрения памяти и trie-подобными ассоциативными структурами данных.

Вы можете проверить эти две реализации:

• Больший implementation from HP; похоже, под LGPL.
• A меньше implementation on Google Code; в соответствии с новой лицензией BSD.