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
lozzow
V2EX  ›  Python

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

  •  
  •   lozzow · 2022-01-08 11:51:26 +08:00 · 4205 次点击
    这是一个创建于 810 天前的主题,其中的信息可能已经有所发展或是发生改变。
    • 有如下一个矩阵,表示 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 个数最多的那一条,但是速度太慢了,我们可能会有好几万一批的数据,得要几个小时,求好兄弟们给个牛逼的解法

    42 条回复    2022-01-14 09:01:04 +08:00
    minamike
        1
    minamike  
       2022-01-08 12:47:45 +08:00 via iPhone   ❤️ 1
    多进程?
    python 好像递归比 for 循环慢多了
    monster1priest
        2
    monster1priest  
       2022-01-08 12:50:58 +08:00   ❤️ 3
    先建图,只考虑大于 0.5 的路径。
    问题转换为删除最少的节点,使得剩余结点之间相互独立。
    也等价于在图中选择最多的互不相邻的结点。
    等价于二分图的最大匹配问题。
    ZRS
        3
    ZRS  
       2022-01-08 13:02:03 +08:00 via iPhone   ❤️ 1
    删除其中关系值大于 0.5 的数据,使之留下的元素之间的两两关系值都小于 0.5

    且元素最多

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

    你是不是需要求解任务分配问题( Assignment Problem )
    lozzow
        4
    lozzow  
    OP
       2022-01-08 13:09:01 +08:00 via Android
    @ZRS 比如你删除了元素 G 之后,元素 E 和 F 就少了一个大于 0.5 的关系,这样就只用删除一个元素,当然也可以删除 EF 两个元素,保留一个 G 元素
    edward1987
        5
    edward1987  
       2022-01-08 14:44:27 +08:00   ❤️ 2
    你的递归方法不能解决吧。
    比如要删除的是 AB,BC,CD,AE,BE,CE
    最优解应该是删除 A,B,C 三个元素。 按你的递归会删除 E,A,B,C
    coymail
        6
    coymail  
       2022-01-08 15:17:12 +08:00 via iPhone   ❤️ 1
    根据关系值大于 0.5 的边及其邻接点构造子图;
    将子图中大于 0.5 的边的关系值大小统一视为 1 ;
    统计每个点的邻接关系值和;
    迭代优先删除邻接关系值和最大的点同时更新该点邻接点的关系值和,直到关系值都降为 0 ;
    kimera
        7
    kimera  
       2022-01-08 15:22:22 +08:00   ❤️ 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
    kimera
        8
    kimera  
       2022-01-08 15:23:31 +08:00   ❤️ 1
    @coymail 咱俩想一块了 哈哈
    edward1987
        9
    edward1987  
       2022-01-08 15:47:23 +08:00   ❤️ 1
    @coymail @kimera 你们俩的思路是楼主的优化版吧,但是还是做不到最优解啊= =。
    imn1
        10
    imn1  
       2022-01-08 16:29:49 +08:00   ❤️ 1
    你是要解决问题,还是做算法题?
    解决问题的话,扔进 pandas/numpy ,一行 mask 语句搞定
    算法的话,我 pass
    ljn917
        11
    ljn917  
       2022-01-08 16:33:00 +08:00 via Android   ❤️ 1
    kimera
        12
    kimera  
       2022-01-08 16:59:24 +08:00   ❤️ 1
    @edward1987 矩阵遍历的复杂度就是 O(N^2)了,想不到有啥可以降低复杂度的方法;算了下 10000 个元素,大概要 50s 左右,10w 数量级就要 5000s ,也是需要一个半小时
    wa007
        13
    wa007  
       2022-01-08 19:20:52 +08:00   ❤️ 1
    @monster1priest 后两者是等价的吗?要怎么理解呢?
    wa007
        14
    wa007  
       2022-01-08 19:28:47 +08:00   ❤️ 1
    如二楼,等价于在图中选择最多的互不相邻的结点。
    初始成一个节点为根节点的有向图,深度优先遍历,动态规划,dp[point][status] 表示根节点为 point 、节点 point 的状态为 status 的子图中存在的最多互不相邻的节点数量。status 表示状态,只有两种取值,是否丢弃。空间复杂度 N*2 ,时间复杂度 N 。
    wa007
        15
    wa007  
       2022-01-08 19:30:28 +08:00   ❤️ 1
    @wa007 根据子节点的取值可以获取状态转移方程,获得父节点的取值
    vance123
        16
    vance123  
       2022-01-08 19:39:02 +08:00   ❤️ 1
    转化成 01 规划问题,丢给求解器试试
    vance123
        17
    vance123  
       2022-01-08 19:49:20 +08:00   ❤️ 1
    又找了会资料,这就是个 NP-hard 的顶点覆盖问题。用最少的点去所有覆盖大于 0.5 的边
    akira
        18
    akira  
       2022-01-08 20:04:26 +08:00   ❤️ 1
    根据 2l 的提示,去看了下二分图的最大匹配问题 ,应该是可以满足需求的
    monster1priest
        19
    monster1priest  
       2022-01-08 20:08:23 +08:00 via iPhone   ❤️ 2
    @wa007 图论相关的结论,二分图的最大独立点个数=点的个数—最小点覆盖数,而最小点覆盖数又等于最大匹配数,具体证明过程我也没了解过。
    lozzow
        20
    lozzow  
    OP
       2022-01-08 20:46:46 +08:00
    @imn1 哈哈哈解决问题
    lozzow
        21
    lozzow  
    OP
       2022-01-08 20:46:59 +08:00
    @kimera 谢谢大佬我瞅瞅
    imn1
        22
    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
        23
    lozzow  
    OP
       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
        24
    monster1priest  
       2022-01-08 22:37:01 +08:00   ❤️ 1
    https://www.cnblogs.com/jamespei/p/5555734.html
    帮楼主找了一个最大匹配的 python 实现,用的是匈牙利算法
    imn1
        25
    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
        26
    imn1  
       2022-01-08 22:51:56 +08:00
    set('ABCDEFG') - set(''.join(df.columns)) # {'G'} 且 len==1
    所以,求出这个符合需求的 df 就行了,基本上逻辑比较的 mask 就可以完成

    具体看你的业务需求吧,我感觉这样 一维 * 几万条记录,也不会太慢
    lozzow
        27
    lozzow  
    OP
       2022-01-08 22:54:00 +08:00
    @imn1 没太理解,能再详细点吗?哈哈哈我是菜鸡,但是感觉做成一维后确实好处理点
    imn1
        28
    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
        29
    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
        30
    rapiz  
       2022-01-08 23:52:44 +08:00   ❤️ 1
    @monster1priest 这个不是二分图吧?一般图的最大独立集是 NP Hard 的
    ZRS
        31
    ZRS  
       2022-01-09 00:22:31 +08:00 via iPhone
    另外如果考虑求解速度可以牺牲一定精度的话,可以看看 Sinkhorn Algorithm

    https://proceedings.neurips.cc/paper/2013/file/af21d0c97db2e27e13572cbf59eb343d-Paper.pdf
    monster1priest
        32
    monster1priest  
       2022-01-09 08:51:25 +08:00
    @rapiz 对 我也刚发现,有可能染色数大于二。。。。普通图只能用搜索解
    xuanbg
        33
    xuanbg  
       2022-01-09 10:38:43 +08:00
    效率取决于数据结构!如果你现在用一个二维数组存储数据的话,老老实实二层循环遍历就是效率最高的。
    jones2000
        34
    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
        35
    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
        36
    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
        37
    necomancer  
       2022-01-10 01:02:32 +08:00
    更正一下,这个对节点数好像是 O(N^3),很蠢了……4000 节点需要 36s ,10000 节点应该是 560s ,2 万节点就得一小时+,几万节点的话可能还是不合适。
    necomancer
        38
    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
        39
    necomancer  
       2022-01-10 01:19:44 +08:00
    ……能 tm 删帖就好了,我是傻逼……
    RecursiveG
        40
    RecursiveG  
       2022-01-10 07:13:50 +08:00
    lozzow
        41
    lozzow  
    OP
       2022-01-10 10:37:49 +08:00 via Android
    @necomancer 哈哈哈哈,没事,谁都会抽抽下
    wa007
        42
    wa007  
       2022-01-14 09:01:04 +08:00 via iPhone
    @monster1priest 懂了,感谢老板!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3920 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 10:25 · PVG 18:25 · LAX 03:25 · JFK 06:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.