Итераторы должны умереть!

Интересная статья Александреску на тему итераторов.

Покер, Функциональное программирование, C#

есть файл, содержащий статистическу информацию о наиболее прибыльных руках в 6max Texac Hold'em.
Примерно вот такой:
Hand SB BB UTG MP CO Btn
AAo 2.62 2.26 2.05 2.58 2.53 2.38
KKo 1.28 1.88 1.63 1.53 1.75 1.81
QQo 1.23 0.88 1.26 0.89 1.07 1.39
JJo 0.77 0.90 0.69 0.83 0.94 1.03
TTo 0.40 0.51 0.56 0.80 0.65 0.87
99o 0.14 0.14 0.26 0.45 0.46 0.39
88o 0.03 0.46 0.16 0.35 0.33 0.13
77o 0.07 -0.05 0.03 0.16 0.09 0.13

Задача - выбрать 13% наиболее доходных рук для игры на UTG и вывести их в "компактном" формате, т.е. вместо "AA","KK","QQ" и т.д. до "88" просто вывести "88+".

Конечный результат должен выглядеть как-то так:
88+,A8s+,...,AJo+,...

Нуу...вот код, решающий эту задачу:

using (StreamReader sr = new StreamReader(@"e:\hands_stat_6x.txt"))

{

    int sum = 0;

    var res = sr.lines()

        .skip(1)

        .map(x => x.Split())

        .map(x => F.tuple(x[0], x[3].to_double())).ToList()

        .sort((x, y) => x.item2==y.item2? 0 : x.item2 < y.item2 ? 1 : -1)

        .filter(x => { sum += (x.item1[0] == x.item1[1]) ? 6 : (x.item1[2] == 's') ? 4 : 12; return sum < ((52 * 51 / 2) * 13 / 100); })

        .ToList();

 

    Console.WriteLine("{0},{1}",

        res.filter(x => x.item1[1] == x.item1[0]).last().item1 + "+"

        , ",".join(

            "so".ToCharArray().SelectMany(suit=>

                "AKQJT9876".ToCharArray()

                .map(x => res.filter(y => y.item1[0] == x && y.item1[1] != x && y.item1[2] == suit).ToList())

                .filter(x => x.Count > 0).map(x => x.last().item1 + "+")

            )));

}

Это разумеется не весь код, я использую свои наработки для работы с tuples, свои функции типа map,skip,fold,filter и т.д. Будем считать что подобные функции есть в .NET (их там нет, и я считаю это недоразумением).

Результирующий код меня впечатлил...
Стоит обратить внимание на то что в коде явно объявлена всего одна переменная. И та вспомогательная... А ведь C# все еще строго типизированный язык:)

Да-да, это write-only код. И отлаживать сложно. Чистое эстетство. Но именно возможность писать такой код привлекает меня в C#. Также как в С++ меня привлекает возможность писать while(*p++). Даже если в реальной работе я этой возможностью пользоваться буду редко и осторожно - коллег жалко).

ух какая интересная задачка

«Продолжи последовательность» - один из самых распространенных типов задач, используемых в тестах на определение IQ. Взглянув на несколько чисел, требуется угадать закономерность, согласно которой построена эта последовательность, и назвать следующее число в ней.
Например:

1, 3, 5, 7, 9, … (последовательность нечетных чисел, ответ - 11)
1, 4, 9, 16, 25, … (последовательность квадратов натуральных чисел, ответ - 36)
2, 0, 3, 1, 4, 2, 5, 3, … (две чередующиеся арифметические прогрессии, ответ - 6)

Предлагается написать программу, демонстрирующую в таких задачах максимально высокий IQ.

Ваша цель – за 1 час создать консольную программу vogster.exe, принимающую на вход 9 чисел и выводящую в stdout свою догадку о том, каким будет десятое. Корректность входных данных проверять не надо – в наших тестах все входные данные будут девятью числами. Для вашего удобства, в предлагаемом проекте-заготовке входная строка уже обрабатывается, и вы можете работать сразу с массивом sequence, состоящим из 9 первых чисел последовательности.

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

Качество оформления кода, наличие комментариев, говорящих имен переменных, объектно-ориентированного стиля и т.п., жюри не интересует. Мы не на экзамене, цель состязания одна – написать самую умную программу.

