Decorate-Sort-Undecorate, как сортировать алфавитное поле в порядке убывания

Question

У меня есть большой набор данных, для которых вычисление ключа сортировки довольно дорого. То, что я хотел бы сделать, это использовать шаблон DSU, где я беру строки и вычисляю ключ сортировки. Пример:

 Qty Name  Supplier 
Row 1: 50 Widgets IBM 
Row 2: 48 Thingies Dell 
Row 3: 99 Googaws IBM 

Для сортировки по количеству и Поставщиком я мог иметь ключи сортировки: 0050 IBM, 0048 Dell, 0099 IBM. Цифры выровнены по правому краю, а текст выравнивается по левому краю, при необходимости все заполняется.

Если мне нужно сортировать по QUANTY в убыванию заказ я могу просто вычесть значение из константы (например, 10000) для создания ключей сортировки: 9950 IBM, 9952 Dell, 9901 IBM.

Как быстро и дешево построить нисходящую клавишу для alphabetic полей в C#?

[Мои данные все 8-битный ASCII ж/символов расширения ISO 8859.]

Примечание: В Perl, это может быть сделано bit-complementing the strings:

$subkey = $string^("\xFF" x length $string); 

Портирование это решение прямо в C# не работает:

subkey = encoding.GetString(encoding.GetBytes(stringval). 
         Select(x => (byte)(x^0xff)).ToArray()); 

Я подозреваю, из-за различий в способе, которым обрабатываются строки в C#/Perl. Возможно, Perl сортируется в порядке ASCII, а C# пытается быть умным?

Вот пример кусок кода, который пытается выполнить это:

 System.Text.ASCIIEncoding encoding = new System.Text.ASCIIEncoding(); 
     List<List<string>> sample = new List<List<string>>() { 
      new List<string>() { "", "apple", "table" }, 
      new List<string>() { "", "apple", "chair" }, 
      new List<string>() { "", "apple", "davenport" }, 
      new List<string>() { "", "orange", "sofa" }, 
      new List<string>() { "", "peach", "bed" }, 
     }; 
     foreach(List<string> line in sample) 
     { 
      StringBuilder sb = new StringBuilder(); 

      string key1 = line[1].PadRight(10, ' '); 
      string key2 = line[2].PadRight(10, ' '); 

      // Comment the next line to sort desc, desc 
      key2 = encoding.GetString(encoding.GetBytes(key2). 
        Select(x => (byte)(x^0xff)).ToArray()); 

      sb.Append(key2); 
      sb.Append(key1); 
      line[0] = sb.ToString(); 
     } 

     List<List<string>> output = sample.OrderBy(p => p[0]).ToList(); 

     return; 

Answer 1

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

Проблема, с которой вы сталкиваетесь с прямым переводом метода Perl, заключается в том, что .NET просто не позволит вам быть таким невмешательством с кодировкой. Однако, если, как вы говорите, ваши данные являются полностью печатаемыми ASCII (т.е. состоит из символов с кодовыми точками Unicode в диапазоне 32..127) - обратите внимание, что нет такой вещи, как «8-бит ASCII», - тогда вы можете сделать это:

  key2 = encoding.GetString(encoding.GetBytes(key2). 
       Select(x => (byte)(32+95-(x-32))).ToArray()); 

в этом выражении я был четко о том, что я делаю:

• Возьмите x (который я предполагаю, чтобы быть в 32..127)
• Карта диапазон 0. .95, чтобы сделать его нулевым
• Обратный путем вычитания из 95
• Добавить 32 на карту обратно в область печати

Это не очень хорошо, но это действительно работает.

Answer 2

Просто напишите IComparer, который будет работать в цепи компараторов. В случае равенства на каждом этапе он должен пройти эвелацию к следующей ключевой части. Если он меньше или больше, просто вернитесь.

Вам нужно что-то вроде этого:

int comparision = 0; 

foreach(i = 0; i < n; i++) 
{ 
comparision = a[i].CompareTo(b[i]) * comparisionSign[i]; 

if(comparision != 0) 
    return comparision; 
} 
return comparision; 

Или еще проще, вы можете пойти с:

list.OrderBy(i=>i.ID).ThenBy(i=>i.Name).ThenByDescending(i=>i.Supplier); 

первый обратный вызов IOrderedEnumerable <>, то, которое может сортировать дополнительные поля.

Answer 3

Отвечая на мой собственный вопрос (но не удовлетворительно). Для того, чтобы построить нисходящую буквенный ключ я использовал этот код, а затем добавляется этот раздел в качестве ключа поиска для объекта:

if (reverse) 
     subkey = encoding.GetString(encoding.GetBytes(subkey) 
       .Select(x => (byte)(0x80 - x)).ToArray()); 
    rowobj.sortKey.Append(subkey); 

После того, как я построил ключи, я не мог просто сделать это:

rowobjList.Sort(); 

Поскольку компаратор по умолчанию не находится в порядке ASCII (на что опирается мой трюк 0x80 - x).Тогда я должен был написать IComparable<RowObject>, который использовал Порядковую сортировку:

public int CompareTo(RowObject other) 
    { 
     return String.Compare(this.sortKey, other.sortKey, 
           StringComparison.Ordinal); 
    } 

Это кажется работать. Я немного недоволен, потому что он чувствует себя неуклюжим в C# с кодировкой/расшифровкой строки.

