숫자를 포함할 수 있는 문자열을 기준으로 정렬
https://stackoverflow.com/questions/104599
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
문자열을 비교하는 Java Comparator 클래스를 작성해야 하지만 한 가지 방법이 있습니다.비교하는 두 문자열이 문자열의 시작과 끝이 같고, 가운데가 다른 부분이 정수인 경우 해당 정수의 숫자 값을 기준으로 비교합니다.예를 들어 다음 문자열이 표시되는 순서대로 끝나기를 원합니다.
- 아아아
- bbb 3ccc
- bbb 12ccc
- CCC 11
- ddd
- eee 3 ddd jpeg2000 eee
- eee 12 ddd jpeg2000 eee
보시다시피 문자열에 다른 정수가 있을 수 있으므로 정규식을 사용하여 정수를 분리할 수는 없습니다.나는 처음부터 일치하지 않는 비트를 찾을 때까지 문자열을 탐색한 다음, 일치하지 않는 비트를 찾을 때까지 끝에서 들어가서 중간에 있는 비트를 비교하는 것을 생각하고 있습니다. 정규 표현식 "[0-9]+", 비교하는 경우 숫자 비교를 수행하고, 그렇지 않으면 어휘 비교를 수행합니다.
더 좋은 방법이 있나요?
업데이트 문자열의 다른 숫자, 일치할 수 있는 숫자 주위에 공백이 없거나 다른 숫자에 공백이 있다고 보장할 수는 없다고 생각합니다.
해결책
웹사이트에서
"사람들은 소프트웨어와 다르게 숫자로 문자열을 정렬합니다.대부분의 정렬 알고리즘은 ASCII 값을 비교하므로 인간의 논리와 일치하지 않는 순서가 생성됩니다.문제를 해결하는 방법은 다음과 같습니다."
편집하다:다음은 Java 비교기 구현 그 사이트에서.
다른 팁
흥미로운 작은 도전이었고, 그것을 해결하는 것이 즐거웠습니다.
문제에 대한 나의 견해는 다음과 같습니다.
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());
이 알고리즘은 훨씬 더 많은 테스트가 필요하지만 꽤 잘 작동하는 것 같습니다.
[편집] 더 명확하게 설명하기 위해 몇 가지 설명을 추가했습니다.제가 코딩을 시작했을 때보다 훨씬 더 많은 답변이 있는 것 같습니다...하지만 좋은 시작 기반 및/또는 몇 가지 아이디어를 제공했으면 좋겠습니다.
여기서 제안하는 구현은 간단하고 효율적입니다.정규식이나 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);
}
나는 당신이 Java에 있다는 것을 알고 있지만 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);
}
}
이 스레드를 발견하기 전에 저는 비슷한 솔루션을 javascript로 구현했습니다.아마도 내 전략은 다른 구문에도 불구하고 당신을 잘 찾을 것입니다.위와 유사하게 비교되는 두 문자열을 구문 분석하고 둘 다 배열로 분할하여 문자열을 연속적인 숫자로 나눕니다.
...
var regex = /(\d+)/g,
str1Components = str1.split(regex),
str2Components = str2.split(regex),
...
즉, 'hello22goodbye 33' => ['안녕', 22, '안녕', 33];따라서 string1과 string2 사이의 쌍으로 배열 요소를 탐색하고, 일부 유형 강제 변환(예: 이 요소가 실제로 숫자입니까?)을 수행하고, 탐색하면서 비교할 수 있습니다.
실제 예시는 다음과 같습니다. http://jsfiddle.net/F46s6/3/
참고로, 현재는 정수 유형만 지원하지만 소수 값을 처리하는 것은 수정하기가 그리 어렵지 않습니다.
내 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);
}
캐릭터별로 패션을 비교해야 할 것 같아요.문자를 잡고 숫자 문자인 경우 계속 잡고 문자를 단일 숫자 문자열로 재조립하여 문자로 변환합니다. int.다른 문자열에 대해서도 반복한 다음 비교를 수행합니다.
짧은 답변:문맥에 따르면 이것이 단지 개인용으로 사용하기 위한 빠르고 더러운 코드인지 아니면 Goldman Sachs의 최신 내부 회계 소프트웨어의 핵심 부분인지 알 수 없으므로 다음과 같이 말하겠습니다.에우.그것은 다소 펑키한 정렬 알고리즘입니다.가능하다면 좀 덜 "구불구불한" 것을 사용해 보세요.
긴 답변:
귀하의 경우 즉시 떠오르는 두 가지 문제는 성능과 정확성입니다.비공식적으로는 속도가 빠른지 확인하고 알고리즘이 총 주문.
(물론 100개 이상의 항목을 정렬하지 않는 경우 이 단락을 무시해도 됩니다.) 성능이 중요합니다. 비교기의 속도가 정렬 속도의 가장 큰 요소가 되기 때문입니다(정렬 알고리즘이 다음과 같다고 가정). 일반적인 목록에 "이상적"입니다).귀하의 경우 비교기의 속도는 주로 문자열의 크기에 따라 달라집니다.문자열은 상당히 짧은 것 같으므로 아마도 목록 크기만큼 큰 비중을 차지하지는 않을 것입니다.
각 문자열을 문자열-숫자-문자열 튜플로 바꾼 다음 다른 답변에서 제안한 대로 이 튜플 목록을 정렬하면 여러 숫자가 나타나는 문자열이 분명히 나타나기 때문에 일부 경우에는 실패합니다.
또 다른 문제는 정확성입니다.특히, 설명하신 알고리즘이 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 순서입니다.또한 제거해야 하는 중복 항목도 있으므로 단일 항목만 얻습니다.
나는 또한 문자열을 사용하여 작업하는 것이 아니라 객체를 주문하고 객체 내의 특정 필드를 사용하여 올바른 순서를 얻습니다.
나에게 맞는 솔루션은 다음과 같습니다.
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());
}
});
여기 Stackoverflow에서 찾은 일부 코드와 내가 필요한 방식으로 작동하도록 내 자신의 일부 조정을 '차용'합니다.
개체를 주문하려고 하고 비교기와 중복 제거가 필요했기 때문에 내가 사용해야 했던 부정적인 퍼지 중 하나는 개체를 Treeset에 쓰기 전에 먼저 TreeMap에 써야 한다는 것이었습니다.성능에 약간 영향을 미칠 수 있지만 목록이 최대 약 80개 코드라는 점을 고려하면 문제가 되지 않습니다.
내 문자열 내부에 공백으로 구분된 세그먼트가 있는 비슷한 문제가 있었습니다.저는 이 방법으로 해결했습니다.
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;
}
보시다시피 저는 Apaches StringUtils.compare() 및 NumberUtils.compere()를 표준 도움말로 사용했습니다.
주어진 예에서 비교하려는 숫자 주위에는 공백이 있지만 다른 숫자에는 공백이 없습니다. 그러면 정규 표현식이 작동하지 않는 이유는 무엇입니까?
bbb 12 ccc
대
eee 12ddd JPEG2000 에에
비교기 클래스를 작성하는 경우 두 문자열을 문자별로 비교하는 자체 비교 메서드를 구현해야 합니다.이 비교 방법은 알파벳 문자, 숫자 또는 혼합 유형(공백 포함)을 다루고 있는지 확인해야 합니다.혼합 유형의 작동 방식, 숫자가 알파벳 문자 앞에 오는지 또는 뒤에 오는지, 공백이 들어가는 위치 등을 정의해야 합니다.
Linux에서 glibc는 strverscmp()를 제공하며 이식성을 위해 gnulib에서도 사용할 수 있습니다.그러나 진정한 "인간" 정렬에는 "The Beatles"가 "Beatles, The"로 정렬되는 것과 같은 다른 많은 특징이 있습니다.이 일반적인 문제에 대한 간단한 해결책은 없습니다.
