it-swarm-tr.com

Sayı içerebilen bir dizgede sıralama

Dizeleri karşılaştıran, ancak bir bükülme ile bir Java Comparator sınıfı yazmam gerekiyor. Karşılaştığı iki dize, dizenin başında ve sonunda aynıysa ve farklı olan orta kısım bir tamsayıysa, o zaman tamsayıların sayısal değerlerine göre karşılaştırın. Örneğin, aşağıdaki dizelerin gösterildikleri sırada bitmesini istiyorum:

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

Gördüğünüz gibi, dizgede başka tamsayılar olabilir, bu yüzden herhangi bir tamsayıyı dağıtmak için normal ifadeleri kullanamıyorum. Dizgileri baştan başa, eşleşmeyen bir parça bulana kadar, sonra da en sonunda eşleşmeyen bir parça bulana kadar yürüdüğümü düşünüyorum ve sonra ortadaki biti karşılaştırarak normal ifade "[0-9] +", ve eğer karşılaştırırsa, sayısal bir karşılaştırma yapıyor, aksi halde sözcüksel bir karşılaştırma yapıyor.

Daha iyi bir yolu var mı?

Güncelleme Dizedeki diğer sayıların, eşleşebilecek sayıların, etraflarında boşluklar olmadığını veya farklı olanların boşluk içerdiğini garanti edemeyeceğimi sanmıyorum.

71
Paul Tomblin

Alphanum Algoritması

Web sitesinden

"İnsanlar dizeleri yazılımdan farklı sayılarla sıralar. Çoğu sıralama algoritması, insan mantığına uygun olmayan bir düzen üreten ASCII değerlerini karşılaştırır.

Düzenleme: İşte bu siteden Java Karşılaştırıcı Uygulaması için bir link.

96
ScArcher2

İlginç küçük bir meydan okuma, çözmekten keyif aldım.

İşte benim problemim:

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

Bu algoritmanın çok daha fazla test edilmesi gerekiyor, ancak oldukça iyi davranıyor gibi görünüyor.

[EDIT] Daha net olmak için bazı yorumlar ekledim. Bunu kodlamaya başladığımdan çok daha fazla cevap olduğunu görüyorum ... Ama umarım iyi bir başlangıç ​​üssü ve/veya bazı fikirler sunmuşumdur.

12
PhiLho

Microsoft’un Ian Griffiths’inde C # uygulaması var Natural Sorting . Java'ya taşıma işlemi C'den daha kolay, daha kolay olmalı!

UPDATE:eekboom üzerinde bir Java örneği var gibi görünüyor, bunu yapan "compareNatural" bölümüne bakın ve bunu sıralamak için karşılaştırıcınız olarak kullanın.

8
Ray Hayes

Java'da olduğunun farkındayım, ama StrCmpLogicalW'ın nasıl çalıştığına bakabilirsin. Explorer’da Windows’taki dosya adlarını sıralamak için kullanılan budur. WINE uygulamasına bakabilirsiniz here .

5
Eclipse

Burada önerdiğim uygulama basit ve etkili. Subring (), split (), toCharArray (), vb. Gibi normal ifadeler veya yöntemler kullanarak doğrudan veya dolaylı olarak herhangi bir fazladan bellek ayırmaz. 

Bu uygulama, ilk önce, her iki dizeden geçerek, bu sırada herhangi bir özel işlem yapmadan, maksimum hızda farklı olan ilk karakterleri arar. Belirli sayı karşılaştırması, yalnızca bu karakterlerin her ikisi de rakam olduğunda tetiklenir. Bu uygulamanın bir yan etkisi, bir basamağın varsayılan harfbilimsel sıranın aksine, diğer harflerden daha büyük olarak kabul edilmesidir.

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

Dize harflerin ve sayıların satırlarına bölün, böylece "foo 12 bar" liste haline gelir ("foo", 12, "bar"), ardından listeyi sıralama anahtarı olarak kullanın. Bu şekilde sayılar, alfabetik olarak değil, sayısal olarak sıralanacaktır.

4
John Millikin

Düzenli ifadeler kullanarak Java'da oldukça basit bir uygulama buldum:

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

İşte nasıl çalışıyor:

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 Güzel, ancak üzerinde çalıştığım bir projenin gereksinimlerini karşılamadı. Negatif sayıları ve ondalık sayıları doğru şekilde sıralayabilmem gerekiyor. İşte geldiğim uygulama. Herhangi bir geri bildirim çok takdir edilecektir.

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 () yöntemini kullanmak ve belirteçleri tutmak için "lookahead/lookbehind" kullanmak istedim, ancak kullandığım normal ifade ile çalışmasını sağlayamadım.

2
JustinKSU

2 sentim. Benim için iyi çalışıyor. Genelde dosya isimleri için kullanıyorum.

    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

ilginç bir problem ve işte önerdiğim çözüm:

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

