Comparação de sequência de ordenação de ordem natural em Java – uma é integrada?

Eu gostaria de algum tipo de function de comparação de seqüência de caracteres que preserva a ordem de sorting natural 1 . Existe algo como isso embutido em Java? Não consigo encontrar nada na class String , e a class Comparator só sabe de duas implementações.

Eu posso fazer o meu próprio (não é um problema muito difícil), mas eu prefiro não reinventar a roda se eu não precisar.

No meu caso específico, eu tenho seqüências de versão de software que eu quero classificar. Então eu quero que “1.2.10.5” seja considerado maior que “1.2.9.1”.


1 Por ordem de sorting “natural”, quero dizer, ela compara as cordas da maneira que um humano as compararia, ao contrário da ordenação “ascii-betical”, que só faz sentido para os programadores. Em outras palavras, “image9.jpg” é menor que “image10.jpg” e “album1set2page9photo1.jpg” é menor que “album1set2page10photo5.jpg” e “1.2.9.1” é menor que “1.2.10.5”

Em java, o significado da ordem “natural” é a ordem “lexicográfica”, portanto, não há implementação no núcleo como a que você está procurando.

Existem implementações de código aberto.

Aqui está um:

NaturalOrderComparator.java

Certifique-se de ler o:

Licença Open Source Cougaar

Eu espero que isso ajude!

Eu testei três implementações de Java mencionadas aqui por outros e descobri que seu trabalho é um pouco diferente, mas nenhum como eu esperaria.

Tanto o AlphaNumericStringComparator quanto o AlphanumComparator não ignoram os espaços em branco, de forma que o pic2 seja colocado antes da pic 1 .

Por outro lado, NaturalOrderComparator ignora não apenas os espaços em branco, mas também todos os zeros à esquerda, de modo que sig[1] preceda sig[0] .

Em relação ao desempenho AlphaNumericStringComparator é ~ x10 mais lento que os outros dois.

Implementos de cadeia Comparável, e é isso que a ordenação natural está em Java (comparando usando a interface comparável). Você pode colocar as strings em um TreeSet ou classificar usando as classs Collections ou Arrays.

No entanto, no seu caso, você não quer “ordenação natural”, você realmente quer um comparador personalizado, que você pode usar no método Collections.sort ou o método Arrays.sort que leva um comparador.

Em termos da lógica específica que você está procurando implementar dentro do comparador, (números separados por pontos) eu não estou ciente de nenhuma implementação padrão existente disso, mas como você disse, não é um problema difícil.

