Sortieren auf eine Zeichenfolge, die eine Zahl enthalten
https://stackoverflow.com/questions/104599
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich brauche eine Java Vergleicher Klasse zu schreiben, die Strings vergleicht, aber mit einem Twist. Wenn die beiden Strings es das gleiche am Anfang und Ende des Strings vergleicht sind die gleichen sind, und der mittlere Teil, der eine ganze Zahl unterscheidet, ist, vergleichen dann auf der Grundlage der numerischen Werte dieser Zahlen. Zum Beispiel möchte ich die folgenden Zeichenfolgen, um sie am Ende sind gezeigt:
- aaa
- bbb 3 ccc
- bbb 12 ccc
- ccc 11
- ddd
- eee 3 ddd jpeg2000 eee
- eee 12 ddd jpeg2000 eee
Wie Sie sehen können, könnte es andere Zahlen in der Kette sein, also kann ich nicht nur reguläre Ausdrücke verwenden, um eine beliebige ganze Zahl auszubrechen. Ich denke an die Zeichenfolge einfach von Anfang an zu Fuß, bis ich etwas finden, das nicht, dann von dem Ende zu Fuß in überein, bis ich ein bisschen finden, die nicht übereinstimmt, und dann in der Mitte das Bits im Vergleich zu dem regulärer Ausdruck „[0-9] +“, und wenn es vergleicht, dann einen numerischen Vergleich tun, sonst einen lexikalischen Vergleich zu tun.
Gibt es einen besseren Weg?
Aktualisieren Ich glaube nicht, dass ich, dass die anderen Zahlen im String garantieren können, diejenigen, die passen kann, haben keine Leerzeichen um sie herum, oder dass diejenigen, die Räume zu tun haben unterscheiden .
Lösung
Von der Website
„Die Menschen sortieren Strings mit Zahlen anders als Software. Die meisten Sortieralgorithmen ASCII-Werten vergleichen, die eine Ordnung erzeugt, die mit der menschlichen Logik unvereinbar ist. Hier ist, wie es zu beheben.“
Edit:. Hier ist ein Link auf die Java Vergleicher Implementierung von dieser Seite
Andere Tipps
Interessante kleine Herausforderung, ich genoss es zu lösen.
Hier ist mein nehmen auf das Problem:
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());
Dieser Algorithmus braucht viel mehr Tests, aber es scheint recht gut zu verhalten.
[EDIT] Ich habe einige mehr Kommentare klarer zu sein. Ich sehe, es gibt viel mehr Antworten, als wenn ich den Autor dieses zu kodieren ... Aber ich hoffe, dass er eine gute Ausgangsbasis und / oder ein paar Ideen.
Ian Griffiths von Microsoft hat eine C # -Implementierung er nennt natürliche Sortierung . Eine Portierung auf Java sollte ziemlich einfach, einfacher als von C sowieso!
UPDATE: Es scheint ein Java-Beispiel auf eekboom , der dies tut, finden Sie in der‚compareNatural‘und verwenden, die als Vergleich zu Art.
Die Umsetzung ich hier vorschlagen, ist einfach und effizient. Es ist zuteilen keinen zusätzlichen Speicher, die direkt oder indirekt durch reguläre Ausdrücke oder Methoden wie substring () verwenden, split (), ToCharArray () usw.
Diese Implementierung geht zuerst über beide Saiten für die ersten Zeichen zu suchen, die anders sind, bei maximaler Geschwindigkeit, ohne daß eine spezielle Verarbeitung während dies zu tun. Spezifische Nummer Vergleich wird nur dann ausgelöst, wenn diese Zeichen beide Ziffern sind. Ein Nebeneffekt dieser Implementierung ist, dass eine Ziffer als größer als die anderen Buchstaben betrachtet, konträr lexicographic um auf dem Standard.
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);
}
Ich weiß, Sie in Java sind, aber Sie können einen Blick darauf werfen, wie StrCmpLogicalW funktioniert. Es ist, was Explorer Dateinamen in Windows sortieren verwendet. Sie können an der WINE Implementierung hier .
Teilen Sie die Zeichenfolge in Läufe von Buchstaben und Zahlen, so „foo 12 bar“ wird die Liste ( „foo“, 12, „bar“), dann verwenden Sie die Liste als Sortierschlüssel. Auf diese Weise die Zahlen werden in numerischer Reihenfolge geordnet werden, nicht alphabetisch.
kam ich mit einer ganz einfachen Implementierung in Java mit regulärer Ausdrücken auf:
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)));
}
}
}
};
}
Hier ist, wie es funktioniert:
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]
Der Alphanum algrothim ist schön, aber es hat für ein Projekt nicht Vorstellungen I‘ m arbeiten. Ich muss in der Lage, richtig negative Zahlen und Dezimalzahlen zu sortieren. Hier ist die Implementierung ich kam. Jedes Feedback würde sehr geschätzt werden.
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. Ich wollte die java.lang.String.split () -Methode verwenden und „Look-Ahead / Lookbehind“ die Token zu halten, aber ich konnte es nicht mit dem regulären Ausdruck zu arbeiten war ich mit.
interessantes Problem, und hier meine vorgeschlagene Lösung:
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);
}
}
Vor diesem Thread zu entdecken, implementiert ich eine ähnliche Lösung in Javascript. Vielleicht wird meine Strategie, die Sie gut finden, trotz unterschiedlicher Syntax. Ähnlich wie oben, parsen I die beiden Strings verglichen werden und spalten sie beide in Arrays, die Fäden bei Dauer Zahlen.
...
var regex = /(\d+)/g,
str1Components = str1.split(regex),
str2Components = str2.split(regex),
...
d.h. 'hello22goodbye 33' => [ 'Hallo', 22, 'Auf Wiedersehen', 33]. So können Sie die Arrays' Elemente in Paaren zwischen string1 und string2 zu Fuß durch, einige Art Zwang (wie ist dieses Element wirklich eine Zahl?), Und vergleichen Sie, wie Sie zu Fuß.
Arbeitsbeispiel hier: http://jsfiddle.net/F46s6/3/
Beachten Sie, ich derzeit nur Integer-Typen Unterstützung, wenn auch nicht allzu schwer sein, eine Änderung würde Dezimalwerte Handhabung.
My 2 cents.Is arbeiten gut für mich. Ich benutze es vor allem für die Dateinamen.
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);
}
Ich denke, Sie den Vergleich auf einer Zeichen-für-Zeichen-Mode zu tun haben. Schnappen Sie sich einen Charakter, wenn es eine Reihe Charakter ist, halten sich ziehen, dann wieder zusammenzusetzen, um Zeichen in eine einzige Zahlenfolge und wandeln es in ein int. Wiederholen Sie auf der anderen Saite, und erst dann den Vergleich zu tun.
Kurze Antwort: basierend auf dem Kontext, kann ich nicht sagen, ob dies nur einige quick-and-dirty-Code für den persönlichen Gebrauch, oder ein wichtiger Bestandteil von Goldman Sachs neuesten internen Buchhaltungssoftware, so werde ich öffnen sagte: eww. Das ist ein ziemlich flippig Sortieralgorithmus; versuchen, etwas ein bisschen weniger „kurvig“ zu verwenden, wenn Sie können.
Lange Antwort:
Die beiden Fragen, die sofort in den Sinn in Ihrem Fall kommen, sind Leistung und Richtigkeit. Informell, stellen Sie sicher, es ist schnell, und stellen Sie sicher, dass Ihr Algorithmus ein totale Ordnung .
(Natürlich, wenn Sie nicht mehr als etwa 100 Sortieren von Gegenständen, können Sie wahrscheinlich diesen Absatz außer Acht lassen.) Performance Angelegenheiten, wie die Geschwindigkeit des Komparators wird der größte Faktor bei der Geschwindigkeit Ihrer Art sein (vorausgesetzt, die Sortieralgorithmus ist „ideal“, um die typische Liste). In Ihrem Fall wird die Geschwindigkeit des Komparator hängt hauptsächlich von der Größe der Zeichenfolge. Die Saiten scheinen ziemlich kurz zu sein, so dass sie wahrscheinlich nicht so viel wie die Größe Ihrer Liste dominieren.
Drehen jede Zeichenfolge in eine String-number-Stringtupel und dann das Sortieren dieser Liste von Tupeln, wie in einer anderen Antwort vorgeschlagen, wird in einige Ihrer Fällen fehlschlagen, da Sie anscheinend Strings mit mehreren Nummern erscheinen haben.
Das andere Problem ist Richtigkeit. Insbesondere dann, wenn der Algorithmus Sie beschrieben wird jemals erlauben A> B> ...> A, dann wird Ihre Art nicht-deterministisch sein. In Ihrem Fall befürchte ich, dass es vielleicht, obwohl ich es nicht beweisen kann. Betrachten wir einige Parsing Fällen wie:
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
Obwohl die Frage eine Java-Lösung gefragt, für jeden, der eine scala Lösung will:
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
})
}
Mein Problem war, dass ich Listen haben, bestehend aus einer Kombination von alphanumerischen Zeichenfolgen (zB C22, C3, C5 usw.), alpha-Strings (zB A, H, R, etc.) und nur Ziffern (zB 99, 45 usw.), die ich nur einen einzigen Eintrag muß in der Reihenfolge A Sortierung, C3, C5, C22, H, R, 45, 99. ich habe auch Duplikate zu entfernen, die so brauchen.
Ich bin auch nicht nur mit Strings arbeiten, ich bin ein Objekt der Bestellung und ein bestimmtes Feld innerhalb des Objekts mit der richtigen Reihenfolge zu erhalten.
Eine Lösung, die für mich zu arbeiten scheint, ist:
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());
}
});
Es leiht sich "einige Code, den ich hier auf Stackoverflow gefunden sowie einige Verbesserungen meiner eigenen, um es einfach zu bekommen arbeiten, wie ich es auch benötigt wird.
Durch versuchen Objekte zu bestellen, einen Komparator sowie doppelte Entfernung benötigen, eine negative Fudge ich beschäftigen musste, war ich zuerst meine Objekte zu einem TreeMap schreiben, bevor sie zu einem TreeSet schreiben. Es kann Auswirkungen auf die Leistung ein wenig, aber da die Listen ein Maximum von etwa 80 Codes sein, es sollte kein Problem sein.
Ich hatte ein ähnliches Problem, wo meine Saiten im Inneren durch Leerzeichen getrennte Segmente hatte. Ich löste es auf diese Weise:
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;
}
Wie Sie sehen, habe ich verwendet Apachen StringUtils.compare () und NumberUtils.compere () als Standard-Hilfe.
In Ihrem gegebenen Beispiel die Zahlen wollen Sie um sie herum haben Räume zu vergleichen, während die anderen Zahlen nicht, also warum würde ein regulärer Ausdruck nicht?
bbb 12 ccc
vs.
eee 12 ddd jpeg2000 eee
Wenn Sie einen Komparator Klasse schreiben, sollten Sie Ihre eigenen vergleichen Methode implementieren, die zwei Strings Zeichen für Zeichen vergleicht. Diese vergleicht Methode soll überprüfen, ob Sie mit Buchstaben, Ziffern oder Mischtypen (inklusive Leerzeichen) zu tun. Sie müssen festlegen, wie Sie ein Mischtyp handeln wollen, ob Zahlen kommen vor Buchstaben oder nach und wo Räume passen etc.
Unter Linux glibc bietet strverscmp (), sondern auch von gnulib für Portabilität zur Verfügung. Doch wirklich „human“ Sortierung hat viele andere Macken wie „The Beatles“ als „Beatles, The“ sortiert werden. Es gibt keine einfache Lösung für dieses allgemeine Problem.
