Неупорядоченное множество (const char) намного медленнее, чем неупорядоченное множество (строка) - PullRequest
Новая
       8

Неупорядоченное множество (const char) намного медленнее, чем неупорядоченное множество (строка)

4 голосов
/ 30 июня 2011

Я загружаю очень длинный список с диска в unordered_set.Если я использую набор строк, это очень быстро.Тестовый список размером около 7 МБ загружается за 1 секунду.Однако использование набора указателей на символы занимает около 2,1 минуты!

Вот код для строковой версии: 

unordered_set<string> Set;
string key;
while (getline(fin, key))
{
    Set.insert(key);
}

Вот код для версии char *: 

struct unordered_eqstr
{
    bool operator()(const char* s1, const char* s2) const
    {
        return strcmp(s1, s2) == 0;
    }
};

struct unordered_deref
{
    template <typename T>
    size_t operator()(const T* p) const
    {
        return hash<T>()(*p);
    }
};

unordered_set<const char*, unordered_deref, unordered_eqstr> Set;
string key;

while (getline(fin, key))
{
    char* str = new(mem) char[key.size()+1];
    strcpy(str, key.c_str());
    Set.insert(str);
}

«new (mem)» заключается в том, что я использую собственный менеджер памяти, чтобы я мог выделять большие блоки памяти и выдавать их крошечным объектам, таким как строки c.Тем не менее, я проверил это с обычным «новым» и результаты идентичны.Я также использовал свой менеджер памяти в других инструментах без проблем.

Две структуры необходимы для вставки и поиска хеш-функции на основе фактической строки c, а не ее адреса.Unordered_deref, который я обнаружил здесь при переполнении стека.

В конечном итоге мне нужно загрузить файлы объемом несколько гигабайт.Вот почему я использую собственный менеджер памяти, но также и то, почему это ужасное замедление недопустимо.Есть идеи?

1 Ответ

4 голосов
/ 01 сентября 2011

Вот и мы. 

struct unordered_deref
{
    size_t operator()(const char* p) const
    {
        return hash<string>()(p);
    }
};
...