💾 Archived View for it.omarpolo.com › articoli › ordinamento-e-stabilita.gmi captured on 2022-01-08 at 13:50:24. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Ordinamento e stabilità

Una delle proprietà degli algoritmi per l’ordinamento è la “stabilità”, ovvero come l’algoritmo si comporta quando ci sono degli elementi che vengono considerati “uguali”.

La stabilità non è semplice da capire quando si considerano vettori numerici, che sono il classico esempio da libro di testo, ma diventano abbastanza ovvi quando bisogna ordinare dei dati strutturati.

Consideriamo il caso di ordinare gli articoli dei gemlog, e di avere i seguenti dati iniziali

[;; sito a:
 {:date "2021-08-26", :title "Post A", :site "example.com"}
 {:date "2021-08-26", :title "Post B", :site "example.com"}
 {:date "2021-08-25", :title "Post C", :site "example.com"}

 ;; sito b:
 {:date "2021-08-26", :title "Post D", :site "foobar.io"}
 {:date "2021-08-25", :title "Post E", :site "foobar.io"}
 {:date "2021-08-25", :title "Post F", :site "foobar.io"}]

L'ordinamento ideale, cosa che in questo caso è dettato puramente dal contesto e dall'assunzione che i post con la stessa data dello stesso sito siano già in ordine di pubblicazione, è "A B D C E F". Ma non è l'unico ordinamento possibile, infatti anche "A D B F E C" è tecnicamente valido, ma non ci permette di costruire una buona UI.

Diversi anni fa, stavo discutendo nel laboratorio 2 di informatica con un collega di un corso diverso lo studio degli algoritmi. Mi ricordo che a un certo punto se ne uscì con una frase tipo:

Però a me non importa la differenza tra quicksort, mergesort, bucketsort ecc, voglio fare .sort() e avere i dati ordinati!!

Sul momento non mi era venuto in mente come ribattere, e poi non volevo stare lì a litigare. Immaginavo che un argomento riguardante l'efficienza non l'avrebbe convinto (ad esempio, se i dati sono già ordinati -- o parzialmente ordinati -- allora quicksort non è poi così tanto efficiente). Alla fine sono stato zitto e ho continuato con quello che stavo facendo.

Ieri però, mentre ragionavo su come implementare le subscription su Telescope, mi sono imbattuto in questo problema. qsort(3) non è un algoritmo d'ordinamento stabile quindi devo usare qualcos'altro (per la cronaca, mergesort(3) perché sono pigro).

La morale è, caro il mio Daniele, che lo studio degli algoritmi è importante, è se .sort() funziona per te, è solo fortuna; con altri dati potrebbe non funzionare.

(E diamine a me che non riesco a pensare una risposta in tempi decenti, mi ci sono voluti 4 anni!)

$BlogIt: ordinamento-e-stabilita.gmi,v 1.1 2021/10/20 07:41:40 op Exp $