Bu konuyu keşfetmeden önce, javascript'te benzer bir çözüm kullandım. Belki farklı stratejime rağmen stratejim seni iyi bulacak. Yukarıdakine benzer şekilde, karşılaştırılan iki dizeyi ayrıştırırım ve dizeleri sürekli sayılara bölerek her ikisini de dizilere bölerim. 

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

Yani, 'merhaba 22 hoşçakal 33' => ['merhaba', 22, 'hoşçakal', 33]; Böylece, dizilerin elementleri string1 ve string2 arasındaki çiftler halinde yürüyebilir, bir tür zorlama yapabilir (bu element gerçekten bir sayı mı?) Ve yürürken karşılaştırabilirsiniz.

Burada çalışan örnek: http://jsfiddle.net/F46s6/3/

Unutmayın, şu anda yalnızca tamsayı türlerini destekliyorum, ancak ondalık değerleri kullanmak bir değişiklik için çok zor olmaz.

1
cdaringe

Soru bir Java çözümü sorsa da, bir scala çözümü isteyen herkes için:

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

Benim sorunum, alfa sayısal dizeleri (örneğin C22, C3, C5 vb.), Alfa dizeleri (örn. A, H, R vb.) Ve sıralaması gereken sadece rakamlardan (ör. 99, 45 vb.) Oluşan bir listeden oluşuyordu. A, C3, C5, C22, H, R, 45, 99 sıralarındadır. Ayrıca kaldırılması gereken kopyalar var, bu yüzden sadece tek bir giriş alacağım. 

Ayrıca sadece Strings ile çalışmıyorum, bir Nesne sipariş ediyorum ve doğru sıralamayı elde etmek için Nesne içinde belirli bir alanı kullanıyorum.

Benim için işe yarayan bir çözüm:

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'ta bulduğum bazı kodları ve de ihtiyacım olan şekilde çalışmasını sağlamak için kendime ait bazı kodları 'ödünç alıyor'.

Nesneler sipariş etmeye çalıştığım için, karşılaştırmalı ve aynı zamanda yinelenen kaldırmaya ihtiyaç duyduğum için, kullanmam gereken bir negatif şekerleme, önce Nesnelerimi bir Ağaç setine yazmadan önce bir Ağaç Haritasına yazmak zorunda kalmamdı. Performansı biraz etkileyebilir ancak listelerin maksimum 80 Kod olacağı göz önüne alındığında sorun olmamalıdır.

0
mavisto

İplerimde boşluklarla ayrılmış kısımların olduğu yerlerde de benzer bir problem vardı. Bu şekilde çözdüm:

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

Gördüğünüz gibi Apaches StringUtils.compare () ve NumberUtils.compere () 'i standart bir yardım olarak kullandım.

0
Sasa

Kısa cevap: Bağlama dayanarak, bunun kişisel kullanım için sadece hızlı ve kirli bir kod mu yoksa Goldman Sachs'in en son dahili muhasebe yazılımının önemli bir parçası mı olduğunu söyleyemem, bu yüzden şunu söyleyerek açacağım: eww . Bu oldukça korkak bir sıralama algoritması; eğer mümkünse biraz daha "bükülmez" bir şey kullanmaya çalışın.

Uzun cevap:

Durumunuzda hemen aklınıza gelen iki konu performans ve doğruluktur. Gayri resmi olarak, hızlı olduğundan ve algoritmanızın total order olduğundan emin olun.

(Tabii ki, yaklaşık 100'den fazla öğeyi sıralamıyorsanız, muhtemelen bu paragrafı göz ardı edebilirsiniz.) Karşılaştırma hızının, sıralama hızınızın en büyük faktörü olacağı için, performans önemlidir (sıralama algoritmasının, Tipik listeye "ideal"). Sizin durumunuzda, karşılaştırıcının hızı esas olarak dizenin boyutuna bağlı olacaktır. Dizeler oldukça kısa görünüyor, bu nedenle muhtemelen listenizin boyutuna kadar hakim olmayacaklar.

Her dizgiyi string-string-string Tuple'a çevirmek ve ardından bu tuples listesini başka bir cevapta önerildiği gibi sıralamak, bazı durumlarda başarısız olacaktır, çünkü görünüşe göre birden fazla sayıya sahip olan karakter dizileri olacaktır.

Diğer sorun doğruluktur. Spesifik olarak, tanımladığınız algoritma A> B> ...> A 'ya izin verirse, sıralamanız deterministik olmaz. Senin durumunda, ispatlayamasam da olabileceğinden korkuyorum. Aşağıdaki gibi ayrıştırma durumlarını göz önünde bulundurun:

  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

Bence karakter bazında moda karşılaştırması yapmanız gerekecek. Bir karakter kapmak, sayı karakteri ise, kapmaya devam etmek, ardından karakterleri tek bir sayı dizesine yeniden monte etmek ve onu int haline dönüştürmek. Diğer dizgede tekrarlayın ve ancak o zaman karşılaştırmayı yapın. 

0
sblundy