按类属性进行低复杂度Python排序(小-大-小)

Question

我希望将我的列表(Class)按小-大-小的顺序排序，例如，如果它是纯数字的，列表是1,5,3,7,7,3,2，排序将是1,3,7,7,5,3,2。

基本的类结构是：

class LaneData:
    def __init__(self):
        self.Name = "Random"
        self.laneWeight = 5

因此，从本质上讲，排序函数将从LaneData.laneWeight变量开始工作。我找到了这个答案here，我不能完全确定它在这个使用类作为列表变量的实例中是否有效。

我的第二个想法是像这样(下面的伪代码) [inspired by]

def sortByWeight(e):
    return e.getLaneWeight()

newList = [] # create a new list to store
lanes.sort(key=sortByWeight) # python default sort by our class attrib
newList = lanes[:len(lanes) // 2] # get the first half of the sorted list (low-high)
lanes.sort(key=sortByWeight, reverse=True) # reverse the sort
newList = newList + lanes[:len(lanes) // 2] # get the first half of the sorted list (high-low)

如果可能，我希望保持排序的小和有效，如果需要的话，我不介意为它构建一个小的算法。你的思维团队是什么？

Answer 1

您的解决方案是有效的，但您先按升序排列列表的末尾，然后按降序排列。

您可以通过以下方式对其进行优化：

• 查找最大值的索引，将最大值与中间位置的元素互换，最后分别对表的前半部分(按升序)和后半部分(按降序)进行排序。

• 而不是对后半部分进行反向排序，您可以简单地反向排序(使用reverse函数)。这不是很复杂(O(n)而不是O(nlog(n))

Answer 2

讨论

既然您可以只使用key参数，那么我将暂时忽略它。

给定序列的算法如下所示：

def middle_sort_flip_OP(seq, key=None):
    result = []
    length = len(seq)
    seq.sort(key=key)
    result = seq[:length // 2]
    seq.sort(key=key, reverse=True)
    result.extend(seq[:length // 2])
    return result
    

print(middle_sort_flip_OP([1, 5, 3, 7, 3, 2, 9, 8]))
# [1, 2, 3, 3, 9, 8, 7, 5]
print(middle_sort_flip_OP([1, 5, 3, 7, 3, 2, 8]))
# [1, 2, 3, 8, 7, 5]

第二个排序步骤完全没有必要(但与在Python中实现的Timsort算法的简单反转具有相同的计算复杂性)，因为您可以简单地向后切片排序的序列(确保计算“中间”元素的正确偏移量)：

def middle_sort_flip(seq, key=None):
    length = len(seq)
    offset = length % 2
    seq.sort(key=key)
    return seq[:length // 2] + seq[:length // 2 - 1 + offset:-1]
    

print(middle_sort_flip([1, 5, 3, 7, 3, 2, 9, 8]))
# [1, 2, 3, 3, 9, 8, 7, 5]
print(middle_sort_flip([1, 5, 3, 7, 3, 2, 8]))
# [1, 2, 3, 8, 7, 5]

另一种理论上更有效的方法是分别对序列的左侧和右侧进行排序。这样效率更高，因为每个排序步骤都是O(N/2 log N/2)，当组合在一起时会得到O(N log N/2) (而不是O(N + N log N))：

def middle_sort_half(seq, key=None):
    length = len(seq)
    return \
        sorted(seq[:length // 2], key=key) \
        + sorted(seq[length // 2:], key=key, reverse=True)

然而，这些方法要么给出一个很大程度上不平衡的结果，即整个右侧大于左侧(middle_sort_flip())，要么具有取决于输入初始顺序的平衡(middle_sort_half())。

通过提取和重组奇偶子序列，可以得到更平衡的结果。这在Python语言中非常简单，这要归功于切片操作，并且具有与middle_sort_flip()相同的渐近复杂性，但具有更好的平衡特性：

def middle_sort_mix(seq, key=None):
    length = len(seq)
    offset = length % 2
    seq.sort(key=key)
    result = [None] * length
    result[:length // 2] = seq[::2]
    result[length // 2 + offset:] = seq[-1 - offset::-2]
    return result


print(middle_sort_mix([1, 5, 3, 7, 3, 2, 9, 8]))
# [1, 3, 5, 8, 9, 7, 3, 2]
print(middle_sort_mix([1, 5, 3, 7, 3, 2, 8]))
# [1, 3, 5, 8, 7, 3, 2]

基准测试

在速度方面，当不使用key参数时，它们都非常相似，因为执行时间由周围的复制控制：

import random


nums = [10 ** i for i in range(1, 7)]
funcs = middle_sort_flip_OP, middle_sort_flip, middle_sort_half, middle_sort_mix
print(nums)
# [10, 100, 1000, 10000, 100000, 1000000]


def gen_input(num):
    return list(range(num))


for num in nums:
    print(f"N = {num}")
    for func in funcs:
        seq = gen_input(num)
        random.shuffle(seq)
        print(f"{func.__name__:>24s}", end="  ")
        %timeit func(seq.copy())
    print()

...
N = 1000000
     middle_sort_flip_OP  542 ms ± 54.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
        middle_sort_flip  510 ms ± 49 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
        middle_sort_half  546 ms ± 4.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
         middle_sort_mix  539 ms ± 63 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

另一方面，当key参数非常重要时，与其他两种方法相比，您的方法具有更多的函数调用，这可能会导致middle_sort_OP()的执行时间显著增加

def gen_input(num):
    return list(range(num))


def key(x):
    return x ** 2


for num in nums:
    print(f"N = {num}")
    for func in funcs:
        seq = gen_input(num)
        random.shuffle(seq)
        print(f"{func.__name__:>24s}", end="  ")
        %timeit func(seq.copy(), key=key)
    print()

...
N = 1000000
     middle_sort_flip_OP  1.33 s ± 16.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
        middle_sort_flip  1.09 s ± 23.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
        middle_sort_half  1.1 s ± 27.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
         middle_sort_mix  1.11 s ± 8.88 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

或者，更贴近您的用例：

class Container():
    def __init__(self, x):
        self.x = x
        
    def get_x(self):
        return self.x

    
def gen_input(num):
    return [Container(x) for x in range(num)]


def key(c):
    return c.get_x()


for num in nums:
    print(f"N = {num}")
    for func in funcs:
        seq = gen_input(num)
        random.shuffle(seq)
        print(f"{func.__name__:>24s}", end="  ")
        %timeit func(seq.copy(), key=key)
    print()

...
N = 1000000
     middle_sort_flip_OP  1.27 s ± 4.44 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
        middle_sort_flip  1.13 s ± 13.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
        middle_sort_half  1.24 s ± 12.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
         middle_sort_mix  1.16 s ± 8.07 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

这看起来没那么戏剧性。