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

如何在 Python3 中对列表 通过比较排序(不懂就问)?

  •  
  •   superhxl · 2021-09-02 11:27:46 +08:00 · 2029 次点击
    这是一个创建于 1182 天前的主题,其中的信息可能已经有所发展或是发生改变。

    已知列表和字典,列表是需排序元素,字典指明了元素间的优先关系,譬如 S1 需在 S3 之前,而 S3 又在 S2 之前。

    s = ['S1','S2','S3']
    
    val = {('S1','S3'):1,('S3','S2'):1}
    

    希望得到的结果是['S1','S3','S2'],请问有何好的实现方式?

    自己想用 python 中的 sort 的 cmp 参数进行排序,结果竟然没排序,不知原因。

    from functools import cmp_to_key
    
     s.sort(key=cmp_to_key(lambda x,y: val.get((x,y),0)))
    
    16 条回复    2021-09-04 19:34:43 +08:00
    toaruScar
        1
    toaruScar  
       2021-09-02 11:37:44 +08:00
    可以弄成一个 class,然后用 functools.total_ordering 自定义对比函数。
    MoYi123
        2
    MoYi123  
       2021-09-02 11:40:58 +08:00
    s = ['S1', 'S2', 'S3']
    val = {('S1', 'S3'): 1, ('S3', 'S2'): 1}


    class S(str):

    ____def __lt__(self, other):
    ________if (self, other) in val:
    ____________return val[(self, other)] == 1
    ________return False


    s = [S(i) for i in s]
    s.sort()
    print([str(i) for i in s])

    能用, 但是应该有更好的办法
    Trim21
        3
    Trim21  
       2021-09-02 11:42:03 +08:00 via Android   ❤️ 1
    key=lambda x: {s1: 1 , s3: 2, s3: 3}.get(x, 0)
    lonelinsky
        4
    lonelinsky  
       2021-09-02 12:16:20 +08:00
    s = ['S1','S2','S3']
    val = {('S1','S3'):-1,('S3','S2'):-1} # 这里你一开始的定义有点问题,如果你希望 S1 排在 S3 前面,则它的值应该是负的

    s.sort(key=cmp_to_key(lambda x,y: val.get((x,y), -val.get((y,x), 0)))) # 这里你可能需要同时处理 (y, x) 的情况,如果你的定义是对称的。即 S1 在 S3 前面 <=> S3 在 S2 后面

    注意你现在的方式里面对于未出现 val 里面的对,都会当成不需要排序的对象。如果你是像解决 AOE 网络的拓扑排序问题,建议直接看相关算法。

    =============================
    你一开始的排序完全没用是因为排序时候,假设按序比较
    (S1, S2) 你的 val 里面没有,返回 0 表示相等,不用做任何操作
    (S2, S3) 你的 val 里面还是没有,返回 0 表示相等,又不用做任何操作,所以它已经排好序了
    lonelinsky
        5
    lonelinsky  
       2021-09-02 12:24:42 +08:00
    typo
    S1 在 S3 前面 <=> S3 在 S1 后面
    superhxl
        6
    superhxl  
    OP
       2021-09-02 12:45:43 +08:00
    @lonelinsky 我的定义没问题,也许有更好的方式。本身问题背景是若干个点,一次对这些点遍历,想要打印遍历的顺序。字典中的值表示相继访问的顺序,访问 S1 后访问 S3,访问 S3 后访问 S2.

    关于 cmp 的应用再查查文档,这个确实是临时搜索的解决方案。

    目前可以通过冒泡排序解决,但我想应该有更好办法。
    ```python
    for p in range(len(s)-1):
    for q in range(p + 1, len(s)):
    if sol[z[(s[q],s[p])]] == 1:
    s[p], s[q] = s[q], s[p]
    ```
    @toaruScar 去学习一下具体用法。
    @MoYi123 好复杂的样子。
    @Trim21 没看懂。
    lonelinsky
        7
    lonelinsky  
       2021-09-02 13:46:54 +08:00
    https://docs.python.org/3/library/functools.html#functools.cmp_to_key
    A comparison function is any callable that accept two arguments, compares them, and returns a negative number for less-than, zero for equality, or a positive number for greater-than.

    你定义的 1 会被认为是 greater-than,而默认排序是从小到大,所以你的定义和你的预期是反的,这是我说你定义有问题的地方,如果执意用 1 做定义的话,可以在 function 里面取个反就行。
    你现在的定义里面不能保证任意两个元素的 cmp 结果都包含,比如你开始的定义里面 S1 和 S2 的大小关系没有显式定义,在冒泡这种会完全比较的排序方法中可能没问题,但是对于类似快排这种,排序中间可能会出现错误的结果。(这个地方是直觉,没有严格证明)

    > 本身问题背景是若干个点,一次对这些点遍历,想要打印遍历的顺序。
    如果是这个问题的话,建议用 OrderedDict https://docs.python.org/3/library/collections.html#collections.OrderedDict,直接打印就好了。
    lonelinsky
        8
    lonelinsky  
       2021-09-02 13:50:48 +08:00
    > 字典中的值表示相继访问的顺序
    我好像理解错了,所以字典中的值会是 1,2,3 这样?是的话对字典按 value 排序,然后对 key 做个 reduce 就好了?
    BBrother
        9
    BBrother  
       2021-09-02 13:51:24 +08:00
    没看到你的问题,你是不是需要拓扑排序?
    princelai
        10
    princelai  
       2021-09-02 16:20:22 +08:00   ❤️ 4
    from networkx import DiGraph, draw_networkx, topological_sort

    s = ['S1', 'S2', 'S3', 'S4', 'S5']
    val = {('S1', 'S3'): 1, ('S3', 'S2'): 1, ('S5', 'S1'): 1, ('S2', 'S4'): 1}
    g = DiGraph()
    g.add_edges_from(val.keys())
    s = list(topological_sort(g))
    ipwx
        11
    ipwx  
       2021-09-02 16:34:53 +08:00
    @superhxl python 默认的不是两两比较排序,而是快速排序,只比 N log N 次。

    所以你期待的 S1 < S3 + S3 < S2 imply S1 < S2 不存在。

    你这个需求可以建图然后用拓扑排序。
    Pythoner666666
        12
    Pythoner666666  
       2021-09-02 17:46:21 +08:00
    老谢 是你吗??
    O5oz6z3
        13
    O5oz6z3  
       2021-09-02 18:14:48 +08:00
    想到一个麻烦的做法:
    def cmp(a, b):
      lt = val.get((a,b))
      if lt == 1:
       return -1
      gt = val.get((b,a))
      if gt == 1:
       return 1
      return -1 if a<b else 1 if a>b else 0
    感觉像 #10 楼那样将 val 换成 set(val.keys()) 也没有问题。这个自定义排序似乎可以再加些功能,比如优先度排序?
    efaun
        14
    efaun  
       2021-09-02 18:39:15 +08:00
    @MoYi123 #2 缩进的下划线是你手动加的还是有工具?
    MoYi123
        15
    MoYi123  
       2021-09-03 13:27:09 +08:00
    @efaun 手动的
    superhxl
        16
    superhxl  
    OP
       2021-09-04 19:34:43 +08:00
    @lonelinsky 明白了,多谢!对 collections 模块缺失不熟悉!

    @princelai networkx 听说过,但没用过。果然学无止境。本来自己把顺序提取出来,就是为了绘图,采用 networkx 直接帮我把问题全解决了。

    @Pythoner666666 ☻,认错人了!

    感谢楼上所有帮忙出注意的 V 友!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3134 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 13:39 · PVG 21:39 · LAX 05:39 · JFK 08:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.