Сортировать по строке, которая может содержать число - PullRequest
71 голосов
/ 19 сентября 2008

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

  • ааа
  • BBB 3 CCC
  • bbb 12 ccc
  • куб. См 11
  • 1012 * ддд *
  • eee 3 ddd jpeg2000 eee
  • ее 12 ддп jpeg2000 ее

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

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

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

Ответы [ 18 ]

1 голос
/ 22 июля 2012

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

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

}
0 голосов
/ 09 ноября 2018

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

0 голосов
/ 03 мая 2016

Несмотря на то, что этот вопрос задан решением 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
   })

}
0 голосов
/ 19 сентября 2008

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

0 голосов
/ 19 сентября 2008

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

bbb 12 ccc

против

eee 12 ddd jpeg2000 eee

0 голосов
/ 19 сентября 2008

Краткий ответ: исходя из контекста, я не могу сказать, является ли это просто быстрым и грязным кодом для личного использования или ключевой частью новейшего программного обеспечения для внутреннего учета 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
0 голосов
/ 19 сентября 2008

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

0 голосов
/ 19 сентября 2008

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...