Повышение производительности в пользовательской сортировке массива строк

Question

Я пытаюсь найти эффективный способ сортировки массива строк на основе числового значения в каждом строковом элементе массива.В настоящее время я использую статический метод Array.Sort (array, customComparer) (быстрая сортировка), с моим классом специального сравнения (сортировка по убыванию):

class StringComparer : IComparer<string>
{
    public int Compare(string a, string b)
    {
        string s1 = a;
        string s2 = b;

        Match matchA = Regex.Match(s1, @"\d+$");
        Match matchB = Regex.Match(s2, @"\d+$");

        long numberA = long.Parse(matchA.Value);
        long numberB = long.Parse(matchB.Value);

        if (numberB - numberA < 0)
        {
            return -1;
        }
        else 
        {
            return 1;
        }
    }
}

Это работает очень хорошо, но иногдасортировка занимает слишком много времени: массив из 100 000 строк занимает более минуты на процессоре с частотой 2,4 ГГц.Интересно, есть ли более эффективный способ сделать то же самое.Например, реализация другого алгоритма сортировки или другой подход, например использование словаря и сортировка по значению (значение является числовой частью строки).Какие-либо предложения?Заранее спасибо!

Answer 1

Вы анализируете значение для каждого сравнения.Я бы посоветовал вам проанализировать один раз , чтобы получить пару строка / длинная, отсортировать ее, а затем извлечь часть строки.

Обратите внимание, что в вашем существующем коде есть ошибка: он будет never return 0, для двух строк, сравниваемых как равные.

Вот альтернативный подход с использованием LINQ (который не сортируется на месте, но прост.)

var sorted = unsorted.OrderBy(x => long.Parse(Regex.Match(x, @"\d+$").Value));
                     .ToList();

(OrderBy проецирует один раз, чтобы получить ключи, затем сравнивает ключи.)

Answer 2

Вы сейчас выполняете регулярные выражения O (n log n) раз.

Рассмотрите возможность зацикливания всех строк, извлечения числового значения и добавления его к SortedDictionary<long, string>

Это требует только O (n) выполнения выражения Reg. В остальном сортировка должна быть сопоставимой.

Answer 3

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

public class FooString {
    private readonly string foo;
    private readonly long bar;

    public FooString(string foo) {
        this.foo = foo;
        Match match = Regex.Match(foo, @"\d+$");
        this.bar = Int64.Parse(match.Value);
    }

    public string Foo { get { return this.foo; } }
    public long Bar { get { return this.bar; } }
}

Я бы даже добавил Contract.Requires к этому классу, который говорит, что foo должен удовлетворять регулярному выражению.

Во-вторых, у вас есть IComparer<T>, который умирает при определенных значениях T (в вашем случае, string с, которые не соответствуют регулярному выражению и не могут быть проанализированы с long). Это вообще плохая идея.

Итак, сделайте сравнение для FooString:

public FooStringComparer : IComparer<FooString> {
    public int Compare(FooString a, FooString b) {
        Contract.Requires(a != null);
        Contract.Requires(b != null);
        return a.Bar.CompareTo(b.Bar);
    }
}

Теперь ваша сортировка будет невероятно быстрой, потому что вы перестали анализировать одну и ту же строку снова и снова.

Answer 4

Создайте Regex только один раз с опцией Compiled.Это увеличит скорость.

class StringComparer : IComparer<string>
{
    private static Regex _regex = new Regex(@"\d+$", RegexOptions.Compiled);

    public int Compare(string a, string b)
    {
        long numberA = Int64.Parse(_regex.Match(a).Value);
        long numberB = Int64.Parse(_regex.Match(b).Value);
        return numberA.CompareTo(numberB);
    }
}