суть с одной стороны именно в ограниченном времени.
с другой - можно и домой дать.

О скорости блокировки с помощью CRITICAL_SECTION

Задумал тут провести сравнения скорости блокировки потоков с помощью CRITICAL_SECTION и с помощью других подходов (CAS, spinlock).
Результат в общем-то получился предсказуемым - с помощью CAS быстрее...В среднем раза в 2. Хотя...не всегда. Периодически тестовые запуски показывали что код с использованием CRITICAL_SECTION так же быстр или даже чуть быстрее...
Я списал эти "неправильные" результаты на флюктуации и решил сравнить скорость блокировки потоков с помощью CRITICAL_SECTION и с помощью spinlock.
Код для реализации spinlock я взял отсюда и немного причесал. В принципе он совпадает с кодом приведенным в википедии.
(также я пробывал использовать код с codeguru но там результаты еще хуже)

Выяснилось...выяснилось что критические секции быстрее самопального спинлока минимум раза в 2. А то и больше - результат колебался от 2х до 4х раз. Хм...там же 4 инструкции...
Чтобы понять в чем фокус я попробывал посмотреть ассемблерный код реализации функций EnterCriticalSection и LeaveCriticalSection (если что - у меня Vista). Заодно бегло посмотрел пару статей об оптимизации ассемблерного кода под современные процессоры. А также о том что такое U-pipe, V-pipe и спаривание комманд...

Выводы:
а) код EnterCriticalSection очень похож на ручную оптимизированную правильную (и т.д.) реализацию спинлока...
б) инструкцию XCNG использовать вообще не рекомендуется.
в) чтобы написать блокировку быстрее CRITICAL_SECTION нужно очень постораться (мне это не грозит). да и то скорее всего будет работать только под конкретную архитектуру.
г) CAS все-таки быстрее. Если его не делать руками...а использовать InterlockedCompareExchangeXXX функции.

Крутил 5 потоков, вызывающих одну и ту же функцию. Считал суммарное время выполнения всех потоков. Разумеется в релизе и с оптимизацией. (там получалось что блокировка вообще не нужна, ну да это детали...)

Код с использованием CRITICAL_SECTION

void calc_synhronized_critical_section_impl()

{

    for(int i=0;i<count;++i)

    {

        EnterCriticalSection(&g_critsec);

 

        int temp = result;

        temp = temp + 1;

        result = temp;

 

        LeaveCriticalSection(&g_critsec);

    }

}

Код с "ручным" спинлоком :

void calc_synhronized_asm_spinlock_impl()

{

    static int vcookie = 0;

    LPVOID cookie = &vcookie;

    for(int i=0;i<count;++i)

    {

        __asm

        {

            mov edx, dword ptr [cookie]

            mov eax, 1

    spinLoop:

            lock xchg eax, dword ptr [edx]

            test eax, eax

            jnz spinLoop

 

        }

 

        int temp = result;

        temp = temp + 1;

        result = temp;

 

        __asm

        {

            mov edx, dword ptr [cookie]

            mov eax, 0

            lock xchg eax, dword ptr [edx]

        }

 

    }

}

Из странного и необьяснимого - если поток был один то код с ручным спинлоком оказывался быстрее...

заткнись и считай

Читал об новых интерпритациях квантовой механики, заодно вспомнил о старых.
Моя позиция осталась неизменной - ближе всего мне интерпритация Поля Дирака (она в заголовке).

RAII паттерн на C#, Nemerle и C++

Многие программисты на С++ перешедшие в С# испытывают дискомфорт от невозможности использования деструкторов. Точнее деструкторы то есть...но вызываются не при выходе за область видимости а когда до неиспользуемого более обьекта доберется GC.
Это делает невозможным испльзование RAII паттерна. Паттерн очень удобный, в коде на С++ я его использую достаточно часто, а к хорошему быстро привыкаешь.

"Обычные" C# программисты используют try...finally, получают простыни кода и не видят проблемы. Чуть более продвинутые слышали про IDisposable и using. Но если класс не наследован от IDisposable - пишут try...finally, получают простыни кода и не видят проблемы.

В целом никакой особой проблемы нет...вот только хочется красоты и икибаны. Недавно на RSDN (ссылку потерял, автору спасибо) видел пример generic класса для подобной обертки. Написал по памяти.

