如何高效从卡车载货CSV数据中找出共享物品最多的两辆相似卡车
高效识别载货重合度最高的卡车配对方案
基础需求说明
需要分析存储卡车ID、载货物品ID的CSV数据,核心目标是共享载货物品数量最多的卡车组合。
使用的CSV数据格式示例如下:
truck_id | item_id 13 | 85394 16 | 294 13 | 294 89 | 3115 89 | 85394 13 | 294 16 | 85394 13 | 3115
在上述示例中,13号卡车和16号卡车的重合度最高,二者共同携带了294、85394两件物品。
现有实现的逻辑与效率问题
当前采用的实现逻辑伪代码如下:
- 遍历一遍CSV,构建
truck_items字典:键为卡车ID,值为对应卡车所有载货物品的列表 - 取出每辆卡车的载货列表,和其余所有卡车的载货列表逐一对比,统计二者共有的物品数量
- 为每辆卡车记录匹配到的最相似对象,最终形成类似结构的存储:
{ 13: [16, 2], # 结构为 卡车ID: [最相似卡车ID, 共同载货数量] 89: ... }
这种实现的明显短板是存在大量重复遍历、冗余对比操作,当卡车总数、载货总规模上升时,会产生大量无意义的计算,整体效率很差。
效率更优的实现思路
核心是转换计算视角,从「卡车对逐一对比载货集合」转为「从物品维度反向关联持有它的卡车对」,彻底避免全量卡车的无意义两两遍历:
- 先对原始CSV做去重处理:过滤掉重复的(卡车ID,物品ID)记录(比如示例中13号卡车的294出现了两次,这类重复条目不应该重复参与计数)
- 构建物品维度的倒排索引:遍历所有去重后的记录,对每个
item_id,整理出所有携带了该物品的卡车ID列表 - 累计重合计数:对每个物品对应的卡车列表,把列表内的卡车两两配对,每组成对就给这对卡车的共同物品计数+1——因为两个卡车同时出现在同一个物品的持有列表中,就代表二者共享了该物品
- 遍历所有累计的计数值,找到计数最高的卡车对,就是全局相似度最高的组合
这类方案的时间复杂度和「去重后的载货总条目数」直接绑定,当大部分卡车的载货品类没有重叠时,运行效率会远高于原有的两两遍历方案。
内容的提问来源于stack exchange,提问作者uber
相关产品推荐
相关产品推荐

