Timsort è generico o specifico di Python?

Question

  

Timsort è un adattivo, stabile,   fusione naturale. Ha soprannaturale   prestazioni su molti tipi di parzialmente   array ordinati (meno di lg (N!)   confronti necessari, e pochi   N-1), ma veloce come il precedente di Python   ibrido campionamento altamente sintonizzato   array casuali.

Hai visto timsort usato al di fuori di CPython? Ha senso?

Answer 1

Sì, ha abbastanza senso usare timsort al di fuori di CPython, in particolare, o Python, in generale.

Al momento è in corso un in atto per sostituire Java & modificato; unisci ordinamento " con timsort e i risultati iniziali sono abbastanza positivi.

Answer 2

L'algoritmo è piuttosto generico, ma i vantaggi sono piuttosto specifici di Python. A differenza della maggior parte delle routine di ordinamento, ciò che interessa a list.sort di Python (che è ciò che usa timsort) è evitare confronti inutili, perché in genere i confronti sono un lotto più costosi dello scambio di oggetti (che è sempre solo un insieme di copie del puntatore) o anche allocare un po 'di memoria aggiuntiva (perché è sempre solo una matrice di puntatori e l'overhead è piccolo rispetto all'overhead medio in qualsiasi operazione Python.)

Se hai vincoli simili, potrebbe essere adatto. Devo ancora vedere qualsiasi altro caso in cui i confronti sono davvero così costosi, però :-)

Answer 3

Non sembra particolarmente familiare, ma "intelligente". le fusioni sono piuttosto comuni nel vasto mondo del software.

Se ha senso, dipende da cosa stai ordinando e dal costo relativo dei confronti rispetto all'allocazione della memoria. Un ordinamento che richiede fino a 2 * N byte di memoria aggiuntiva non sarà una buona scelta in un ambiente limitato dalla memoria.

Answer 4

Risposta ora su Wikipedia : timsort verrà utilizzato in Java 7 che lo ha copiato da Android.

Answer 5

Timsort è anche in Android ora: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort

Answer 6

La descrizione che hai collegato sembra del tutto generale.