Сортировка по строке, которая может содержать число
https://stackoverflow.com/questions/104599
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Мне нужно написать класс Java Comparator, который сравнивает строки, однако с одним поворотом.Если две строки, которые он сравнивает, одинаковы в начале и конце строки, а средняя часть, которая отличается, является целым числом, то сравните на основе числовых значений этих целых чисел.Например, я хочу, чтобы следующие строки заканчивались в порядке их отображения:
- ааа
- ввв 3 ссс
- ввв 12 ссс
- ссс 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());
Этот алгоритм нуждается в гораздо большем тестировании, но, похоже, он ведет себя довольно хорошо.
[РЕДАКТИРОВАТЬ] Я добавил еще несколько комментариев, чтобы было понятнее.Я вижу, что ответов гораздо больше, чем когда я начинал это кодировать...Но я надеюсь, что предоставил хорошую стартовую базу и / или несколько идей.
У Иэна Гриффитса из Microsoft есть реализация на C #, которую он называет Естественная Сортировка.Портирование на Java должно быть довольно простым, во всяком случае, проще, чем с C!
Обновить: Кажется, есть пример 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);
}
Я понимаю, что вы работаете на 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;
}
}
PS.Я хотел использовать 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 элементов, вы, вероятно, можете проигнорировать этот пункт.) Производительность имеет значение, поскольку скорость компаратора будет самым большим фактором скорости вашей сортировки (при условии, что алгоритм сортировки "идеален" для типичного списка).В вашем случае скорость компаратора будет зависеть в основном от размера строки.Строки кажутся довольно короткими, поэтому они, вероятно, не будут доминировать так сильно, как размер вашего списка.
Превращение каждой строки в кортеж string-number-string, а затем сортировка этого списка кортежей, как предложено в другом ответе, в некоторых ваших случаях завершится неудачей, поскольку у вас, по-видимому, будут появляться строки с несколькими числами.
Другая проблема - это корректность.В частности, если описанный вами алгоритм когда-нибудь разрешит 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, для всех, кто хочет решение 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
})
}
Моя проблема заключалась в том, что у меня есть списки, состоящие из комбинации буквенно-цифровых строк (например, 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, плюс несколько моих собственных настроек, чтобы заставить его работать именно так, как мне было нужно.
Из-за попытки упорядочить объекты, необходимости в компараторе, а также удаления дубликатов, одним из недостатков, который мне пришлось применить, было то, что я сначала должен был записать свои объекты в TreeMap, прежде чем записывать их в Treeset.Это может немного повлиять на производительность, но, учитывая, что списки будут содержать максимум около 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() в качестве стандартной справки.
В приведенном вами примере числа, которые вы хотите сравнить, окружены пробелами, в то время как другие числа - нет, так почему регулярное выражение не будет работать?
ввв 12 ссс
против.
eee 12 ddd jpeg2000 иии
Если вы пишете класс comparator, вам следует реализовать свой собственный метод compare, который будет сравнивать две строки посимвольно.Этот метод сравнения должен проверить, имеете ли вы дело с буквенными символами, цифровыми символами или смешанными типами (включая пробелы).Вам нужно будет определить, как вы хотите, чтобы действовал смешанный тип, идут ли цифры перед буквенными символами или после, где помещаются пробелы и т.д.
В Linux glibc предоставляет strverscmp(), он также доступен из gnulib для удобства переносимости.Однако по-настоящему "человеческая" сортировка имеет множество других причуд, например, "The Beatles" сортируются как "Битлз, The".Простого решения этой общей проблемы не существует.
