Блог

Я пытаюсь оптимизировать приложение, которое выполняет поиск в больших «базах данных».

Мое первое приложение использовало метод грубой силы, выполняя поиск всех документов в базе данных и сравнивая их с моим запросом:

 for(i = 0; i < n_base;   i)
{
    float dist = compute_distance(query, *base[i]);
    query_result[i] = std::make_pair(dist, i);
}
std::partial_sort(query_result.begin(),query_result.begin() K, query_result.end(), compare_score_idx_sort);
query_result.resize(K);
  

Затем я попробовал другой подход, используя словарь кодовых слов и присваивая каждому документу в базе данных его ближайшее кодовое слово. Это дает мне список для каждого кодового слова документов базы данных.

Затем моя база данных сохраняется в этом контейнере:

 std::vector< std::pair< unsigned int, std::vector< unsigned short > > **  base = new std::vector< std::pair< unsigned int, std::vector< unsigned short > > * [NK];
  

где NK размер словаря.

Затем, когда я ищу в базе данных с таким типом структуры, я нахожу N ближайшие кодовые слова моего запроса и перебираю списки:

 for(unsigned int i = 0; i < nearest_codewords.size();   i)
        {
            for(unsigned int j = 0; j < base[nearest_codewords[i]]->size();   j)
            {
                std::pair< unsigned int, std::vector< unsigned short > > base_item = (*base[nearest_codewords[i]])[j];
                float dist = compute_distance(query,base_item.second);
                query_result[base_item.first] = std::make_pair(dist, base_item.first);
            }
        }
std::partial_sort(query_result.begin(), query_result.begin() K, query_result.end(), compare_score_idx_sort);
  

Когда я просматриваю 25% своей базы данных с помощью этой версии, время выполнения сокращается менее чем на 50% (110 мс -> 65 мс).

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

PS: Я компилирую с этими параметрами : -O2 -msse2

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

Вот ссылка на статью, в которой упоминается видео Бьярне на Going Native 2012; http://bulldozer00.com/2012/02/09/vectors-and-lists /

Я думаю, что вы видите улучшения из-за непрерывного (или почти непрерывного) расположения данных в памяти.

Редактировать: я нашел другое видео, которое искал; http://channel9.msdn.com/Events/Build/2014/2-661 Херб Саттер подробно рассказывает об этом с очень красивыми графиками, диаграммами, пояснениями и т. Д. Примерно с отметки 23:30, И он берет материал Бьярне примерно с отметки 46:00.