python - 在 Python 中移动和合并列表元素的最有效方法 (2048)

Question

我有一个函数，它基本上右对齐一个列表，但也将两个相等的元素合并为一个(列表将始终至少有一个元素):

def shift(sequence):
    for i in range(len(sequence)-1):
        current_value = sequence[i]
        next_value = sequence[i+1]
        if next_value == 0:
            sequence[i], sequence[i+1] = 0, current_value
        elif current_value == next_value:
            sequence[i], sequence[i+1] = 0, current_value*2
    return sequence

下面是一些示例输入和输出:

>>> shift([0, 0, 1, 0])
[0, 0, 0, 1]
>>> shift([1, 1, 0, 0])
[0, 0, 0, 2]
>>> shift([2, 0, 1, 0])
[0, 0, 2, 1]

最有效的方法是什么？如果对矩阵中的每一行都这样做，是否有更有效的方法:

matrix = [shift(row) for row in matrix]

此外，如果我要在其他三个方向(除了右边)移动矩阵，是否有比这三个更有效的方法:

#Left
matrix = [shift(row[::-1])[::-1] for row in matrix]

#Down
matrix = map(list, zip(*[shift(row) for row in map(list, zip(*matrix))]))

#Up
matrix = map(list, zip(*[shift(row[::-1])[::-1] for row in map(list, zip(*matrix))]))

如果重复执行这些移位操作(以及每次更改矩阵中的一个值)，我是否应该跟踪任何事情以提高效率？

编辑

我的功能并不总是有效:

>>> shift([1, 1, 1, 1])
[0, 2, 0, 2]

输出应该是:

[0, 0, 2, 2]

更多预期的输入和输出:

[1, 1, 1]             --> [0, 1, 2]
[1, 2, 2, 3, 5, 5, 2] --> [0, 0, 1, 4, 3, 10, 2]

编辑 2

不一定要向右移动，也可以向右移动。

Answer 1

这是否更有效取决于timeit:

def streaming_sum(sequence):
    values = reversed(sequence)
    last = next(values)
    for value in values:
        if value == last:
            yield last + value
            last = 0
        else:
            yield last
            last = value
    yield last


def shift(sequence):
    length = len(sequence)
    reduced = list(reversed(filter(None, streaming_sum(sequence))))
    return [0] * (length - len(reduced)) + reduced


for sequence, expected in [
    ([0, 0, 1, 0], [0, 0, 0, 1]),
    ([1, 1, 0, 0], [0, 0, 0, 2]),
    ([2, 0, 1, 0], [0, 0, 2, 1]),
    ([1, 1, 1, 1], [0, 0, 2, 2]),
    ([1, 1, 1], [0, 1, 2]),
    ([1, 2, 2, 3, 5, 5, 2], [0, 0, 1, 4, 3, 10, 2]),
]:
    actual = shift(sequence)
    assert actual == expected, (actual, expected)