📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 7901| 回复: 8
跳转到指定楼层
上一主题 下一主题
收起左侧

[高频题] 讨论一道高频 力扣1570 Dot product of two sparse vectors

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
这道题本身不太难,但是我有些不确定follow up的考察点,所以拿来地里讨论一下,希望听取小伙伴们的提示和想法

如题题目:给两个sparse vectors, 要求实现一个class SparseVector,可以高效的保存sparse vetor,并且与另一个SparseVector做高效的dot product。
这个题不算是特别难的的题,可以想到多种解法,比如(1)用两个hashtable h1 h2分别保存两个sparse vector中非0的元素,比如 idx: non-zero val,然后遍历h1的元素,在h2中搜索是否存在,存在就计算两个val的product;

(2)用两个list h1 h2 保存非0的元素,比如[(idx, val), ...],然后用双指针或者二分法搜索
很明显用hashtable在时间复杂度上占优势,时间复杂度是O(min(h1, h2)),用双指针是O(h1+h2),用二分法是O(h1*log(h2))

但是这个题还有一个follow-up是 What if only one of the vectors is sparse? 力扣的答案中并没有详细的讨论
并且在discussion中:https://leetcode.com/discuss/int ... ct-of-sparse-vector
有人提到,在面试中回答了hashtable的方法,但是面试官询问“what would be a better data structure to use instead of a hash map to represent the vectors, with the spec that its a sparse vectors could be millions of entries with hundreds of non-empty entries.”
discussion中也有人提到面试官似乎在得到hashtable的答案后,想要继续考察list pair + 二分的方法

我的问题是,这个follow up的是想要考察list pair + 二分吗?如果是,那么list pair为什么在这种情况会优于hashtable?
有人在discussion中提到list pair可以保留order的信息,但是hashtable就会丢失这个信息,也许面试官对这个order有特殊的需求。也许我想不到这个需求是什么
或者还有什么其他的hashtable在这个follow up中不适合?比如数据太大,dense vector会造成更多的collisions,以致于hashtable的搜索无法实现O(1)的时间?

评分

参与人数 1大米 +15 收起 理由
14417335 + 15

查看全部评分


上一篇:请问LeetCode Problems是按什么排序的?
下一篇:Software engineer Mock interview
推荐
magicsets 2021-1-11 18:21:56 | 只看该作者
全局:
本帖最后由 magicsets 于 2021-1-11 18:24 编辑

对于followup问题,可以用一个std::vector(Java则是ArrayList)使得idx位置存的就是对应idx的val

比如考虑两个vector A和B。A为sparse:[(idx=0, val=1), (idx=3, val=2)],B为dense:[(idx=0, val=6), (idx=1, val=7), (idx=2, val=8), (idx=4, val=9)]

那么A采用list of pairs的存储,B直接存为一个数值vector:[6, 7, 8, 0, 9]

求dot product的代码也非常简单:
  1. result = 0;
  2. for each (idx, val) in A:
  3.   if idx < B.length:
  4.     result += val * B[idx];
复制代码


比起B使用HashTable的实现,直接通过单次idx偏移寻址估计要快上至少10倍(因为HashTable的Get操作虽然是O(1),但需要耗费大量的CPU cycles,比如计算hash值并与bucket内的进行比较 -> 然后再比较原始值 -> 如果发生了collision还要查看更多的bucket,以及这中间发生的多次if branching造成的CPU流水线问题,等等)


评分

参与人数 5大米 +10 收起 理由
caudalienature + 1 很有用的信息!
牧moon + 1 给你点个赞!
不知道小帅 + 2 给你点个赞!
Z君 + 1 给你点个赞!
14417335 + 5

查看全部评分

回复

使用道具 举报

🔗
Z君 2021-1-12 04:25:50 | 只看该作者
全局:
magicsets 发表于 2021-1-11 18:21
对于followup问题,可以用一个std::vector(Java则是ArrayList)使得idx位置存的就是对应idx的val

比如 ...

感谢分享!
回复

使用道具 举报

🔗
 楼主| 牧moon 2021-1-12 07:30:53 | 只看该作者
