Algoritmo de clasificación natural

¿Cómo se ordena una serie de cadenas de forma natural en diferentes lenguajes de progtwigción? Publique su implementación y en qué idioma se encuentra en la respuesta.

A continuación, le mostramos cómo puede obtener un comportamiento similar al del explorador en Python:

#!/usr/bin/env python """ >>> items = u'a1 a003 b2 a2 a10 1 10 20 2 c100'.split() >>> items.sort(explorer_cmp) >>> for s in items: ... print s, 1 2 10 20 a1 a2 a003 a10 b2 c100 >>> items.sort(key=natural_key, reverse=True) >>> for s in items: ... print s, c100 b2 a10 a003 a2 a1 20 10 2 1 """ import re def natural_key(astr): """See http://www.codinghorror.com/blog/archives/001018.html""" return [int(s) if s.isdigit() else s for s in re.split(r'(\d+)', astr)] def natural_cmp(a, b): return cmp(natural_key(a), natural_key(b)) try: # use explorer's comparison function if available import ctypes explorer_cmp = ctypes.windll.shlwapi.StrCmpLogicalW except (ImportError, AttributeError): # not on Windows or old python version explorer_cmp = natural_cmp if __name__ == '__main__': import doctest; doctest.testmod() 

Para admitir cadenas Unicode, debe usarse .isdigit() lugar de .isdigit() .

.isdigit() también puede fallar (valor de retorno que no es aceptado por int() ) para una cadena de bytes en Python 2 en algunas configuraciones regionales, por ejemplo, ‘\ xb2’ (‘²’) en la configuración regional cp1252 en Windows .

JavaScript

 Array.prototype.alphanumSort = function(caseInsensitive) { for (var z = 0, t; t = this[z]; z++) { this[z] = [], x = 0, y = -1, n = 0, i, j; while (i = (j = t.charAt(x++)).charCodeAt(0)) { var m = (i == 46 || (i >=48 && i <= 57)); if (m !== n) { this[z][++y] = ""; n = m; } this[z][y] += j; } } this.sort(function(a, b) { for (var x = 0, aa, bb; (aa = a[x]) && (bb = b[x]); x++) { if (caseInsensitive) { aa = aa.toLowerCase(); bb = bb.toLowerCase(); } if (aa !== bb) { var c = Number(aa), d = Number(bb); if (c == aa && d == bb) { return c - d; } else return (aa > bb) ? 1 : -1; } } return a.length - b.length; }); for (var z = 0; z < this.length; z++) this[z] = this[z].join(""); } 

Fuente

Aquí hay una limpieza del código en el artículo al que se vincula la pregunta:

 def sorted_nicely(strings): "Sort strings the way humans are said to expect." return sorted(strings, key=natural_sort_key) def natural_sort_key(key): import re return [int(t) if t.isdigit() else t for t in re.split(r'(\d+)', key)] 

Pero en realidad no he tenido ocasión de ordenar nada de esta manera.

Para MySQL, personalmente utilizo el código de un módulo de Drupal, que está disponible en hhttp: //drupalcode.org/project/natsort.git/blob/refs/heads/5.x-1.x: /natsort.install.mysql

Básicamente, ejecutas el script SQL publicado para crear funciones y luego utilizas ORDER BY natsort_canon(field_name, 'natural')

Aquí hay un archivo léame sobre la función: http://drupalcode.org/project/natsort.git/blob/refs/heads/5.x-1.x:/README.txt

Si el OP está preguntando sobre expresiones de ordenación idomáticas, entonces no todos los lenguajes tienen una expresión natural incorporada. Para c, iría a y usaría qsort . Algo en las líneas de:

 /* non-functional mess deleted */ 

para ordenar los argumentos en orden léxico Lamentablemente, este modismo es bastante difícil de analizar para aquellos que no utilizan las formas de c.


Adecuadamente castigado por el voto a favor, de hecho leí el artículo vinculado. Mea culpa.

En cualquier caso, el código original no funcionó, excepto en el caso único que probé. Maldita sea. Plain vanilla c no tiene esta función, ni está en ninguna de las bibliotecas habituales.

El código siguiente ordena los argumentos de línea de comando de forma natural como vinculados. Caveat Emptor ya que solo se prueba ligeramente.

 #include  #include  #include  #include  int naturalstrcmp(const char **s1, const char **s2); int main(int argc, char **argv){ /* Sort the command line arguments in place */ qsort(&argv[1],argc-1,sizeof(char*), (int(*)(const void *, const void *))naturalstrcmp); while(--argc){ printf("%s\n",(++argv)[0]); }; } int naturalstrcmp(const char **s1p, const char **s2p){ if ((NULL == s1p) || (NULL == *s1p)) { if ((NULL == s2p) || (NULL == *s2p)) return 0; return 1; }; if ((NULL == s2p) || (NULL == *s2p)) return -1; const char *s1=*s1p; const char *s2=*s2p; do { if (isdigit(s1[0]) && isdigit(s2[0])){ /* Compare numbers as numbers */ int c1 = strspn(s1,"0123456789"); /* Could be more efficient here... */ int c2 = strspn(s2,"0123456789"); if (c1 > c2) { return 1; } else if (c1 < c2) { return -1; }; /* the digit strings have equal length, so compare digit by digit */ while (c1--) { if (s1[0] > s2[0]){ return 1; } else if (s1[0] < s2[0]){ return -1; }; s1++; s2++; }; } else if (s1[0] > s2[0]){ return 1; } else if (s1[0] < s2[0]){ return -1; }; s1++; s2++; } while ( (s1!='\0') || (s2!='\0') ); return 0; } 

Este enfoque es bastante fuerza bruta, pero es simple y probablemente pueda duplicarse en cualquier lenguaje imperativo.

