2022-09-26-快手MMU二投三面-30min

7月29号一投 ~ 搜索引擎工程师 ~ 8月8号一面 ~ 8月11号二面 ~ 8月15号挂
8月18号二投 ~ C++向量检索平台工程师 ~ 8月19号约的26号一面 ~ 9月19号二面 ~ 9月26号三面

二投二面：https://www.nowcoder.com/discuss/1056807
二投一面：https://www.nowcoder.com/discuss/1029052
一投二面：https://www.nowcoder.com/discuss/1011603
一投一面：https://www.nowcoder.com/discuss/1008199

聊了下实习和论文，
题目是算稀疏向量的内积，每个稀疏向量是一千万维，每个数是32位float

其实还有个v4没说有点可惜，属于自己的数据分发领域应用到包分类算法领域的一个借鉴方法，
在 https://shuiyuan.sjtu.edu.cn/t/topic/60494/2?u=赶路人 有提到：

用两个位集01110101010100......存储两个高维稀疏向量里非0的位置，非零则为1，否则标记为0
计算内积时就是要快速找出a、b里都不为零的位，也就是做与运算
两个位集里肯定有很多位为0，于是可以用RLE编码存储位集，
另外可以用聚合的方法，比如连续64位里都是0，则编码为0，有一个1就编码为1，这样存储开销直接下降到原来的64分之1，在做与运算时当两个对应的位都是1时才精确检查下层的64位是不是有都为1的位。

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// LSH

vector<float> inner_product(const vector<float>& a, const vector<float>& b){

// v1
    #pragma for

// v2 avx2
// 

// v3
    unordered_map<int32_t,float> ma, mb; // 问unordered_map原理，hash散列表

    for(int32_t i=0;i<a.size();i++){
        if(a[i]!=0) ma[i]=a[i];
        if(b[i]!=0) mb[i]=b[i];
    }

    float ipv=0.0;

    for(auto& [i,v]:ma){
        if(mb.count(i)){
            ipv+=ma[i]*mb[i];
        }
    }

    return ipv; // 问复杂度，分情况，算上存储unordered_map开销是On否则是非0个数

}

int main() {

}

// multimedia  MMUnderstanding 200人 快手短视频搜索系统以及视频理解的 AI 中台
// 视觉/音频/横向产品、工程/milvus（20-30人）