全局:
本帖最后由 牧moon 于 2021-1-12 07:38 编辑
magicsets 发表于 2021-1-11 18:21
对于followup问题,可以用一个std::vector(Java则是ArrayList)使得idx位置存的就是对应idx的val

比如 ...

谢谢分享!

我有一个问题,由于没有贴出原题的例子,所以可能没有清楚的给出题目的要求。这道题要求实现一个class SparseVector,我的理解是A和B都需要建立SparseVector,比如这个例子
  1. Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
  2. Output: 8
  3. Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
  4. v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8
复制代码


如果nums1和nums2用不同的方式表示,nums1用list of pairs,nums2就是一个regular vector,实现这个SparseVector类是有些困难的吧?
但是你的答案给了我思路就是hashtable会由于数据过大,在实际过程中不一定能达到理论的O(1)时间复杂度,也许这是可以回答的一个点。


回复

使用道具 举报

🔗
lllbl 2021-1-12 09:33:53 | 只看该作者
全局:
LC国服论坛里看到的:创建map常数项大,考虑到数列创建后没有变动,利用vector二分搜索也可达到相同的复杂度。
回复

使用道具 举报

🔗
magicsets 2021-1-13 18:04:30 | 只看该作者
全局:
本帖最后由 magicsets 于 2021-1-13 18:25 编辑
牧moon 发表于 2021-1-12 07:30
谢谢分享!

我有一个问题,由于没有贴出原题的例子,所以可能没有清楚的给出题目的要求。这道题要求实 ...

