Re[55]: Как скрестить ужа и ежа или статическую и утиные тип
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.01.07 23:02
Оценка: 8 (3)
Здравствуйте, Denis2005, Вы писали:

D>Хорошо, давай сварганим тест без выделения памяти.

D>Копирование ({1}) ~1.4 сек.
D>Копирование + сортировка ({1}+{2}) ~10.6
D>Копирование + сортировка ({1}+{3}) ~11.8

D>Я думаю не надо быть гением, чтобы сделать соответствующие выводы.


И каковы же твои выводы?

Ладно, достал. Убил хрен знает сколько времени чтобы сделать приличный тест.
Результат:
Framework version: 2.0.50727.308
--------------------------------------------------
Test               Sort Fun took: 00:00:02.0639765     Test OK.
Test          Sort Delegate took: 00:00:02.5174177     Test OK.
Test         Sort Interface took: 00:00:02.2520124     Test OK.
Test               Sort Int took: 00:00:01.3553026     Test OK.
Test             Array.Sort took: 00:00:01.2027735     Test OK.
Test  Array.Sort + Delegate took: 00:00:03.2673144     Test OK.
--------------------------------------------------
Test               Sort Fun took: 00:00:02.0579892     Test OK.
Test          Sort Delegate took: 00:00:02.4767103     Test OK.
Test         Sort Interface took: 00:00:02.2513230     Test OK.
Test               Sort Int took: 00:00:01.3561866     Test OK.
Test             Array.Sort took: 00:00:01.2009146     Test OK.
Test  Array.Sort + Delegate took: 00:00:03.2260957     Test OK.


Собственно все как я и говорил, за тем исключением, что похоже в новой версии фрэймворка похоже еще разогнали делегаты.
Если вычисть из тестов время теста Sort Int можно оценить реальное время затраченное на использование компаратора.

Исходник:
using System;
using System.Console;
using Nemerle.Utility;
using System.Diagnostics;

module Program
{
  Main() : void
  {
    WriteLine("Framework version: " + Environment.Version.ToString());

    def run(test, msg) : void
    {
      def calcCheckSum(ary) { ary.Fold(0 : long, _ + _) }
        def ary = array(10_000_000) : array[int];
        def r = Random(123);
        
      for (mutable i = 0; i < ary.Length; i++)
            ary[i] = r.Next(0, 1000000);

          def etalon = calcCheckSum(ary);
          def timer = Stopwatch.StartNew();
          
      test(ary);

      Write("Test {1,22} took: {0}", timer.Elapsed, msg);

          Trace.Assert(etalon == calcCheckSum(ary));
          _ = ary.Fold(0, fun(x, acc) { Trace.Assert(x >= acc); x });
      WriteLine("     Test OK.");
    }

    def runAll()
    {
      WriteLine("--------------------------------------------------");

      run(ary => ary.Sort(_ > _),                   "Sort Fun");
      run(ary => ary.SortDelegate(_ > _),           "Sort Delegate");
      run(ary => ary.SortInterface(Utils.CmpInt()), "Sort Interface");
      run(ary => ary.SortInt(),                     "Sort Int");
      run(ary => Array.Sort(ary),                   "Array.Sort");
      run(ary => Array.Sort(ary, _ - _),            "Array.Sort + Delegate");
    }

    runAll();
    runAll();
  }
}

public module Utils
{
  public Sort[T](this ary : array[T]) : void
    where T : IComparable[T]
  {
    Sort(ary, 0, ary.Length - 1, (x, y) => x.CompareTo(y) > 0);
  }
  
  public Sort[T](this ary : array[T], left : int, right : int) : void    
    where T : IComparable[T]
  {
    Sort(ary, left, right, (x, y) => x.CompareTo(y) > 0);
  }

  public Sort[T](this ary : array[T], isGreat : T * T -> bool) : void
  {
      Sort(ary, 0, ary.Length - 1, isGreat);
  }

  public Sort[T](
      this ary : array[T],
          left : int,
         right : int,
       isGreat : T * T -> bool
  )
    : void    
  {
    mutable i = left;
    mutable j = right;
    def center = ary[(left + right) / 2];

    while (i <= j)
    {
        while (isGreat(center, ary[i]))
            i++;
        while (isGreat(ary[j], center))
            j--;

        when (i <= j)
        {
          ary[i] <-> ary[j];
          i++;
          j--;
        }
    }

    when (left < j)
        Sort(ary, left, j, isGreat);
    when (right > i)
        Sort(ary, i, right, isGreat);
  }

  public delegate Cmp[T](x : T, y : T) : bool;
  
  public SortDelegate[T](this ary : array[T], isGreat : Cmp[T]) : void
  {
      SortDelegate(ary, 0, ary.Length - 1, isGreat);
  }

  public SortDelegate[T](
      this ary : array[T],
          left : int,
         right : int,
       isGreat : Cmp[T]
  )
    : void    
  {
    mutable i = left;
      mutable j = right;
      def center = ary[(left + right) / 2];

      while (i <= j)
      {
          while (isGreat(center, ary[i]))
              i++;
          while (isGreat(ary[j], center))
              j--;

          when (i <= j)
          {
            ary[i] <-> ary[j];
              i++;
              j--;
          }
      }

      when (left < j)
          SortDelegate(ary, left, j, isGreat);
      when (right > i)
          SortDelegate(ary, i, right, isGreat);
  }

  public interface ICmp[T] { Cmp(x : T, y : T) : bool; }
  public class CmpInt : ICmp[int] { public Cmp(x : int, y : int) : bool { x > y } }

  public SortInterface[T](this ary : array[T], isGreat : ICmp[T]) : void
  {
      SortInterface(ary, 0, ary.Length - 1, isGreat);
  }

  public SortInterface[T](
      this ary : array[T],
          left : int,
         right : int,
       isGreat : ICmp[T]
  )
    : void    
  {
    mutable i = left;
      mutable j = right;
      def center = ary[(left + right) / 2];

      while (i <= j)
      {
          while (isGreat.Cmp(center, ary[i]))
              i++;
          while (isGreat.Cmp(ary[j], center))
              j--;

          when (i <= j)
          {
            ary[i] <-> ary[j];
              i++;
              j--;
          }
      }

      when (left < j)
          SortInterface(ary, left, j, isGreat);
      when (right > i)
          SortInterface(ary, i, right, isGreat);
  }

  public SortInt(this ary : array[int]) : void
  {
    SortInt(ary, 0, ary.Length - 1);
  }

  public SortInt(
      this ary : array[int],
          left : int,
         right : int
  )
    : void    
  {
    mutable i = left;
    mutable j = right;
    def center = ary[(left + right) / 2];

    while (i <= j)
    {
        while (center > ary[i])
            i++;
        while (ary[j] > center)
            j--;

        when (i <= j)
        {
          ary[i] <-> ary[j];
          i++;
          j--;
        }
    }

    when (left < j)
        SortInt(ary, left, j);
    when (right > i)
        SortInt(ary, i, right);
  }
}
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.