1
问一个删除元素的问题，要求要求速度快
source link: https://www.v2ex.com/t/826970
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
- 有如下一个矩阵，表示 ABCDEFG 这 7 个元素的两两关系（只写了下半部分，是对称的），现在要求删除其中关系值大于 0.5 的数据，使之留下的元素之间的两两关系值都小于 0.5 且元素最多
元素 A B C D E F G
A 1
B 0.3 1
C 0.4 0.2 1
D 0.5 0.1 0.33 1
E 0.7 0.9 0.56 0.2 1
F 0.5 0.4 0.1 0.9 0.9 1
G 0.3 0.2 0.23 0.2 0.7 0.7 1
现在我能想到的就是递归删除，每次删除大于 0.5 个数最多的那一条，但是速度太慢了，我们可能会有好几万一批的数据，得要几个小时，求好兄弟们给个牛逼的解法
33 条回复 • 2022-01-09 10:38:43 +08:00
monster1priest 1 天前 
3
先建图，只考虑大于 0.5 的路径。
问题转换为删除最少的节点，使得剩余结点之间相互独立。
也等价于在图中选择最多的互不相邻的结点。
等价于二分图的最大匹配问题。
问题转换为删除最少的节点，使得剩余结点之间相互独立。
也等价于在图中选择最多的互不相邻的结点。
等价于二分图的最大匹配问题。
ZRS 1 天前 via iPhone 1
删除其中关系值大于 0.5 的数据，使之留下的元素之间的两两关系值都小于 0.5
且元素最多
第二个条件没看明白 第一个条件不就已经规定了删除方式了 怎么还能有元素最多这个约束
你是不是需要求解任务分配问题（ Assignment Problem ）
且元素最多
第二个条件没看明白 第一个条件不就已经规定了删除方式了 怎么还能有元素最多这个约束
你是不是需要求解任务分配问题（ Assignment Problem ）
lozzow 1 天前 via Android
@ZRS 比如你删除了元素 G 之后，元素 E 和 F 就少了一个大于 0.5 的关系，这样就只用删除一个元素，当然也可以删除 EF 两个元素，保留一个 G 元素
coymail 1 天前 via iPhone 1
根据关系值大于 0.5 的边及其邻接点构造子图；
将子图中大于 0.5 的边的关系值大小统一视为 1 ；
统计每个点的邻接关系值和；
迭代优先删除邻接关系值和最大的点同时更新该点邻接点的关系值和，直到关系值都降为 0 ；
将子图中大于 0.5 的边的关系值大小统一视为 1 ；
统计每个点的邻接关系值和；
迭代优先删除邻接关系值和最大的点同时更新该点邻接点的关系值和，直到关系值都降为 0 ；
kimera 1 天前 2
处理思路
- 将原矩阵简化成 0 ，1 （大于等于 0.5 转换为 1 ，小于 0.5 转换为 0 ）
- 构建每个位置 i 的元素和与他相邻的节点放到 nexts 列表中
- 将列表放入大根堆，按照相邻元素从大到小排序
- 依次取出每一个元素 X 删除，并在邻接表中对应元素的 nexts 中删除 X
- 直到队列中的所有元素的 nexts 都变成 0 ，那么这些元素就是完全独立的，输出即可
代码实现 https://raw.githubusercontent.com/rikei/walle/master/walle-study/src/main/java/com/panpan/walle/study/temp/V2exAlg.java
- 将原矩阵简化成 0 ，1 （大于等于 0.5 转换为 1 ，小于 0.5 转换为 0 ）
- 构建每个位置 i 的元素和与他相邻的节点放到 nexts 列表中
- 将列表放入大根堆，按照相邻元素从大到小排序
- 依次取出每一个元素 X 删除，并在邻接表中对应元素的 nexts 中删除 X
- 直到队列中的所有元素的 nexts 都变成 0 ，那么这些元素就是完全独立的，输出即可
代码实现 https://raw.githubusercontent.com/rikei/walle/master/walle-study/src/main/java/com/panpan/walle/study/temp/V2exAlg.java
kimera 1 天前 1
@edward1987 矩阵遍历的复杂度就是 O(N^2)了，想不到有啥可以降低复杂度的方法；算了下 10000 个元素，大概要 50s 左右，10w 数量级就要 5000s ，也是需要一个半小时
wa007 1 天前 1
如二楼，等价于在图中选择最多的互不相邻的结点。
初始成一个节点为根节点的有向图，深度优先遍历，动态规划，dp[point][status] 表示根节点为 point 、节点 point 的状态为 status 的子图中存在的最多互不相邻的节点数量。status 表示状态，只有两种取值，是否丢弃。空间复杂度 N*2 ，时间复杂度 N 。
初始成一个节点为根节点的有向图，深度优先遍历，动态规划，dp[point][status] 表示根节点为 point 、节点 point 的状态为 status 的子图中存在的最多互不相邻的节点数量。status 表示状态，只有两种取值，是否丢弃。空间复杂度 N*2 ，时间复杂度 N 。
monster1priest 1 天前 via iPhone 1
@wa007 图论相关的结论，二分图的最大独立点个数=点的个数—最小点覆盖数，而最小点覆盖数又等于最大匹配数，具体证明过程我也没了解过。
imn1 23 小时 22 分钟前
@lozzow #20
解决问题那还是 pandas 吧
df = pd.DataFrame(...)
mask = df<0.5
df1 = df.where(mask)
mask 是个 True|False 矩阵
df1 是一个保留匹配数据，其他置为 nan 的矩阵，看你需要哪个
如果求单行或单列匹配的个数，用 pd.Series.count()就可以了，pd 的 count 是排除 None/nan 值的个数
估计有用的函数还有 max/idxmax/sort/head/tail 等
你这个是纯数值，很快的，百万数据耗时单位应该是秒 /分钟，不可能是小时
如果实际操作仍然觉得慢，可以加上 dask ，dask 处理这些单类型 dataframe 很快
PS: 我有点好奇你的原始数据格式是什么，如果是这个矩阵，其实有点浪费空间(有效单元格只有不到一半)，应该不是这个吧？如果不是这个，可能还有其他优化方法
我觉得这个矩阵转一维，处理更快更方便
解决问题那还是 pandas 吧
df = pd.DataFrame(...)
mask = df<0.5
df1 = df.where(mask)
mask 是个 True|False 矩阵
df1 是一个保留匹配数据，其他置为 nan 的矩阵，看你需要哪个
如果求单行或单列匹配的个数，用 pd.Series.count()就可以了，pd 的 count 是排除 None/nan 值的个数
估计有用的函数还有 max/idxmax/sort/head/tail 等
你这个是纯数值，很快的，百万数据耗时单位应该是秒 /分钟，不可能是小时
如果实际操作仍然觉得慢，可以加上 dask ，dask 处理这些单类型 dataframe 很快
PS: 我有点好奇你的原始数据格式是什么，如果是这个矩阵，其实有点浪费空间(有效单元格只有不到一半)，应该不是这个吧？如果不是这个，可能还有其他优化方法
我觉得这个矩阵转一维，处理更快更方便
lozzow 22 小时 43 分钟前
@imn1 不不不，这样会删除过多的数据，就像上面是说的,我们看 G 那一行和对应的 EF 那两列的（ G,E ）(G,F),假设我们整个矩阵就这两个对应关系是大于 0.5 的，按照你这个做法，那么 G,E,F 三个元素都会被删除，实际上我们只需要删除元素 G ，就能满足要求，或者删除 E ，F 也能满足要求，我们又要使剩余元素最多，那么只能删除 G ，不知道我有没有表述清楚
imn1 22 小时 23 分钟前
@lozzow #23
虽然我理解错了 最多删除 --> 最少删除，但好像也影响也不大
转一维后，表头变成 AB | AC | AD ... | EF | EG | FG
此例末三个(0.9, 0.7, 0.7)置 nan 后，提取剩余的表头，就能确定里面不含 G 了
但因为还有 DE(0.2)和 BF(0.4)剩下，所以 E/F 可以确认保留
只是逻辑变换一下而已
虽然我理解错了 最多删除 --> 最少删除，但好像也影响也不大
转一维后，表头变成 AB | AC | AD ... | EF | EG | FG
此例末三个(0.9, 0.7, 0.7)置 nan 后，提取剩余的表头，就能确定里面不含 G 了
但因为还有 DE(0.2)和 BF(0.4)剩下，所以 E/F 可以确认保留
只是逻辑变换一下而已
imn1 22 小时 11 分钟前
set('ABCDEFG') - set(''.join(df.columns)) # {'G'} 且 len==1
所以，求出这个符合需求的 df 就行了，基本上逻辑比较的 mask 就可以完成
具体看你的业务需求吧，我感觉这样 一维 * 几万条记录，也不会太慢
所以，求出这个符合需求的 df 就行了，基本上逻辑比较的 mask 就可以完成
具体看你的业务需求吧，我感觉这样 一维 * 几万条记录，也不会太慢
imn1 21 小时 34 分钟前
In [40]: df=pd.DataFrame([[1,0.2,3,0.4,0.5,0.6]], columns=['AB','AC','AD','BC','BD','CD'])
In [41]: mask=df<0.5
In [42]: df['rest']=[set('ABCD')-set(''.join(df[mask].loc[i,:].dropna().index)) for i in df.index]
In [43]: df
Out[43]:
AB AC AD BC BD CD rest
0 1 0.2 3 0.4 0.5 0.6 {D}
根据你的业务逻辑 求 df['rest'] 的值，如果复杂可以写成函数，用 apply/map
当然也可以根据需求添加更多的列，用其他 mask
In [41]: mask=df<0.5
In [42]: df['rest']=[set('ABCD')-set(''.join(df[mask].loc[i,:].dropna().index)) for i in df.index]
In [43]: df
Out[43]:
AB AC AD BC BD CD rest
0 1 0.2 3 0.4 0.5 0.6 {D}
根据你的业务逻辑 求 df['rest'] 的值，如果复杂可以写成函数，用 apply/map
当然也可以根据需求添加更多的列，用其他 mask
imn1 21 小时 25 分钟前
加一行数据，更直观些
脑子实了，列名应该是 remove 不是 rest
In [49]: df=pd.DataFrame([[1,0.2,3,0.4,0.5,0.6], [1,0.5,0.9,0.4,0.3,0.01]], columns=['AB','AC','AD','BC','BD','CD'])
In [50]: df
Out[50]:
AB AC AD BC BD CD
0 1 0.2 3.0 0.4 0.5 0.60
1 1 0.5 0.9 0.4 0.3 0.01
In [51]: mask=df<0.5
In [52]: df['remove']=[set('ABCD')-set(''.join(df[mask].loc[i,:].dropna().index)) for i in df.index]
In [53]: df
Out[53]:
AB AC AD BC BD CD remove
0 1 0.2 3.0 0.4 0.5 0.60 {D}
1 1 0.5 0.9 0.4 0.3 0.01 {A}
脑子实了，列名应该是 remove 不是 rest
In [49]: df=pd.DataFrame([[1,0.2,3,0.4,0.5,0.6], [1,0.5,0.9,0.4,0.3,0.01]], columns=['AB','AC','AD','BC','BD','CD'])
In [50]: df
Out[50]:
AB AC AD BC BD CD
0 1 0.2 3.0 0.4 0.5 0.60
1 1 0.5 0.9 0.4 0.3 0.01
In [51]: mask=df<0.5
In [52]: df['remove']=[set('ABCD')-set(''.join(df[mask].loc[i,:].dropna().index)) for i in df.index]
In [53]: df
Out[53]:
AB AC AD BC BD CD remove
0 1 0.2 3.0 0.4 0.5 0.60 {D}
1 1 0.5 0.9 0.4 0.3 0.01 {A}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK