Decorate-Sort-Undecorate, how to sort an alphabetical field in descending order

Question

I have a large dataset for which sorting key calculation is quite expensive. What I would like to do is use the DSU template where I take the strings and calculate the sort key. Example:

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

Sorted by number of supplier and I might be the sort keys: 0050 IBM, 0048 Dell, 0099 IBM. The numbers are right-aligned, and the text is left-aligned, if necessary, everything is filled.

If I need to sort in descending order of quantum, I can simply subtract the value of the constants (for example, 10000) for creating sort keys: 9950 IBM, 9952 Dell, 9901 IBM.

How to quickly / cheaply build a top-down key for alphabetical fields in C #?

[My details are all 8-bit ASCII characters w / ISO 8859.]

Note. In Perl, this can be done using the padding bit of a string :

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

Porting this solution directly to C # does not work:

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

I suspect due to differences in how strings are processed in C # / Perl. Perhaps Perl is sorted in ASCII order and C # is trying to be smart?

Here is an example of a piece of code that tries to execute this:

        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

You can get where you want, although I admit that I do not know if there is a better general way.

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

. , # / .

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

:

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

, , - , .