Ordinamento di una matrice di numeri con posizioni decimali

Il tuo problema è che i tuoi "numeri" non hanno posizioni decimali. Hai una stringa che consiste di due numeri interi separati da . . Analizzali come due numeri interi e scrivi un comparatore personalizzato. L'algoritmo di ordinamento può rimanere lo stesso, è sufficiente passare il confronto.

In C # un simile comparatore potrebbe sembrare simile a questo:

void Test()
{
    var data=new string[]{ "1.34", "1.15", "1.1", "1.2", "1.26", "1.10", "1.20", "1.17" };
    Array.Sort(data, VersionComparer);
    data.Dump();
}

static int VersionComparer(string s1, string s2)
{
    List<int> parts1 = s1.Split('.').Select(int.Parse).ToList();
    List<int> parts2 = s2.Split('.').Select(int.Parse).ToList();

    while(parts1.Count < parts2.Count)
        parts1.Add(0);
    while(parts2.Count < parts1.Count)
        parts2.Add(0);

    for(int i = 0; i < parts1.Count; i++)
    {
         if(parts1[i] < parts2[i])
             return -1;
         if(parts1[i] > parts2[i])
             return +1;
    }
    return 0;
}

Un po 'di nitpicking: se alcuni valori hanno cifre più significative di altri, allora quello che hai è non fluttuante. Le stringhe devono essere interpretate come float , ma devi interpretarle ogni volta che le accedi, ed è proprio questo il problema qui.

Fondamentalmente hai due opzioni. O si utilizza un algoritmo di ordinamento standard e si programma la routine di confronto in modo che esegua Float.parseFloat() prima di calcolare qualsiasi cosa con i suoi argomenti - oppure si esegue l'analisi una volta per tutte in un passaggio separato e si memorizzano i valori numerici da qualche parte, quindi non devi farlo di nuovo.

Ovviamente, quale soluzione è migliore dipende da quanto spesso verrà chiamato il comparatore. Se la lista è in ordine casuale, la maggior parte dei valori verrà probabilmente toccata più di una volta durante l'ordinamento, quindi è consigliabile pre-calcolare i valori che si desidera confrontare. Ma se la lista tende ad essere quasi ordinata o se l'analisi del float è troppo economica per preoccuparsi (rispetto allo sforzo di programmazione di aggiungere una fase di trasformazione), è meglio farlo al volo durante ogni confronto.

Come sempre, quale sia il migliore in generale non si può rispondere, e quale è meglio nel tuo caso non si può rispondere senza profilare entrambe le soluzioni. Mai dare per scontato - misura sempre.

A seconda della grandezza di un array con cui stai lavorando potresti desiderare di applicare il modello di programmazione funzionale "decorare un tipo non decorato" (che è una forma di Memoizzazione ).

Dividere costantemente la stringa in parti ottenendo la sua lunghezza e poi scartare i dati può essere inefficiente, dopotutto, la stringa non cambia mentre la stai ordinando, devi solo farlo una volta.

In perl, questa è conosciuta come Trasformata di Schwartzian - il codice per questo assomiglia a:

#!/usr/bin/perl
use strict;
my @data = qw ( 1.34 1.15 1.1 1.2 1.26 1.10 1.20 1.17 );
my @sorted =
    map { $_->[0] }
    sort { $a->[1] <=> $b->[1] or $a->[2] <=> $b->[2]  }
    map {
      my @l = split(/\./);
      [$_, length($l[1]), $l[1]] }
    @data;
print join(',', @sorted),"\n";

Il trucco è che il cambio da "1.15" a ["1.15", 2, 15] viene eseguito una sola volta, e quindi l'ordinamento sta lavorando su quei valori. Per gli array di piccole dimensioni si tratta di un miglioramento minore nelle prestazioni. Per i grandi array, può essere molto significativo.

Nelle lingue che mancano del "lanciare semplicemente le cose in un array e ordinarle comunque", questo diventa un po 'più complesso. Dovresti creare un oggetto con i dati originali e le parti componenti e l'ordinabile. Questo è leggermente più facile da usare perché potresti metterlo nel costruttore.

In Java, si potrebbe usare il seguente approccio:

public class DecimalSortable implements Comparable<DecimalSortable> {
    private int len;
    private int dec;
    private String data;
    public DecimalSortable(String data) {
        this.data = data;
        String[] array = data.split("\.");
        len = array[1].length();
        dec = Integer.parseInt(array[1]);
    }

    @Override
    public int compareTo(DecimalSortable o) {
        int rv = Integer.compare(len, o.len);
        if(rv == 0) {
            rv = Integer.compare(dec, o.dec);
        }
        return rv;
    }

    public String getData() {
        return data;
    }
}

Notare la singola chiamata per dividere ed estrarre i valori che verranno successivamente ordinati. Sì, è un po 'più sovraccarico rispetto ai linguaggi più dinamici, ma ti viene l'idea di come funziona e come evitare chiamate ripetute alla divisione (e la relativa creazione di nuovi oggetti String per ciascun confronto).