Python heapq : How do I sort the heap using nth element of the list of lists?

Python heapq : How do I sort the heap using nth element of the list of lists? – StackOverflow

heapqに拘る理由がよく分からないけど,計算時間を気にするのであれば.

numpyで処理するのが一番速い.10 x 10までなら,

import numpy as np

np_n = np.array(n)
np_n[np.lexsort(np_n.T)]

array([[ 6, 3, 12],
[ 2, 6, 44],
[ 4, 7, 45],
[ 1, 5, 93]])

それ以上なら,見た目はちょっと複雑になるけど,もっと高速な方法.

np_n[np.argsort(np.dot(np_n, np.arange(1, np_n.shape[1]+1)))]

array([[ 6, 3, 12],
[ 2, 6, 44],
[ 4, 7, 45],
[ 1, 5, 93]])

heapq.heapifyで処理しようと思うと,

from heapq import heapify, heappop

q = [[x, y] for y, x in zip(n, list(zip(*n))[2])]
heapify(q)
heappop(q)

[12, [6, 3, 12]]

それよりは,sorted()でソートしたアイテムを渡す方が良い.

a = sorted(n, key=lambda x: x[2])
heappush([], a)
heappop(a)

[6, 3, 12]

%%timeit
sorted(n, key=lambda x: x[2])

2.28 µs ± 131 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%%timeit
np_n[np.lexsort(np_n.T)]

9.3 µs ± 593 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%%timeit
q = [[x, y] for y, x in zip(n, list(zip(*n))[2])]
heapify(q)

3.35 µs ± 195 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%%timeit
a = sorted(n, key=lambda x: x[2])
heappush([], a)

2.71 µs ± 222 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

データ数に応じて,sorted()かnumpyでソートしてからheappushすれば良い.
 
 
 

関連:
Pythonでソート(sorted()/list.sort(), numpy.sort())

2dのnumpy.ndarrayをソートするPythonicな方法

任意の要素だけソートしてそれ以外は元の位置を維持

広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中