Предположим, что N = 169647, а размеры двух на практике равны m, n соответственно.

Что касается ваших вопросов:

• Исходная сложность равна (N²).

• Сложность предлагаемого вами решения составляет O((m + n) log(max(m, n)), что, вероятно, будет намного меньше; использование std::unordered_map вместо этого вы можете уменьшить это значение до ожидаемого O(m + n).

• Звучит неплохо, но, как всегда - YMMV. Вы должны профилировать как эту операцию в контексте всего вашего приложения (чтобы увидеть, является ли это проблемой), так и шаги внутри этой операции.

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

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

Ориентир

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

Полный код

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

Полученные результаты

Explanation of the output of the benchmark:
  pairs: implementation using (sorted) std::vector of pairs
  map'd: implementation using std::map
  hashm: implementation using std::unordered_map
  class: implementation using two separate std::vector for indices and values respectively
  specl dot (naive map): dot product using map.find instead of proper iteration
  specl cos (optimised): cosine distance iterating only once over both vectors

Columns are the percentage of non-zeros in the random sparse vector (on average).
Values are in terms of the vector of pairs implementation
(1: equal runtime, 2: took twice as long, 0.5: took half as long).

                    inner product (dot)
            5%          10%          15%          25%
map'd       3.3          3.5          3.7          4.0
hashm       3.6          4.0          4.8          5.2
class       1.1          1.1          1.1          1.1
special[1]  8.3          9.8         10.7         10.8

                    norm squared (len2)
            5%          10%          15%          25%
map'd       6.9          7.6          8.3         10.2
hashm       2.3          3.6          4.1          4.8
class       0.98         0.95         0.93         0.75

                    cosine distance (cos)
            5%          10%          15%          25%
map'd       4.0          4.3          4.6          5.0
hashm       3.2          3.9          4.6          5.0
class       1.1          1.1          1.1          1.1
special[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] (равная реализации OP):

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 — количество ненулевых элементов в разреженном векторе: это тривиально увидеть для map и vector как реализацию Dot < strong>то же самое, и неупорядоченная карта достигает этого путем реализации find в O(1) с амортизацией.

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

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