1

最近、リスト内の上位 n 個の要素を見つけて、値と位置の両方を返すコードを書くように依頼されました。

これより (実行時間の点で) 速くできますか?

def highest(L, n):
    return sorted(enumerate(L), reverse=True, key=lambda x: x[1])[:n]

if __name__ == '__main__':

    M = [102, 56, 2355, 3, 25, 78, 19, 25, 1002, -54, 0, 23, -1]
    r = highest(M,5)
    print r  #[(2, 2355), (8, 1002), (0, 102), (5, 78), (1, 56)]
4

2 に答える 2

9

nリストの長さに比べて小さい場合は、リストheapq.nlargest全体をソートするよりも高速です。また、より読みやすくなっています。

def highest(L, n):
    return heapq.nlargest(n, enumerate(L), key=operator.itemgetter(1))

>>> M = [102, 56, 2355, 3, 25, 78, 19, 25, 1002, -54, 0, 23, -1]
>>> highest(M,5)
[(2, 2355), (8, 1002), (0, 102), (5, 78), (1, 56)]

これは、並べ替えの O(NlogN) とは対照的に、O(N + nlogn) で機能します。ここNで、 はリストの長さであり、n返されるアイテムの数です。

于 2013-02-28T13:30:04.467 に答える
1

加えて、kth_smallestパンダで使用して O(N) の値を見つけることができます。

import numpy as np
import pandas as pd
a = np.array([102, 56, 2355, 3, 25, 78, 19, 25, 1002, -54, 0, 23, -1.0])
pd.algos.kth_smallest(a, len(a)-5)

コードはここにあります：

https://github.com/pydata/pandas/blob/master/pandas/algos.pyx#L653

注:kth_smallestは値のみを返しますが、配列をスキャンして位置を見つけることができます。

于 2013-02-28T14:05:50.893 に答える