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

«Продолжи последовательность» - один из самых распространенных типов задач, используемых в тестах на определение 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хмерном пространстве нужна еще одна ось - Й.

Задачка на вероятность.

Практическая.

Интервал движения автобуса 30 минут. Ехать от моей остоновки до следующей 5 минут. Идти пешком - 30 минут. Вопрос - сколько ждать автобус прежде чем пойти пешком?

Теоретическая.

Взять DVD посмотреть стоит 4$. Купить - 16$. Вопрос - сколько раз брать DVD посмотреть перед тем как купить?

Теоретической эта задача является в том смысле что "да я лучше из инета скачаю".

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

И где же свобода слова!!!???

Вот видео, на нем видно как полиция арестовывает человека в футболке с надписью McCain & Palin на праздновании избрания Б.Обамы президентом США.
Какой кошмар и ужас...какое попрание свободы...если бы не...

Ну во первых приходить к фанатам Спартака после первой за 8 лет победы над Зенитом в футболке "Зенит - чемпион!" само по себе не самая лучшая идея. Чтобы так сделать нужно сильно не дружить с головой.

А во вторых смотрим тут. На 3:33 видно что у чудика за спиной что-то типа меча. Не ну может быть там конечно безопасный вибратор, но этого не видно.

так что неплохая попытка мистер провокатор...

но с другой стороны - "осадочек остался". как же я это терпеть ненавижу...

кстати...при всей моей нелюбви к подобным массовым гуляниям то что чудика не взгрели - жирный плюсик Обамавским фанам.

Nemerle+Project Euler2 - продолжение.

Окозалось что нужные мне операторы есть!
В результате удалось написать вот такое:

SC.WriteLine(

    (1,1)

    |> F.unfold(_,(a,b)=>(a+2*b,2*a+3*b))

    |> F.takewhile(_,(a,b)=>(a+b)<4000000)

    |> F.fold(_,0,(v,x)=>v[0]+v[1]+x)

А можно было извратиться и дальше и написать вот так:

def write = SC.WriteLine:int -> void;

 

(1,1)   |> F.unfold(_,(a,b)=>(a+2*b,2*a+3*b))

        |> F.takewhile(_,(a,b)=>(a+b)<4000000)

        |> F.fold(_,0,(v,x)=>v[0]+v[1]+x)

        |> write(_);

дальше - забавы с pattern matching

Nemerle - что это и где...

Наконец-то решил изучить поподробнее...

Итак, что мы имеем. Nemerle это язык для платформы .NET. Гибридный. С кучей современных возможностей.

Помимо стандартных возможностей предлагает следующие замечательные вещи:

0. Привычный мейнстрим синтаксис. Т.е. это не хаскел, нет. Рядовой C#/C++/Java разработчик может перейти на Nemerle прочитав пару статей.

1. Tuples (это которые кортежи). Очень сложно обьяснить тем кто не пользовался насколько часто это удобно и насколько это упрощает некоторые вещи.
Тем кто знаком с Python - ага, те самые.
В терминах C#3.0 это будет "анонимные гетерогенные массивы" или как-то так. Но с правильной типизацией и очень удобные в использовании.

2. Pattern Matching (сопостовление по образцу). Если по простому - это "switch on steroids". Опять таки...после некоторого времени писанины на языке у которого есть поддержка pattern matching возврат к "старым добрым" if и switch вызывает ломку.

3. Type Inference (вывод типов). Правильнее чем в C#3.0, мощнее, удобнее. Вообщем код начинает питоновский напоминать. Хотя не хаскел конечно, но это и не нужно. К слову - фанаты динамических языков часто упрекают языки со статеческой типизацией в излишней многословности. Так вот - благодаря этому самому type inference это не так. Опять же - после использования языка с развитым type reference возврат в привычную песочницу вызывает ломку.

4. List Comprehensions (как это будет по русски - затрудняюсь). Фича присутствует в Python/Ruby/Haskell/Groovy и возможно где-то еще, не знаю. Фича удобная, когда ее отнимают ломка не возникает но все равно с ней приятнее чем без нее.

5. Функциональные типы (functional types). Я в этом разбираюсь достаточно поверхностно. Но даже моего уровня хватает чтобы понять - делегаты зло, функциональные типы это правильно. Делегаты в C# это некоторое подобие именнованных функциональных типов. Усложненное и с недостатками. Также функциональные типы напоминают Func<A,B>, но все равно их реализация в Nemerle намного правильнее.
Например функцию которая принимает в качестве параметра фукнцию принимающую int и string и возвращающую int можно описать вот так

some_func(f:int*string->string):void

6. Алгебраические типы. Есть отличия от "классических" алгебраических типов, но как по мне только в лучшую сторону. Опять же по простому для знающих С++ "алгебраические типы" это "union on steroids". Обобенно мощно себя проявляют в связке с pattern matching.

дальше просто лень писать ибо долго и много, но еще есть
...матапрограммирование (и огого-го какое. Например linq из С# реализуется макросами языка)...лямбды(ну куда ж без них в наше то время)...closures...да много чего. Причем большенство - прямо от рождения. Т.е. Nemerle таким умным родился, а не эволюционировал к пятой версии.

Вообщем по фичам языка вот тут интересная табличка. Сделайте скидку на то что составлялась евангелистом (читай - фанатом) языка. Но как по мне у него есть все основания фанатствовать.

Для знакомства с языком решил поиграться с первыми задачами из ProjectEuler...

Итак задача 2.

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million

Понятно что задача простая (хотя и тут можно кое-что...), суть не в ней.
Написав (точнее переписав) несколько extension methods для удобной работы с перечисляемыми типами (IEnumerable) я в первоначально пришел вот к такому решению:

        WriteLine(

            (1,1)

            .unfold((a,b)=>(b,a+b))

            .takewhile((_,b)=>b<4000000)

            .filter((a,_)=>a%2==0)

            .fold(0,(v,x)=>v[0]+x)

            );

теперь немного о простоте задачи. простая-то она простая, но и в ней можно оптимизировать решение.
рассмотрим первые числа последовательности, но следить будем только за четностью...
o(1),o(1),e(2),o(3),o(5),e(8),o,o,e,o,o,e,....

ну думаю заметно о чем идет речь...
и тогда наш код преобразуется в:

     WriteLine(

            (1,1)

            .unfold((a,b)=>(a+2*b,2*a+3*b))

            .take((a,b)=>(a+b)<4000000)

            .fold(0,(v,x)=>v[0]+v[1]+x)

            );

Попытался сделать макрос для функциональной композиции, чтобы код можно было записать так (идея честно украдена в F#):

     WriteLine(

            (1,1) |> unfold((a,b)=>(b,a+b)) |> take((_,b)=>b<4000000) |> filter((a,_)=>a%2==0) |> fold(0,(v,x)=>v[0]+x)

            );

пока не получилось...(

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

А вообще ситуация выглядит так:
- отдать бы Nemerle в хорошие руки (читать - микрософт. там к слову авторы языка уже обитают), и чтобы эти руки выделили человек 10 на разработку и еще несколько раз по столько на доки/примеры/т.д.
И чтобы эти руки добавили dynamic и какой-нибудь оператор для функциональной композиции. Ну и так...по мелочам.
И через полгода-год у нас бы был прекрасный язык, и еще через полгода все бы забыли про C#.

Выводы -
1. Nemerle это язык которым C# дай бог станет лет через пять. А то и все десять. И то - с ограничениями...
2. Если хорошие руки не найдутся - there is no future for Nemerle in this stupid and cruel world(.

А пока попробую всякие поделки клепать на Nemerle.