Вопрос по string, algorithm, sorting, java – Сортировать по строке, которая может содержать число

71

Мне нужно написать класс компаратора Java, который сравнивает строки, однако с одним поворотом. Если две строки, которые он сравнивает, одинаковы в начале и конце строки одинаковы, а средняя часть, которая отличается, представляет собой целое число, то сравните на основе числовых значений этих целых. Например, я хочу, чтобы следующие строки заканчивались в том порядке, в котором они показаны:

aaa bbb 3 ccc bbb 12 ccc ccc 11 ddd eee 3 ddd jpeg2000 eee eee 12 ddd jpeg2000 eee

Как вы можете видеть, в строке могут быть и другие целые числа, поэтому я не могу просто использовать регулярные выражения для выделения любого целого числа. Я думаю о том, чтобы просто пройтись по струнам с самого начала, пока не найду бит, который не соответствует, затем войти с конца, пока не найду бит, который не соответствует, и затем сравнить бит по центру с регулярное выражение «[0-9] +», и если оно сравнивается, то выполняется числовое сравнение, в противном случае выполняется лексическое сравнение.

Есть ли способ лучше?

Update Я не думаю, что могу гарантировать, что другие числа в строке, те, которые могут совпадать, не имеют пробелов вокруг них или что те, которые отличаются, имеют пробелы.

Ваш Ответ

18   ответов
1

имен файлов.

    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);
        }
4

foo 12 bar & quot; становится списком («foo», 12, «bar»), затем использует список в качестве ключа сортировки. Таким образом, числа будут упорядочены по порядку, а не по алфавиту.

5

что вы в Java, но вы можете взглянуть на то, как работает StrCmpLogicalW. Это то, что Explorer использует для сортировки имен файлов в Windows. Вы можете посмотреть на реализацию WINEВот.

-1

которые вы хотите сравнить, имеют пробелы вокруг них, в то время как другие числа нет, так почему бы регулярное выражение не сработало?

БББ12 ссс

против

эээ 12 дддjpeg2000 еее

96

Алфавитный алгоритм

С веб-сайта

& quot; Люди сортируют строки с номерами не так, как программное обеспечение. Большинство алгоритмов сортировки сравнивают значения ASCII, что создает порядок, который не согласуется с человеческой логикой. Вот как это исправить.

Изменить: здесь ссылка наРеализация компаратора Java с этого сайта.

Это не решает проблему полностью - вам необходимо маркировать строку, которую нужно отсортировать, и сортировать, используя этот алгоритм для каждого фрагмента в отдельности.
Примечание. Пол принял ваш ответ, но мой алгоритм более близко подходит к его проблеме (так, как она это объяснила!), Например, «Allegia 51B Clasteron». Не проблема, он выбирает то, что соответствует его потребностям, и эта реализация Alphanum хороша (и мультиязычна!), Я просто хотел указать на это. :-П
Спасибо. Почему бы вам не подтолкнутьgist.github.com ?!
обратите внимание, что это GNU-менее лицензированный
Эта реализация имеет дело с конкретными примерами ввода OP, но для общего использования следует помнить, что она не справляется с числами, которые имеют начальные нули. Он считает, что "01234" больше, чем "5678".
0

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
   })

}
0

что вам придется сравнивать их по буквам. Возьмите символ, если он является числовым символом, продолжайте захват, затем соберите символы в единую числовую строку и преобразуйте вint, Повторите для другой строки, и только затем сделайте сравнение.

-1

он также доступен для переносимости в gnulib. Однако по-настоящему «человек» У сортировки есть много других причуд, таких как «Битлз». сортируется как "Beatles, The". Нет простого решения этой общей проблемы.

-1

вы должны реализовать свой собственный метод сравнения, который будет сравнивать две строки символ за символом. Этот метод сравнения должен проверять, имеете ли вы дело с буквенными, числовыми или смешанными типами (включая пробелы). Вам нужно будет определить, как вы хотите, чтобы смешанный тип действовал, должны ли цифры стоять перед буквенными символами или после, а также место в пробелах и т. Д.

2

Alphanum algrothim хорош, но он не соответствует требованиям для проекта, над которым я работаю. Мне нужно уметь правильно сортировать отрицательные и десятичные числа. Вот реализация, которую я придумал. Любая обратная связь будет высоко ценится.

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 () и использовать & quot; lookahead / lookbehind & quot; чтобы сохранить токены, но я не мог заставить его работать с регулярным выражением, которое я использовал.