Код вспомогательных классов:

namespace test

{

    public static class DHelpers

    {

        public static Disposable<T> MakeDisposable<T>(this T obj, Action<T> dispose){

            return new Disposable<T>(obj, dispose);

        }

        public static Disposable<T> MakeDisposable<T>(this T obj, Action<T> begin, Action<T> dispose){

            return new Disposable<T>(obj, begin, dispose);

        }

    }

 

    public class Disposable<T> : IDisposable

    {

        private readonly Action<T> dispose;

        public readonly T @value;

 

        public Disposable(T @value, Action<T> dispose){

            this.dispose = dispose;

            this.@value = @value;

        }

        public Disposable(T @value, Action<T> begin, Action<T> dispose){

            this.dispose = dispose;

            this.@value = @value;

            begin(@value);

        }

        public Disposable(Func<T> get, Action<T> dispose){

            this.@value = get();

            this.dispose = dispose;

        }

        public void Dispose() { dispose(@value); }

    }

}

Пример использования:

namespace test

{

    ..............

 

 

    public class MadClass

    {

        public MadClass() { Console.WriteLine("Create"); }

        public void Close() { Console.WriteLine("Close"); }

        public void Action() { Console.WriteLine("Using"); }

    }

 

    internal class Program

    {

        private static void Main()

        {

            using (var mad = (new MadClass()).MakeDisposable(x => x.Close()))

            {

                mad.value.Action();

            }

        }

    }

}

Благодаря closure можно оборачивать не только классы но и локальные переменные:

bool value = false;

Console.WriteLine(value);

using (value.MakeDisposable(_ => value = true, _ => value = false))

{

    Console.WriteLine(value);

}

Console.WriteLine(value);

Вариант кода на Nemerle для решения той же задачи(автор - WolfHound c RSDN. в принципе по коду можно найти тему в которой это было). Что интересно - не понадобился отдельный класс. И расширения тоже не понадобились. И даже ключевое слово using как часть языка не понадобилось...Метопрограммирование...итить.

Сам макрос (примитивный, в реальном коде нужно было бы усложнить):

using Nemerle.Compiler;

 

public macro ScopeGuard(begin, end, body)

syntax ("scope", "(", begin, ";", end, ")", body)

{

    <[

    {

        $begin;

        try

        {

            $body

        }

        finally

        {

            $end;

        }

    }

    ]>

}

Использование:

using System;

using System.Console;

using Nemerle.Utility;

 

class MadClass

{

    public this() { WriteLine("create"); }

    public Close() : void { WriteLine("close"); }

}

 

module Program

{

    Main() : void

    {

        scope (def x = MadClass(); x.Close())

        {

            WriteLine("Hi!");

        }

        _ = ReadKey();

    }

}

Ну и под конец С++. Писать стандартную RAII обертку бессмысленно. Напишу лучше про "нестандартное" использование shared_ptr.

Итак, вот часто встречаемый вариант:

{

    SomeType* p = GetSomeType();

    DoSomethingWithSomeType(p);

    ReleaseSomeType();

}

С использование boost::shared_ptr этот код может выглядеть вот так:

{

    boost::shared_ptr<void> p(GetSomeType(),boost::bind(&ReleaseSomeType,_1));

    DoSomethingWithSomeType(p.get());

}

Выглядит не очень практично? Вот реальные варианты использования (выдрано из личного кода)
раз

boost::shared_ptr<wchar_t>    pszBuffer(

                        reinterpret_cast<wchar_t*>(*m_consolePaste.get()),

                        boost::bind<BOOL>(::VirtualFreeEx, ::GetCurrentProcess(), _1, NULL, MEM_RELEASE));

и два

m_hSharedEvent = boost::shared_ptr<void>(

    ::CreateEvent(NULL, FALSE, FALSE, (name + std::wstring(L"_event")).c_str()),

                    ::CloseHandle);

То ли еще будет...когда в С++ появятся лямбды и замыкания.

Хотя вариант Nemerle мне кажется наиболее оптимальным с точки зрения бритвы Оккама.

Странности в C# Type Inference (вывод типов)

Код:

namespace test

{

    class MainClass

    {

        delegate void Del(int x);

        static void temp(int x) { Console.WriteLine(x); }

