我有一份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]
,则(i1, j1)
在(i2, j2)
iff 之前出现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))
我认为这种方法不好。我们可以做得更好吗?
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();
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句