题目重点：将稀疏向量重复调用和连续重复值压缩归为输入表示变体，避免展开巨大向量。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 向量维度相同，点积为同索引值相乘求和。稀疏表示(index,value)唯一索引；RLE表示(value,count)，count为正整数，表示连续重复，二者不是同一种编码。
- 整数示例用Python任意精度；浮点乘加有舍入与累加顺序差异，不能要求所有表示bitwise相同。
解题路线
- 稀疏hash map只保留非零坐标，dot遍历非零数较少的一侧并查另一侧，均摊O(min(nnzA,nnzB))。重复dot不反复扫描/压缩原dense数组，构造一次供后续复用。
- 已排序稀疏列表用两个指针：索引相同贡献乘积并双移，较小索引单移。省hash表但一次dot扫描两侧非零项，需要已排序/无重复索引前提；输入乱序要先处理。
- RLE不能按run序号直接乘，因为两向量run边界不一致。记录当前两段remaining，消费min(remainingA,remainingB)，贡献valueA×valueB×take，耗尽才前移相应run。
- RLE先验证展开总长度相同，计数正整数；不实际展开。即使段长10^15，只要run数很小也可计算。相邻同值run可保留，不影响正确性。
- 选择编码取决于数据：很多零适合稀疏，大块相同非零值适合RLE。负值无需特殊忽略；不能把只存非零坐标的压缩当成按run连续长度。
手动走一遍
A=[1,1,1,2]编码[(1,3),(2,1)]，B=[3,4,4,4]编码[(3,1),(4,3)]。分段消费1、2、1，点积3+8+8=19。把run按序号相乘得到3+8=11是错的。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class SparseVector:
def __init__(self,values):
self.entries={i:v for i,v in enumerate(values) if v!=0}
self.length=len(values)
def dot(self,other):
if self.length!=other.length:raise ValueError('dimension mismatch')
a,b=self.entries,other.entries
if len(a)>len(b):a,b=b,a
return sum(v*b.get(i,0) for i,v in a.items())
def sorted_sparse_dot(left,right):
"""Sorted unique (index,value) lists, same declared dimension required outside.
Zero values harmless. Caller validates index range/unique ordering once.
"""
i=j=0;total=0
while i<len(left) and j<len(right):
a,x=left[i];b,y=right[j]
if a==b:total+=x*y;i+=1;j+=1
elif a<b:i+=1
else:j+=1
return total
def run_length_dot(left,right):
"""(value,count) runs, integer positive counts, equal expanded dimensions.
Streams are not expanded; supports huge run counts and adjacent equal runs.
"""
if any(count<=0 or not isinstance(count,int) for _,count in left+right):
raise ValueError('positive integer run lengths')
if sum(n for _,n in left)!=sum(n for _,n in right):raise ValueError('dimension mismatch')
i=j=0;remaining_a=remaining_b=0;total=0
while i<len(left) and j<len(right):
if remaining_a==0:remaining_a=left[i][1]
if remaining_b==0:remaining_b=right[j][1]
take=min(remaining_a,remaining_b);total+=left[i][0]*right[j][0]*take
remaining_a-=take;remaining_b-=take
if remaining_a==0:i+=1
if remaining_b==0:j+=1
return total
复杂度
dense构造O(n)、稀疏空间O(nnz)，hash dot均摊O(min(nnzA,nnzB))，排序双指针O(nnzA+nnzB)。RLE dot O(rA+rB)时间/O(1)扫描状态，预验证同阶；不按展开长度N计遍历。
易错点与追问
容易失分的边界
- 每次dot重新压缩dense输入，重复调用没有真正复用收益。
- 排序稀疏有重复索引未先聚合，会遗漏/重复乘积。
- RLE两侧计数不等但不验证维度，尾部被悄悄丢掉。
继续深挖
- 一个向量稀疏、另一个dense时，用稀疏索引直接查dense如何算复杂度？
- 稀疏索引允许在线更新，hash与有序结构如何权衡查询/更新？
