словарь — вычислить расстояние между картами, которые представляют разреженные векторы Переполнение стека

Общее представление разреженных векторов представляет собой простой массив индексов и одно из значений или иногда массив пар индексов и значений, поскольку обычно вам необходим доступ к индексу вместе со значением (кроме случаев, когда вам не нравится длина вектора / нормализация или аналогичная). Были предложены две другие формы: использование std::map а также std::unordered_map,

Пожалуйста, найдите заключение в конце.

Я реализовал векторную длину операций и внутреннее произведение (скалярное произведение) для этих четырех представлений. Кроме того, я реализовал внутренний продукт очень прямым путем, предложенным в вопросе ОП, и улучшил вычисление косинусного расстояния для реализации пар векторов.

Полный код

Я провел тест на этих реализациях. Вы можете проверить мой код из этого ссылка на сайт откуда я взял следующие числа (хотя соотношения довольно точно совпадают с пробегами на моей собственной машине только с гораздо выше RunCount для более равномерного распределения случайных входных векторов). Вот результаты:

Результаты

Пояснения к выводу эталонного теста:
пары: реализация с использованием (отсортировано) std :: vector пар
map'd: реализация с использованием std :: map
hashm: реализация с использованием std :: unordered_map
class: реализация, использующая два отдельных std :: vector для индексов и значений соответственно
specl dot (naive map): продукт точки, использующий map.find вместо правильной итерации
specl cos (оптимизированный): косинусное расстояние, повторяющееся только один раз по обоим векторам

Столбцы - это процент ненулевых значений в случайном разреженном векторе (в среднем).
Значения в терминах вектора реализации пар
(1: равное время выполнения, 2: заняло вдвое больше времени, 0,5: заняло вдвое меньше времени).

внутреннее произведение (точка)
5% 10% 15% 25%
map'd 3.3 3.5 3.7 4.0
хеш 3,6 4,0 4,8 5,2
класс 1.1 1.1 1.1 1.1
специальные [1] 8,3 9,8 10,7 10,8

норма в квадрате (len2)
5% 10% 15% 25%
map'd 6,9 7,6 8,3 10,2
хэш 2,3 3,6 4,1 4,8
класс 0,98 0,95 0,93 0,75

косинусное расстояние (cos)
5% 10% 15% 25%
map'd 4.0 4.3 4.6 5.0
хэш 3,2 3,9 4,6 5,0
класс 1.1 1.1 1.1 1.1
специальные [2] 0,92 0,95 0,93 0,94

Реализация тестируется

За исключением special[2]-при случае я использовал следующую косинусную функцию расстояния:

template<class Vector>
inline float CosineDistance(const Vector& lhs, const Vector& rhs) {
return Dot(lhs, rhs) / std::sqrt(LenSqr(lhs) * LenSqr(rhs));
}

Контейнеры пары

Вот реализация Dot для обоих отсортировано vector<pair<size_t,float>> и map<size_t,float>:

template<class PairContainerSorted>
inline float DotPairsSorted(const PairContainerSorted& lhs, const PairContainerSorted& rhs) {
float dot = 0;
for(auto pLhs = lhs.begin(), pRhs = rhs.begin(), endLhs = lhs.end(), endRhs = rhs.end(); pRhs != endRhs;) {
for(; pLhs != endLhs && pLhs->first < pRhs->first; ++pLhs);
if(pLhs == endLhs)
break;
for(; pRhs != endRhs && pRhs->first < pLhs->first; ++pRhs);
if(pRhs == endRhs)
break;
if(pLhs->first == pRhs->first) {
dot += pLhs->second * pRhs->second;
++pLhs;
++pRhs;
}
}
return dot;
}

Это реализация для Dot как для неупорядоченной карты, так и для special[1] (соответствует реализации ОП):

template<class PairMap>
inline float DotPairsMapped(const PairMap& lhs, const PairMap& rhs) {
float dot = 0;
for(auto& pair : lhs) {
auto pos = rhs.find(pair.first);
if(pos != rhs.end())
dot += pair.second * pos->second;
}
return dot;
}

Реализация LenSqr:

template<class PairContainer>
inline float LenSqrPairs(const PairContainer& vec) {
float dot = 0;
for(auto& pair : vec)
dot += pair.second * pair.second;
return dot;
}

Пара вектор

Обратите внимание, что я упаковал пару векторов в структуру (или class) SparseVector (проверьте полный код для деталей):

inline float Dot(const SparseVector& lhs, const SparseVector& rhs) {
float dot = 0;
if(!lhs.idx.empty() && !rhs.idx.empty()) {
const size_t *itIdxLhs = &lhs.idx[0], *endIdxLhs = &lhs.idx[0] + lhs.idx.size();
const float *itValLhs = &lhs.val[0], *endValLhs = &lhs.val[0] + lhs.val.size();
const size_t *itIdxRhs = &rhs.idx[0], *endIdxRhs = &rhs.idx[0] + rhs.idx.size();
const float *itValRhs = &rhs.val[0], *endValRhs = &rhs.val[0] + rhs.val.size();
while(itIdxRhs != endIdxRhs) {
for(; itIdxLhs < endIdxLhs && *itIdxLhs < *itIdxRhs; ++itIdxLhs, ++itValLhs);
if(itIdxLhs == endIdxLhs)
break;
for(; itIdxRhs < endIdxRhs && *itIdxRhs < *itIdxLhs; ++itIdxRhs, ++itValRhs);
if(itIdxRhs == endIdxRhs)
break;
if(*itIdxLhs == *itIdxRhs) {
dot += (*itValLhs) * (*itValRhs);
++itIdxLhs;
++itValLhs;
++itIdxRhs;
++itValRhs;
}
}
}
return dot;
}

inline float LenSqr(const SparseVector& vec) {
float dot = 0;
for(float v : vec.val)
dot += v * v;
return dot;
}

special[2] просто вычисляет квадратичную норму обоих векторов, повторяя их во время внутреннего произведения (подробности см. в полном коде). Я добавил это, чтобы доказать: попадания в кеш имеют значение. Я могу превзойти наивный подход векторов пар с парами векторов один, если я просто получу доступ к своей памяти более эффективно (то же самое было бы верно, если бы вы оптимизировали другие пути, конечно).

Обратите внимание, что все протестированные реализации (за исключением special[1] у которого есть O(k*logk) поведение) демонстрируют теоретическое поведение во время выполнения O(k) где k число ненулевых элементов в разреженном векторе: это тривиально, чтобы увидеть карту и вектор как реализацию Dot та же и неупорядоченная карта достигает этого путем реализации find в O(1) амортизируется.

Почему же тогда карта не подходит для разреженного вектора? За std::map ответ — это издержки итерации древовидной структуры, для std::unordered_map шаблон доступа к произвольной памяти для find, что приводит к огромным накладным расходам во время промахов кэша.

Демистифицировать теоретическую пользу std::unordered_map над std::map проверить результаты для special[1], Это реализация, которую std::unordered_map не потому, что он лучше подходит для решения проблемы, а потому, что std::map был неоптимальным.