java - programacion - Ordenar en una cadena que puede contener un número
manual de programacion android pdf (17)
Necesito escribir una clase Java Comparator que compare cadenas, sin embargo con un giro. Si las dos cadenas que está comparando son las mismas al principio y al final de la cadena, son las mismas, y la parte central que difiere es un entero, luego se compara según los valores numéricos de esos enteros. Por ejemplo, quiero que las siguientes cadenas terminen para que se muestren:
- aaa
- bbb 3 ccc
- bbb 12 ccc
- ccc 11
- ddd
- eee 3 ddd jpeg2000 eee
- eee 12 ddd jpeg2000 eee
Como puede ver, puede haber otros enteros en la cadena, por lo que no puedo usar expresiones regulares para dividir cualquier número entero. Estoy pensando en caminar las cuerdas desde el principio hasta que encuentre un poco que no concuerde, luego caminar desde el final hasta encontrar un poco que no coincida, y luego comparar el bit en el medio con el expresión regular "[0-9] +", y si se compara, hacer una comparación numérica, de lo contrario hacer una comparación léxica.
¿Hay una mejor manera?
Actualización No creo que pueda garantizar que los otros números en la cadena, los que pueden coincidir, no tengan espacios a su alrededor, o que los que difieren tengan espacios.
Antes de descubrir este hilo, implementé una solución similar en JavaScript. Tal vez mi estrategia te encuentre bien, a pesar de la sintaxis diferente. De forma similar a la anterior, analizo las dos cadenas que se comparan y las divido en matrices, dividiendo las cadenas en números continuos.
...
var regex = /(/d+)/g,
str1Components = str1.split(regex),
str2Components = str2.split(regex),
...
Es decir, ''hello22goodbye 33'' => [''hola'', 22, ''adiós'', 33]; Por lo tanto, puede recorrer los elementos de los arreglos por pares entre string1 y string2, hacer algún tipo de coerción (como, ¿este elemento es realmente un número?), Y comparar mientras camina.
Ejemplo de trabajo aquí: http://jsfiddle.net/F46s6/3/
Tenga en cuenta que actualmente solo soporto tipos enteros, aunque manejar valores decimales no sería una modificación demasiado dura.
Aunque la pregunta fue sobre una solución java, para cualquiera que quiera una solución scala:
object Alphanum {
private[this] val regex = "((?<=[0-9])(?=[^0-9]))|((?<=[^0-9])(?=[0-9]))"
private[this] val alphaNum: Ordering[String] = Ordering.fromLessThan((ss1: String, ss2: String) => (ss1, ss2) match {
case (sss1, sss2) if sss1.matches("[0-9]+") && sss2.matches("[0-9]+") => sss1.toLong < sss2.toLong
case (sss1, sss2) => sss1 < sss2
})
def ordering: Ordering[String] = Ordering.fromLessThan((s1: String, s2: String) => {
import Ordering.Implicits.infixOrderingOps
implicit val ord: Ordering[List[String]] = Ordering.Implicits.seqDerivedOrdering(alphaNum)
s1.split(regex).toList < s2.split(regex).toList
})
}
Creo que tendrás que hacer la comparación en una forma de personaje por personaje. Coge un personaje, si es un personaje numérico, sigue agarrando, luego reensambla a los personajes en una sola cadena numérica y conviértelo en un int . Repite en la otra cuerda, y solo entonces haz la comparación.
Divida la cadena en series de letras y números, de modo que "foo 12 bar" se convierta en la lista ("foo", 12, "barra"), luego use la lista como la clave de clasificación. De esta forma, los números se ordenarán en orden numérico, no alfabético.
En Linux, glibc proporciona strverscmp (), también está disponible desde gnulib para la portabilidad. Sin embargo, la clasificación verdaderamente "humana" tiene muchos otros caprichos como "The Beatles" ordenados como "Beatles, The". No hay una solución simple a este problema genérico.
En su ejemplo dado, los números que quiere comparar tienen espacios a su alrededor, mientras que los otros números no, ¿por qué una expresión regular no funcionaría?
bbb 12 ccc
vs.
eee 12 ddd jpeg2000 eee
Ian Griffiths de Microsoft tiene una implementación de C # a la que llama Natural Sorting . ¡Portar a Java debería ser bastante fácil, más fácil que hacerlo con C de todos modos!
ACTUALIZACIÓN: Parece que hay un ejemplo de Java en eekboom que hace esto, consulte "compareNatural" y utilícelo como su comparador.
La implementación que propongo aquí es simple y eficiente. No asigna ninguna memoria adicional, directa o indirectamente, mediante el uso de expresiones regulares o métodos como subserie (), split (), toCharArray (), etc.
Esta implementación va primero a través de ambas cadenas para buscar los primeros caracteres que son diferentes, a máxima velocidad, sin hacer ningún procesamiento especial durante esto. La comparación de números específicos se activa solo cuando estos caracteres son ambos dígitos. Un efecto secundario de esta implementación es que un dígito se considera como mayor que otras letras, al contrario del orden lexicográfico predeterminado.
public static final int compareNatural (String s1, String s2)
{
// Skip all identical characters
int len1 = s1.length();
int len2 = s2.length();
int i;
char c1, c2;
for (i = 0, c1 = 0, c2 = 0; (i < len1) && (i < len2) && (c1 = s1.charAt(i)) == (c2 = s2.charAt(i)); i++);
// Check end of string
if (c1 == c2)
return(len1 - len2);
// Check digit in first string
if (Character.isDigit(c1))
{
// Check digit only in first string
if (!Character.isDigit(c2))
return(1);
// Scan all integer digits
int x1, x2;
for (x1 = i + 1; (x1 < len1) && Character.isDigit(s1.charAt(x1)); x1++);
for (x2 = i + 1; (x2 < len2) && Character.isDigit(s2.charAt(x2)); x2++);
// Longer integer wins, first digit otherwise
return(x2 == x1 ? c1 - c2 : x1 - x2);
}
// Check digit only in second string
if (Character.isDigit(c2))
return(-1);
// No digits
return(c1 - c2);
}
Me doy cuenta de que estás en Java, pero puedes echar un vistazo a cómo funciona StrCmpLogicalW. Es lo que Explorer usa para clasificar nombres de archivo en Windows. Puede ver la implementación de WINE here .
Mis 2 centavos. Me está funcionando bien. Lo uso principalmente para nombres de archivos.
private final boolean isDigit(char ch)
{
return ch >= 48 && ch <= 57;
}
private int compareNumericalString(String s1,String s2){
int s1Counter=0;
int s2Counter=0;
while(true){
if(s1Counter>=s1.length()){
break;
}
if(s2Counter>=s2.length()){
break;
}
char currentChar1=s1.charAt(s1Counter++);
char currentChar2=s2.charAt(s2Counter++);
if(isDigit(currentChar1) &&isDigit(currentChar2)){
String digitString1=""+currentChar1;
String digitString2=""+currentChar2;
while(true){
if(s1Counter>=s1.length()){
break;
}
if(s2Counter>=s2.length()){
break;
}
if(isDigit(s1.charAt(s1Counter))){
digitString1+=s1.charAt(s1Counter);
s1Counter++;
}
if(isDigit(s2.charAt(s2Counter))){
digitString2+=s2.charAt(s2Counter);
s2Counter++;
}
if((!isDigit(s1.charAt(s1Counter))) && (!isDigit(s2.charAt(s2Counter)))){
currentChar1=s1.charAt(s1Counter);
currentChar2=s2.charAt(s2Counter);
break;
}
}
if(!digitString1.equals(digitString2)){
return Integer.parseInt(digitString1)-Integer.parseInt(digitString2);
}
}
if(currentChar1!=currentChar2){
return currentChar1-currentChar2;
}
}
return s1.compareTo(s2);
}
Pequeño desafío interesante, disfruté resolviéndolo.
Aquí está mi opinión sobre el problema:
String[] strs =
{
"eee 5 ddd jpeg2001 eee",
"eee 123 ddd jpeg2000 eee",
"ddd",
"aaa 5 yy 6",
"ccc 555",
"bbb 3 ccc",
"bbb 9 a",
"",
"eee 4 ddd jpeg2001 eee",
"ccc 11",
"bbb 12 ccc",
"aaa 5 yy 22",
"aaa",
"eee 3 ddd jpeg2000 eee",
"ccc 5",
};
Pattern splitter = Pattern.compile("(//d+|//D+)");
public class InternalNumberComparator implements Comparator
{
public int compare(Object o1, Object o2)
{
// I deliberately use the Java 1.4 syntax,
// all this can be improved with 1.5''s generics
String s1 = (String)o1, s2 = (String)o2;
// We split each string as runs of number/non-number strings
ArrayList sa1 = split(s1);
ArrayList sa2 = split(s2);
// Nothing or different structure
if (sa1.size() == 0 || sa1.size() != sa2.size())
{
// Just compare the original strings
return s1.compareTo(s2);
}
int i = 0;
String si1 = "";
String si2 = "";
// Compare beginning of string
for (; i < sa1.size(); i++)
{
si1 = (String)sa1.get(i);
si2 = (String)sa2.get(i);
if (!si1.equals(si2))
break; // Until we find a difference
}
// No difference found?
if (i == sa1.size())
return 0; // Same strings!
// Try to convert the different run of characters to number
int val1, val2;
try
{
val1 = Integer.parseInt(si1);
val2 = Integer.parseInt(si2);
}
catch (NumberFormatException e)
{
return s1.compareTo(s2); // Strings differ on a non-number
}
// Compare remainder of string
for (i++; i < sa1.size(); i++)
{
si1 = (String)sa1.get(i);
si2 = (String)sa2.get(i);
if (!si1.equals(si2))
{
return s1.compareTo(s2); // Strings differ
}
}
// Here, the strings differ only on a number
return val1 < val2 ? -1 : 1;
}
ArrayList split(String s)
{
ArrayList r = new ArrayList();
Matcher matcher = splitter.matcher(s);
while (matcher.find())
{
String m = matcher.group(1);
r.add(m);
}
return r;
}
}
Arrays.sort(strs, new InternalNumberComparator());
Este algoritmo necesita muchas más pruebas, pero parece comportarse bastante bien.
[EDIT] Agregué algunos comentarios más para ser más claro. Veo que hay muchas más respuestas que cuando comencé a codificar esto ... Pero espero haber proporcionado una buena base de partida y / o algunas ideas.
Respuesta corta: basado en el contexto, no puedo decir si este es solo un código rápido y sucio para uso personal, o una parte clave del último software interno de contabilidad de Goldman Sachs, así que lo abriré diciendo: eww . Ese es un algoritmo de clasificación bastante funky; trate de usar algo un poco menos "retorcido" si puede.
Respuesta larga:
Los dos problemas que inmediatamente se le vienen a la mente en su caso son el rendimiento y la corrección. Informalmente, asegúrese de que sea rápido y asegúrese de que su algoritmo sea un pedido total .
(Por supuesto, si no está ordenando más de 100 elementos, probablemente no tenga en cuenta este párrafo.) El rendimiento importa, ya que la velocidad del comparador será el factor más importante en la velocidad de su tipo (suponiendo que el algoritmo de clasificación es "ideal" a la lista típica). En su caso, la velocidad del comparador dependerá principalmente del tamaño de la cuerda. Las cadenas parecen ser bastante cortas, por lo que probablemente no dominarán tanto como el tamaño de tu lista.
Convirtiendo cada cadena en una tupla string-number-string y luego ordenando esta lista de tuplas, como se sugiere en otra respuesta, fallará en algunos de sus casos, ya que aparentemente tendrá cadenas con múltiples números apareciendo.
El otro problema es la corrección. Específicamente, si el algoritmo que describió permitirá alguna vez A> B> ...> A, su clasificación será no determinista. En tu caso, me temo que podría hacerlo, aunque no puedo probarlo. Considere algunos casos de análisis tales como:
aa 0 aa
aa 23aa
aa 2a3aa
aa 113aa
aa 113 aa
a 1-2 a
a 13 a
a 12 a
a 2-3 a
a 21 a
a 2.3 a
Se me ocurrió una implementación bastante simple en Java usando expresiones regulares:
public static Comparator<String> naturalOrdering() {
final Pattern compile = Pattern.compile("(//d+)|(//D+)");
return (s1, s2) -> {
final Matcher matcher1 = compile.matcher(s1);
final Matcher matcher2 = compile.matcher(s2);
while (true) {
final boolean found1 = matcher1.find();
final boolean found2 = matcher2.find();
if (!found1 || !found2) {
return Boolean.compare(found1, found2);
} else if (!matcher1.group().equals(matcher2.group())) {
if (matcher1.group(1) == null || matcher2.group(1) == null) {
return matcher1.group().compareTo(matcher2.group());
} else {
return Integer.valueOf(matcher1.group(1)).compareTo(Integer.valueOf(matcher2.group(1)));
}
}
}
};
}
Así es como funciona:
final List<String> strings = Arrays.asList("x15", "xa", "y16", "x2a", "y11", "z", "z5", "x2b", "z");
strings.sort(naturalOrdering());
System.out.println(strings);
[x2a, x2b, x15, xa, y11, y16, z, z, z5]
Si está escribiendo una clase de comparación, debe implementar su propio método de comparación que compare dos cadenas carácter por carácter. Este método de comparación debe verificar si se trata de caracteres alfabéticos, caracteres numéricos o tipos mixtos (incluidos los espacios). Tendrá que definir cómo quiere que actúe un tipo mixto, ya sea que los números vengan antes que los caracteres alfabéticos o después, y donde encajen los espacios, etc.
problema interesante, y aquí mi solución propuesta:
import java.util.Collections;
import java.util.Vector;
public class CompareToken implements Comparable<CompareToken>
{
int valN;
String valS;
String repr;
public String toString() {
return repr;
}
public CompareToken(String s) {
int l = 0;
char data[] = new char[s.length()];
repr = s;
valN = 0;
for (char c : s.toCharArray()) {
if(Character.isDigit(c))
valN = valN * 10 + (c - ''0'');
else
data[l++] = c;
}
valS = new String(data, 0, l);
}
public int compareTo(CompareToken b) {
int r = valS.compareTo(b.valS);
if (r != 0)
return r;
return valN - b.valN;
}
public static void main(String [] args) {
String [] strings = {
"aaa",
"bbb3ccc",
"bbb12ccc",
"ccc 11",
"ddd",
"eee3dddjpeg2000eee",
"eee12dddjpeg2000eee"
};
Vector<CompareToken> data = new Vector<CompareToken>();
for(String s : strings)
data.add(new CompareToken(s));
Collections.shuffle(data);
Collections.sort(data);
for (CompareToken c : data)
System.out.println ("" + c);
}
}
Alphanum algrothim es agradable, pero no coincide con los requisitos para un proyecto en el que estoy trabajando. Necesito poder ordenar los números negativos y decimales correctamente. Aquí está la implementación que surgió. Cualquier comentario sería muy apreciado.
public class StringAsNumberComparator implements Comparator<String> {
public static final Pattern NUMBER_PATTERN = Pattern.compile("(//-?//d+//.//d+)|(//-?//.//d+)|(//-?//d+)");
/**
* Splits strings into parts sorting each instance of a number as a number if there is
* a matching number in the other String.
*
* For example A1B, A2B, A11B, A11B1, A11B2, A11B11 will be sorted in that order instead
* of alphabetically which will sort A1B and A11B together.
*/
public int compare(String str1, String str2) {
if(str1 == null || str2 == null) {
return 0;
}
List<String> split1 = split(str1);
List<String> split2 = split(str2);
int diff = 0;
for(int i = 0; diff == 0 && i < split1.size() && i < split2.size(); i++) {
String token1 = split1.get(i);
String token2 = split2.get(i);
if((NUMBER_PATTERN.matcher(token1).matches() && NUMBER_PATTERN.matcher(token2).matches()) {
diff = (int) Math.signum(Double.parseDouble(token1) - Double.parseDouble(token2));
} else {
diff = token1.compareToIgnoreCase(token2);
}
}
if(diff != 0) {
return diff;
} else {
return split1.size() - split2.size();
}
}
/**
* Splits a string into strings and number tokens.
*/
private List<String> split(String s) {
List<String> list = new ArrayList<String>();
try (Scanner scanner = new Scanner(s)) {
int index = 0;
String num = null;
while ((num = scanner.findInLine(NUMBER_PATTERN)) != null) {
int indexOfNumber = s.indexOf(num, index);
if (indexOfNumber > index) {
list.add(s.substring(index, indexOfNumber));
}
list.add(num);
index = indexOfNumber + num.length();
}
if (index < s.length()) {
list.add(s.substring(index));
}
}
return list;
}
}
PD. Quería usar el método java.lang.String.split () y usar "lookahead / lookbehind" para conservar los tokens, pero no pude hacerlo funcionar con la expresión regular que estaba usando.
Desde el sitio web
"La gente ordena las cadenas con números de manera diferente que el software. La mayoría de los algoritmos de clasificación comparan los valores ASCII, lo que produce un orden que no es coherente con la lógica humana. Aquí se explica cómo solucionarlo".
Editar: Aquí hay un enlace a la implementación de Java Comparator desde ese sitio.