在列表列表中调整值

Question

我有一份A长度列表清单m.每个列表都A包含正数{1, 2, ..., n}.以下是一个例子,其中m = 3和n = 4.

A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]]

我是代表每个数字x中A为一对(i, j),其中A[i][j] = x.我想A按非递减顺序对数字进行排序; 以最低的第一指数打破关系.也就是说,如果A[i1][j1] == A[i2][j2],那么iff (i1, j1)之前.(i2, j2)i1 <= i2

在这个例子中,我想返回对:

(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)

它代表排序的数字

1, 1, 1, 1, 1, 2, 2, 3, 4

我所做的是一种天真的方法,其工作原理如下:

• 首先,我将每个列表排序A.
• 然后我迭代数字{1, 2, ..., n}和列表A并添加对.

码:

for i in range(m): 
    A[i].sort()
S = []
for x in range(1, n+1):
    for i in range(m):
        for j in range(len(A[i])):
            if A[i][j] == x:
                S.append((i, j))

我认为这种方法并不好.我们可以做得更好吗？

Answer 1

您可以制作三元组(x, i, j),对这些三元组进行排序,然后提取索引(i, j).这是有效的,因为三元组包含排序所需的所有信息,并按照排序所需的顺序包含在最终列表中.(这被称为"装饰 - 排序 - 未装饰"成语,与Schwartzian变换相关 - 帽子提示@Morgen的名称和概括以及我解释这种技术的一般性的动机.)这可以结合起来在一个单一的陈述中,但为了清楚起见,我把它分开了.

A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]]

triplets = [(x, i, j) for i, row in enumerate(A) for j, x in enumerate(row)]
pairs = [(i, j) for x, i, j in sorted(triplets)]
print(pairs)

这是打印结果:

[(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)]

Answer 2

list.sort

您可以生成索引列表,然后调用list.sort了key:

B = [(i, j) for i, x in enumerate(A) for j, _ in enumerate(x)]
B.sort(key=lambda ix: A[ix[0]][ix[1]])

print(B)
[(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)]

请注意,在支持函数中的可迭代解包的python-2.x中,您可以sort稍微简化调用:

B.sort(key=lambda (i, j): A[i][j])

sorted

这是上述版本的替代方案,并生成两个列表(一个在内存中sorted然后处理,返回另一个副本).

B = sorted([
       (i, j) for i, x in enumerate(A) for j, _ in enumerate(x)
    ], 
    key=lambda ix: A[ix[0]][ix[1]]
)

print(B)
[(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)]

性能

在流行的需求,添加一些时间和情节.

从图中,我们看到调用list.sort比效率更高sorted.这是因为list.sort执行就地排序,因此创建具有的数据副本没有时间/空间开销sorted.

功能

def cs1(A):
    B = [(i, j) for i, x in enumerate(A) for j, _ in enumerate(x)]
    B.sort(key=lambda ix: A[ix[0]][ix[1]]) 

    return B

def cs2(A):
    return sorted([
           (i, j) for i, x in enumerate(A) for j, _ in enumerate(x)
        ], 
        key=lambda ix: A[ix[0]][ix[1]]
    )

def rorydaulton(A):

    triplets = [(x, i, j) for i, row in enumerate(A) for j, x in enumerate(row)]
    pairs = [(i, j) for x, i, j in sorted(triplets)]

    return pairs

def jpp(A):
    def _create_array(data):
        lens = np.array([len(i) for i in data])
        mask = np.arange(lens.max()) < lens[:,None]
        out = np.full(mask.shape, max(map(max, data))+1, dtype=int)  # Pad with max_value + 1
        out[mask] = np.concatenate(data)
        return out

    def _apply_argsort(arr):
        return np.dstack(np.unravel_index(np.argsort(arr.ravel()), arr.shape))[0]

    return _apply_argsort(_create_array(A))[:sum(map(len, A))]

def agngazer(A):
    idx = np.argsort(np.fromiter(chain(*A), dtype=np.int))
    return np.array(
       tuple((i, j) for i, r in enumerate(A) for j, _ in enumerate(r))
    )[idx]

绩效基准代码

from timeit import timeit
from itertools import chain

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

res = pd.DataFrame(
       index=['cs1', 'cs2', 'rorydaulton', 'jpp', 'agngazer'],
       columns=[10, 50, 100, 500, 1000, 5000, 10000, 50000],
       dtype=float
)

for f in res.index: 
    for c in res.columns:
        l = [[1, 1, 3], [1, 2], [1, 1, 2, 4]] * c
        stmt = '{}(l)'.format(f)
        setp = 'from __main__ import l, {}'.format(f)
        res.at[f, c] = timeit(stmt, setp, number=30)

ax = res.div(res.min()).T.plot(loglog=True) 
ax.set_xlabel("N"); 
ax.set_ylabel("time (relative)");

plt.show();