La funzione sorted() di python è garantita per essere stabile?

Il documentation non garantisce che. C'è qualche altro posto che è documentato?La funzione sorted() di python è garantita per essere stabile?

Immagino che potrebbe essere stabile poiché il metodo di ordinamento sugli elenchi è guaranteed to be stable (Punto 9 Note: "A partire da Python 2.3, il metodo sort() è stabile") e ordinato è funzionalmente simile. Tuttavia, non sono in grado di trovare alcuna fonte definitiva che lo dica.

Scopo: Ho bisogno di ordinare in base a una chiave primaria e anche una chiave secondaria nei casi in cui la chiave primaria è uguale in entrambi i record. Se sort() è garantito stabile, posso ordinare sulla chiave secondaria, quindi ordinare sulla chiave primaria e ottenere il risultato che mi serve.

PS: Per evitare qualsiasi confusione, sto usando stabile nel senso di "un ordinamento è stabile se garantisce di non modificare l'ordine relativo di elementi che si confrontano uguali".

fonte

2009-12-16 sundar

Sì, l'intenzione del manuale è infatti quella di garantire che sorted sia stabile e che utilizzi esattamente lo stesso algoritmo del metodo sort. Mi rendo conto che i documenti non sono al 100% chiari su questa identità; le patch per i doc sono sempre accettate felicemente!

fonte

2009-12-16 15:36:08

Ho scoperto che se sto ordinando le tuple o le liste, ogni volta che le chiavi di ordinamento "primarie" sono uguali, finisce con l'ordinamento per il tasto "secondario". Ad esempio, 'sorted ([(1, 2), (1, 1)])' restituisce '[(1, 1), (1, 2)]' invece di restituire l'input originale nella stessa sequenza/ordine. Non dovrebbe la garanzia di stabilità significa che dovrebbe restituire l'input originale '[(1, 2), (1, 1)]'? In tal caso, devi essere esplicito e dire 'sort ([(1, 2), (1, 1)], key = lambda t: t [0])' – ray

Non è questo che ci si aspetta in questo caso? Python confronterà le tuple attraverso tutti gli elementi per impostazione predefinita, non solo la prima "primaria". Se vuoi solo ordinare sul primo elemento, puoi passare esplicitamente il parametro 'key'. –

Il "What's New" docs for Python 2.4 rende effettivamente il punto che sort() prima crea un elenco, quindi chiama sort() su di esso, fornendo la garanzia di cui hai bisogno anche se non nei documenti "ufficiali". Potresti anche controllare la fonte, se sei davvero preoccupato.

fonte

2009-12-16 15:38:39

Puoi indicare dove dice così? Dice sort() "funziona come il posto list.sort()" e "una copia appena formata è ordinata", ma non la vedo dicendo che usa internamente sort(). – sundar

La "copia" che si forma è una lista (questo è ciò che si ottiene come valore di ritorno), e .sort() viene chiamato su quell'elenco prima di ritornare. QED. No, non è una prova inattaccabile, ma fino a quando Python avrà uno standard ufficiale non lo otterrete. –

Sono stable. Sebbene non sia necessario sapere se l'ordinamento e l'ordinamento sono stabili, perché non è necessario ordinare in due passaggi quando si hanno più chiavi.

Per esempio, se si desidera ordinare gli oggetti in base alle loro last_name, first_name attributi, è possibile:

sorted_list= sorted(
    your_sequence_of_items, 
    key= lambda item: (item.last_name, item.first_name))

approfittando di confronto tuple.

Questa risposta, così com'è, copre la domanda originale. Per ulteriori domande relative allo smistamento, c'è lo Python Sorting How-To.

fonte

2009-12-28 22:42:14 tzot

Questo può avere effetto indesiderato se si desidera invertire l'ordinamento. Ad esempio, quando si ordinano i prodotti, è possibile ordinare prima il punteggio (ordine crescente) e poi il prezzo (anche in ordine crescente). Se si capovolge questo, si desidera ordinare la classificazione in ordine decrescente ma sul prezzo in ordine crescente. Questo non funziona con questa soluzione. –

@RemcoWendt: non c'era alcun requisito per quello che descrivi. In ogni caso, considera 'chiave = oggetto lambda: (-item.rating, item.price)' o fornendo un 'cmp' invece di un argomento' key'. Non sono ancora sicuro dello scopo del tuo commento, comunque. – tzot

In effetti non era un requisito, ma voleva sottolineare questa sottile differenza quando altre persone lo leggevano e facevano una scelta tra la tua soluzione o la funzione di ordinamento stabile di Python. –

probabilmente è cambiato nel frattempo, ma la documentazione corrente di sorted garantuees esplicitamente:

il built-in sorted() funzionamento è garantito per essere stabile. Un ordinamento è stabile se garantisce di non modificare l'ordine relativo di elementi che si equivalgono - questo è utile per l'ordinamento in più passaggi (ad esempio, ordina per dipartimento, quindi per grado di stipendio).

fonte

2017-05-16 22:49:52 MSeifert

La funzione sorted() di python è garantita per essere stabile?

risposta

Problemi correlati