高级农民
- 积分
- 2737
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-6-18
- 最后登录
- 1970-1-1
|
本帖最后由 magicsets 于 2021-1-13 18:25 编辑
是的,这个SparseVector具体怎么实现其实并不简单,最基本的设计有几点:
(1) 可以用工厂模式来创建具有不同底层格式的SparseVector
(2) 可以使用继承机制或者tagged union (C++ std::variant)来统一各种格式下SparseVector的行为
继承机制就是说SparseVector是一个基类,然后创建subclass比如HashTableBasedSparseVector、SortedListBasedSparseVector等等,然后大家都实现一个abstract method叫做DotProduct
但是这里有一个比较重要的工程问题就是如果你有m种底层格式的话,那么就有m * m种DotProduct的组合可能,也就是说需要写m * m份不同的代码去处理所有这些组合 —— 那么可不可以把需要写的代码份数降到O(m) 呢?是可以的,但是如果想要做到最佳性能(也就是编译器可以进行内联优化而不是做虚函数调用)那就比较麻烦。
实际工程中如果真有这样的问题要解决,往往都是要求架构上的精简性和最佳性能兼备的,实现途径之一就是C++的模板系统,我下面写了一份代码,这个代码量比较大不适用于面试但是可以参考一下设计..
- #include <algorithm>
- #include <cstddef>
- #include <iostream>
- #include <string>
- #include <type_traits>
- #include <unordered_map>
- #include <utility>
- #include <variant>
- #include <vector>
- // SparseVector的三种内存布局
- enum class Format {
- // 自动选择
- kAuto,
- // HashTable,idx -> val
- kHashTable,
- // List of pairs,按照idx排序
- kSortedList,
- // 直接用一个dense vector存储包括0在内的所有值
- kDenseVector,
- };
- ////////////////////////////////////////////////////////////////////////////////
- ////////////////// 下面的代码定义了三个class,对应三种内存布局的实现 ///////////////////
- ////////////////////////////////////////////////////////////////////////////////
- // 为了高效地支持dot product,每个class需要实现两个接口:
- //
- // 1. 以回调方式枚举所有元素
- // --
- // template <typename Functor>
- // void ForEach(Functor&& fn) const;
- // --
- // 其中fn的参数类型规定为 void (size_t idx, double val)
- //
- // 2. 给定idx,访问对应位置上的val
- // --
- // double operator[](size_t idx) const;
- // --
- // HashTable格式的实现
- class HashTableRepr {
- public:
- template <typename Functor>
- void ForEach(Functor&& fn) const {
- // 枚举所有元素
- for (const auto& entry : hash_table) {
- fn(entry.first, entry.second);
- }
- }
- double operator[](size_t idx) const {
- // 在HashTable里面查找
- const auto it = hash_table.find(idx);
- return it == hash_table.end() ? 0 : it->second;
- };
- std::string GetFormatName() const { return "HashTable"; }
- // 由原始数据构造HashTable
- HashTableRepr(const std::vector<double>& values) {
- for (size_t i = 0; i < values.size(); ++i) {
- if (values[i] != 0) {
- hash_table[i] = values[i];
- }
- }
- }
- private:
- std::unordered_map<size_t, double> hash_table;
- };
- // SortedList格式的实现
- class SortedListRepr {
- public:
- template <typename Functor>
- void ForEach(Functor&& fn) const {
- // 枚举所有元素
- for (const auto& entry : sorted_list) {
- fn(entry.first, entry.second);
- }
- }
- double operator[](size_t idx) const {
- // 二分查找
- const auto it = std::lower_bound(sorted_list.begin(), sorted_list.end(),
- idx,
- [](const auto& lhs, const size_t rhs) {
- return lhs.first < rhs;
- });
- return (it == sorted_list.end() || it->first != idx) ? 0 : it->second;
- };
- std::string GetFormatName() const { return "SortedList"; }
- // 由原始数据构造SortedList
- SortedListRepr(const std::vector<double>& values) {
- for (size_t i = 0; i < values.size(); ++i) {
- if (values[i] != 0) {
- sorted_list.emplace_back(i, values[i]);
- }
- }
- std::sort(sorted_list.begin(), sorted_list.end(),
- [](const auto& lhs, const auto& rhs) {
- return lhs.first < rhs.first;
- });
- }
- private:
- std::vector<std::pair<size_t, double>> sorted_list;
- };
- // DenseVector格式的实现
- class DenseVectorRepr {
- public:
- template <typename Functor>
- void ForEach(Functor&& fn) const {
- // 枚举所有(非0)元素
- for (size_t i = 0; i < dense_vector.size(); ++i) {
- if (dense_vector[i] != 0) {
- fn(i, dense_vector[i]);
- }
- }
- }
- double operator[](size_t idx) const {
- // 直接访问idx位置的元素
- return idx < dense_vector.size() ? dense_vector[idx] : 0;
- };
- std::string GetFormatName() const { return "DenseVector"; }
- // 由原始数据构造DenseVector
- DenseVectorRepr(const std::vector<double>& values)
- : dense_vector(values) {}
- private:
- std::vector<double> dense_vector;
- };
- ////////////////////////////////////////////////////////////////////////////////
- /////////////////////// SparseVector以及DotProduct的实现 /////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
- class SparseVector {
- public:
- // 工厂模式,可以自己指定format,也可以设成auto
- static SparseVector Create(const std::vector<double>& values,
- Format format = Format::kAuto) {
- if (format == Format::kAuto) {
- format = ChooseBestFormat(values);
- }
- switch (format) {
- case Format::kHashTable:
- return SparseVector(HashTableRepr(values));
- case Format::kSortedList:
- return SparseVector(SortedListRepr(values));
- case Format::kDenseVector:
- return SparseVector(DenseVectorRepr(values));
- default:
- break;
- }
- throw "Unreachable";
- }
- std::string GetFormatName() const {
- return std::visit([](const auto& instance) {
- return instance.GetFormatName();
- },
- repr_);
- }
- // DotProduct实现
- double DotProduct(const SparseVector& other) const {
- // 要实现高性能的话需要让编译器进行内联(inlining)优化
- // 那么这里就要做模版展开(template expansion),共3 * 3 = 9种instantiation
- return std::visit(
- [&](const auto& left_repr) {
- return std::visit(
- [&](const auto& right_repr) {
- return DotProductImpl(left_repr, right_repr);
- },
- other.repr_);
- },
- repr_);
- }
- private:
- using Repr = std::variant<HashTableRepr, SortedListRepr, DenseVectorRepr>;
- explicit SparseVector(Repr repr) : repr_(std::move(repr)) {}
- static Format ChooseBestFormat(const std::vector<double>& values) {
- // 这里设定一个简单的heuristic就是0的个数有没有超过50%
- const double zero_ratio =
- std::count(values.begin(), values.end(), 0.0)
- / static_cast<double>(values.size());
- return zero_ratio > 0.5 ? Format::kHashTable : Format::kDenseVector;
- }
- // 得到具体内存格式后进行的高效dot product,注意这里ForEach和operator[]的使用
- template <typename LeftRepr, typename RightRepr>
- static double DotProductImpl(const LeftRepr left, const RightRepr right) {
- double sum = 0;
- left.ForEach([&](size_t idx, double val) {
- sum += val * right[idx];
- });
- return sum;
- }
- Repr repr_;
- };
- ////////////////////////////////////////////////////////////////////////////////
- ////////////////////////////////// 三种格式的测试 /////////////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
- int main(int argc, char* argv[]) {
- SparseVector vec1 = SparseVector::Create({0, 100, 0, 0, 200});
- // 输出:HashTable
- std::cout << vec1.GetFormatName() << "\n";
- SparseVector vec2 = SparseVector::Create({100, 200, 0, 0, 300, 400});
- // 输出:DenseVector
- std::cout << vec2.GetFormatName() << "\n";
- SparseVector vec3 = SparseVector::Create({300, 200, 0, 100},
- Format::kSortedList);
- // 输出:SortedList
- std::cout << vec3.GetFormatName() << "\n";
- // 三种格式互相进行DotProduct,共九种组合
- std::cout << "vec1 . vec1 = " << vec1.DotProduct(vec1) << "\n";
- std::cout << "vec1 . vec2 = " << vec1.DotProduct(vec2) << "\n";
- std::cout << "vec1 . vec3 = " << vec1.DotProduct(vec3) << "\n";
- std::cout << "vec2 . vec1 = " << vec2.DotProduct(vec1) << "\n";
- std::cout << "vec2 . vec2 = " << vec2.DotProduct(vec2) << "\n";
- std::cout << "vec2 . vec3 = " << vec2.DotProduct(vec3) << "\n";
- std::cout << "vec3 . vec1 = " << vec3.DotProduct(vec1) << "\n";
- std::cout << "vec3 . vec2 = " << vec3.DotProduct(vec2) << "\n";
- std::cout << "vec3 . vec3 = " << vec3.DotProduct(vec3) << "\n";
- return 0;
- }
复制代码 [/i][/i][/i][/i][/i][/i][/i]
补充内容 (2021-1-14 15:35):
DotProductImpl的参数应该是引用类型:
static double DotProductImpl(const LeftRepr& left, const RightRepr& right) |
|