EDIT: Em seu comentário, seu link você recebe aqui , o que faz um trabalho decente, se você não se importa com o fato de que é sensível a maiúsculas e minúsculas. Aqui está esse código modificado para permitir que você passe o String.CASE_INSENSITIVE_ORDER :

  /* * The Alphanum Algorithm is an improved sorting algorithm for strings * containing numbers. Instead of sorting numbers in ASCII order like * a standard sort, this algorithm sorts numbers in numeric order. * * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com * * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * */ import java.util.Comparator; /** * This is an updated version with enhancements made by Daniel Migowski, * Andre Bogus, and David Koelle * * To convert to use Templates (Java 1.5+): * - Change "implements Comparator" to "implements Comparator" * - Change "compare(Object o1, Object o2)" to "compare(String s1, String s2)" * - Remove the type checking and casting in compare(). * * To use this class: * Use the static "sort" method from the java.util.Collections class: * Collections.sort(your list, new AlphanumComparator()); */ public class AlphanumComparator implements Comparator { private Comparator comparator = new NaturalComparator(); public AlphanumComparator(Comparator comparator) { this.comparator = comparator; } public AlphanumComparator() { } private final boolean isDigit(char ch) { return ch >= 48 && ch < = 57; } /** Length of string is passed in for improved efficiency (only need to calculate it once) **/ private final String getChunk(String s, int slength, int marker) { StringBuilder chunk = new StringBuilder(); char c = s.charAt(marker); chunk.append(c); marker++; if (isDigit(c)) { while (marker < slength) { c = s.charAt(marker); if (!isDigit(c)) break; chunk.append(c); marker++; } } else { while (marker < slength) { c = s.charAt(marker); if (isDigit(c)) break; chunk.append(c); marker++; } } return chunk.toString(); } public int compare(String s1, String s2) { int thisMarker = 0; int thatMarker = 0; int s1Length = s1.length(); int s2Length = s2.length(); while (thisMarker < s1Length && thatMarker < s2Length) { String thisChunk = getChunk(s1, s1Length, thisMarker); thisMarker += thisChunk.length(); String thatChunk = getChunk(s2, s2Length, thatMarker); thatMarker += thatChunk.length(); // If both chunks contain numeric characters, sort them numerically int result = 0; if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0))) { // Simple chunk comparison by length. int thisChunkLength = thisChunk.length(); result = thisChunkLength - thatChunk.length(); // If equal, the first different number counts if (result == 0) { for (int i = 0; i < thisChunkLength; i++) { result = thisChunk.charAt(i) - thatChunk.charAt(i); if (result != 0) { return result; } } } } else { result = comparator.compare(thisChunk, thatChunk); } if (result != 0) return result; } return s1Length - s2Length; } private static class NaturalComparator implements Comparator { public int compare(String o1, String o2) { return o1.compareTo(o2); } } } 

Dê uma olhada nessa implementação. Deve ser o mais rápido possível, sem quaisquer expressões regulares ou manipulação de matriz ou chamadas de método, apenas alguns flags e muitos casos.

Isso deve classificar qualquer combinação de números dentro de seqüências de caracteres e oferecer suporte a números que são iguais e seguir em frente.

 public static int naturalCompare(String a, String b, boolean ignoreCase) { if (ignoreCase) { a = a.toLowerCase(); b = b.toLowerCase(); } int aLength = a.length(); int bLength = b.length(); int minSize = Math.min(aLength, bLength); char aChar, bChar; boolean aNumber, bNumber; boolean asNumeric = false; int lastNumericCompare = 0; for (int i = 0; i < minSize; i++) { aChar = a.charAt(i); bChar = b.charAt(i); aNumber = aChar >= '0' && aChar < = '9'; bNumber = bChar >= '0' && bChar < = '9'; if (asNumeric) if (aNumber && bNumber) { if (lastNumericCompare == 0) lastNumericCompare = aChar - bChar; } else if (aNumber) return 1; else if (bNumber) return -1; else if (lastNumericCompare == 0) { if (aChar != bChar) return aChar - bChar; asNumeric = false; } else return lastNumericCompare; else if (aNumber && bNumber) { asNumeric = true; if (lastNumericCompare == 0) lastNumericCompare = aChar - bChar; } else if (aChar != bChar) return aChar - bChar; } if (asNumeric) if (aLength > bLength && a.charAt(bLength) >= '0' && a.charAt(bLength) < = '9') // as number return 1; // a has bigger size, thus b is smaller else if (bLength > aLength && b.charAt(aLength) >= '0' && b.charAt(aLength) < = '9') // as number return -1; // b has bigger size, thus a is smaller else if (lastNumericCompare == 0) return aLength - bLength; else return lastNumericCompare; else return aLength - bLength; } 

Que tal usar o método split () de String, analisar a string numérica única e então compará-los um por um?

  @Test public void test(){ System.out.print(compare("1.12.4".split("\\."), "1.13.4".split("\\."),0)); } public static int compare(String[] arr1, String[] arr2, int index){ // if arrays do not have equal size then and comparison reached the upper bound of one of them // then the longer array is considered the bigger ( --> 2.2.0 is bigger then 2.2) if(arr1.length < = index || arr2.length <= index) return arr1.length - arr2.length; int result = Integer.parseInt(arr1[index]) - Integer.parseInt(arr2[index]); return result == 0 ? compare(arr1, arr2, ++index) : result; } 

Eu não verifiquei os casos de canto, mas isso deve funcionar e é bem compacto

Ele concatia os dígitos e os compara. E se não for aplicável, continua.

 public int compare(String o1, String o2) { if(o1 == null||o2 == null) return 0; for(int i = 0; i Integer.valueOf(dig2)) return 1; } if(o1.charAt(i)o2.charAt(i)) return 1; } return 0; 

}

Pode ser uma resposta tardia. Mas minha resposta pode ajudar alguém que precisa de um comparador como esse.

Eu verifiquei alguns outros comparadores também. Mas o meu parece pouco eficiente do que outros que comparei. Também tentei o que Yishai postou. O meu está tomando apenas metade do tempo como o mencionado para dados de um dataset alfanuméricos de 100 inputs.

 /** * Sorter that compares the given Alpha-numeric strings. This iterates through each characters to * decide the sort order. There are 3 possible cases while iterating, * * 
  • If both have same non-digit characters then the consecutive characters will be considered for * comparison.
  • * *
  • If both have numbers at the same position (with/without non-digit characters) the consecutive * digit characters will be considered to form the valid integer representation of the characters * will be taken and compared.
  • * *
  • At any point if the comparison gives the order(either > or < ) then the consecutive characters * will not be considered.
  • * * For ex., this will be the ordered O/P of the given list of Strings.(The bold characters decides * its order) 2b,100b,a1,A2y,a100, * * @author kannan_r * */ class AlphaNumericSorter implements Comparator { /** * Does the Alphanumeric sort of the given two string */ public int compare(String theStr1, String theStr2) { char[] theCharArr1 = theStr1.toCharArray(); char[] theCharArr2 = theStr2.toCharArray(); int aPosition = 0; if (Character.isDigit(theCharArr1[aPosition]) && Character.isDigit(theCharArr2[aPosition])) { return sortAsNumber(theCharArr1, theCharArr2, aPosition++ ); } return sortAsString(theCharArr1, theCharArr2, 0); } /** * Sort the given Arrays as string starting from the given position. This will be a simple case * insensitive sort of each characters. But at any given position if there are digits in both * arrays then the method sortAsNumber will be invoked for the given position. * * @param theArray1 The first character array. * @param theArray2 The second character array. * @param thePosition The position starting from which the calculation will be done. * @return positive number when the Array1 is greater than Array2
    * negative number when the Array2 is greater than Array1
    * zero when the Array1 is equal to Array2 */ private int sortAsString(char[] theArray1, char[] theArray2, int thePosition) { int aResult = 0; if (thePosition < theArray1.length && thePosition < theArray2.length) { aResult = (int)theArray1[thePosition] - (int)theArray2[thePosition]; if (aResult == 0) { ++thePosition; if (thePosition < theArray1.length && thePosition < theArray2.length) { if (Character.isDigit(theArray1[thePosition]) && Character.isDigit(theArray2[thePosition])) { aResult = sortAsNumber(theArray1, theArray2, thePosition); } else { aResult = sortAsString(theArray1, theArray2, thePosition); } } } } else { aResult = theArray1.length - theArray2.length; } return aResult; } /** * Sorts the characters in the given array as number starting from the given position. When * sorted as numbers the consecutive characters starting from the given position upto the first * non-digit character will be considered. * * @param theArray1 The first character array. * @param theArray2 The second character array. * @param thePosition The position starting from which the calculation will be done. * @return positive number when the Array1 is greater than Array2
    * negative number when the Array2 is greater than Array1
    * zero when the Array1 is equal to Array2 */ private int sortAsNumber(char[] theArray1, char[] theArray2, int thePosition) { int aResult = 0; int aNumberInStr1; int aNumberInStr2; if (thePosition < theArray1.length && thePosition < theArray2.length) { if (Character.isDigit(theArray1[thePosition]) && Character.isDigit(theArray1[thePosition])) { aNumberInStr1 = getNumberInStr(theArray1, thePosition); aNumberInStr2 = getNumberInStr(theArray2, thePosition); aResult = aNumberInStr1 - aNumberInStr2; if (aResult == 0) { thePosition = getNonDigitPosition(theArray1, thePosition); if (thePosition != -1) { aResult = sortAsString(theArray1, theArray2, thePosition); } } } else { aResult = sortAsString(theArray1, theArray2, ++thePosition); } } else { aResult = theArray1.length - theArray2.length; } return aResult; } /** * Gets the position of the non digit character in the given array starting from the given * position. * * @param theCharArr /the character array. * @param thePosition The position after which the array need to be checked for non-digit * character. * @return The position of the first non-digit character in the array. */ private int getNonDigitPosition(char[] theCharArr, int thePosition) { for (int i = thePosition; i < theCharArr.length; i++ ) { if ( !Character.isDigit(theCharArr[i])) { return i; } } return -1; } /** * Gets the integer value of the number starting from the given position of the given array. * * @param theCharArray The character array. * @param thePosition The position form which the number need to be calculated. * @return The integer value of the number. */ private int getNumberInStr(char[] theCharArray, int thePosition) { int aNumber = 0; for (int i = thePosition; i < theCharArray.length; i++ ) { if(!Character.isDigit(theCharArray[i])) { return aNumber; } aNumber += aNumber * 10 + (theCharArray[i] - 48); } return aNumber; } }

    O uso de RuleBasedCollator pode ser uma opção. Embora você tenha que adicionar todas as regras de ordenação antecipadamente, não é uma boa solução se você quiser levar em conta números maiores também.

    Adicionar personalizações específicas, como 2 < 10 é bastante fácil e pode ser útil para classificar identificadores de versão especiais como Trusty < Precise < Xenial < Yakkety .

     RuleBasedCollator localRules = (RuleBasedCollator) Collator.getInstance(); String extraRules = IntStream.range(0, 100).mapToObj(String::valueOf).collect(joining(" < ")); RuleBasedCollator c = new RuleBasedCollator(localRules.getRules() + " & " + extraRules); List a = asList("1-2", "1-02", "1-20", "10-20", "fred", "jane", "pic01", "pic02", "pic02a", "pic 5", "pic05", "pic 7", "pic100", "pic100a", "pic120", "pic121"); shuffle(a); a.sort(c); System.out.println(a);