فرز الأرقام المختلطة والسلاسل

Question

لدي قائمة بالسلاسل التي يمكن أن تحتوي على حرف أو سلسلة تمثل int (رقمين كحد أقصى).يجب فرزها إما أبجديًا أو (عندما تكون في الواقع int) على القيمة العددية التي تمثلها.

مثال:

IList<string> input = new List<string>()
    {"a", 1.ToString(), 2.ToString(), "b", 10.ToString()};

input.OrderBy(s=>s)
  // 1
  // 10
  // 2
  // a
  // b

ما أريده هو

  // 1
  // 2
  // 10
  // a
  // b

لدي فكرة تتضمن تنسيقها من خلال محاولة تحليلها، ثم إذا كانت محاولة تحليل ناجحة، فقم بتنسيقها باستخدام تنسيق السلسلة المخصص الخاص بي لجعلها تحتوي على أصفار سابقة.آمل أن يكون هناك شيء أكثر بساطة وأداء.

يحرر
انتهى بي الأمر إلى إنشاء IComparer الذي ألقيته في مكتبة Utils الخاصة بي لاستخدامه لاحقًا.
بينما كنت في ذلك رميت الزوجي في المزيج أيضًا.

public class MixedNumbersAndStringsComparer : IComparer<string> {
    public int Compare(string x, string y) {
        double xVal, yVal;

        if(double.TryParse(x, out xVal) && double.TryParse(y, out yVal))
            return xVal.CompareTo(yVal);
        else 
            return string.Compare(x, y);
    }
}

//Tested on int vs int, double vs double, int vs double, string vs int, string vs doubl, string vs string.
//Not gonna put those here
[TestMethod]
public void RealWorldTest()
{
    List<string> input = new List<string>() { "a", "1", "2,0", "b", "10" };
    List<string> expected = new List<string>() { "1", "2,0", "10", "a", "b" };
    input.Sort(new MixedNumbersAndStringsComparer());
    CollectionAssert.AreEquivalent(expected, input);
}

Answer 1

ربما يمكنك اتباع نهج أكثر عمومية واستخدام الفرز الطبيعي خوارزمية مثل تنفيذ C# هنا.

Answer 2

هناك طريقتان تتبادران إلى ذهني، لست متأكدًا من أيهما أكثر أداءً.تنفيذ IComparer مخصص:

class MyComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        int xVal, yVal;
        var xIsVal = int.TryParse( x, out xVal );
        var yIsVal = int.TryParse( y, out yVal );

        if (xIsVal && yIsVal)   // both are numbers...
            return xVal.CompareTo(yVal);
        if (!xIsVal && !yIsVal) // both are strings...
            return x.CompareTo(y);
        if (xIsVal)             // x is a number, sort first
            return -1;
        return 1;               // x is a string, sort last
    }
}

var input = new[] {"a", "1", "10", "b", "2", "c"};
var e = input.OrderBy( s => s, new MyComparer() );

أو قم بتقسيم التسلسل إلى أرقام وغير أرقام، ثم قم بفرز كل مجموعة فرعية، وأخيرًا قم بضم النتائج التي تم فرزها؛شيء مثل:

var input = new[] {"a", "1", "10", "b", "2", "c"};

var result = input.Where( s => s.All( x => char.IsDigit( x ) ) )
                  .OrderBy( r => { int z; int.TryParse( r, out z ); return z; } )
                  .Union( input.Where( m => m.Any( x => !char.IsDigit( x ) ) )
                               .OrderBy( q => q ) );

Answer 3

استخدام الزائد الآخر من OrderBy الذي يأخذ IComparer معامل.

يمكنك بعد ذلك تنفيذ بنفسك IComparer الذي يستخدم int.TryParse لمعرفة ما إذا كان رقمًا أم لا.

Answer 4

أود أن أقول أنه يمكنك تقسيم القيم باستخدام RegularExpression (بافتراض أن كل شيء عبارة عن int) ثم إعادة ضمها معًا.

//create two lists to start
string[] data = //whatever...
List<int> numbers = new List<int>();
List<string> words = new List<string>();

//check each value
foreach (string item in data) {
    if (Regex.IsMatch("^\d+$", item)) {
        numbers.Add(int.Parse(item));
    }
    else {
        words.Add(item);
    }
}

ثم باستخدام القائمتين، يمكنك فرز كل منهما ثم دمجهما معًا مرة أخرى بأي تنسيق تريده.

Answer 5

يمكنك فقط استخدام الوظيفة المقدمة من Win32 API:

[DllImport ("shlwapi.dll", CharSet=CharSet.Unicode, ExactSpelling=true)]
static extern int StrCmpLogicalW (String x, String y);

ونسميها من IComparer كما أظهر آخرون.

Answer 6

public static int? TryParse(string s)
{
    int i;
    return int.TryParse(s, out i) ? (int?)i : null;
}

// in your method
IEnumerable<string> input = new string[] {"a", "1","2", "b", "10"};
var list = input.Select(s => new { IntVal = TryParse(s), String =s}).ToList();
list.Sort((s1, s2) => {
    if(s1.IntVal == null && s2.IntVal == null)
    {
        return s1.String.CompareTo(s2.String);
    }
    if(s1.IntVal == null)
    {
        return 1;
    }
    if(s2.IntVal == null)
    {
        return -1;
    }
    return s1.IntVal.Value.CompareTo(s2.IntVal.Value);
});
input = list.Select(s => s.String);

