chardict2.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

/* Results
  
Dictionary. Time elapsed: 00:00:12.0486110, single iteration: 0.00012048611 ms.
CharDictionary. Time elapsed: 00:00:00.5085145, single iteration: 5.085145E-06 ms
CompactCharDictionary. Time elapsed: 00:00:02.6166454, single iteration: 2.6166454E-05 ms 

 Env: 2.6GHz, Windows 7, .NET 4.5, Release mode, running executable directly
 
 */

public static class CharDictTests {
  public static void RunTest() {
    // source data
    var keywords = new[] { "%", "&", "!", "*", "$"};//, "for", "foreach", "return", "начало", "конец", "—" };
    var stringLookup = keywords.ToLookup(s => s[0]);

    // create dictionaries
    var plainDictionary = stringLookup.ToDictionary(g => g.Key, g => g.OrderByDescending(s => s.Length).ToArray());
    var compactCharDictionary = new CompactCharDictionary<string[]>(plainDictionary);
    var charDictionary = new CharDictionary<string[]>(plainDictionary);

    // warm up
    Benchmark(charDictionary, 1, false);
    Benchmark(compactCharDictionary, 1,  false);

    // run benchmarks
    const int iterations = 100 * 1000 * 1000;
    Benchmark(plainDictionary, iterations);
    Benchmark(charDictionary, iterations);
    Benchmark(compactCharDictionary, iterations);
  }

  static void Benchmark(Dictionary<char, string[]> chars, int iterations) {
    string[] tmp; 
    var sw = Stopwatch.StartNew();
    for (var i = 0; i < iterations; i++) {
      chars.TryGetValue('<', out tmp); chars.TryGetValue('>', out tmp); chars.TryGetValue('/', out tmp);
      chars.TryGetValue('*', out tmp); chars.TryGetValue('f', out tmp); chars.TryGetValue('r', out tmp);
      chars.TryGetValue('н', out tmp); chars.TryGetValue('к', out tmp); chars.TryGetValue('—', out tmp);
      chars.TryGetValue('X', out tmp);
    }
    sw.Stop();
    Console.WriteLine("Dictionary. Time elapsed: {0}, single iteration: {1} ms.", sw.Elapsed, sw.Elapsed.TotalMilliseconds / iterations);
  }

  static void Benchmark(CharDictionary<string[]> chars, int iterations, bool report = true) {
    string[] tmp;
    var sw = Stopwatch.StartNew();
    for (var i = 0; i < iterations; i++) {
      tmp = chars['<']; tmp = chars['>']; tmp = chars['/'];
      tmp = chars['*']; tmp = chars['f']; tmp = chars['r'];
      tmp = chars['н']; tmp = chars['к']; tmp = chars['_'];
      tmp = chars['X'];
    }
    sw.Stop();
    if (report)
      Console.WriteLine("CharDictionary. Time elapsed: {0}, single iteration: {1} ms", sw.Elapsed, sw.Elapsed.TotalMilliseconds / iterations);
  }

  static void Benchmark(CompactCharDictionary<string[]> chars, int iterations, bool report = true) {
    string[] tmp;
    var sw = Stopwatch.StartNew();
    for (var i = 0; i < iterations; i++) {
      tmp = chars['<']; tmp = chars['>']; tmp = chars['/'];
      tmp = chars['*']; tmp = chars['f']; tmp = chars['r'];
      tmp = chars['н']; tmp = chars['к']; tmp = chars['_'];
      tmp = chars['X'];
    }
    sw.Stop();
    if (report)
      Console.WriteLine("CompactCharDictionary. Time elapsed: {0}, single iteration: {1} ms", sw.Elapsed, sw.Elapsed.TotalMilliseconds / iterations);
  }
}

public class Tuplex<T1, T2> {
  public T1 Item1;
  public T2 Item2;
  public Tuplex(T1 item1, T2 item2) {
    Item1 = item1;
    Item2 = item2;
  }
}

public class CompactCharDictionary<T> {
  private struct CharLookupData {
    public Tuplex<char, T>[] Data;
  }

  public CompactCharDictionary() {
    Table = new CharLookupData[256];
    for (int i = 0; i < Table.Length; i++)
      Table[i] = new CharLookupData(); 
  }

  public CompactCharDictionary(IEnumerable<KeyValuePair<char, T>> source)
    : this() {
    foreach (var pair in source) {
      this[pair.Key] = pair.Value;
    }
  }

  // slim table to look up single-byte chars
  private CharLookupData[] Table;


  public T this[char c] {
    get {
      var index = c & 0xFF;
      var lookupArray = Table[index];
      var lookupData = lookupArray.Data;

      if (lookupData != null) {
        /*if (lookupData.Length == 1) {
          var d = lookupData[0];
          if (d.Item1 == c)
            return d.Item2;

        }*/
        for (var i = 0; i < lookupData.Length; i++) {
          var tuple = lookupData[i];
          if (tuple.Item1 == c) {
            return tuple.Item2;
          }
          if (tuple.Item1 > c) {
            break;
          }
        }
      }

      return default(T); 
    }

    set {
      var index = c & 0xFF;
      var lookupArray = Table[index];
      var lookupData = lookupArray.Data ?? new Tuplex<char, T>[0];

      var tuple = new Tuplex<char, T>(c, value);
      for (var i = 0; i < lookupData.Length; i++) {
        if (lookupData[i].Item1 == c) {
          lookupData[i] = tuple;
          return;
        }
      }

      Table[index].Data = lookupData.Concat(new[] { tuple }).OrderBy(t => t.Item1).ToArray();
    }
  }
}

public class CharDictionary<T> {
  public CharDictionary() {
    AsciiTable = new T[256];
    UnicodeTable = new T[256][];
  }

  public CharDictionary(IEnumerable<KeyValuePair<char, T>> source)
    : this() {
    foreach (var pair in source) {
      this[pair.Key] = pair.Value;
    }
  }

  // slim table to look up single-byte chars
  private T[] AsciiTable;

  // sparse jagged table to look up two-byte chars
  private T[][] UnicodeTable;


  public T this[char c] {
    get {
      var low = c & 0xFF;
      var high = c >> 8;
      if (high == 0)
        return AsciiTable[low];
      var tmp = UnicodeTable[high - 1];
      if (tmp == null)
        return default(T);
      return tmp[low];
      //return high == 0 ? AsciiTable[low] : UnicodeTable[high - 1][low];
    }

    set {
      var low = c & 0xFF;
      var high = c >> 8;
      if (high == 0) {
        AsciiTable[low] = value;
        return;
      }

      var table = UnicodeTable[high - 1];
      if (table == null) {
        table = new T[255];
        UnicodeTable[high - 1] = table;
      }

      table[low] = value;
    }
  }
}