是的,这个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++的模板系统,我下面写了一份代码,这个代码量比较大不适用于面试但是可以参考一下设计..

  1. #include <algorithm>
  2. #include <cstddef>
  3. #include <iostream>
  4. #include <string>
  5. #include <type_traits>
  6. #include <unordered_map>
  7. #include <utility>
  8. #include <variant>
  9. #include <vector>

  10. // SparseVector的三种内存布局
  11. enum class Format {
  12.   // 自动选择
  13.   kAuto,
  14.   // HashTable,idx -> val
  15.   kHashTable,
  16.   // List of pairs,按照idx排序
  17.   kSortedList,
  18.   // 直接用一个dense vector存储包括0在内的所有值
  19.   kDenseVector,
  20. };

  21. ////////////////////////////////////////////////////////////////////////////////
  22. ////////////////// 下面的代码定义了三个class,对应三种内存布局的实现 ///////////////////
  23. ////////////////////////////////////////////////////////////////////////////////

  24. // 为了高效地支持dot product,每个class需要实现两个接口:
  25. //
  26. // 1. 以回调方式枚举所有元素
  27. // --
  28. //   template <typename Functor>
  29. //   void ForEach(Functor&& fn) const;
  30. // --
  31. // 其中fn的参数类型规定为 void (size_t idx, double val)
  32. //
  33. // 2. 给定idx,访问对应位置上的val
  34. // --
  35. // double operator[](size_t idx) const;
  36. // --

  37. // HashTable格式的实现
  38. class HashTableRepr {
  39. public:
  40.   template <typename Functor>
  41.   void ForEach(Functor&& fn) const {
  42.     // 枚举所有元素
  43.     for (const auto& entry : hash_table) {
  44.       fn(entry.first, entry.second);
  45.     }
  46.   }

  47.   double operator[](size_t idx) const {
  48.     // 在HashTable里面查找
  49.     const auto it = hash_table.find(idx);
  50.     return it == hash_table.end() ? 0 : it->second;
  51.   };

  52.   std::string GetFormatName() const { return "HashTable"; }

  53.   // 由原始数据构造HashTable
  54.   HashTableRepr(const std::vector<double>& values) {
  55.     for (size_t i = 0; i < values.size(); ++i) {
  56.       if (values[i] != 0) {
  57.         hash_table[i] = values[i];
  58.       }
  59.     }
  60.   }

  61. private:
  62.   std::unordered_map<size_t, double> hash_table;
  63. };

  64. // SortedList格式的实现
  65. class SortedListRepr {
  66. public:
  67.   template <typename Functor>
  68.   void ForEach(Functor&& fn) const {
  69.     // 枚举所有元素
  70.     for (const auto& entry : sorted_list) {
  71.       fn(entry.first, entry.second);
  72.     }
  73.   }

  74.   double operator[](size_t idx) const {
  75.     // 二分查找
  76.     const auto it = std::lower_bound(sorted_list.begin(), sorted_list.end(),
  77.                                      idx,
  78.                                      [](const auto& lhs, const size_t rhs) {
  79.                                          return lhs.first < rhs;
  80.                                      });
  81.     return (it == sorted_list.end() || it->first != idx) ? 0 : it->second;
  82.   };

  83.   std::string GetFormatName() const { return "SortedList"; }

  84.   // 由原始数据构造SortedList
  85.   SortedListRepr(const std::vector<double>& values) {
  86.     for (size_t i = 0; i < values.size(); ++i) {
  87.       if (values[i] != 0) {
  88.         sorted_list.emplace_back(i, values[i]);
  89.       }
  90.     }
  91.     std::sort(sorted_list.begin(), sorted_list.end(),
  92.               [](const auto& lhs, const auto& rhs) {
  93.                   return lhs.first < rhs.first;
  94.               });
  95.   }

  96. private:
  97.   std::vector<std::pair<size_t, double>> sorted_list;
  98. };

  99. // DenseVector格式的实现
  100. class DenseVectorRepr {
  101. public:
  102.   template <typename Functor>
  103.   void ForEach(Functor&& fn) const {
  104.     // 枚举所有(非0)元素
  105.     for (size_t i = 0; i < dense_vector.size(); ++i) {
  106.       if (dense_vector[i] != 0) {
  107.         fn(i, dense_vector[i]);
  108.       }
  109.     }
  110.   }

  111.   double operator[](size_t idx) const {
  112.     // 直接访问idx位置的元素
  113.     return idx < dense_vector.size() ? dense_vector[idx] : 0;
  114.   };

  115.   std::string GetFormatName() const { return "DenseVector"; }

  116.   // 由原始数据构造DenseVector
  117.   DenseVectorRepr(const std::vector<double>& values)
  118.       : dense_vector(values) {}

  119. private:
  120.   std::vector<double> dense_vector;
  121. };


  122. ////////////////////////////////////////////////////////////////////////////////
  123. /////////////////////// SparseVector以及DotProduct的实现 /////////////////////////
  124. ////////////////////////////////////////////////////////////////////////////////

  125. class SparseVector {
  126. public:
  127.   // 工厂模式,可以自己指定format,也可以设成auto
  128.   static SparseVector Create(const std::vector<double>& values,
  129.                              Format format = Format::kAuto) {
  130.     if (format == Format::kAuto) {
  131.       format = ChooseBestFormat(values);
  132.     }
  133.     switch (format) {
  134.       case Format::kHashTable:
  135.         return SparseVector(HashTableRepr(values));
  136.       case Format::kSortedList:
  137.         return SparseVector(SortedListRepr(values));
  138.       case Format::kDenseVector:
  139.         return SparseVector(DenseVectorRepr(values));
  140.       default:
  141.         break;
  142.     }
  143.     throw "Unreachable";
  144.   }

  145.   std::string GetFormatName() const {
  146.     return std::visit([](const auto& instance) {
  147.                         return instance.GetFormatName();
  148.                       },
  149.                       repr_);
  150.   }

  151.   // DotProduct实现
  152.   double DotProduct(const SparseVector& other) const {
  153.     // 要实现高性能的话需要让编译器进行内联(inlining)优化
  154.     // 那么这里就要做模版展开(template expansion),共3 * 3 = 9种instantiation
  155.     return std::visit(
  156.         [&](const auto& left_repr) {
  157.           return std::visit(
  158.               [&](const auto& right_repr) {
  159.                 return DotProductImpl(left_repr, right_repr);
  160.               },
  161.               other.repr_);
  162.         },
  163.         repr_);
  164.   }

  165. private:
  166.   using Repr = std::variant<HashTableRepr, SortedListRepr, DenseVectorRepr>;

  167.   explicit SparseVector(Repr repr) : repr_(std::move(repr)) {}

  168.   static Format ChooseBestFormat(const std::vector<double>& values) {
  169.     // 这里设定一个简单的heuristic就是0的个数有没有超过50%
  170.     const double zero_ratio =
  171.         std::count(values.begin(), values.end(), 0.0)
  172.             / static_cast<double>(values.size());
  173.     return zero_ratio > 0.5 ? Format::kHashTable : Format::kDenseVector;
  174.   }

  175.   // 得到具体内存格式后进行的高效dot product,注意这里ForEach和operator[]的使用
  176.   template <typename LeftRepr, typename RightRepr>
  177.   static double DotProductImpl(const LeftRepr left, const RightRepr right) {
  178.     double sum = 0;
  179.     left.ForEach([&](size_t idx, double val) {
  180.                    sum += val * right[idx];
  181.                  });
  182.     return sum;
  183.   }

  184.   Repr repr_;
  185. };

  186. ////////////////////////////////////////////////////////////////////////////////
  187. ////////////////////////////////// 三种格式的测试 /////////////////////////////////
  188. ////////////////////////////////////////////////////////////////////////////////

  189. int main(int argc, char* argv[]) {
  190.   SparseVector vec1 = SparseVector::Create({0, 100, 0, 0, 200});
  191.   // 输出:HashTable
  192.   std::cout << vec1.GetFormatName() << "\n";

  193.   SparseVector vec2 = SparseVector::Create({100, 200, 0, 0, 300, 400});
  194.   // 输出:DenseVector
  195.   std::cout << vec2.GetFormatName() << "\n";

  196.   SparseVector vec3 = SparseVector::Create({300, 200, 0, 100},
  197.                                            Format::kSortedList);
  198.   // 输出:SortedList
  199.   std::cout << vec3.GetFormatName() << "\n";

  200.   // 三种格式互相进行DotProduct,共九种组合
  201.   std::cout << "vec1 . vec1 = " << vec1.DotProduct(vec1) << "\n";
  202.   std::cout << "vec1 . vec2 = " << vec1.DotProduct(vec2) << "\n";
  203.   std::cout << "vec1 . vec3 = " << vec1.DotProduct(vec3) << "\n";
  204.   std::cout << "vec2 . vec1 = " << vec2.DotProduct(vec1) << "\n";
  205.   std::cout << "vec2 . vec2 = " << vec2.DotProduct(vec2) << "\n";
  206.   std::cout << "vec2 . vec3 = " << vec2.DotProduct(vec3) << "\n";
  207.   std::cout << "vec3 . vec1 = " << vec3.DotProduct(vec1) << "\n";
  208.   std::cout << "vec3 . vec2 = " << vec3.DotProduct(vec2) << "\n";
  209.   std::cout << "vec3 . vec3 = " << vec3.DotProduct(vec3) << "\n";

  210.   return 0;
  211. }
