Ordenar por una cadena que puede contener un número
https://stackoverflow.com/questions/104599
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Necesito escribir una clase Java Comparator que compare cadenas, aunque con un solo giro.Si las dos cadenas que se comparan son iguales al principio y al final de la cadena y la parte central que difiere es un número entero, entonces compare en función de los valores numéricos de esos números enteros.Por ejemplo, quiero que las siguientes cadenas terminen en el orden en que se muestran:
- aaa
- bbb 3 cc
- bbb 12 cc
- ccc 11
- dddd
- eee 3 ddd jpeg2000 eee
- eee 12 ddd jpeg2000 eee
Como puede ver, puede haber otros números enteros en la cadena, por lo que no puedo usar expresiones regulares para dividir cualquier número entero.Estoy pensando en simplemente recorrer las cuerdas desde el principio hasta encontrar un trozo que no coincida, luego caminar desde el final hasta encontrar un trozo que no coincida, y luego comparar el trozo del medio con el expresión regular "[0-9]+", y si se compara, entonces se hace una comparación numérica; de lo contrario, se hace una comparación léxica.
¿Existe una mejor manera?
Actualizar No creo que pueda garantizar que los otros números en la cadena, los que pueden coincidir, no tengan espacios alrededor, o que los que difieren sí tengan espacios.
Solución
Desde el sitio web
"La gente clasifica las cadenas con números de forma diferente que el software.La mayoría de los algoritmos de clasificación comparan valores ASCII, lo que produce un orden que es inconsistente con la lógica humana.He aquí cómo solucionarlo".
Editar:Aquí hay un enlace al Implementación del comparador Java de ese sitio.
Otros consejos
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.
[EDITAR] Agregué algunos comentarios más para que quede 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.
Ian Griffiths de Microsoft tiene una implementación de C# que él llama Clasificación natural.La migración a Java debería ser bastante fácil, ¡más fácil que desde C de todos modos!
ACTUALIZAR: Parece haber un ejemplo de Java en eekboom que hace esto, vea "compareNatural" y utilícelo como comparador de tipos.
La implementación que propongo aquí es simple y eficiente.No asigna memoria adicional, directa o indirectamente mediante el uso de expresiones regulares o métodos como substring(), split(), toCharArray(), etc.
Esta implementación primero recorre ambas cadenas para buscar los primeros caracteres que sean diferentes, a máxima velocidad, sin realizar 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 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 usa Explorer para ordenar nombres de archivos en Windows.Puedes ver la implementación de WINE. aquí.
Divida la cadena en series de letras y números, de modo que "foo 12 bar" se convierta en la lista ("foo", 12, "bar"), luego use la lista como clave de clasificación.De esta forma los números estarán ordenados en orden numérico, no alfabético.
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]
El Alfanum algogrothim es bueno, pero no cumplía con los requisitos de un proyecto en el que estoy trabajando.Necesito poder ordenar números negativos y decimales correctamente.Aquí está la implementación que se me ocurrió.Cualquier comentario será 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 == str2) return 0;
else if(str1 == null) return 1;
else if(str2 == null) return -1;
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.
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);
}
}
Antes de descubrir este hilo, implementé una solución similar en javascript.Quizás mi estrategia te encuentre bien, a pesar de la diferente sintaxis.De manera similar a lo 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, 'hola22adiós 33' => ['hola', 22, 'adiós', 33];Por lo tanto, puede recorrer los elementos de las matrices en pares entre cadena1 y cadena2, realizar alguna coerción de tipo (por ejemplo, ¿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 admito tipos de números enteros, aunque manejar valores decimales no sería una modificación demasiado difícil.
Mis 2 centavos. Está funcionando bien para mí.Lo estoy usando 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);
}
Creo que tendrás que hacer la comparación personaje por personaje.Tome un carácter, si es un carácter numérico, siga tomándolo, luego vuelva a ensamblar los caracteres en una sola cadena numérica y conviértalo en un int.Repita en la otra cuerda y solo entonces haga la comparación.
Respuesta corta:Según el contexto, no puedo decir si se trata simplemente de un código rápido y sucio para uso personal, o una parte clave del último software de contabilidad interna de Goldman Sachs, así que comenzaré diciendo:eww.Es un algoritmo de clasificación bastante original;Intenta usar algo un poco menos "retorcido" si puedes.
Respuesta larga:
Las dos cuestiones que inmediatamente me vienen a la mente en su caso son el rendimiento y la corrección.De manera informal, asegúrese de que sea rápido y asegúrese de que su algoritmo sea un pedido total.
(Por supuesto, si no está clasificando más de 100 elementos, probablemente pueda ignorar este párrafo). El rendimiento importa, ya que la velocidad del comparador será el factor más importante en la velocidad de su clasificación (suponiendo que el algoritmo de clasificación sea "ideal" a la lista típica).En tu 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 su lista.
Convertir cada cadena en una tupla cadena-número-cadena y luego ordenar esta lista de tuplas, como se sugiere en otra respuesta, fallará en algunos de sus casos, ya que aparentemente aparecerán cadenas con múltiples números.
El otro problema es la corrección.Específicamente, si el algoritmo que describió alguna vez permitirá A > B > ...> A, entonces su clasificación no será determinista.En su caso, me temo que sí, aunque no puedo demostrarlo.Considere algunos casos de análisis 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
Aunque la pregunta planteaba 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
})
}
Mi problema era que tengo listas que consisten en una combinación de cadenas alfanuméricas (por ejemplo, C22, C3, C5, etc.), cadenas alfa (por ejemplo, A, H, R, etc.) y solo dígitos (por ejemplo, 99, 45, etc.) que necesitan ordenarse. el orden A, C3, C5, C22, H, R, 45, 99.También tengo duplicados que es necesario eliminar, por lo que solo obtengo una entrada.
Tampoco estoy trabajando solo con cadenas, estoy ordenando un objeto y usando un campo específico dentro del objeto para obtener el orden correcto.
Una solución que parece funcionar para mí es:
SortedSet<Code> codeSet;
codeSet = new TreeSet<Code>(new Comparator<Code>() {
private boolean isThereAnyNumber(String a, String b) {
return isNumber(a) || isNumber(b);
}
private boolean isNumber(String s) {
return s.matches("[-+]?\\d*\\.?\\d+");
}
private String extractChars(String s) {
String chars = s.replaceAll("\\d", "");
return chars;
}
private int extractInt(String s) {
String num = s.replaceAll("\\D", "");
return num.isEmpty() ? 0 : Integer.parseInt(num);
}
private int compareStrings(String o1, String o2) {
if (!extractChars(o1).equals(extractChars(o2))) {
return o1.compareTo(o2);
} else
return extractInt(o1) - extractInt(o2);
}
@Override
public int compare(Code a, Code b) {
return isThereAnyNumber(a.getPrimaryCode(), b.getPrimaryCode())
? isNumber(a.getPrimaryCode()) ? 1 : -1
: compareStrings(a.getPrimaryCode(), b.getPrimaryCode());
}
});
"Toma prestado" algún código que encontré aquí en Stackoverflow además de algunos ajustes propios para que funcione tal como lo necesitaba.
Debido a que intenté ordenar Objetos, necesitaba un comparador y también la eliminación de duplicados, un truco negativo que tuve que emplear fue que primero tenía que escribir mis Objetos en un TreeMap antes de escribirlos en un Treeset.Puede afectar un poco el rendimiento, pero dado que las listas tendrán un máximo de aproximadamente 80 códigos, no debería ser un problema.
Tuve un problema similar en el que mis cadenas tenían segmentos separados por espacios en su interior.Lo resolví de esta manera:
public class StringWithNumberComparator implements Comparator<MyClass> {
@Override
public int compare(MyClass o1, MyClass o2) {
if (o1.getStringToCompare().equals(o2.getStringToCompare())) {
return 0;
}
String[] first = o1.getStringToCompare().split(" ");
String[] second = o2.getStringToCompare().split(" ");
if (first.length == second.length) {
for (int i = 0; i < first.length; i++) {
int segmentCompare = StringUtils.compare(first[i], second[i]);
if (StringUtils.isNumeric(first[i]) && StringUtils.isNumeric(second[i])) {
segmentCompare = NumberUtils.compare(Integer.valueOf(first[i]), Integer.valueOf(second[i]));
if (0 != segmentCompare) {
// return only if uneven numbers in case there are more segments to be checked
return segmentCompare;
}
}
if (0 != segmentCompare) {
return segmentCompare;
}
}
} else {
return StringUtils.compare(o1.getDenominazione(), o2.getDenominazione());
}
return 0;
}
Como puede ver, he utilizado Apaches StringUtils.compare() y NumberUtils.compere() como ayuda estándar.
En el ejemplo dado, los números que desea comparar tienen espacios alrededor mientras que los otros números no, entonces, ¿por qué no funcionaría una expresión regular?
bbb 12 ccc
vs.
eee 12 dd jpeg2000 eee
Si está escribiendo una clase de comparación, debe implementar su propio método de comparación que comparará dos cadenas carácter por carácter.Este método de comparación debería comprobar si se trata de caracteres alfabéticos, numéricos o tipos mixtos (incluidos espacios).Tendrás que definir cómo quieres que actúe un tipo mixto, si los números van antes o después de los caracteres alfabéticos, dónde encajan los espacios, etc.
En Linux, glibc proporciona strverscmp(), también está disponible en gnulib para portabilidad.Sin embargo, la clasificación verdaderamente "humana" tiene muchas otras peculiaridades, como que "The Beatles" se clasifique como "Beatles, The".No existe una solución sencilla para este problema genérico.
