Algoritmo semplice per calcolare un valore ordinabile da una stringa

0

Vorrei calcolare un valore numerico per le stringhe contenenti solo /[a-z0-9]/i (ignora maiuscole / minuscole). Più tardi, voglio usare questo valore per ordinare le righe. Per questo post, sto ignorando anche il numero.

Il mio pensiero era, che posso definire un alfabeto come 0123456789a...z e calcolare un valore ordinabile sommando gli indici di ogni carattere trovato, come questo (pseudo codice ma dovrebbe funzionare in ES6):

const alpha = 'abcdefghijklmnopqrstuvwxzy'.split('');

function easySort(myString) {
  myString = myString.toLowerCase();
  let sortableValue = 0;
  for (let i = 0; i < myString.length; i++) {
    sortableValue += alpha.indexOf(myString.charAt(i)) + 1; // to avoid 0
  }
  return sortableValue;
};

Semplice esempio (assumendo gli indici a = 1, b = 2, ..):

let arr = ['abc', 'ab', 'abd', 'aba'];
let ordered = arr.sort((a, b) => easySort(a) - easySort(b));
// ordered now is ['ab', 'aba', 'abc', 'abd']

La domanda è, è un buon approccio per le stringhe di quell'alfabeto? Ci sono casi in cui questo non funzionerebbe nel modo previsto?

Non sto chiedendo miglioramenti del codice, ma piuttosto l'algoritmo e se può comportarsi inaspettatamente per determinati valori (per questo non intendo valori illegali).

    
posta user654123 29.03.2017 - 13:40
fonte

1 risposta

5

È un approccio sbagliato perché non funziona. Questa è fondamentalmente una questione di dimensioni del dominio.

Anche con solo 36 possibili caratteri, ci sono ampiamente più stringhe possibili che probabilmente si adattano al tipo intero di tua scelta. Ciò significa che pre-calcolare un indice di ordinamento non funziona; puoi sempre ottenere collisioni tra stringhe che dovrebbero essere ordinate in modo diverso ma che il tuo indice afferma di essere uguale.

Pertanto, le stringhe, anche da un set di caratteri limitato, sono il loro indice di ordinamento e nessun indice di ordinamento più piccolo può essere corretto. Se non ti interessa l'ordinamento esatto, basta usare un prefisso a dimensione fissa di ogni stringa invece di una trasformazione complicata.

    
risposta data 29.03.2017 - 13:47
fonte

Leggi altre domande sui tag