it-swarm-eu.dev

Seřadit na řetězec, který může obsahovat číslo

Musím napsat třídu Java Comparator, která srovnává Strings, ale s jedním twistem. Pokud jsou dva řetězce, které porovnáváte, stejné na začátku a na konci řetězce, jsou stejné a střední část, která se liší, je celé číslo, pak porovnejte na základě číselných hodnot těchto celých čísel. Například chci, aby následující řetězce skončily v pořadí, v jakém jsou zobrazeny:

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

Jak vidíte, v řetězci mohou být jiná celá čísla, takže nemohu použít regulární výrazy, abych vylomil celé číslo. Přemýšlím jen o tom, že budu procházet struny od začátku, dokud nenajdu kousek, který neodpovídá, a pak odcházím od konce, dokud nenajdu bit, který neodpovídá, a pak porovnávám bit uprostřed. regulární výraz "[0-9] +", a pokud to porovná, pak dělá numerické srovnání, jinak dělá lexikální srovnání.

Existuje lepší způsob?

Update Nemyslím si, že mohu zaručit, že ostatní čísla v řetězci, které se mohou shodovat, nemají kolem sebe mezery, nebo že ty, které se liší, mají mezery.

71
Paul Tomblin

Alfanumový algoritmus

Z webu

"Lidé třídí řetězce s čísly odlišnými od softwaru. Většina třídicích algoritmů porovnává hodnoty ASCII, což vytváří uspořádání, které je v rozporu s lidskou logikou. Zde je návod, jak to opravit."

Edit: Zde je odkaz na Java Comparator Implementation z tohoto webu.

96
ScArcher2

Zajímavá malá výzva, užil jsem si to.

Zde je můj problém s tímto problémem:

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

Tento algoritmus vyžaduje mnohem více testování, ale zdá se, že se chová spíše pěkně.

[EDIT] Přidal jsem několik dalších komentářů, abych byl jasnější. Vidím, že existuje mnohem více odpovědí, než když jsem to začal kódovat ... Ale doufám, že jsem poskytl dobrou výchozí základnu a/nebo nějaké nápady.

12
PhiLho

Ian Griffiths z Microsoftu má implementaci C #, kterou volá Natural Sorting . Portování do Javy by mělo být poměrně snadné, snadnější než z C!

UPDATE: Zdá se, že existuje Java příklad na eekboom , který to dělá, viz "compareNatural" a používejte jej jako svůj srovnávací nástroj k řazení.

8
Ray Hayes

Uvědomuji si, že jste v Javě, ale můžete se podívat, jak funguje StrCmpLogicalW. To je to, co Explorer používá k třídění jmen souborů ve Windows. Můžete se podívat na implementaci WINE zde .

5
Eclipse

Implementace, kterou zde navrhuji, je jednoduchá a účinná. Nepřiděluje žádnou další paměť, přímo ani nepřímo pomocí regulárních výrazů nebo metod, jako je například podřetězec (), split (), toCharArray () atd. 

Tato implementace nejprve jde přes oba řetězce hledat první charaktery, které jsou různé, u maximální rychlosti, bez dělat nějaké zvláštní zpracování během toho. Porovnání specifických čísel se spouští pouze v případě, že tyto znaky jsou obě číslice. Vedlejším efektem této implementace je, že číslice je považována za větší než jiná písmena, v protikladu k výchozímu lexikografickému řádu.

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);
}
5
Olivier OUDOT

Řetězec rozdělte do řádků písmen a číslic, takže "foo 12 bar" se stane seznamem ("foo", 12, "bar"), poté použijte seznam jako klíč řazení. Tímto způsobem budou čísla uspořádána v číselném pořadí, ne abecedně.

4
John Millikin

Přišel jsem s poměrně jednoduchou implementací v jazyce Java pomocí regulárních výrazů:

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

Jak to funguje:

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]

3
Helder Pereira

Alphanum algrothim je Nice, ale neodpovídá požadavkům na projekt, na kterém pracuji. Musím být schopen správně třídit záporná čísla a desetinná místa. Zde je implementace, kterou jsem přišel. Jakákoli zpětná vazba by byla velmi oceněna.

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. Chtěl jsem použít metodu Java.lang.String.split () a použít "lookahead/lookbehind", abych udržel tokeny, ale nemohl jsem ho dostat do práce s regulárním výrazem, který jsem používal.

