قم بالفرز على سلسلة قد تحتوي على رقم
https://stackoverflow.com/questions/104599
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أحتاج إلى كتابة فئة Java Comparator التي تقارن السلاسل، ولكن بلمسة واحدة.إذا كانت السلسلتان اللتان تتم مقارنتهما متماثلتين في بداية السلسلة ونهايتها، والجزء الأوسط الذي يختلف هو عدد صحيح، فقم بالمقارنة بناءً على القيم الرقمية لتلك الأعداد الصحيحة.على سبيل المثال، أريد أن تنتهي السلاسل التالية بالترتيب الذي تظهر به:
- aaa
- بي بي بي 3 سي سي سي
- بي بي بي 12 سي سي
- سي سي سي 11
- ddd
- إيي 3 دي دي جي بي إي جي 2000 إيي
- إيي 12 دي دي جي بي إي جي 2000 إيي
كما ترون، قد تكون هناك أعداد صحيحة أخرى في السلسلة، لذلك لا يمكنني استخدام التعبيرات العادية لتقسيم أي عدد صحيح.أفكر في المشي على الأوتار من البداية حتى أجد جزءًا غير متطابق، ثم المشي من النهاية حتى أجد جزءًا غير مطابق، ثم مقارنة الجزء الموجود في المنتصف بالجزء الموجود التعبير النمطي "[0-9]+"، وإذا قارن فيتم مقارنة رقمية، وإلا يتم إجراء مقارنة معجمية.
هل هناك طريقة أفضل؟
تحديث لا أعتقد أنني أستطيع أن أضمن أن الأرقام الأخرى في السلسلة، تلك التي قد تتطابق، لا تحتوي على مسافات حولها، أو أن الأرقام التي تختلف بها مسافات.
المحلول
من الموقع
"يقوم الأشخاص بفرز السلاسل ذات الأرقام بشكل مختلف عن البرامج.تقارن معظم خوارزميات الفرز قيم ASCII، مما ينتج عنه ترتيب غير متوافق مع المنطق البشري.وإليك كيفية إصلاحه."
يحرر:وهنا رابط ل تنفيذ مقارنة جافا من ذلك الموقع.
نصائح أخرى
تحدي صغير مثير للاهتمام، لقد استمتعت بحله.
وهنا رأيي في المشكلة:
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());
تحتاج هذه الخوارزمية إلى المزيد من الاختبارات، ولكن يبدو أنها تعمل بشكل جيد.
[تحرير] أضفت بعض التعليقات الأخرى لتكون أكثر وضوحا.أرى أن هناك إجابات أكثر بكثير مما كانت عليه عندما بدأت في ترميز هذا ...لكني آمل أن أكون قد قدمت قاعدة انطلاق جيدة و/أو بعض الأفكار.
لدى إيان غريفيث من Microsoft تطبيق C# يسميه الفرز الطبيعي.يجب أن يكون النقل إلى Java سهلاً إلى حد ما، وأسهل من C على أي حال!
تحديث: يبدو أن هناك مثال Java على ekboom الذي يفعل هذا، راجع "compareNatural" واستخدمه كمقارن للأنواع.
التنفيذ الذي أقترحه هنا بسيط وفعال.ولا يخصص أي ذاكرة إضافية، بشكل مباشر أو غير مباشر باستخدام التعبيرات أو الأساليب العادية مثل السلسلة الفرعية ()، والتقسيم ()، و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);
}
أدرك أنك تستخدم جافا، ولكن يمكنك إلقاء نظرة على كيفية عمل StrCmpLogicalW.إنه ما يستخدمه Explorer لفرز أسماء الملفات في Windows.يمكنك إلقاء نظرة على تنفيذ WINE هنا.
قم بتقسيم السلسلة إلى مجموعات من الحروف والأرقام، بحيث تصبح "foo 12 bar" هي القائمة ("foo"، 12، "bar")، ثم استخدم القائمة كمفتاح الفرز.بهذه الطريقة سيتم ترتيب الأرقام حسب الترتيب الرقمي، وليس الأبجدي.
لقد توصلت إلى تطبيق بسيط جدًا في 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]
ال ألفانوم برنامج algrothim جميل، لكنه لا يتوافق مع متطلبات المشروع الذي أعمل عليه.يجب أن أكون قادرًا على فرز الأرقام السالبة والكسور العشرية بشكل صحيح.هنا هو التنفيذ الذي توصلت إليه.ان أي ردود فعل يحظى بتقدير كبير.
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;
}
}
ملاحظة.كنت أرغب في استخدام طريقة java.lang.String.split() واستخدام "lookahead/lookbehind" للاحتفاظ بالرموز المميزة، لكن لم أتمكن من جعلها تعمل مع التعبير العادي الذي كنت أستخدمه.
مشكلة مثيرة للاهتمام، وهنا الحل المقترح:
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);
}
}
قبل اكتشاف هذا الموضوع، قمت بتنفيذ حل مماثل في جافا سكريبت.ربما ستجدك استراتيجيتي جيدًا، على الرغم من اختلاف تركيب الجملة.كما هو مذكور أعلاه، أقوم بتحليل السلسلتين الجاري مقارنتهما، وتقسيمهما إلى مصفوفات، وتقسيم السلاسل بأرقام متصلة.
...
var regex = /(\d+)/g,
str1Components = str1.split(regex),
str2Components = str2.split(regex),
...
على سبيل المثال، 'hello22goodbye 33' => ['hello', 22, 'goodbye', 33];وبالتالي، يمكنك التنقل عبر عناصر المصفوفات في أزواج بين السلسلة 1 والسلسلة 2، وإجراء بعض عمليات الإكراه على الكتابة (مثل، هل هذا العنصر رقم حقًا؟)، والمقارنة أثناء المشي.
مثال العمل هنا: http://jsfiddle.net/F46s6/3/
لاحظ أنني أدعم حاليًا الأنواع الصحيحة فقط، على الرغم من أن التعامل مع القيم العشرية لن يكون صعبًا للغاية عند التعديل.
سنتي 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);
}
أعتقد أنه سيتعين عليك إجراء المقارنة على أساس كل حرف على حدة.احصل على حرف، إذا كان حرفًا رقميًا، استمر في الإمساك به، ثم أعد تجميع الأحرف في سلسلة رقمية واحدة وقم بتحويلها إلى int.كرر ذلك مع السلسلة الأخرى، وعندها فقط قم بإجراء المقارنة.
اجابة قصيرة:استنادًا إلى السياق، لا يمكنني معرفة ما إذا كان هذا مجرد رمز سريع وقذر للاستخدام الشخصي، أو جزء أساسي من أحدث برامج المحاسبة الداخلية لـ Goldman Sachs، لذلك سأبدأ بالقول:eww.هذه خوارزمية فرز غير تقليدية إلى حد ما؛حاول استخدام شيء أقل "ملتويًا" إذا استطعت.
اجابة طويلة:
المسألتان اللتان تتبادران إلى ذهنك على الفور في حالتك هما الأداء والصحة.بشكل غير رسمي، تأكد من أنه سريع، وتأكد من أن الخوارزمية الخاصة بك هي الطلب الكلي.
(بالطبع، إذا كنت لا تقوم بفرز أكثر من حوالي 100 عنصر، فمن المحتمل أن تتجاهل هذه الفقرة.) الأداء مهم، حيث أن سرعة المقارنة ستكون العامل الأكبر في سرعة الفرز (بافتراض أن خوارزمية الفرز هي "مثالية" للقائمة النموذجية).في حالتك، ستعتمد سرعة المقارنة بشكل أساسي على حجم السلسلة.يبدو أن السلاسل قصيرة إلى حد ما، لذلك ربما لن تهيمن على حجم قائمتك.
إن تحويل كل سلسلة إلى مجموعة من سلسلة أرقام السلسلة ثم فرز قائمة المجموعات هذه، كما هو مقترح في إجابة أخرى، سوف يفشل في بعض الحالات، حيث يبدو أنه سيكون لديك سلاسل تحتوي على أرقام متعددة تظهر.
والمشكلة الأخرى هي الصواب.على وجه التحديد، إذا كانت الخوارزمية التي وصفتها ستسمح بـ A > B > ...> أ، فإن تصنيفك سيكون غير حتمي.في حالتك، أخشى أن يكون الأمر كذلك، على الرغم من أنني لا أستطيع إثبات ذلك.النظر في بعض حالات التحليل مثل:
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
على الرغم من أن السؤال طرح حل جافا، لمن يريد حل سكالا:
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
})
}
كانت مشكلتي هي أن لدي قوائم تتكون من مجموعة من السلاسل الأبجدية الرقمية (مثل 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 رمزًا، فلا ينبغي أن يكون ذلك مشكلة.
واجهت مشكلة مماثلة حيث كانت سلاسلي تحتوي على أجزاء مفصولة بمسافات بداخلها.لقد قمت بحلها بهذه الطريقة:
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;
}
كما ترون، لقد استخدمت Apaches StringUtils.compare() و NumberUtils.compere() كمساعدة قياسية.
في المثال الذي قدمته، الأرقام التي تريد مقارنتها بها مسافات حولها بينما لا تحتوي الأرقام الأخرى على مسافات، فلماذا لا يعمل التعبير العادي؟
bbb 12 com.ccc
ضد.
إيي 12 دي دي jpeg2000 إيييي
إذا كنت تكتب فئة مقارنة، فيجب عليك تنفيذ طريقة المقارنة الخاصة بك والتي ستقارن بين سلسلتين حرفًا بحرف.يجب أن تتحقق طريقة المقارنة هذه مما إذا كنت تتعامل مع أحرف أبجدية أو أحرف رقمية أو أنواع مختلطة (بما في ذلك المسافات).سيتعين عليك تحديد الطريقة التي تريد أن يتصرف بها النوع المختلط، سواء كانت الأرقام تأتي قبل الأحرف الأبجدية أو بعدها، وأين تناسب المسافات وما إلى ذلك.
في Linux، يوفر glibc الدالة strverscmp()، وهي متاحة أيضًا من gnulib لسهولة النقل.ومع ذلك، فإن التصنيف "البشري" حقًا يحتوي على الكثير من المراوغات الأخرى مثل تصنيف "فرقة البيتلز" على أنها "البيتلز، ذا".لا يوجد حل بسيط لهذه المشكلة العامة.
