숫자를 포함 할 수있는 문자열을 기준으로 정렬
문자열을 비교하는 Java Comparator 클래스를 작성해야합니다. 비교중인 두 문자열이 문자열의 시작과 끝에서 동일하고 다른 중간 부분이 정수이면 해당 정수의 숫자 값을 기준으로 비교합니다. 예를 들어 다음 문자열이 표시되는 순서대로 끝나기를 원합니다.
- aaa
- bbb 3 ccc
- bbb 12 ccc
- ccc 11
- ddd
- eee 3 ddd jpeg2000 eee
- eee 12 ddd jpeg2000 eee
보시다시피 문자열에 다른 정수가있을 수 있으므로 정규식을 사용하여 정수를 구분할 수는 없습니다. 나는 처음부터 일치하지 않는 비트를 찾을 때까지 줄을 걷다가, 일치하지 않는 비트를 찾을 때까지 끝에서 걸어 간 다음 중간에있는 비트를 정규식 "[0-9] +", 비교하면 숫자 비교를 수행하고 그렇지 않으면 어휘 비교를 수행합니다.
더 좋은 방법이 있습니까?
업데이트 문자열의 다른 숫자, 일치 할 수있는 숫자, 주위에 공백이 없거나 다른 숫자에 공백이 있음을 보장 할 수 없다고 생각합니다.
웹 사이트에서
"사람들은 숫자가있는 문자열을 소프트웨어와 다르게 정렬합니다. 대부분의 정렬 알고리즘은 ASCII 값을 비교하여 인간의 논리와 일치하지 않는 순서를 생성합니다.이 문제를 해결하는 방법은 다음과 같습니다."
편집 : 여기에 해당 사이트에서 Java Comparator 구현에 대한 링크 가 있습니다.
재미있는 작은 도전, 나는 그것을 해결하는 것을 즐겼습니다.
문제에 대한 나의 견해는 다음과 같습니다.
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());
이 알고리즘은 훨씬 더 많은 테스트가 필요하지만 꽤 잘 작동하는 것 같습니다.
[편집] 좀 더 명확하게 설명을 추가했습니다. 나는 이것을 코딩하기 시작했을 때보 다 훨씬 더 많은 답이 있다는 것을 알았다. 그러나 나는 좋은 시작 기반 및 / 또는 몇 가지 아이디어를 제공하기를 바란다.
Microsoft의 Ian Griffiths는 Natural Sorting 이라고 부르는 C # 구현을 가지고 있습니다. Java로 포팅하는 것은 어쨌든 C에서보다 훨씬 쉽고 쉬워야합니다!
업데이트 : 이 작업 을 수행 하는 eekboom에 Java 예제가있는 것 같습니다 . "compareNatural"을 참조하고이를 비교 자로 사용하여 정렬합니다.
여기서 제안하는 구현은 간단하고 효율적입니다. substring (), split (), toCharArray () 등과 같은 정규식이나 메서드를 사용하여 직접 또는 간접적으로 추가 메모리를 할당하지 않습니다.
이 구현은 먼저 두 문자열에 걸쳐 특별한 처리를 수행하지 않고 최대 속도로 다른 첫 번째 문자를 검색합니다. 특정 숫자 비교는 이러한 문자가 모두 숫자 인 경우에만 트리거됩니다. 이 구현의 부작용은 숫자가 기본 사전 식 순서와 반대로 다른 문자보다 큰 것으로 간주된다는 것입니다.
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);
}
나는 당신이 자바에 있다는 것을 알고 있지만 StrCmpLogicalW가 어떻게 작동하는지 살펴볼 수 있습니다. Explorer가 Windows에서 파일 이름을 정렬하는 데 사용하는 것입니다. 여기 에서 WINE 구현을 볼 수 있습니다 .
문자열을 문자와 숫자로 나누어 "foo 12 bar"가 목록 ( "foo", 12, "bar")이 된 다음 목록을 정렬 키로 사용합니다. 이렇게하면 숫자가 알파벳순이 아닌 숫자 순으로 정렬됩니다.
정규식을 사용하여 Java에서 매우 간단한 구현을 생각해 냈습니다.
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)));
}
}
}
};
}
작동 방식은 다음과 같습니다.
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]
영숫자 algrothim 좋은이지만, 내가 일하고 있어요 프로젝트의 요구 사항과 일치하지 않습니다. 음수와 소수를 올바르게 정렬 할 수 있어야합니다. 여기에 내가 제안한 구현이 있습니다. 모든 의견을 많이 주시면 감사하겠습니다.
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;
}
}
추신. java.lang.String.split () 메서드를 사용하고 "lookahead / lookbehind"를 사용하여 토큰을 유지하고 싶었지만 사용중인 정규식으로 작동하도록 가져올 수 없었습니다.
흥미로운 문제, 그리고 여기 내 제안 된 해결책 :
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);
}
}
이 스레드를 발견하기 전에 자바 스크립트에서 유사한 솔루션을 구현했습니다. 아마도 내 전략은 다른 구문에도 불구하고 당신을 잘 찾을 것입니다. 위와 비슷하게 비교되는 두 문자열을 구문 분석하고 두 문자열을 배열로 분할하여 문자열을 연속 된 숫자로 나눕니다.
...
var regex = /(\d+)/g,
str1Components = str1.split(regex),
str2Components = str2.split(regex),
...
즉, 'hello22goodbye 33'=> [ 'hello', 22, 'goodbye', 33]; 따라서 string1과 string2 사이의 쌍으로 배열의 요소를 살펴보고, 어떤 유형 강제 변환 (예 :이 요소가 실제로 숫자입니까?)을 수행하고 걷는 동안 비교할 수 있습니다.
작업 예 : http://jsfiddle.net/F46s6/3/
10 진수 값을 처리하는 것이 수정하기 너무 어렵지는 않지만 현재 정수 유형 만 지원합니다.
내 2 센트. 잘 작동하고 있습니다. 주로 파일 이름으로 사용하고 있습니다.
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);
}
다른 구현을 비교하기 위해 프로젝트 를 만들었습니다 . 완전하지는 않지만 시작점입니다.
다음은 Alphanum Algorithm에 비해 다음과 같은 이점이있는 솔루션입니다.
- 3.25 배 더 빠름 ( Alphanum 설명 의 'Epilogue'장 데이터에서 테스트 됨 )
- 추가 메모리를 사용하지 않습니다 (문자열 분할 없음, 숫자 구문 분석 없음).
- 선행 0을 올바르게 처리합니다 (예 :
"0001"같음"1","01234"보다 작음"4567").
public class NumberAwareComparator implements Comparator<String>
{
@Override
public int compare(String s1, String s2)
{
int len1 = s1.length();
int len2 = s2.length();
int i1 = 0;
int i2 = 0;
while (true)
{
// handle the case when one string is longer than another
if (i1 == len1)
return i2 == len2 ? 0 : -1;
if (i2 == len2)
return 1;
char ch1 = s1.charAt(i1);
char ch2 = s2.charAt(i2);
if (Character.isDigit(ch1) && Character.isDigit(ch2))
{
// skip leading zeros
while (i1 < len1 && s1.charAt(i1) == '0')
i1++;
while (i2 < len2 && s2.charAt(i2) == '0')
i2++;
// find the ends of the numbers
int end1 = i1;
int end2 = i2;
while (end1 < len1 && Character.isDigit(s1.charAt(end1)))
end1++;
while (end2 < len2 && Character.isDigit(s2.charAt(end2)))
end2++;
int diglen1 = end1 - i1;
int diglen2 = end2 - i2;
// if the lengths are different, then the longer number is bigger
if (diglen1 != diglen2)
return diglen1 - diglen2;
// compare numbers digit by digit
while (i1 < end1)
{
if (s1.charAt(i1) != s2.charAt(i2))
return s1.charAt(i1) - s2.charAt(i2);
i1++;
i2++;
}
}
else
{
// plain characters comparison
if (ch1 != ch2)
return ch1 - ch2;
i1++;
i2++;
}
}
}
}
캐릭터별로 비교 해봐야 할 것 같아요. 문자를 잡고 숫자 문자 인 경우 계속 잡고 문자로 재 조립하여 단일 숫자 문자열로 변환하여 int. 다른 문자열에 대해 반복 한 다음 비교 만 수행하십시오.
짧은 대답 : 컨텍스트를 기반으로 볼 때 이것이 개인적인 사용을위한 빠르고 더러운 코드인지 아니면 Goldman Sachs의 최신 내부 회계 소프트웨어의 핵심 부분인지 알 수 없으므로 다음과 같이 말하겠습니다. . 그것은 다소 펑키 한 정렬 알고리즘입니다. 가능하다면 좀 덜 "꼬인"것을 사용하십시오.
긴 대답 :
귀하의 경우에 즉시 떠오르는 두 가지 문제는 성능과 정확성입니다. 비공식적으로 속도가 빠른지 확인하고 알고리즘이 총 주문 인지 확인하세요 .
(물론 약 100 개가 넘는 항목을 정렬하지 않는 경우이 단락을 무시할 수 있습니다.) 비교기의 속도가 정렬 속도에서 가장 큰 요소가되므로 성능이 중요합니다 (정렬 알고리즘이 다음과 같다고 가정). 일반적인 목록에 "이상적"). 귀하의 경우 비교기의 속도는 주로 문자열의 크기에 따라 다릅니다. 문자열은 상당히 짧아서 목록의 크기만큼 지배적이지 않을 것입니다.
각 문자열을 string-number-string tuple로 바꾸고 다른 답변에서 제안한 것처럼이 튜플 목록을 정렬하면 여러 숫자가 표시된 문자열이 분명히 나타나기 때문에 일부 경우에 실패합니다.
다른 문제는 정확성입니다. 특히 설명한 알고리즘이 A> B> ...> A를 허용하는 경우 정렬은 비 결정적입니다. 당신의 경우, 증명할 수는 없지만 그럴지도 모른다는 두려움이 있습니다. 다음과 같은 구문 분석 사례를 고려하십시오.
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
질문이 Java 솔루션을 요청했지만 스칼라 솔루션을 원하는 사람에게는 다음과 같습니다.
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
})
}
내 문제는 알파벳 숫자 문자열 (예 : C22, C3, C5 등), 알파 문자열 (예 : A, H, R 등) 및 정렬이 필요한 숫자 (예 : 99, 45 등)로 구성된 목록이 있다는 것입니다. 주문 A, C3, C5, C22, H, R, 45, 99. 또한 제거해야하는 중복 항목이 있으므로 단일 항목 만 얻습니다.
나는 또한 Strings로 작업하는 것이 아니라 Object를 주문하고 Object 내의 특정 필드를 사용하여 올바른 순서를 얻습니다.
나를 위해 일하는 것 같은 해결책은 다음과 같습니다.
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 'borrows' some code that I found here on Stackoverflow plus some tweaks of my own to get it working just how I needed it too.
Due to trying to order Objects, needing a comparator as well as duplicate removal, one negative fudge I had to employ was I first have to write my Objects to a TreeMap before writing them to a Treeset. It may impact performance a little but given that the lists will be a max of about 80 Codes, it shouldn't be a problem.
I had a similar problem where my strings had space-separated segments inside. I solved it in this way:
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;
}
As you can see I have used Apaches StringUtils.compare() and NumberUtils.compere() as a standard help.
In your given example, the numbers you want to compare have spaces around them while the other numbers do not, so why would a regular expression not work?
bbb 12 ccc
vs.
eee 12 ddd jpeg2000 eee
If you're writing a comparator class, you should implement your own compare method that will compare two strings character by character. This compare method should check if you're dealing with alphabetic characters, numeric characters, or mixed types (including spaces). You'll have to define how you want a mixed type to act, whether numbers come before alphabetic characters or after, and where spaces fit in etc.
On Linux glibc provides strverscmp(), it's also available from gnulib for portability. However truly "human" sorting has lots of other quirks like "The Beatles" being sorted as "Beatles, The". There is no simple solution to this generic problem.
참고URL : https://stackoverflow.com/questions/104599/sort-on-a-string-that-may-contain-a-number
'Development Tip' 카테고리의 다른 글
| 임시 변수가 내 프로그램을 느리게합니까? (0) | 2020.10.26 |
|---|---|
| 중괄호가있는 Javascript (ES6) const (0) | 2020.10.26 |
| JavaScript에서 이름 문자열로 동적으로 전역 변수 가져 오기 (0) | 2020.10.26 |
| _some 필드에서만 Enter 키를 통한 양식 제출 비활성화 (0) | 2020.10.26 |
| Tortoise SVN : 'theirs'를 사용하여 갈등을 해결합니다. (0) | 2020.10.26 |