Solo uso StrCmpLogicalW . Hace exactamente lo que Jeff quiere, ya que es la misma API que usa el explorador. Es cierto que no es portátil.

En C ++:

 bool NaturalLess(const wstring &lhs, const wstring &rhs) { return StrCmpLogicalW(lhs.c_str(), rhs.c_str()) < 0; } vector strings; // ... load the strings sort(strings.begin(), strings.end(), &NaturalLess); 

Solo un enlace a un buen trabajo en Common Lisp por Eric Normand:

http://www.lispcast.com/wordpress/2007/12/human-order-sorting/

En C, esta solución maneja correctamente los números con ceros a la izquierda:

 #include  #include  /* like strcmp but compare sequences of digits numerically */ int strcmpbynum(const char *s1, const char *s2) { for (;;) { if (*s2 == '\0') return *s1 != '\0'; else if (*s1 == '\0') return 1; else if (!(isdigit(*s1) && isdigit(*s2))) { if (*s1 != *s2) return (int)*s1 - (int)*s2; else (++s1, ++s2); } else { char *lim1, *lim2; unsigned long n1 = strtoul(s1, &lim1, 10); unsigned long n2 = strtoul(s2, &lim2, 10); if (n1 > n2) return 1; else if (n1 < n2) return -1; s1 = lim1; s2 = lim2; } } } 

Si desea usarlo con qsort , use esta función auxiliar:

 static int compare(const void *p1, const void *p2) { const char * const *ps1 = p1; const char * const *ps2 = p2; return strcmpbynum(*ps1, *ps2); } 

Y puedes hacer algo del orden de

 char *lines = ...; qsort(lines, next, sizeof(lines[0]), compare); 

En C ++ utilizo este código de ejemplo para hacer una ordenación natural. El código requiere la biblioteca de impulso.

Tenga en cuenta que para la mayoría de estas preguntas, puede consultar el Wiki del Código Rosetta . Adapte mi respuesta de la entrada para ordenar enteros.

En el lenguaje de progtwigción de un sistema, hacer algo como esto generalmente va a ser más feo que con un lenguaje de manejo de cadenas especial. Afortunadamente para Ada, la versión más reciente tiene una rutina de biblioteca para este tipo de tareas.

Para Ada 2005, creo que podría hacer algo en las siguientes líneas (advertencia, no comstackdo):

 type String_Array is array(Natural range <>) of Ada.Strings.Unbounded.Unbounded_String; function "<" (L, R : Ada.Strings.Unbounded.Unbounded_String) return boolean is begin --// Natural ordering predicate here. Sorry to cheat in this part, but --// I don't exactly grok the requirement for "natural" ordering. Fill in --// your proper code here. end "<"; procedure Sort is new Ada.Containers.Generic_Array_Sort (Index_Type => Natural; Element_Type => Ada.Strings.Unbounded.Unbounded_String, Array_Type => String_Array ); 

Ejemplo de uso:

  using Ada.Strings.Unbounded; Example : String_Array := (To_Unbounded_String ("Joe"), To_Unbounded_String ("Jim"), To_Unbounded_String ("Jane"), To_Unbounded_String ("Fred"), To_Unbounded_String ("Bertha"), To_Unbounded_String ("Joesphus"), To_Unbounded_String ("Jonesey")); begin Sort (Example); ... end; 

Python, usando itertools:

 def natural_key(s): return tuple( int(''.join(chars)) if isdigit else ''.join(chars) for isdigit, chars in itertools.groupby(s, str.isdigit) ) 

Resultado:

 >>> natural_key('abc-123foo456.xyz') ('abc-', 123, 'foo', 456, '.xyz') 

Clasificación:

 >>> sorted(['1.1.1', '1.10.4', '1.5.0', '42.1.0', '9', 'banana'], key=natural_key) ['1.1.1', '1.5.0', '1.10.4', '9', '42.1.0', 'banana'] 

Mi implementación en Clojure 1.1:

 (ns alphanumeric-sort (:import [java.util.regex Pattern])) (defn comp-alpha-numerical "Compare two strings alphanumerically." [ab] (let [regex (Pattern/compile "[\\d]+|[a-zA-Z]+") sa (re-seq regex a) sb (re-seq regex b)] (loop [seqa sa seqb sb] (let [counta (count seqa) countb (count seqb)] (if-not (not-any? zero? [counta countb]) (- counta countb) (let [c (first seqa) d (first seqb) c1 (read-string c) d1 (read-string d)] (if (every? integer? [c1 d1]) (def result (compare c1 d1)) (def result (compare cd))) (if-not (= 0 result) result (recur (rest seqa) (rest seqb))))))))) (sort comp-alpha-numerical ["a1" "a003" "b2" "a10" "a2" "1" "10" "20" "2" "c100"]) 

Resultado:

(“1” “2” “10” “20” “a1” “a2” “a003” “a10” “b2” “c100”)

Para Tcl, la opción -dict (dictionary) para lsort:

 % lsort -dict {ab 1 c 2 d 13} 1 2 13 abcd 

php tiene una función fácil “natsort” para hacer eso, y yo lo implemento solo:

 ='0'&&$a<='9' ; } function my_nat_func($a,$b){ if(preg_match('/[0-9]/',$a)){ if(preg_match('/[0-9]/',$b)){ $i=0; while(!is_alpha($a[$i])) ++$i; $m = intval(substr($a,$i)); $i=0; while(!is_alpha($b[$i])) ++$i; $n = intval(substr($b,$i)); return $m>$n?1:($m==$n?0:-1); } return 1; }else{ if(preg_match('/[0-9]/',$b)){ return -1; } return $a>$b?1:($a==$b?0:-1); } }