Dato un elenco di elementi comparabili n (ad esempio numeri o stringa), l'algoritmo ottimale per trovare l'elemento ordinato i richiede tempo O(n).Statistica dell'ordine in Python
Python implementa in modo nativo le statistiche di orario O(n) per elenchi, dit, serie, ...?
Nessuna delle strutture di dati citate di Python implementa nativamente l'algoritmo di statistica dell'ordine.
In effetti, potrebbe non avere molto senso per i dizionari e gli insiemi, dato che entrambi non fanno ipotesi sull'ordinamento dei suoi elementi. Per gli elenchi, non dovrebbe essere difficile implementare il selection algorithm, che fornisce il tempo di esecuzione O (n).
Se i < < n si può dare un'occhiata a http://docs.python.org/library/heapq.html#heapq.nlargest e http://docs.python.org/library/heapq.html#heapq.nsmallest (il non risolvono il problema, ma sono più veloci di smistamento e prendere l'elemento i-esimo).
Questa non è una soluzione nativa, ma è possibile utilizzare NumPy's partition per trovare il k -a statistica ordine di un elenco in tempo O (n).
import numpy as np
x = [2, 4, 0, 3, 1]
k = 2
print('The k-th order statistic is:', np.partition(np.asarray(x), k)[k])
EDIT: questo presuppone zero indicizzazione, cioè il "statistica ordine zero" di cui sopra è 0.
Questo non è accurato. Dopo il partizionamento, è necessario trovare il massimo. Quindi questo 'np.partition (np.asarray (x), k) [: k] .max()' – piRSquared
@piRSquared, grazie. Penso che tu l'abbia interpretato come 1-indicizzato, quindi ora lo ho chiarito. – Garrett
Il mio punto è che 'np.partition' non sta ordinando. Questo è il punto e perché è meglio. Detto questo, poiché non è ordinato, non vi è alcuna garanzia che la statistica del kth dell'ordine sia nella posizione k. Non mi riferisco a zero o a una indicizzazione basata. Mi riferisco al fatto che a volte la tua soluzione produrrà la risposta sbagliata. Supponiamo che volessi la statistica del quinto ordine da un insieme casuale di numeri interi da 0 a 36. La tua risposta produce '1' con il mio esempio qui:' np.random.seed (0); np.partition (np.random.permutation (np.arange (37)), 5) [4] '. E la risposta dovrebbe essere "4". – piRSquared
Apprezzeremmo un commento dal downvoter e dal closevoter. – Randomblue