Значения Argsorting в списке списков
У меня есть список списков 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))
Я думаю, что этот подход не очень хорош. Мы можем сделать лучше?
Ответы
Ответ 1
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)]
Спектакль
По многочисленным просьбам, добавляя некоторые тайминги и сюжет.
![enter image description here]()
Из графика видно, что вызов 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();
Ответ 2
Вы можете сделать триплеты (x, i, j), отсортировать эти триплеты, а затем извлечь индексы (i, j). Это работает, потому что триплеты содержат всю информацию, необходимую для сортировки и для включения в окончательный список, в порядке, необходимом для сортировки. (Это называется идиомой "Украсить-Сортировать-Undecorate", связанной с преобразованием Шварца - Hat-tip для @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)]
Ответ 3
Просто потому, что @jpp развлекается:
from itertools import chain
import numpy as np
def agn(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]
Сроки:
Тест 1:
Сравнение с самым быстрым методом от @coldspeed:
In [1]: import numpy as np
In [2]: print(np.__version__)
1.13.3
In [3]: from itertools import chain
In [4]: import sys
In [5]: print(sys.version)
3.5.5 |Anaconda, Inc.| (default, Mar 12 2018, 16:25:05)
[GCC 4.2.1 Compatible Clang 4.0.1 (tags/RELEASE_401/final)]
In [6]: A = [[1],[0, 0, 0, 1, 1, 3], [1, 2], [1, 1, 2, 4]] * 10000
In [7]: %timeit np.array(tuple((i, j) for i, r in enumerate(A) for j, _ in enumerate(r)))[np.argsort(np.fromit
...: er(chain(*A), dtype=np.int))]
89.4 ms ± 718 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [8]: %timeit B = [(i, j) for i, x in enumerate(A) for j, _ in enumerate(x)]; B.sort(key=lambda ix: A[ix[0]]
...: [ix[1]])
93.5 ms ± 1.65 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Тест 2a:
В этом тесте используется один произвольно сгенерированный большой массив A (каждый подсписщик сортируется, потому что именно так выглядит список OP):
In [20]: A = [sorted([random.randint(1, 100) for _ in range(random.randint(1,1000))]) for _ in range(10000)]
In [21]: def agn(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]
...:
In [22]: %timeit agn(A)
3.1 s ± 62.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [23]: %timeit cs1(A)
3.2 s ± 89.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Тест 2.b
Подобно тесту 2.b, но с несортированным массивом A:
In [25]: A = [[random.randint(1, 100) for _ in range(random.randint(1,1000))] for _ in range(10000)]
In [26]: %timeit cs1(A)
4.24 s ± 215 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [27]: %timeit agn(A)
3.44 s ± 49.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Ответ 4
Для удовольствия, здесь метод с помощью numpy библиотеки сторонних разработчиков. Производительность около ~ 10% медленнее, чем решение @coldspeed из-за дорогостоящего шага заполнения.
Кредиты: для этого решения я адаптировал рецепт @Divakar array-from- jagged -list и скопировал дословное многопользовательское решение argsort @AshwiniChaudhary.
import numpy as np
A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]]
def create_array(data):
"""Convert jagged list to numpy array; pad with max_value + 1"""
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):
"""Flatten, argsort, extract indices, then stack into a single array"""
return np.dstack(np.unravel_index(np.argsort(arr.ravel()), arr.shape))[0]
# limit only to number of elements in A
res = apply_argsort(create_array(A))[:sum(map(len, A))]
print(res)
[[0 0]
[0 1]
[1 0]
[2 0]
[2 1]
[1 1]
[2 2]
[0 2]
[2 3]]
