반응형
Java의 자연 정렬 순서 문자열 비교-내장되어 있습니까?
이 질문에 이미 답변이 있습니다.
- 숫자 21 답변을 포함 할 수있는 문자열로 정렬
자연스러운 정렬 순서 1 을 유지하는 일종의 문자열 비교 함수를 원합니다 . 이와 같은 것이 Java에 내장되어 있습니까? 나는 아무것도 찾을 수 없습니다 String 클래스를 하고, 비교기 클래스는 두 구현 알고있다.
나는 내 자신을 굴릴 수 있지만 (그다지 어려운 문제는 아니지만) 필요하지 않으면 바퀴를 다시 발명하지 않고 싶습니다.
특정 경우에는 정렬하려는 소프트웨어 버전 문자열이 있습니다. 따라서 "1.2.10.5"가 "1.2.9.1"보다 큰 것으로 간주되기를 원합니다.
1 "자연스러운"정렬 순서는 프로그래머에게만 의미가있는 "ascii-betical"정렬 순서와 달리 사람이 문자열을 비교하는 방식으로 문자열을 비교한다는 의미입니다. 즉, "image9.jpg"는 "image10.jpg"보다 작고 "album1set2page9photo1.jpg"는 "album1set2page10photo5.jpg"보다 작고 "1.2.9.1"은 "1.2.10.5"보다 작습니다.
자바에서 "자연스러운"순서 의미는 "사전"순서이므로 찾고있는 것과 같은 핵심 구현이 없습니다.
오픈 소스 구현이 있습니다.
다음은 하나입니다.
다음을 읽어보십시오.
이게 도움이 되길 바란다!
다른 사람들이 여기에서 언급 한 세 가지 Java 구현을 테스트 한 결과 작업이 약간 다르지만 예상했던 것과는 다릅니다.
AlphaNumericStringComparator 및 AlphanumComparator 모두 공백을 무시하지 않으므로 pic2앞에 배치됩니다 pic 1.
반면에 NaturalOrderComparator는 공백뿐만 아니라 있도록 모든 앞에 0이 아니라 무시 sig[1]선행을 sig[0].
성능과 관련하여 AlphaNumericStringComparator 는 다른 두 개보다 ~ x10 느립니다.
String은 Comparable을 구현하고 이것이 Java에서 자연스러운 순서입니다 (비교 인터페이스를 사용하여 비교). 문자열을 TreeSet에 넣거나 Collections 또는 Arrays 클래스를 사용하여 정렬 할 수 있습니다.
그러나 귀하의 경우 "자연 순서"를 원하지 않는 경우 사용자 지정 비교기가 필요합니다. 그런 다음 Collections.sort 메서드 또는 비교기를 사용하는 Arrays.sort 메서드에서 사용할 수 있습니다.
비교기 내에서 구현하려는 특정 논리 (점으로 구분 된 숫자)와 관련하여 기존 표준 구현에 대해서는 잘 모르지만 말씀하신대로 어려운 문제는 아닙니다.
편집 : 귀하의 코멘트, 귀하의 링크를 얻을 여기 당신이 대소 문자를 구별한다는 사실을 괜찮다면 괜찮은 일을한다. 다음은 다음을 전달할 수 있도록 수정 된 코드입니다 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<String>"
* - 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<String>
{
private Comparator<String> comparator = new NaturalComparator();
public AlphanumComparator(Comparator<String> 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<String> {
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
}
}
이 구현을 살펴보십시오. 정규식이나 배열 조작 또는 메서드 호출없이 가능한 한 빨리 처리해야합니다. 몇 개의 플래그와 많은 경우가 필요합니다.
This should sort any combination of numbers inside strings and properly support numbers which are equal and move on.
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;
}
How about using the split() method from String, parse the single numeric string and then compare them one by one?
@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;
}
I did not check the corner cases but that should work and it's quite compact
It concats the digits, then compares it. And if it's not applicable it continues.
public int compare(String o1, String o2) {
if(o1 == null||o2 == null)
return 0;
for(int i = 0; i<o1.length()&&i<o2.length();i++){
if(Character.isDigit(o1.charAt(i)) || Character.isDigit(o2.charAt(i)))
{
String dig1 = "",dig2 = "";
for(int x = i; x<o1.length() && Character.isDigit(o1.charAt(i)); x++){
dig1+=o1.charAt(x);
}
for(int x = i; x<o2.length() && Character.isDigit(o2.charAt(i)); x++){
dig2+=o2.charAt(x);
}
if(Integer.valueOf(dig1) < Integer.valueOf(dig2))
return -1;
if(Integer.valueOf(dig1) > Integer.valueOf(dig2))
return 1;
}
if(o1.charAt(i)<o2.charAt(i))
return -1;
if(o1.charAt(i)>o2.charAt(i))
return 1;
}
return 0;
}
Might be a late reply. But my answer can help someone else who needs a comparator like this.
I verified couple of other comparators too. But mine seems bit efficient than others I compared. Also tried the one that Yishai has posted. Mine is taking only half of the time as the mentioned one for data of alphanumeric data set of 100 entries.
/**
* 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,
*
* <li>If both have same non-digit characters then the consecutive characters will be considered for
* comparison.</li>
*
* <li>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.</li>
*
* <li>At any point if the comparison gives the order(either > or <) then the consecutive characters
* will not be considered.</li>
*
* For ex., this will be the ordered O/P of the given list of Strings.(The bold characters decides
* its order) <i><b>2</b>b,<b>100</b>b,a<b>1</b>,A<b>2</b>y,a<b>100</b>,</i>
*
* @author kannan_r
*
*/
class AlphaNumericSorter implements Comparator<String>
{
/**
* 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<br/>
* negative number when the Array2 is greater than Array1<br/>
* 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<br/>
* negative number when the Array2 is greater than Array1<br/>
* 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;
}
}
Using RuleBasedCollator might be an option as well. Though you'd have to add all the sort order rules in advance so it's not a good solution if you want to take larger numbers into account as well.
Adding specific customizations such as 2 < 10 is quite easy though and might be useful for sorting special version identifiers like 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<String> 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);
반응형
'Development Tip' 카테고리의 다른 글
| Is it possible to access the current Fragment being viewed by a ViewPager? (0) | 2020.11.05 |
|---|---|
| Does anything like number exist? (0) | 2020.11.05 |
| SurfaceHolder 콜백은 활동 수명주기와 어떤 관련이 있나요? (0) | 2020.11.05 |
| 연결 문자열에서 초기 카탈로그와 데이터베이스 키워드의 차이점 (0) | 2020.11.05 |
| ReactJS : 자식 구성 요소 내부 부모의 setState (0) | 2020.11.05 |