Classificar em uma seqüência que pode conter um número
https://stackoverflow.com/questions/104599
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu preciso escrever uma classe Java comparador que compara Cordas, porém com uma torção. Se as duas cordas que está comparando são os mesmos no início e no fim da cadeia são os mesmos, e a parte do meio que difere é um inteiro, e depois comparar com base nos valores numéricos referentes a estes inteiros. Por exemplo, eu quero as seguintes cadeias de acabar no fim eles são mostrados:
- aaa
- bbb 3 ccc
- bbb 12 ccc
- ccc 11
- ddd
- eee 3 ddd JPEG2000 eee
- eee 12 ddd JPEG2000 eee
Como você pode ver, pode haver outros inteiros na seqüência, então eu não pode apenas usar expressões regulares para romper qualquer inteiro. Estou pensando em apenas andando as cordas desde o início até que eu encontre um pouco que não corresponde, então anda dentro do final até que eu encontre um pouco que não corresponde, em seguida, comparando a pouco no meio do expressão regular "[0-9] +", e se ele se compara, em seguida, fazendo uma comparação numérica, caso contrário, fazendo uma comparação lexical.
Existe uma maneira melhor?
Atualizar Eu não acho que eu posso garantir que os outros números na seqüência, os que podem combinar, não tem espaços em torno deles, ou que aqueles que diferem têm espaços .
Solução
A partir do site
"cordas de classificação Pessoas com números de forma diferente do que software. A maioria dos algoritmos de ordenação comparar valores ASCII, que produz uma ordenação que seja inconsistente com a lógica humana. Aqui está como corrigi-lo."
Edit: Aqui está um link para o Java Comparator Implementação a partir desse site.
Outras dicas
pequeno desafio interessante, eu gostava de resolvê-lo.
Aqui é a minha opinião para o 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());
Esta necessidade algoritmo muito mais testes, mas parece comportar-se bastante bem.
[EDIT] Eu adicionei mais alguns comentários a ser mais clara. Vejo que há muito mais respostas do que quando eu comecei a este código ... Mas espero que eu forneci um bom começando base e / ou algumas ideias.
Ian Griffiths da Microsoft tem um C # implementação ele chama Natural Sorting . Portando para Java deve ser bastante fácil, mais fácil do que de C de qualquer maneira!
UPDATE: Não parece ser um exemplo Java em eekboom que faz isso, consulte o 'compareNatural' e usar isso como o seu comparador de tipos.
A implementação proponho aqui é simples e eficiente. Ele não aloca qualquer memória extra, direta ou indiretamente, usando expressões regulares ou métodos como substring (), split (), ToCharArray (), etc.
Esta implementação vai em primeiro lugar em ambas as cadeias de pesquisa para os primeiros caracteres que são diferentes, em velocidade máxima, sem fazer qualquer processamento especial durante este. comparação número específico é acionado somente quando esses personagens são os dois dígitos. Um efeito colateral dessa implementação é que um dígito é considerado como maior do que outras letras, ao contrário do padrão ordem lexicográfica.
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);
}
Eu sei que você está em java, mas você pode dar uma olhada em como StrCmpLogicalW funciona. É o que Explorer usa para classificar nomes de arquivos no Windows. Você pode olhar para a implementação VINHO aqui .
Dividir a string em corridas de letras e números, por isso "foo 12 bar" torna-se a lista ( "foo", 12, "bar"), então usar a lista como a chave de ordenação. Desta forma, os números serão ordenados por ordem numérica, não alfabética.
Eu vim com um bastante simples implementação em Java usando expressões 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)));
}
}
}
};
}
Aqui está 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]
O alphanum algrothim é bom, mas não se encontraram requisitos para um projeto que eu' m trabalhando. Eu preciso ser capaz de ordenar os números negativos e decimais corretamente. Aqui é a implementação eu vim. Qualquer comentário seria muito 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;
}
}
PS. Eu queria usar o método eo uso java.lang.String.split () "lookahead / lookbehind" para manter as fichas, mas eu não poderia obtê-lo para trabalhar com a expressão regular que eu estava usando.
problema interessante, e aqui a minha solução 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);
}
}
Antes de descobrir esta discussão, eu implementada uma solução semelhante em javascript. Talvez minha estratégia vai encontrá-lo bem, apesar de sintaxe diferente. Semelhante ao acima, eu analisar as duas cordas sendo comparados, e dividi-los tanto em matrizes, dividindo as cordas em números contínuos.
...
var regex = /(\d+)/g,
str1Components = str1.split(regex),
str2Components = str2.split(regex),
...
i, 'hello22goodbye 33' => [ 'Olá', 22, 'despedir', 33].; Assim, você pode caminhar por elementos das matrizes em pares entre string1 e string2, fazer algum tipo de coerção (como, é este elemento realmente um número?), E comparar como você anda.
Exemplo de aplicação aqui: http://jsfiddle.net/F46s6/3/
Note, eu atualmente só suportam inteiro tipos, embora lidar com valores decimais não seria muito difícil de uma modificação.
As minhas 2 cents.Is que trabalham bem para mim. Estou principalmente usá-lo para nomes de arquivos.
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);
}
Eu acho que você vai ter que fazer a comparação em uma moda caractere por caractere. Pegue um personagem, se é um personagem número, mantenha agarrando e remonte aos caracteres em uma única seqüência número e convertê-lo em um int. Repita do outro corda, e só então fazer a comparação.
Resposta curta: com base no contexto, não posso dizer se isso é apenas algum código rápida e suja para uso pessoal, ou uma parte fundamental do mais recente software de contabilidade interna Goldman Sachs', então eu vou abrir por dizendo: eww. Isso é um algoritmo em vez descolados classificação; Tente usar algo um pouco menos "sinuosa", se puder.
Resposta longa:
As duas questões que vêm imediatamente à mente no seu caso são o desempenho, e correção. Informalmente, certifique-se é rápido, e se certificar que seu algoritmo é um total de ordenação .
(Claro, se você não está classificando mais de cerca de 100 itens, você provavelmente pode ignorar este parágrafo.) Questões de desempenho, como a velocidade do comparador será o maior fator na velocidade de sua espécie (assumindo que o algoritmo de ordenação é "ideal" para a lista típica). No seu caso, a velocidade do comparador dependerá principalmente do tamanho da cadeia. As cordas parecem ser bastante curto, de modo que provavelmente não vai dominar tanto quanto o tamanho de sua lista.
Virando cada corda em uma tupla corda-número-string e, em seguida, classificar esta lista de tuplas, como sugerido em outra resposta, irá falhar em alguns de seus casos, uma vez que, aparentemente, terá cordas com vários números que aparecem.
O outro problema é correto. Especificamente, se o algoritmo que você descreveu nunca vai permitir A> B> ...> A, então o seu tipo será não-determinista. No seu caso, temo que pôde, embora eu não posso provar. Considere alguns casos de análise, tais 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
Embora a pergunta feita uma solução java, para quem quer uma solução 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
})
}
Meu problema foi que têm listas que consistem de uma combinação de alfa cadeias numéricas (por exemplo, C22, C3, C5, etc), alfa cordas (por exemplo, A, H, R, etc.) e apenas a dígitos (por exemplo, 99, 45 etc.) que necessidade de ordenar no sentido a, C3, C5, C22, H, R, 45, 99. também têm duplicados que necessitam de remoção de modo que só tem uma única entrada.
Estou também não apenas trabalhar com Cordas, estou ordenando um objeto e usando um campo específico dentro do objeto para obter a ordem correta.
Uma solução que parece funcionar para mim é:
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());
}
});
It 'toma emprestado' algum código que eu encontrei aqui no Stackoverflow além de alguns ajustes de meu próprio para fazê-lo funcionar apenas como eu precisava disso também.
Devido a tentar ordem Objects, precisando de um comparador, bem como a remoção duplicado, um fudge negativo que eu tinha que empregam era eu primeiro tenho que escrever meus objetos para um TreeMap antes de escrever-los a um TreeSet. Ele pode afetar o desempenho um pouco, mas dado que as listas será um máximo de cerca de 80 códigos, não deve ser um problema.
Eu tive um problema semelhante onde minhas cordas tinha segmentos separados por espaços dentro. Eu resolvi desta forma:
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 você pode ver eu usei Apaches StringUtils.compare () e NumberUtils.compere () como uma ajuda padrão.
Em seu determinado exemplo, os números que você deseja comparar ter espaços em torno deles, enquanto os outros números não fizer isso, então por que uma expressão regular não trabalho?
bbb 12 ccc
vs.
eee 12 ddd JPEG2000 eee
Se você estiver escrevendo uma classe de comparação, você deve implementar seu próprio método de comparar que irá comparar caráter duas cordas de caráter. Este método compara deve verificar se você está lidando com caracteres alfabéticos, caracteres numéricos, ou tipos mistos (incluindo espaços). Você terá que definir como você deseja um tipo misto de agir, se os números vêm antes de caracteres alfabéticos ou depois, e onde os espaços encaixar etc.
No Linux glibc fornece strverscmp (), também é disponível a partir gnulib para a portabilidade. No entanto verdadeiramente "humano" triagem tem muitas outras peculiaridades, como "The Beatles" que estão sendo classificados como "Beatles, The". Não há uma solução simples para esse problema genérico.
