Ordina su una stringa che può contenere un numero
https://stackoverflow.com/questions/104599
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Devo scrivere una classe Java Comparator che confronta le stringhe, tuttavia con una svolta. Se le due stringhe che sta confrontando sono uguali all'inizio e alla fine della stringa sono uguali e la parte centrale che differisce è un numero intero, quindi confrontare in base ai valori numerici di tali numeri interi. Ad esempio, voglio che le seguenti stringhe finiscano nell'ordine in cui sono visualizzate:
- AAA
- bbb 3 ccc
- bbb 12 ccc
- ccc 11
- ddd
- eee 3 ddd jpeg2000 eee
- eee 12 ddd jpeg2000 eee
Come puoi vedere, potrebbero esserci altri numeri interi nella stringa, quindi non posso semplicemente usare espressioni regolari per dividere qualsiasi numero intero. Sto pensando di camminare solo sulle corde dall'inizio fino a quando non trovo un po 'che non corrisponde, quindi di entrare dalla fine fino a quando non trovo un po' che non corrisponde, e quindi confrontare il bit nel mezzo con il espressione regolare " [0-9] + " ;, e se confronta, quindi facendo un confronto numerico, altrimenti facendo un confronto lessicale.
C'è un modo migliore?
Aggiorna Non credo di poter garantire che gli altri numeri nella stringa, quelli che potrebbero corrispondere, non abbiano spazi attorno a loro, o che quelli che differiscono abbiano spazi .
Soluzione
Dal sito web
" Le persone ordinano le stringhe con numeri in modo diverso rispetto al software. La maggior parte degli algoritmi di ordinamento confronta i valori ASCII, che produce un ordinamento incompatibile con la logica umana. Ecco come risolverlo. & Quot;
Modifica: ecco un link alla Implementazione del comparatore Java da quel sito.
Altri suggerimenti
Piccola sfida interessante, mi è piaciuto risolverlo.
Ecco la mia opinione sul 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());
Questo algoritmo richiede molti più test, ma sembra comportarsi piuttosto bene.
[EDIT] Ho aggiunto altri commenti per essere più chiari. Vedo che ci sono molte più risposte rispetto a quando ho iniziato a scrivere questo codice ... Ma spero di aver fornito una buona base di partenza e / o alcune idee.
Ian Griffiths di Microsoft ha un'implementazione in C # che chiama Ordinamento naturale . Il porting su Java dovrebbe essere abbastanza facile, più facile che da C comunque!
AGGIORNAMENTO: sembra esserci un esempio Java su eekboom che fa questo, vedi il " compareNatural " e usalo come comparatore per ordinare.
L'implementazione che propongo qui è semplice ed efficiente. Non alloca memoria aggiuntiva, direttamente o indirettamente, usando espressioni regolari o metodi come substring (), split (), toCharArray (), ecc.
Questa implementazione attraversa prima entrambe le stringhe per cercare i primi caratteri che sono diversi, alla massima velocità, senza eseguire alcuna elaborazione speciale durante questo. Il confronto di numeri specifici viene attivato solo quando questi caratteri sono entrambi cifre. Un effetto collaterale di questa implementazione è che una cifra è considerata maggiore di altre lettere, contrariamente all'ordine lessicografico predefinito.
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);
}
Mi rendo conto che sei in Java, ma puoi dare un'occhiata a come funziona StrCmpLogicalW. È ciò che Explorer usa per ordinare i nomi dei file in Windows. Puoi vedere l'implementazione WINE qui .
Dividi la stringa in serie di lettere e numeri, quindi "12 piedi". diventa l'elenco (" foo " ;, 12, " bar "), quindi utilizza l'elenco come chiave di ordinamento. In questo modo i numeri verranno ordinati in ordine numerico, non alfabetico.
Ho realizzato un'implementazione abbastanza semplice in Java usando espressioni regolari:
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)));
}
}
}
};
}
Ecco come funziona:
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]
Il Alphanum algrothim è carino, ma non corrisponde ai requisiti di un progetto I ' sto lavorando su. Devo essere in grado di ordinare correttamente i numeri negativi e i decimali. Ecco l'implementazione che mi è venuta in mente. Qualsiasi feedback sarebbe molto apprezzato.
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. Volevo usare il metodo java.lang.String.split () e usare " lookahead / lookbehind " per mantenere i token, ma non sono riuscito a farlo funzionare con l'espressione regolare che stavo usando.
problema interessante, e qui la mia soluzione proposta:
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);
}
}
Prima di scoprire questo thread, ho implementato una soluzione simile in javascript. Forse la mia strategia ti troverà bene, nonostante la sintassi diversa. Simile a quello sopra, analizzo le due stringhe confrontate e le divido entrambe in array, dividendo le stringhe in numeri continui.
...
var regex = /(\d+)/g,
str1Components = str1.split(regex),
str2Components = str2.split(regex),
...
Cioè, 'ciao22goodbye 33' = > ['ciao', 22, 'arrivederci', 33]; Quindi, puoi camminare attraverso gli elementi delle matrici in coppie tra stringa1 e stringa2, fare un po 'di coercizione del tipo (come, questo elemento è davvero un numero?) E confrontare mentre cammini.
Esempio di lavoro qui: http://jsfiddle.net/F46s6/3/
Nota, attualmente supporto solo tipi interi, anche se la gestione di valori decimali non sarebbe troppo difficile da modificare.
I miei 2 centesimi stanno funzionando bene per me. Lo sto usando principalmente per i nomi dei file.
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);
}
Penso che dovrai fare un paragone secondo la moda carattere per carattere. Prendi un personaggio, se è un carattere numerico, continua ad afferrarlo, quindi riassemblalo in caratteri in un'unica stringa numerica e convertilo in un int . Ripeti sull'altra stringa e solo allora fai il confronto.
Risposta breve: in base al contesto, non posso dire se si tratta solo di un codice rapido per uso personale o di una parte fondamentale dell'ultimo software di contabilità interna di Goldman Sachs, quindi aprirò da dicendo: eww. È un algoritmo di ordinamento piuttosto originale; prova a usare qualcosa di un po 'meno "twisty" se puoi.
Risposta lunga:
I due problemi che vengono immediatamente in mente nel tuo caso sono le prestazioni e la correttezza. Informalmente, assicurati che sia veloce e assicurati che il tuo algoritmo sia un ordinamento totale .
(Naturalmente, se non stai ordinando più di circa 100 articoli, puoi probabilmente ignorare questo paragrafo.) Le prestazioni contano, poiché la velocità del comparatore sarà il fattore più grande nella velocità del tuo ordinamento (supponendo che l'algoritmo di ordinamento è "ideale" nell'elenco tipico). Nel tuo caso, la velocità del comparatore dipenderà principalmente dalla dimensione della stringa. Le stringhe sembrano essere piuttosto corte, quindi probabilmente non domineranno tanto quanto le dimensioni della tua lista.
Trasformare ogni stringa in una tupla stringa-numero-stringa e quindi ordinare questo elenco di tuple, come suggerito in un'altra risposta, fallirà in alcuni dei tuoi casi, poiché apparentemente avrai stringhe con più numeri che appaiono.
L'altro problema è la correttezza. In particolare, se l'algoritmo che hai descritto consentirà mai A > B > ... > A, il tuo ordinamento non sarà deterministico. Nel tuo caso, temo che potrebbe, anche se non posso provarlo. Prendi in considerazione alcuni casi di analisi come:
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
Sebbene la domanda abbia posto una soluzione java, per chiunque desideri una soluzione 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
})
}
Il mio problema era che avevo liste costituite da una combinazione di stringhe alfanumeriche (ad es. C22, C3, C5 ecc.), stringhe alfa (ad es. A, H, R ecc.) e solo cifre (ad es. 99, 45 ecc.) che ho bisogno di ordinare nell'ordine A, C3, C5, C22, H, R, 45, 99. Ho anche dei duplicati che devono essere rimossi, quindi ottengo una sola voce.
Non sto solo lavorando con le stringhe, sto ordinando un oggetto e usando un campo specifico all'interno dell'oggetto per ottenere l'ordine corretto.
Una soluzione che sembra funzionare per me è:
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());
}
});
"Prende in prestito" un po 'di codice che ho trovato qui su StackOverflow oltre ad alcune mie modifiche per farlo funzionare proprio come ne avevo bisogno.
A causa del tentativo di ordinare gli oggetti, che necessitano di un comparatore e di una rimozione duplicata, un fondamento negativo che ho dovuto impiegare è stato quello di scrivere i miei oggetti su una TreeMap prima di scriverli su un set di alberi. Potrebbe avere un leggero impatto sulle prestazioni, ma dato che le liste avranno un massimo di circa 80 codici, non dovrebbe essere un problema.
Ho avuto un problema simile in cui le mie stringhe avevano segmenti separati da spazio all'interno. L'ho risolto in questo modo:
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;
}
Come puoi vedere, ho usato Apaches StringUtils.compare () e NumberUtils.compere () come guida standard.
Nel tuo esempio dato, i numeri che vuoi confrontare hanno spazi attorno a loro mentre gli altri numeri no, quindi perché un'espressione regolare non funziona?
bbb 12 ccc
vs.
eee 12 ddd jpeg2000 eee
Se stai scrivendo una classe di confronto, dovresti implementare il tuo metodo di confronto che confronterà due stringhe carattere per carattere. Questo metodo di confronto dovrebbe verificare se hai a che fare con caratteri alfabetici, caratteri numerici o tipi misti (inclusi gli spazi). Dovrai definire come vuoi che un tipo misto agisca, se i numeri vengono prima dei caratteri alfabetici o dopo, e dove si adattano gli spazi ecc.
Su Linux glibc fornisce strverscmp (), è anche disponibile da gnulib per la portabilità. Tuttavia veramente "umano" l'ordinamento ha molte altre stranezze come " The Beatles " essendo ordinati come " Beatles, il " ;. Non esiste una soluzione semplice a questo problema generico.