        static void test_type_inference_action<V>(Action<V> f, V p) { f(p); }

        static void test_type_inference_delegate(Del f, int p) { f(p); }

        static void Main()

        {

            test_type_inference_action(delegate(int x) { Console.WriteLine(x); }, 1);

            test_type_inference_action(x => Console.WriteLine(x), 1);

            test_type_inference_action(temp, 1);

 

            Del d = delegate(int x) { Console.WriteLine(x); };

            //ERROR

            //The type arguments for method

            //'test.MainClass.test_type_inference_action<V>(System.Action<V>, V)'

            //cannot be inferred from the usage.

            //Try specifying the type arguments explicitly.   

            test_type_inference_action(d, 1);

 

            test_type_inference_delegate(d, 1);

            test_type_inference_delegate(x => Console.WriteLine(x), 1);

            test_type_inference_delegate(temp, 1);

            test_type_inference_delegate(delegate(int x) { Console.WriteLine(x); }, 1);

        }

    }   

}

Почему в отмеченной функции выдается ошибка я понять не могу...это к вопросу о разнице между делегатами и нормальными функциональными типами.

Из архивов

Нашел тут старую запись.
Суть сводилась к следующей задаче:

Во входном файле две ASCII-строки, одна состоит только из больших латинских букв, в другой могут встречаться большие латинские буквы и еще два спецсимвола - * (звездочка) и ? (знак вопроса). Строки могут иметь длину от 1 до 255 символов, быть в файле в произвольном порядке (но их всего две, формат входных данных корректен). Строку только с буквами назовем словом. Строка со спецсимволами - шаблон, в котором "?" и "*" играют роль символов подстановки по правилам, идентичным wildcards в именах файлов в DOS или Unix-shell, т.е. "?" заменяет собой ровно один произвольный символ, а "*" заменяет собой любое количество произвольных символов - 0 или более (т.е. может заменять и пустую строку). Программа должна выдать ответ YES, если слово подпадает под шаблон (match'ит его), либо NO в противном случае.

Ок. Паттерн-матчинг. Решил "поучаствовать" на время. Заняло минут 15. Получилось вот так вот:

bool match(const char* s,const char* p)

{

    if(!p)return *p==*s;

    if(*p==*s||*p=='?') return match(s+1,p+1);

    while(*s && !match(s++,p+1));

    return *s?true:match(0,p+1);

}

еще минут десять искал ошибку, в результате в код перед while добавилась строчка
if(*p!='*')return false;

красиво (правда проверки на то что строки содержат только большие латинские буквы нет)...можно было бы все лавры себе приписать...если бы не...
Есть такая книжка - Beautiful Code. Одня из статей в ней - как раз и реализация подобного алгоритма на С. Автор статьи - Кернинган, тот самый, брат Ричи. Я кода не помню, но помню одно - было действительно красиво. Красота она в рекурсии... следовательно... см. код. Т.е. алгоритм выстроился в основном по воспоминаниям об этой статье. Даже не столько по воспоминаниям о статье сколько об абстрактных воспоминаниях об ощущениях в процессе цтения. Не читай я эту статью не уверен что до идеи рекурсии дошел бы самостоятельно.
Занятно.

...........
Просмотрел комменты. Наткнулся на:

bool match(const char *word, char const *pattern)

{

    if (!*pattern) return !*word;

    if (*word == *pattern || *pattern == '?') return match(word+1, pattern+1);

    if (*pattern != '*') return false;

    while (*word)  if (match(word++, pattern+1)) return true;

    return match(word, pattern+1);

}

автор кода либо шибко шарит либо тоже читал эту книжку

Fast Inverse Square Root

Баян для занимающихся 3D.

Итак...нужно посчитать 1/sqrt(x):

float InvSqrt (float x){

    float xhalf = 0.5f*x;

    int i = *(int*)&x;

    i = 0x5f3759df - (i>>1);

    x = *(float*)&i;

    x = x*(1.5f - xhalf*x*x);

    return x;

}

магия в чистом виде...

дзен заключен в этой строчке:

    i = 0x5f3759df - (i>>1);

Про именование координатных осей

В двумерном случае оси ординат обычно обозначаются X и Y. Соответственно в 3хмерном пространстве нужна еще одна ось - Й.