2
JustinKSU

Moje 2 centy. Používám ho hlavně pro názvy souborů.

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

zajímavý problém, a zde mé navrhované řešení:

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

}
1

Před objevením tohoto vlákna jsem implementoval podobné řešení v javascriptu. Možná, že vás moje strategie najde i přes odlišnou syntaxi. Podobně jako výše, rozebírám dva řetězce, které se srovnávají, a rozděluji je na pole, dělící řetězce na spojitá čísla. 

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

Tj. 'Hello22goodbye 33' => ['hello', 22, 'sbohem', 33]; Tímto způsobem můžete procházet prvky polí v párech mezi řetězcem 1 a řetězcem 2, provádět nějaký typ donucování (například tento prvek je opravdu číslo?) A porovnávat při procházce.

Pracovní příklad zde: http://jsfiddle.net/F46s6/3/

Všimněte si, že v současné době podporuji pouze celočíselné typy, i když zpracování desetinných hodnot by nebylo příliš těžké na modifikaci.

1
cdaringe

Ačkoliv otázka položila Java řešení, pro každého, kdo chce scala řešení:

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
Bennie Krijger

Mým problémem bylo, že mám seznamy skládající se z kombinace alfanumerických řetězců (např. C22, C3, C5 atd.), Alfa řetězců (např. A, H, R atd.) A jen číslic (např. 99, 45 atd.), Které potřebují třídit pořadí A, C3, C5, C22, H, R, 45, 99. Také mám duplikáty, které je třeba odstranit, takže dostanu jen jeden záznam. 

Nejsem také jen pracovat s řetězci, objednávám objekt a používám konkrétní pole v objektu, abych získal správný řád.

Řešení, které pro mě funguje, je:

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

"Půjčuje si" nějaký kód, který jsem zde našel na Stackoverflow, a několik vylepšení, abych fungoval tak, jak jsem to potřeboval.

Kvůli pokusu o objednání objektů, které potřebují komparátor, stejně jako duplikované odstranění, jeden negativní fudge, který jsem musel použít, jsem musel nejprve napsat své objekty do TreeMapu předtím, než je napíšu do Stromesetu. Může to mít vliv na výkon, ale vzhledem k tomu, že seznam bude maximálně 80 kódů, neměl by to být problém.

0
mavisto

Krátká odpověď: na základě kontextu nemohu říci, zda se jedná pouze o rychlý a špinavý kód pro osobní použití, nebo o klíčovou součást nejnovějšího interního účetního softwaru společnosti Goldman Sachs, takže budu říkat: eww . To je spíše funky třídicí algoritmus; pokusit se použít něco trochu méně "twisty", pokud můžete.

Dlouhá odpověď:

Dva problémy, které ve vašem případě okamžitě napadnou, jsou výkonnost a správnost. Neformálně se ujistěte, že je rychlý a ujistěte se, že váš algoritmus je celkové objednání .

(Samozřejmě, pokud neřadíte více než 100 položek, můžete tento odstavec ignorovat.) Výkonnost je důležitá, protože rychlost komparátoru bude největším faktorem rychlosti vašeho druhu (za předpokladu, že algoritmus třídění je "ideální" do typického seznamu). Ve vašem případě bude rychlost komparátoru záviset především na velikosti řetězce. Řetězy se zdají být poměrně krátké, takže pravděpodobně nebudou dominovat ani velikosti vašeho seznamu.

Otočení každého řetězce na řetězec-řetězec-řetězec Tuple a pak třídění tohoto seznamu n-tic, jak bylo navrženo v jiné odpovědi, selže v některých případech, protože zřejmě bude mít řetězce s více čísly.

Dalším problémem je správnost. Konkrétně, pokud algoritmus, který jste popsali, někdy dovolí A> B> ...> A, pak váš druh bude deterministický. Ve vašem případě se obávám, že by to mohlo být, i když to nedokážu dokázat. Zvažte některé případy analýzy:

  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
Paul Brinkley

Myslím, že budete muset udělat srovnání na charakter-by-charakter módy. Uchopte postavu, je-li to číselný znak, udržujte grabování, poté znovu sestavte na znaky do jednoho číselného řetězce a převeďte je na int. Opakujte na druhý řetězec a teprve pak proveďte porovnání. 

0
sblundy