Объект списка отсортированных массивов в Котлине [дубликат]

Хотя вопрос задал 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
   })

}

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

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

I.e., 'hello22goodbye 33' => ['hello', 22, 'goodbye', 33]; Таким образом, вы можете перемещаться по элементам массивов в парах между строками1 и строкой2, делать какое-то принуждение типа (например, этот элемент действительно число?) И сравнивать по ходу.

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

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

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

интересная проблема, и здесь мое предлагаемое решение:

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

}

Я придумал довольно простую реализацию на 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]

В Linux glibc предоставляет strverscmp (), он также доступен из gnulib для переносимости. Однако действительно «человеческая» сортировка имеет множество других причуд, таких как «The Beatles», которые сортируются как «Beatles, The». Нет простого решения этой общей проблемы.

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

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

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 == null || str2 == null) {
            return 0;
        }

        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» для сохранения токенов, но я не мог заставить его работать с регулярным выражением, которое я использовал.

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

Короткий ответ: исходя из контекста, я не могу сказать, является ли это всего лишь очень быстро и грязным кодом для личного использования или ключевой частью последнего внутреннего программного обеспечения Goldman Sachs, поэтому я открою говоря: eww. Это довольно забавный алгоритм сортировки; попробуйте использовать что-то немного менее «извилистым», если сможете.

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

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

(Конечно, если вы не сортируете более 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

Интересная небольшая проблема, мне понравилось ее решать.

Вот мой подход к проблеме:

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

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

[EDIT] Я добавил еще несколько комментариев, чтобы быть более четкими. Я вижу, что ответов гораздо больше, чем когда я начал кодировать это ... Но я надеюсь, что я дал хорошую стартовую базу и / или некоторые идеи.

Ян Гриффитс из Microsoft имеет реализацию C #, которую он называет Natural Sorting .

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

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

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

bbb 12 ccc

vs.

eee 12 ddd jpeg2000 eee

Мои 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);
        }

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