问一个删除元素的问题，要求要求速度快

[lozzow]

• 有如下一个矩阵，表示 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 个数最多的那一条，但是速度太慢了，我们可能会有好几万一批的数据，得要几个小时，求好兄弟们给个牛逼的解法

[lozzow]

@kimera 谢谢大佬我瞅瞅

[imn1]

@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: 我有点好奇你的原始数据格式是什么，如果是这个矩阵，其实有点浪费空间(有效单元格只有不到一半)，应该不是这个吧？如果不是这个，可能还有其他优化方法
我觉得这个矩阵转一维，处理更快更方便

[lozzow]

@imn1 不不不，这样会删除过多的数据，就像上面是说的,我们看 G 那一行和对应的 EF 那两列的（ G,E ）(G,F),假设我们整个矩阵就这两个对应关系是大于 0.5 的，按照你这个做法，那么 G,E,F 三个元素都会被删除，实际上我们只需要删除元素 G ，就能满足要求，或者删除 E ，F 也能满足要求，我们又要使剩余元素最多，那么只能删除 G ，不知道我有没有表述清楚

[monster1priest]

https://www.cnblogs.com/jamespei/p/5555734.html
帮楼主找了一个最大匹配的 python 实现，用的是匈牙利算法

[imn1]

@lozzow #23
虽然我理解错了 最多删除 --> 最少删除，但好像也影响也不大
转一维后，表头变成 AB | AC | AD ... | EF | EG | FG
此例末三个(0.9, 0.7, 0.7)置 nan 后，提取剩余的表头，就能确定里面不含 G 了
但因为还有 DE(0.2)和 BF(0.4)剩下，所以 E/F 可以确认保留

只是逻辑变换一下而已

[imn1]

set('ABCDEFG') - set(''.join(df.columns)) # {'G'} 且 len==1
所以，求出这个符合需求的 df 就行了，基本上逻辑比较的 mask 就可以完成

具体看你的业务需求吧，我感觉这样 一维 * 几万条记录，也不会太慢

[lozzow]

@imn1 没太理解，能再详细点吗？哈哈哈我是菜鸡，但是感觉做成一维后确实好处理点

[imn1]

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

[imn1]

加一行数据，更直观些
脑子实了，列名应该是 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}

[rapiz]

@monster1priest 这个不是二分图吧？一般图的最大独立集是 NP Hard 的

[ZRS]

另外如果考虑求解速度可以牺牲一定精度的话，可以看看 Sinkhorn Algorithm

https://proceedings.neurips.cc/paper/2013/file/af21d0c97db2e27e13572cbf59eb343d-Paper.pdf

[monster1priest]

@rapiz 对 我也刚发现，有可能染色数大于二。。。。普通图只能用搜索解

[xuanbg]

效率取决于数据结构！如果你现在用一个二维数组存储数据的话，老老实实二层循环遍历就是效率最高的。

[jones2000]

多线程统计 或 分布式统计， 汇总需要删的元素， 最后统一删除不就可以了。 最快的速度就 1 个元素遍历全部元素的关系。
A->A,B,C ，D,E,F, G 单独一个线程
B->A,B,C ，D,E,F, G 单独一个线程
C->A,B,C ，D,E,F, G 单独一个线程
。。。。。

[necomancer]

按照楼主的思路：
ret = a - np.diag(np.ones(a.shape[0])) # 主元不参与比较
drops = []
while (ret>=0.5).any():
....i_drop = np.argmax(np.sum(ret > 0.5, axis=0))
....drops.append(i_drop)
....ret = np.delete(ret, i_drop, axis=0)
....ret = np.delete(ret, i_drop, axis=1)
我试了试 10000x10000 的随机数组，粗略估计一下可能需要 4000s+，但 1000x1000 还是挺快的，大约 0.5s ，也就是能容纳 10^3 的节点数，几万个节点估计还是扯淡

[necomancer]

按照楼主的思路：
ret = a - np.diag(np.ones(a.shape[0])) # 主元不参与比较
drops = []
idx = np.arange(a.shape[0])
while (ret>=0.5).any():
....i_drop = np.argmax(np.sum(ret > 0.5, axis=0))
....drops.append(idx[i_drop])
....ret = np.delete(ret, i_drop, axis=0)
....ret = np.delete(ret, i_drop, axis=1)
....idx = np.delete(idx, i_drop)
抱歉，应该换算一下 index ，这样 drops 最后给出的就是应该被删除的元素编号，ret 最后是一个都小于 0.5 的矩阵。

[necomancer]

更正一下，这个对节点数好像是 O(N^3)，很蠢了……4000 节点需要 36s ，10000 节点应该是 560s ，2 万节点就得一小时+，几万节点的话可能还是不合适。

[necomancer]

对不起我还在脑残中……按照你的思路：
def test(a):
....a = a - np.diag(np.ones(a.shape[0])) # 主元不参与比较
....ind = np.sum(a >= 0.5, axis=0) # 每个节点大于 0.5 的计数
....g = a >= 0.5 # 节点对是否大于 0.5
....drops = []
....while (ind > 0).any():
........i_drop = np.argmax(ind)
........ind = ind - g[i_drop] # 剩下计数减掉被删掉的节点（大于 0.5 则-1 ，否则-0 ）
........ind[i_drop] = -1 # 每次删掉计数最大的
........drops.append(i_drop)
....ret = np.delete(a, drops, axis=0)
....ret = np.delete(ret, drops, axis=1)
....return ret, drops
这个很快。几万也行。

[necomancer]

……能 tm 删帖就好了，我是傻逼……

[RecursiveG]

16L +1 https://en.wikipedia.org/wiki/Vertex_cover