Войти
ПрограммированиеФорумОбщее

Быстрая загрузка огромного словаря из файла

Страницы: 1 2 Следующая »
#0
18:49, 27 мар. 2016

Есть файл, в нём 500 000 элементов. У каждого элемента есть имя длиной порядка 20-30 символов, дальше идут данные длиной около килобайта. Нужно, чтобы программа могла быстро ориентироваться в этом файле и находить данные по имени.
Сейчас я тупо завёл unordered_map<string, uint32_t>, где ключ - имя, а значение - номер элемента в файле. И завёл массив, который содержит информацию обо всех элементах - позиция элемента в файле и его имя. Понятно, что структура неоптимальная и её ещё надо оптимизировать. Как минимум избавиться от дублирования строк и их аллокаций.
Вот только не совсем понятен момент, как я сохраню полученный индекс в файл, чтобы потом его быстро прочитать и быстро искать? unordered_map вроде не позволяет сохранить своё внутренное представление в файл, а потом читать оттуда. Если сохранять по одному элементу, а потом читать и добавлять в unordered_map по одному элементу, то это как-то тоже не очень быстро. Тем более, что в будущем может быть не 500 000 элементов, а 10 000 000.

Пока в голову приходит только сделать просто сортированный массив, который легко сохранять и загружать, а искать бинарным поиском. Но тогда каждый поиск займет около 20 итераций со сравнением строк... С хешмапой наверное поиск быстрее будет всё-таки.


#1
19:07, 27 мар. 2016
unordered_map вроде не позволяет сохранить своё внутренное представление в файл, а потом читать оттуда.

ну а аллокатор свой подсунуть, который все выделения памяти сделает в одном непрерывном куске - потом кусок этот в файл записать\прочитать оттуда.
Но тогда каждый поиск займет около 20 итераций со сравнением строк

И что мешает вместо строк хеши сохранять (дополнительно к строке) и сравнивать уже хеши?
#2
19:18, 27 мар. 2016

Hartmann
> ну а аллокатор свой подсунуть, который все выделения памяти сделает в одном
> непрерывном куске - потом кусок этот в файл записать\прочитать оттуда.
Кстати да, это идея, спасибо. Только надо разбираться с STL'ными аллокаторами. Я STL не очень глубоко знаю, потому что раньше делал только свой движок, а там свои велосипеды, более удобные, чем STL.

Hartmann
> И что мешает вместо строк хеши сохранять (дополнительно к строке) и сравнивать
> уже хеши?
Так в бинарном поиске строки же сравниваются оператором <. А хэши можно только на равенство проверять.
Хотя можно наверное пожертвовать скоростью поиска, сделав просто сортированный массив. 20 сравнений наверное ничто по сравнению с алгоритмом сложности O(N^2), где N ~ 1000, который прогоняется практически после каждого поиска...

#3
19:26, 27 мар. 2016

gammaker
> А хэши можно только на равенство проверять.
С чего это? Хеши - обычные числа.

#4
19:31, 27 мар. 2016

Delfigamer
> С чего это? Хеши - обычные числа.
Не, ну я могу эти числа сравнить, но к исходным строкам это никакого отношения иметь не будет. Результат будет почти рандомный, если конечно хэш-функция хорошая.

#5
21:12, 27 мар. 2016

gammaker
Ну и сортировал бы по хешам, а строки - второй очередью, на случай коллизий и с возможностью вообще отключить их КЕМ, по сути перейдя от строк к М-битным идентификаторам.

#6
21:30, 27 мар. 2016

тут бинарный поиск в большом файле + маленькая таблица для быстрого нахождения диапазона:
https://geidav.wordpress.com/2013/12/29/optimizing-binary-search/
если файл большой, то можно читать его через mmap().

#7
21:52, 27 мар. 2016

Delfigamer
> Ну и сортировал бы по хешам
Кстати да, не подумал об этом как-то.

PVSector
> тут бинарный поиск в большом файле + маленькая таблица для быстрого нахождения
> диапазона:
Спасибо, буду смотреть.

PVSector
> если файл большой, то можно читать его через mmap()
Как раз большой файл мапить целиком в память не хотелось бы, потому что адресного пространства не хватит и программу придётся делать 64-bit only. Но мне надо мапить не исходный файл, а индекс для быстрого поиска, который занимает намного меньше 2 ГБ.

#8
22:19, 27 мар. 2016

Короче понятно, нужно в любом случае или что-то реализовывать самому, либо брать обычный бинарный поиск. Стандартного ничего нет. Тогда пока возьму просто бинарный поиск, а если будет тормозить, то попробую улучшить его хэшами или какими-то другими структурами. Но наверное всё-таки до этого даже не дойдёт.
Так что всем спасибо за ответы.

#9
10:13, 28 мар. 2016

вы обсуждаете как сделать БД - не проще ли взять готовую?

#10
11:42, 28 мар. 2016

leonardo98
> вы обсуждаете как сделать БД - не проще ли взять готовую?
Брать готовую БД - это как-то жирно для моего простого случая. К тому же, время, потраченное на её прикручивание и изучение будет больше, чем сделать бинарный поиск или даже что-то посложнее.
Тот файл с кучей данных уже есть в исходном формате, причём довольно распространённом в сфере, с которой связана моя программа. Хотелось бы использовать его без конверсии, только в отдельном файле сохранить индекс для быстрого поиска.
В общем, наверное всё-таки обычного бинарного поиска хватит и ничего даже городить не придётся. Только формат для индекса придумать, который быстро читается и занимает как можно меньше места. Но я уже придумал и почти реализовал.

#11
11:58, 28 мар. 2016

gammaker
> Брать готовую БД - это как-то жирно для моего простого случая. К тому же,
> время, потраченное на её прикручивание и изучение будет больше, чем сделать
> бинарный поиск или даже что-то посложнее.

SQLite же,... там прикручивать даже нечего, всё тривиально - по мотивам stackoverflow

bool SQLiteProxy::open(const std::string dbpath)
{
  assert(_db == NULL);

    if (sqlite3_open(dbpath.c_str(), &_db) != SQLITE_OK)
    {
      _db = NULL;
      return false;
    }

    return ((_db == NULL) ? false : true);
}

void SQLiteProxy::close()
{
  if (_db)
    {
      sqlite3_close(_db);
        _db = NULL;
    }
    _db = NULL;
}

std::vector<std::vector<std::string> > SQLiteProxy::query(const std::string q)
{

  assert(_db);
  sqlite3_stmt* stmt(NULL);

    std::vector<std::vector<std::string> >  results;
    results.clear();
    int res(0);
    std::string empty("");

    _err = sqlite3_prepare_v2(_db, q.c_str(), -1, &stmt, 0);
    const char* errstr = sqlite3_errmsg(_db);
    if (_err == SQLITE_OK)
    {
      int cols = sqlite3_column_count(stmt);


        if (cols>0) while(true)
        {
          ///1
          res = sqlite3_step(stmt);

            ///2
          if ( res != SQLITE_ROW) {_err = res; break;}

            ///3
            {
              std::vector<std::string> cells; cells.reserve(cols);

                for (size_t i=0; i<cols; i++)
                {
                  const char* p = sqlite3_column_text(stmt, i);
                    if (p != NULL) cells.push_back(std::string(p));
                    else cells.push_back(empty);
                }
                results.push_back(cells);
            }
        }

        sqlite3_finalize(stmt);
    }


    return results;
}

void SQLiteProxy::execute(const std::string q)
{
  assert(_db);
  sqlite3_stmt* stmt(NULL);

    std::vector<std::vector<std::string> >  results;
    results.clear();
    int res(0);
    std::string empty("");

    _err = sqlite3_prepare_v2(_db, q.c_str(), -1, &stmt, 0);
    if (_err == SQLITE_OK)
    {
        _err = sqlite3_step(stmt);
    }
    sqlite3_finalize(stmt);
}

#12
13:28, 28 мар. 2016

gammaker
> 500 000 элементов
> данные длиной около килобайта.
итого 500Мб. Может просто целиком прочитать в память? Не придется шуршать диском для каждого обращения.
---
а, там дальше про 10 гигов. Ну ок. Голосую за B-дерево.

#13
14:32, 28 мар. 2016

gammaker
> Брать готовую БД - это как-то жирно для моего простого случая. К тому же,
> время, потраченное на её прикручивание и изучение будет больше, чем сделать
> бинарный поиск или даже что-то посложнее.
Зато у тебя останется опыт работы и прикручивания этой бд и в следующий раз не нужно будет велосипедить. :)

#14
16:41, 28 мар. 2016

gammaker
сделай в конце файла массив {ХешИмени, ОффсетДанныхВФайле} отсортированнуй по хешу, когда надо будет получить доступ к какому-то элементу не надо будет читать весь файл, только его конец, делать бинарный поиск по хешу, и для каждого совпадения быстро найти нужные данные по оффсету и сравнивать по имени

Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.