@Holger Интересная идея. Я бы это реализовал и выложил как отдельный ответ. Я брошу вам голос.
Хорошее предложение. Код обновлен. Сканер также теперь закрыт с помощью «попробуйте с ресурсами».
Вы можете кэшировать свойPattern.compile() звонки, учитывая, что они вызваны сO(N log N) сложность!
Я не знаю, является ли он достаточно уникальным, чтобы заслуживать другого ответа. В конце концов, он все равно будет делать то же самое. Кстати, первоначальное утверждениеif(str1 == null || str2 == null) { return 0; } нарушается, так как это означает, что если любой из аргументовnullбудет сообщено, чтоequal на другой аргумент. Но когдаnull равно любому другому входу, все входы должны быть равны (transitivity правило). Самое простое решение - не поддерживатьnull совсем. В противном случае вам придется использовать что-то вродеif(str1 == str2) return 0; if(str1 == null) return 1; if(str2 == null) return -1;.
Вместо того, чтобы иметь дело сScannerВы могли бы просто позвонитьNUMBER_PATTERN.matcher(s)с последующим повторным звонкомfind на возвращенномMatcher, Самое замечательное в том, что устройство сопоставления скажет вам начальную и конечную позиции для каждого совпадения, делая всю операцию разбиения тривиальной. И это не ресурс, требующийtry(…) {…} блок.
0

в зависимости от контекста я не могу сказать, является ли это просто быстрым и грязным кодом для личного использования или ключевой частью Goldman Sachs & apos; последнее программное обеспечение внутреннего учета, поэтому я открою, сказав: Eww. Это довольно прикольный алгоритм сортировки; попробуйте использовать что-то немного менее "извилистое" если ты можешь.

Длинный ответ:

Две проблемы, которые сразу приходят на ум в вашем случае, это производительность и правильность. Неформально, убедитесь, что это быстро, и убедитесь, что ваш алгоритмобщий заказ.

(Конечно, если вы не сортируете более 100 элементов, вы, вероятно, можете не учитывать этот абзац.) Производительность имеет значение, поскольку скорость компаратора будет самым большим фактором скорости вашего рода (если предположить, что алгоритм сортировки «идеальный» к типичному списку). В вашем случае скорость компаратора будет зависеть главным образом от размера строки. Строки кажутся довольно короткими, поэтому они, вероятно, не будут доминировать над размером вашего списка.

Превращение каждой строки в кортеж string-number-string и последующая сортировка этого списка кортежей, как предлагается в другом ответе, в некоторых случаях не удастся, поскольку у вас, очевидно, появятся строки с несколькими числами.

Другая проблема - правильность. В частности, если описанный вами алгоритм когда-нибудь разрешит A & gt; B & gt; ... & gt; А, тогда ваш вид будет недетерминированным. В вашем случае я боюсь, что это возможно, хотя я не могу это доказать. Рассмотрим некоторые случаи разбора, такие как:

  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
12

Вот мой взгляд на проблему:

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());

Этот алгоритм требует гораздо большего тестирования, но, похоже, ведет себя довольно хорошо.

[РЕДАКТИРОВАТЬ] Я добавил еще несколько комментариев, чтобы быть более понятным. Я вижу, что ответов гораздо больше, чем когда я начал это кодировать ... Но я надеюсь, что предоставил хорошую стартовую базу и / или некоторые идеи.

хороший! Дополнительная ноль и экземпляр проверки String тоже подойдет
@HRgiger У вас есть пункт о проверке нуля, я предположил, что массив был "вменяемым". Но сегодня я бы просто отказался от синтаксиса до Java 1.5 и использовал дженерики, а не instanceof.
1

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);
    }

}
5

которую я предлагаю здесь, проста и эффективна. Он не выделяет никакой дополнительной памяти, прямо или косвенно, используя регулярные выражения или методы, такие как 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);
}
3

ных выражений:

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]

8

Натуральная сортировка, Портировать на Java должно быть довольно легко, проще, чем на C!

UPDATE: Кажется, есть пример Java наeekboom что делает это, см. "CompareNatural" и используйте это как свой компаратор для сортировки.

0

что у меня есть списки, состоящие из комбинации буквенно-цифровых строк (например, 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 кодов, это не должно быть проблемой.

1

ожно, моя стратегия найдет вас хорошо, несмотря на другой синтаксис. Как и выше, я анализирую две сравниваемые строки и разделяю их на массивы, разделяя строки на непрерывные числа.

...
var regex = /(\d+)/g,
    str1Components = str1.split(regex),
    str2Components = str2.split(regex),
...

То есть, "привет, до свидания, 33"; = & GT; ['привет', 22, 'до свидания', 33]; Таким образом, вы можете ходить по массивам & apos; элементы в парах между string1 и string2, выполняют какое-либо приведение типов (например, действительно ли этот элемент является числом?) и сравнивают по ходу работы.

Рабочий пример здесь:http://jsfiddle.net/F46s6/3/

Обратите внимание, что в настоящее время я поддерживаю только целочисленные типы, хотя обработка десятичных значений не будет слишком сложной для модификации.

Похожие вопросы