foreach(var x in input)
{
    Console.WriteLine(x);
}

لا يزال يقوم بالتحويل، ولكن مرة واحدة فقط/العنصر.

Answer 7

يمكنك استخدام مقارن مخصص - سيكون بيان الطلب بعد ذلك:

var result = input.OrderBy(s => s, new MyComparer());

حيث يتم تعريف MyComparer على النحو التالي:

public class MyComparer : Comparer<string>
{
    public override int Compare(string x, string y)
    {

        int xNumber;
        int yNumber;
        var xIsNumber = int.TryParse(x, out xNumber);
        var yIsNumber = int.TryParse(y, out yNumber);

        if (xIsNumber && yIsNumber)
        {
            return xNumber.CompareTo(yNumber);
        }
        if (xIsNumber)
        {
            return -1;
        }
        if (yIsNumber)
        {
            return 1;
        }
        return x.CompareTo(y);
    }
}

على الرغم من أن هذا قد يبدو مطولًا بعض الشيء، إلا أنه يلخص منطق الفرز في نوع مناسب.يمكنك بعد ذلك، إذا كنت ترغب في ذلك، إخضاع المقارن بسهولة للاختبار الآلي (اختبار الوحدة).كما أنها قابلة لإعادة الاستخدام.

(قد يكون من الممكن جعل الخوارزمية أكثر وضوحًا بعض الشيء، ولكن هذا كان أفضل ما يمكنني تجميعه بسرعة.)

Answer 8

يمكنك أيضًا "الغش" بمعنى ما.بناءً على وصفك للمشكلة، فأنت تعلم أن أي سلسلة بطول 2 ستكون رقمًا.لذلك فقط قم بفرز جميع السلاسل ذات الطول 1.ثم قم بفرز جميع السلاسل ذات الطول 2.ثم قم بإجراء مجموعة من عمليات التبديل لإعادة ترتيب سلاسلك بالترتيب الصحيح.في الأساس ستعمل العملية على النحو التالي:(بافتراض أن بياناتك موجودة في مصفوفة.)

الخطوة 1:ادفع جميع السلاسل ذات الطول 2 إلى نهاية المصفوفة.تتبع كم لديك.

الخطوة 2:في مكان فرز سلاسل الطول 1 وسلاسل الطول 2.

الخطوه 3:ابحث ثنائيًا عن "a" الذي سيكون على حدود النصفين.

الخطوة 4:قم بتبديل السلاسل المكونة من رقمين بالأحرف حسب الضرورة.

ومع ذلك، على الرغم من أن هذا النهج سينجح، إلا أنه لا يتضمن تعبيرات عادية، ولا يحاول تحليل القيم غير int كقيمة int - لا أوصي به.ستكتب تعليمات برمجية أكثر بكثير من الأساليب الأخرى المقترحة بالفعل.إنه يحجب الهدف مما تحاول القيام به.لن ينجح الأمر إذا حصلت فجأة على سلاسل مكونة من حرفين أو سلاسل مكونة من ثلاثة أرقام.إلخ.لقد قمت بتضمينها فقط لإظهار كيف يمكنك النظر إلى المشكلات بشكل مختلف، والتوصل إلى حلول بديلة.

Answer 9

إستخدم تحويل شوارتزي لإجراء تحويلات O(n)!

private class Normalized : IComparable<Normalized> {
  private readonly string str;
  private readonly int val;

  public Normalized(string s) {
    str = s;

    val = 0;
    foreach (char c in s) {
      val *= 10;

      if (c >= '0' && c <= '9')
        val += c - '0';
      else
        val += 100 + c;
    }
  }

  public String Value { get { return str; } }

  public int CompareTo(Normalized n) { return val.CompareTo(n.val); }
};

private static Normalized In(string s) { return new Normalized(s); }
private static String Out(Normalized n) { return n.Value; }

public static IList<String> MixedSort(List<String> l) {
  var tmp = l.ConvertAll(new Converter<String,Normalized>(In));
  tmp.Sort();
  return tmp.ConvertAll(new Converter<Normalized,String>(Out));
}

Answer 10

واجهت مشكلة مماثلة وهبطت هنا:فرز السلاسل التي تحتوي على لاحقة رقمية كما في المثال التالي.

إبداعي:

"Test2", "Test1", "Test10", "Test3", "Test20"

نتيجة الفرز الافتراضية:

"Test1", "Test10", "Test2", "Test20", "Test3"

نتيجة الفرز المطلوبة:

"Test1", "Test2", "Test3, "Test10", "Test20"

انتهى بي الأمر باستخدام مقارن مخصص:

public class NaturalComparer : IComparer
{

    public NaturalComparer()
    {
        _regex = new Regex("\\d+$", RegexOptions.IgnoreCase);
    }

    private Regex _regex;

    private string matchEvaluator(System.Text.RegularExpressions.Match m)
    {
        return Convert.ToInt32(m.Value).ToString("D10");
    }

    public int Compare(object x, object y)
    {
        x = _regex.Replace(x.ToString, matchEvaluator);
        y = _regex.Replace(y.ToString, matchEvaluator);

        return x.CompareTo(y);
    }
}   

هث ؛س)