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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 1049 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

删除

元素

大于

ABCDEFG

42 条回复 • 2022-01-14 09:01:04 +08:00

minamike

2022-01-08 12:47:45 +08:00 via iPhone

多进程？
python 好像递归比 for 循环慢多了

monster1priest

2022-01-08 12:50:58 +08:00

先建图，只考虑大于 0.5 的路径。
问题转换为删除最少的节点，使得剩余结点之间相互独立。
也等价于在图中选择最多的互不相邻的结点。
等价于二分图的最大匹配问题。

ZRS

2022-01-08 13:02:03 +08:00 via iPhone

删除其中关系值大于 0.5 的数据，使之留下的元素之间的两两关系值都小于 0.5

且元素最多

第二个条件没看明白第一个条件不就已经规定了删除方式了怎么还能有元素最多这个约束

你是不是需要求解任务分配问题（ Assignment Problem ）

lozzow

2022-01-08 13:09:01 +08:00 via Android

@ZRS 比如你删除了元素 G 之后，元素 E 和 F 就少了一个大于 0.5 的关系，这样就只用删除一个元素，当然也可以删除 EF 两个元素，保留一个 G 元素

edward1987

2022-01-08 14:44:27 +08:00

你的递归方法不能解决吧。
比如要删除的是 AB,BC,CD,AE,BE,CE
最优解应该是删除 A,B,C 三个元素。按你的递归会删除 E,A,B,C

coymail

2022-01-08 15:17:12 +08:00 via iPhone

根据关系值大于 0.5 的边及其邻接点构造子图；
将子图中大于 0.5 的边的关系值大小统一视为 1 ；
统计每个点的邻接关系值和；
迭代优先删除邻接关系值和最大的点同时更新该点邻接点的关系值和，直到关系值都降为 0 ；

kimera

2022-01-08 15:22:22 +08:00

处理思路
- 将原矩阵简化成 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

2022-01-08 15:23:31 +08:00

@coymail 咱俩想一块了哈哈

edward1987

2022-01-08 15:47:23 +08:00

@coymail @kimera 你们俩的思路是楼主的优化版吧，但是还是做不到最优解啊= =。

imn1

2022-01-08 16:29:49 +08:00

你是要解决问题，还是做算法题？
解决问题的话，扔进 pandas/numpy ，一行 mask 语句搞定
算法的话，我 pass

ljn917

2022-01-08 16:33:00 +08:00 via Android

https://stackoverflow.com/questions/32419189/remove-minimum-number-of-vertices-to-make-all-the-vertices-isolated

好像和这个一样

kimera

2022-01-08 16:59:24 +08:00

@edward1987 矩阵遍历的复杂度就是 O(N^2)了，想不到有啥可以降低复杂度的方法；算了下 10000 个元素，大概要 50s 左右，10w 数量级就要 5000s ，也是需要一个半小时

wa007

2022-01-08 19:20:52 +08:00

@monster1priest 后两者是等价的吗？要怎么理解呢？

wa007

2022-01-08 19:28:47 +08:00

如二楼，等价于在图中选择最多的互不相邻的结点。
初始成一个节点为根节点的有向图，深度优先遍历，动态规划，dp[point][status] 表示根节点为 point 、节点 point 的状态为 status 的子图中存在的最多互不相邻的节点数量。status 表示状态，只有两种取值，是否丢弃。空间复杂度 N*2 ，时间复杂度 N 。

wa007

2022-01-08 19:30:28 +08:00

@wa007 根据子节点的取值可以获取状态转移方程，获得父节点的取值

vance123

2022-01-08 19:39:02 +08:00

转化成 01 规划问题，丢给求解器试试

vance123

2022-01-08 19:49:20 +08:00

又找了会资料，这就是个 NP-hard 的顶点覆盖问题。用最少的点去所有覆盖大于 0.5 的边

akira

2022-01-08 20:04:26 +08:00

根据 2l 的提示，去看了下二分图的最大匹配问题，应该是可以满足需求的

monster1priest

2022-01-08 20:08:23 +08:00 via iPhone

@wa007 图论相关的结论，二分图的最大独立点个数=点的个数—最小点覆盖数，而最小点覆盖数又等于最大匹配数，具体证明过程我也没了解过。

lozzow

2022-01-08 20:46:46 +08:00

@imn1 哈哈哈解决问题

lozzow

2022-01-08 20:46:59 +08:00

@kimera 谢谢大佬我瞅瞅

imn1

2022-01-08 21:41:41 +08:00

@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

2022-01-08 22:20:11 +08:00

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

monster1priest

2022-01-08 22:37:01 +08:00

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

imn1

2022-01-08 22:40:46 +08:00

@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

2022-01-08 22:51:56 +08:00

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

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

lozzow

2022-01-08 22:54:00 +08:00

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

imn1

2022-01-08 23:28:56 +08:00

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

2022-01-08 23:37:56 +08:00

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

2022-01-08 23:52:44 +08:00

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

ZRS

2022-01-09 00:22:31 +08:00 via iPhone

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

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

monster1priest

2022-01-09 08:51:25 +08:00

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

xuanbg

2022-01-09 10:38:43 +08:00

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

jones2000

2022-01-09 22:27:58 +08:00

多线程统计或分布式统计，汇总需要删的元素，最后统一删除不就可以了。最快的速度就 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

2022-01-10 00:57:41 +08:00

按照楼主的思路：
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

2022-01-10 00:59:57 +08:00

按照楼主的思路：
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

2022-01-10 01:02:32 +08:00

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

necomancer

2022-01-10 01:18:22 +08:00

对不起我还在脑残中……按照你的思路：
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

2022-01-10 01:19:44 +08:00

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

RecursiveG

2022-01-10 07:13:50 +08:00

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

lozzow

2022-01-10 10:37:49 +08:00 via Android

@necomancer 哈哈哈哈，没事，谁都会抽抽下

wa007

2022-01-14 09:01:04 +08:00 via iPhone

@monster1priest 懂了，感谢老板！