复制代码
[/i][/i][/i][/i][/i][/i][/i]

补充内容 (2021-1-14 15:35):
DotProductImpl的参数应该是引用类型:
static double DotProductImpl(const LeftRepr& left, const RightRepr& right)

评分

参与人数 1大米 +2 收起 理由
牧moon + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

全局:
magicsets 发表于 2021-1-13 18:04
是的,这个SparseVector具体怎么实现其实并不简单,最基本的设计有几点:

(1) 可以用工厂模式来创建具 ...

感谢大神指点
回复

使用道具 举报

🔗
 楼主| 牧moon 2021-1-15 10:55:52 | 只看该作者
全局:
magicsets 发表于 2021-1-13 18:04
是的,这个SparseVector具体怎么实现其实并不简单,最基本的设计有几点:

(1) 可以用工厂模式来创建具 ...

学习了,谢谢详细的回复!
回复

使用道具 举报

🔗
onemu3fen 2024-3-22 05:51:23 | 只看该作者
全局:
magicsets 发表于 2021-1-13 03:04
是的,这个SparseVector具体怎么实现其实并不简单,最基本的设计有几点:

(1) 可以用工厂模式来创建具 ...

这个SparseVector除了这个dot之外,没有任何interface的定义,实际上外部只需要一个get函数就够用了,所以这个题可以简单的在内部加一个类型判断即可,如果是sparse的,用sparse的方法存,如果不是用数组存。实现方式非常简单,就跟NestedInteger那个是一摸一样的。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表