1

我有一个列表，其中包含此类项目的子列表。

mylist = [
['ITEM A', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'NO'],
['ITEM B', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'MAYBE'],
['ITEM C', 'YES', 'YES', 'YES', 'YES', 'NO', 'NO', 'MAYBE', 'NO', 'MAYBE']
]

现在我想在这种情况下对子列表进行排序——每行（即子列表）中的项目越'YES'多'MAYBE'，它就越高。'NO'每行的 s越多，它在排序列表中的移动越低。

理想的结果是——</p> 

mylist = [
['ITEM C', 'YES', 'YES', 'YES', 'YES', 'NO', 'NO', 'MAYBE', 'NO', 'MAYBE'],
['ITEM B', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'MAYBE'],
['ITEM A', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'NO']
]
#Item C has 4 'YES' and 2 'MAYBE'
#Item B has 3 'YES' and 1 'MAYBE'
#Item C has 3 'YES'

可悲的是，我被困在Python 2.3上，需要找出最有效的方法来做到这一点。

4

2 回答 2

3

要在 Python 2.3 或更低版本中按键排序，您可以使用cmp参数。但有时key样式排序更容易阅读；并且在任何情况下，它的工作量都会减少，因为cmp将被调用 O(n log n) 次，而key函数只会被调用 O(n) 次。

考虑到这一点，这是一种key在更高版本的 Python 中重现参数行为的方法。它使用 decorate-sort-undecorate 成语，也就是Schwartzian Transform。这不会像复制副本那样节省空间，但是对于大型列表，它可能会更节省时间。我之所以命名它sorted是因为它大致再现了sorted2.4 中添加的功能；检查python版本并有条件地导入它，这样你就不会破坏sorted新版本中的内置 - 或者只是重命名它。

def sorted(seq, key=lambda x: None, reverse=False):
    seq = [(key(x), i, x) for i, x in enumerate(seq)]
    seq.sort()
    if reverse:
        seq.reverse()
    return [x for k, i, x in seq]

请注意，enumerate仅当您关心对具有相等键的不相等值进行稳定排序时才需要这样做；它会减慢头发的功能。对您的数据进行了测试：

>>> key=lambda x: (x.count('YES'), x.count('MAYBE'), x.count('NO'))
>>> my_sorted(mylist, key=key, reverse=True)
[['ITEM C', 'YES', 'YES', 'YES', 'YES', 'NO', 'NO', 'MAYBE', 'NO', 'MAYBE'], 
 ['ITEM B', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'MAYBE'], 
 ['ITEM A', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'NO']]

您也可以考虑使用字典进行计数；这样，只需要一次通过。但是，经过充分优化，至少在我的机器上，count三遍仍然比一个 Python循环快。for因此，仅当您需要计算大量值时才使用它。我将把它留在这里以供后代使用：

def my_key(inner_list):
    counts = {'YES':0, 'MAYBE':0, 'NO':0}
    for i in inner_list:
        if i in counts:
            counts[i] += 1
    return (counts['YES'], counts['MAYBE'], counts['NO'])

我做了一些测试；为长篇大论道歉。以下仅适用于好奇和好奇的人。

我的测试表明，在较小的列表中， decorate, sort, undecorate已经比使用内置的 sort +更快cmp。在更大的列表中，差异变得更加显着。定义：

def key_count(x):
    return (x.count('YES'), x.count('MAYBE'), x.count('NO'))

def key_dict(inner_list):
    counts = {'YES':0, 'MAYBE':0, 'NO':0}
    for i in inner_list:
        if i in counts:
            counts[i] += 1
    return (counts['YES'], counts['MAYBE'], counts['NO'])

def decorate_sort(seq, key=lambda x: None, reverse=False):
    seq = [(key(x), i, x) for i, x in enumerate(seq)]
    seq.sort()
    if reverse:
        seq.reverse()
    return [x for k, i, x in seq]

def builtin_sort(seq, key, reverse=False):
    seq.sort(lambda p, q: cmp(key(p), key(q)))
    if reverse:
        seq.reverse()

测试：

>>> mylist = [
... ['ITEM A', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'NO'],
... ['ITEM B', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'MAYBE'],
... ['ITEM C', 'YES', 'YES', 'YES', 'YES', 'NO', 'NO', 'MAYBE', 'NO', 'MAYBE']
... ]
>>> %timeit decorate_sort(mylist, key=key_count, reverse=True)
100000 loops, best of 3: 5.03 us per loop
>>> %timeit builtin_sort(mylist, key=key_count, reverse=True)
100000 loops, best of 3: 5.28 us per loop

内置版本已经很慢了！由于添加了to ，不太通用的版本mylist.sort(lambda p, q: -cmp(key(p), key(q)))对于一个简短的列表来说是更好的选择。没有它，速度会更快（在我之前的测试中每个循环 4.28 us）：enumeratedecorate_sortdecorate_sort

>>> %timeit mylist.sort(lambda p, q: -cmp(key_count(p), key_count(q)))
100000 loops, best of 3: 4.74 us per loop

但是，在这种情况下使用key_dict是一个错误：

>>> %timeit decorate_sort(mylist, key=key_dict, reverse=True)
100000 loops, best of 3: 8.97 us per loop
>>> %timeit builtin_sort(mylist, key=key_dict, reverse=True)
100000 loops, best of 3: 11.4 us per loop

在更大的列表上对其进行测试，结果基本相同：

>>> import random
>>> mylist = [[random.choice(('YES', 'MAYBE', 'NO')) for _ in range(1000)] 
              for _ in range(100)]
>>> %timeit decorate_sort(mylist, key=key_count, reverse=True)
100 loops, best of 3: 6.93 ms per loop
>>> %timeit builtin_sort(mylist, key=key_count, reverse=True)
10 loops, best of 3: 34.5 ms per loop

不太通用的版本现在比decorate_sort.

>>> %timeit mylist.sort(lambda p, q: -cmp(key_count(p), key_count(q)))
100 loops, best of 3: 13.5 ms per loop

而且key_dict还是比较慢。（但比builtin_sort！）

>>> %timeit decorate_sort(mylist, key=key_dict, reverse=True)
10 loops, best of 3: 20.4 ms per loop
>>> %timeit builtin_sort(mylist, key=key_dict, reverse=True)
10 loops, best of 3: 103 ms per loop

所以结果是 Schwartzian 变换提供了一种更快、更通用的解决方案——一种罕见而美妙的组合。

于 2012-06-18T14:38:13.000 回答
2

一般解决方案：list.sort与返回元组的键函数一起使用：

mylist.sort(key=lambda sl: (sl.count('YES') + sl.count('MAYBE'), -sl.count('NO')), reverse=True)

key并reverse在 Python 2.4 中添加，因此您必须手动完成：

key = lambda sl: (sl.count('YES') + sl.count('MAYBE'), -sl.count('NO'))
mylist.sort(lambda p, q: -cmp(key(p), key(q)))

如果key速度很慢，最好使用key只对每个项目计算一次函数的解决方案（所谓的“施瓦茨变换”）。请注意 >=Python 2.4 已经执行了这个优化（或类似的）：

def key_sort(seq, cmp=None, key=None, reverse=False):
    if key is not None:
        transform = [(key(x), i, x) for i, x in enumerate(seq)]
        transform.sort(None if cmp is None else lambda (k, _, _), (l, _, _): cmp(k, l))
        seq[:] = [x for _, _, x in transform]
    else:
        seq.sort(cmp)
    if reverse:
        seq.reverse()
于 2012-06-18T13:39:58.053 回答