Answer 4

Если ключевое вычисление дорогое, зачем вычислять ключ вообще? Сравнение строк само по себе не является бесплатным, это действительно дорогой цикл через символы и не будет работать лучше, чем пользовательский цикл сравнения.

В этом тесте пользовательская сортировка сортировки выполняет примерно в 3 раза лучше, чем DSU.

Обратите внимание, что подсчет ключей DSU не измеряется в этом тесте, он предварительно вычисляется.

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 
using System.Text; 
using Microsoft.VisualStudio.TestTools.UnitTesting; 

namespace DSUPatternTest 
{ 
[TestClass] 
public class DSUPatternPerformanceTest 
{ 
    public class Row 
    { 
    public int Qty; 
    public string Name; 
    public string Supplier; 
    public string PrecomputedKey; 

    public void ComputeKey() 
    { 
    // Do not need StringBuilder here, String.Concat does better job internally. 
    PrecomputedKey = 
    Qty.ToString().PadLeft(4, '0') + " " 
    + Name.PadRight(12, ' ') + " " 
    + Supplier.PadRight(12, ' '); 
    } 

    public bool Equals(Row other) 
    { 
    if (ReferenceEquals(null, other)) return false; 
    if (ReferenceEquals(this, other)) return true; 
    return other.Qty == Qty && Equals(other.Name, Name) && Equals(other.Supplier, Supplier); 
    } 

    public override bool Equals(object obj) 
    { 
    if (ReferenceEquals(null, obj)) return false; 
    if (ReferenceEquals(this, obj)) return true; 
    if (obj.GetType() != typeof (Row)) return false; 
    return Equals((Row) obj); 
    } 

    public override int GetHashCode() 
    { 
    unchecked 
    { 
    int result = Qty; 
    result = (result*397)^(Name != null ? Name.GetHashCode() : 0); 
    result = (result*397)^(Supplier != null ? Supplier.GetHashCode() : 0); 
    return result; 
    } 
    } 
    } 

    public class RowComparer : IComparer<Row> 
    { 
    public int Compare(Row x, Row y) 
    { 
    int comparision; 

    comparision = x.Qty.CompareTo(y.Qty); 
       if (comparision != 0) return comparision; 

    comparision = x.Name.CompareTo(y.Name); 
       if (comparision != 0) return comparision; 

    comparision = x.Supplier.CompareTo(y.Supplier); 

    return comparision; 
    } 
    } 

    [TestMethod] 
    public void CustomLoopIsFaster() 
    { 
    var random = new Random(); 
    var rows = Enumerable.Range(0, 5000).Select(i => 
      new Row 
       { 
       Qty = (int) (random.NextDouble()*9999), 
       Name = random.Next().ToString(), 
    Supplier = random.Next().ToString() 

       }).ToList(); 

    foreach (var row in rows) 
    { 
    row.ComputeKey(); 
    } 

    var dsuSw = Stopwatch.StartNew(); 
    var sortedByDSU = rows.OrderBy(i => i.PrecomputedKey).ToList(); 
    var dsuTime = dsuSw.ElapsedMilliseconds; 

    var customSw = Stopwatch.StartNew(); 
    var sortedByCustom = rows.OrderBy(i => i, new RowComparer()).ToList(); 
    var customTime = customSw.ElapsedMilliseconds; 

    Trace.WriteLine(dsuTime); 
    Trace.WriteLine(customTime); 

    CollectionAssert.AreEqual(sortedByDSU, sortedByCustom); 

    Assert.IsTrue(dsuTime > customTime * 2.5); 
    } 
} 
} 

Если вам нужно построить сортировщик динамически вы можете использовать что-то вроде этого:

var comparerChain = new ComparerChain<Row>() 
.By(r => r.Qty, false) 
.By(r => r.Name, false) 
.By(r => r.Supplier, false); 

var sortedByCustom = rows.OrderBy(i => i, comparerChain).ToList(); 

Вот пример реализации Comparer цепи строитель:

public class ComparerChain<T> : IComparer<T> 
    { 
     private List<PropComparer<T>> Comparers = new List<PropComparer<T>>(); 

     public int Compare(T x, T y) 
     { 
      foreach (var comparer in Comparers) 
      { 
       var result = comparer._f(x, y); 
       if (result != 0) 
        return result; 
      } 
      return 0; 
     } 
     public ComparerChain<T> By<Tp>(Func<T,Tp> property, bool descending) where Tp:IComparable<Tp> 
     { 
      Comparers.Add(PropComparer<T>.By(property, descending)); 
      return this; 
     } 
    } 

    public class PropComparer<T> 
    { 
     public Func<T, T, int> _f; 

     public static PropComparer<T> By<Tp>(Func<T,Tp> property, bool descending) where Tp:IComparable<Tp> 
     { 
      Func<T, T, int> ascendingCompare = (a, b) => property(a).CompareTo(property(b)); 
      Func<T, T, int> descendingCompare = (a, b) => property(b).CompareTo(property(a)); 
      return new PropComparer<T>(descending ? descendingCompare : ascendingCompare); 
     } 

     public PropComparer(Func<T, T, int> f) 
     { 
      _f = f; 
     } 
    } 

Он работает немного бит медленнее, может быть, из-за перебора делегатов.