Trier sur une chaîne pouvant contenir un nombre
https://stackoverflow.com/questions/104599
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je dois écrire une classe de comparateur Java qui compare les chaînes, mais avec une torsion. Si les deux chaînes comparées sont identiques au début et à la fin de la chaîne, la partie centrale qui diffère est un entier, puis comparez en fonction des valeurs numériques de ces entiers. Par exemple, je veux que les chaînes suivantes se retrouvent dans l'ordre indiqué:
- aaa
- bbb 3 ccc
- bbb 12 ccc
- ccc 11
- ddd
- eee 3 ddd jpeg2000 eee
- eee 12 ddd jpeg2000 eee
Comme vous pouvez le constater, la chaîne contient peut-être d'autres entiers. Par conséquent, je ne peux pas simplement utiliser des expressions régulières pour décomposer un entier. Je songe à faire marcher les cordes du début jusqu'à ce que je trouve un morceau qui ne correspond pas, puis à partir de la fin jusqu'à ce que je trouve un morceau qui ne correspond pas, puis à comparer le morceau situé au milieu avec le expression régulière "[0-9] +", et si elle se compare, effectue une comparaison numérique, sinon effectue une comparaison lexicale.
Y a-t-il un meilleur moyen?
Mettre à jour Je ne pense pas pouvoir garantir que les autres nombres de la chaîne, ceux qui peuvent correspondre, ne comportent pas d'espaces ou que ceux qui diffèrent le sont. .
La solution
À partir du site Web
"Les utilisateurs trient les chaînes avec des nombres différemment des logiciels. La plupart des algorithmes de tri comparent les valeurs ASCII, ce qui produit un ordre incohérent avec la logique humaine. Voici comment résoudre ce problème. "
Modifier: voici un lien vers la Implémentation du comparateur Java de ce site.
Autres conseils
Petit défi intéressant, j'ai adoré le résoudre.
Voici mon point de vue sur le problème:
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());
Cet algorithme nécessite beaucoup plus de tests, mais il semble se comporter plutôt bien.
[EDIT] J'ai ajouté quelques commentaires supplémentaires pour être plus clair. Je vois qu’il ya beaucoup plus de réponses que lorsque j’ai commencé à coder ceci ... Mais j’espère avoir fourni une bonne base de départ et / ou quelques idées.
Ian Griffiths de Microsoft a une implémentation C # qu’il appelle Tri naturel . Le portage sur Java devrait être assez facile, bien plus facile que depuis C!
UPDATE: Il semble y avoir un exemple Java sur eekboom , reportez-vous à la section" compareNatural ". et l'utiliser comme votre comparateur pour trier.
L’implémentation que je propose ici est simple et efficace. Il n'alloue pas de mémoire supplémentaire, directement ou indirectement, à l'aide d'expressions régulières ou de méthodes telles que substring (), split (), toCharArray (), etc.
Cette implémentation parcourt d’abord les deux chaînes pour rechercher les premiers caractères différents, à la vitesse maximale, sans effectuer de traitement spécial pendant cette opération. La comparaison de numéros spécifiques est déclenchée uniquement lorsque ces caractères sont composés de deux chiffres. Un effet secondaire de cette implémentation est qu’un chiffre est considéré comme plus grand que les autres lettres, contrairement à l’ordre lexicographique par défaut.
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);
}
Je me rends compte que vous êtes en Java, mais vous pouvez jeter un coup d'œil à la façon dont StrCmpLogicalW fonctionne. C'est ce que l'explorateur utilise pour trier les noms de fichiers dans Windows. Vous pouvez consulter la mise en œuvre de WINE ici .
Scindez la chaîne en séries de lettres et de chiffres afin que "foo 12 bar" devient la liste ("foo", 12, "bar"), puis utilise la liste comme clé de tri. De cette façon, les numéros seront classés par ordre numérique et non par ordre alphabétique.
Je suis arrivé à une implémentation assez simple en Java en utilisant des expressions régulières:
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)));
}
}
}
};
}
Voici comment cela fonctionne:
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]
Le Alphanum est bien, mais il ne correspondait pas aux conditions requises pour un projet I ' m travaille sur. Je dois pouvoir trier correctement les nombres négatifs et les nombres décimaux. Voici la mise en œuvre je suis venu. Tout commentaire serait très apprécié.
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;
}
}
PS. Je souhaitais utiliser la méthode java.lang.String.split () et utiliser < lookahead / lookbehind " garder les jetons, mais je ne pouvais pas le faire fonctionner avec l'expression régulière que j'utilisais.
problème intéressant, et voici ma solution proposée:
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);
}
}
Avant de découvrir ce fil, j’avais implémenté une solution similaire en javascript. Peut-être que ma stratégie vous trouvera bien malgré une syntaxe différente. Semblable à ce qui précède, j'analyse les deux chaînes comparées et les divise en tableaux, en divisant les chaînes en nombres continus.
...
var regex = /(\d+)/g,
str1Components = str1.split(regex),
str2Components = str2.split(regex),
...
I.e., 'hello22goodbye 33' = > ["bonjour", 22 ans, "au revoir", 33 ans]; Ainsi, vous pouvez parcourir les éléments des tableaux en paires, entre chaîne1 et chaîne2, effectuer une certaine coercition de type (par exemple, cet élément est-il vraiment un nombre?), Et comparer en marchant.
Exemple de travail ici: http://jsfiddle.net/F46s6/3/
Remarque: je ne prends actuellement en charge que les types entiers, bien que la gestion des valeurs décimales ne soit pas une modification difficile.
Mes 2 cents. Cela fonctionne bien pour moi. Je l'utilise principalement pour les noms de fichiers.
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);
}
Je pense que vous devrez faire la comparaison, mode par caractère. Saisissez un caractère, s’il s’agit d’un chiffre, continuez à le saisir, puis réassemblez les caractères en une chaîne numérique unique et convertissez-le en int . Répétez l'opération sur l'autre chaîne, puis effectuez la comparaison.
Réponse courte: en fonction du contexte, je ne peux pas dire s'il s'agit simplement d'un code rapide et malveillant à usage personnel, ou d'un élément clé du dernier logiciel de comptabilité interne de Goldman Sachs. Par conséquent, je commencerai par en disant: eww. C'est un algorithme de tri assez funky; essayez d'utiliser quelque chose d'un peu moins "twisty" si vous le pouvez.
Réponse longue:
Les deux problèmes qui vous viennent immédiatement à l’esprit dans votre cas sont la performance et l’exactitude. De manière informelle, assurez-vous que tout est rapide et que votre algorithme est un total de la commande .
(Bien sûr, si vous ne triez pas plus de 100 éléments, vous pouvez probablement ignorer ce paragraphe.) La performance compte, car la vitesse du comparateur sera le facteur le plus important de la rapidité de votre tri (en supposant que le L’algorithme de tri est "idéal" dans la liste typique). Dans votre cas, la vitesse du comparateur dépendra principalement de la taille de la chaîne. Les chaînes semblent être assez courtes, elles ne domineront donc probablement pas autant que la taille de votre liste.
Transformer chaque chaîne en un tuple chaîne-nombre-chaîne puis trier cette liste de n-uplets, comme suggéré dans une autre réponse, échouera dans certains cas, car vous aurez apparemment des chaînes contenant plusieurs numéros.
L’autre problème est l’exactitude. Plus précisément, si l'algorithme que vous avez décrit autorisera un jour > B > ... > A, alors ton tri sera non déterministe. Dans votre cas, je le crains, bien que je ne puisse pas le prouver. Considérez certains cas d'analyse tels que:
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
Même si la question demandait une solution Java, si vous souhaitez une solution 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
})
}
Mon problème était que j'avais des listes consistant en une combinaison de chaînes alphanumériques (par exemple, C22, C3, C5, etc.), de chaînes alpha (par exemple, A, H, R, etc.) et uniquement de chiffres (par exemple, 99, 45, etc.). besoin de trier dans l'ordre A, C3, C5, C22, H, R, 45, 99. J'ai également des doublons qui doivent être supprimés afin que je ne reçois qu'une seule entrée.
Je ne travaille pas uniquement avec des chaînes, je commande un objet et utilise un champ spécifique dans l'objet pour obtenir le bon ordre.
Une solution qui semble fonctionner pour moi est la suivante:
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());
}
});
Il "emprunte" du code que j'ai trouvé ici sur Stackoverflow, plus quelques ajustements personnels pour le faire fonctionner exactement comme j'en avais besoin.
Après avoir essayé de commander des objets, nécessitant un comparateur ainsi que la suppression des doublons, un fudge négatif que je devais employer était que je devais d’abord écrire mes objets sur une TreeMap avant de les écrire sur un arbre. Cela peut avoir un léger impact sur les performances mais étant donné que les listes contiendront un maximum de 80 codes, cela ne devrait pas poser de problème.
J'ai eu un problème similaire: mes chaînes contenaient des segments séparés par des espaces. Je l'ai résolu de cette façon:
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;
}
Comme vous pouvez le constater, j'ai utilisé Apaches StringUtils.compare () et NumberUtils.compere () comme aide standard.
Dans votre exemple, les nombres que vous souhaitez comparer sont entourés d'espaces alors que les autres ne le sont pas. Pourquoi une expression régulière ne fonctionnerait-elle pas?
bbb 12 ccc
vs.
eee 12 ddd jpeg2000 eee
Si vous écrivez une classe de comparaison, vous devez implémenter votre propre méthode de comparaison permettant de comparer deux chaînes caractère par caractère. Cette méthode de comparaison doit vérifier si vous utilisez des caractères alphabétiques, des caractères numériques ou des types mixtes (y compris les espaces). Vous devrez définir comment vous voulez qu'un type mixte agisse, que les nombres soient avant ou après les caractères alphabétiques, et où les espaces s’inscrivent, etc.
Sous Linux, glibc fournit strverscmp (), il est également disponible auprès de gnulib pour la portabilité. Cependant, vraiment " humain " le tri a beaucoup d’autres bizarreries comme "The Beatles". en cours de tri comme "Beatles, The". Il n’existe pas de solution simple à ce problème générique.
