Алгоритм возведения в степень

Сегодня узнал красивый алгоритм возведения в степень. Образованным людям, наверное, это не интересно, но я поделюсь впечатлениями. Итак, мы хотим вычислить a^n. Представим n в следующем виде:

n = b[k] * 2^k + b[k-1] * 2^(k-1) + ... + b[0] * 2^0

Тогда:

a^n = a^(b[k] * 2^k + b[k-1] * 2^(k-1) + ... + b[0] * 2^0) =
  = a^(b[k] * 2^k) * a^(b[k-1] * 2^(k-1)) * ... * a^(b[0] * 2^0)

На основании чего получаем:

int Pow(int a, int p) {
    int res = 1;
    for (; p; p >>= 1, a *= a)
        if (p & 1)
            res *= a;
    return res;
}

Многопоточность. Защита разделяемых данных при инициализации (C++11 std::once_flag, std::call_once)

Часто какой-то разделяемый несколькими потоками ресурс используется только для чтения. Запись требуется только при инициализации ресурса. Очевидное решение проблемы:

std::shared_ptr<some_resource> resource_ptr;
std::mutex resource_mutex;

void foo() {
    std::unique_lock<std::mutex> lk(resource_mutex);
    if (!resource_ptr) {
        resource_ptr.reset(new some_resource);
    }
    lk.unlock();
    resource_ptr->do_something();
}

Это решение вполне thread-safe. Но оно обладает недостатком: даже после инициализации ресурса, при каждом обращении лочится мьютекс, что, конечно, занимает определенное время (особенно если 2 или более потока пытаются залочить мьютекс одновременно). Есть довольно популярный анти-паттерн, решающий проблему:

std::shared_ptr<some_resource> resource_ptr;
std::mutex resource_mutex;

void foo() {
    if (!resource_ptr) { // !!! data race
        std::lock_guard<std::mutex> lk(resource_mutex);
        if (!resource_ptr) {
            resource_ptr.reset(new some_resource);
        }
        resource_ptr->do_something();
    }
    resource_ptr->do_something(); // !!! data race
}

Даже от опытных разработчиков со стажем я уже не раз слышал перлы вроде: запись лочить нужно, чтение - нет; бит ведь неделим, либо запишется, либо нет. Бит, может быть, и неделим :) Но вот операции чтения/записи даже одного бита - не атомарны. Это как минимум 3 инструкции на ассемблере: 1) извлечь данные из памяти в регистр; 2) изменить данные; 3) поместить новое значение в память. Между шагами 1-2 и 2-3 может произойти смена контекста. Поэтому в примере выше - race condition. В С++11, оказывается, есть встроенное решение этой проблемы, обещающее меньший оверхед при локе:

std::shared_ptr<some_resource> resource_ptr;
std::once_flag resource_flag;

void init_resource() {
    resource_ptr.reset(new some_resource);
}

void foo() {
    std::call_once(resource_flag, init_resource);
    resource_ptr->do_something();
}

Более того, в C++11 гарантируется атомарность инициализации локальных статических переменных:

class my_class;
my_class& get_my_class_instance() {
    static my_class instance; // thread-safe
    return instance;
}

Источник: Anthony Williams, "C++ Concurrency in Action"

Знакомство с Erlang. Часть 3.

Решение problem2 на projecteuler

Вариант 1

-module(problem002).
-export([solve/1, fib_ex/4]).

fib_ex(Max, Sum, P, PP) ->
    Next = P + PP,
    if
        Next < Max, Next rem 2 == 0 -> fib_ex(Max, Next + Sum, Next, P);
        Next < Max, Next rem 2 == 1 -> fib_ex(Max, Sum, Next, P);
        Next >= Max -> Sum
    end.

solve(Max) ->
    fib_ex(Max, 0, 1, 1).

Вариант 2

-module(problem002).
-export([solve/1, fib_ex/4]).

fib_ex(Max, Sum, P, PP) when P + PP >= Max ->
    Sum;
fib_ex(Max, Sum, P, PP) ->
    Next = P + PP,
    case Next rem 2 of
        0 -> fib_ex(Max, Next + Sum, Next, P);
        1 -> fib_ex(Max, Sum, Next, P)
    end.

solve(Max) ->
    fib_ex(Max, 0, 1, 1).

Знакомство с Erlang. Часть 2.

Вычисление факториала

Книжный пример. Тут все просто и понятно:

factorial(0) -> 1;
factorial(N) ->
    N * factorial(N-1).

Вычисление чисел Фибоначчи

Пишу реализацию в лоб в надежде, что интерпретатор Erlang внутри реализует DP.

fib(0) -> 0;
fib(1) -> 1;
fib(N) ->
    fib(N-1) + fib(N-2).

Но уже при N=50 не могу дождаться результата. Выходит, никакого DP внутри нет, интерпретатор тупо уходит в рекурсию. Экспоненциальная сложность. Конечно, можно исправить на хвостовую рекурсию, но это уже не так красиво:

fib_ex(1) -> {1, 0};
fib_ex(2) -> {1, 1};
fib_ex(Num) ->
    {P, PP} = fib_ex(Num-1),
    {P + PP, P}.

fib(N) ->
    {P, _PP} = fib_ex(N),
    P.

Знакомство с Erlang. Часть 1.

Уже 5 лет разрабатываю на С++. И до сих пор не хочу ни на что его менять. Но вдруг появилось желание познакомиться с функциональными языками, в частности Erlang. На Yac2011 один умный дядечка призывал изучать другие языки программирования, т.к. это помогает взглянуть на вещи под другим углом. Ведь простые в одних языках конструкции, могут быть сложно выразимы в других. На эту тему есть отличное видео на TED (правда, про natural languages, но один в один):

Вдохновленный этими идеями и, несмотря на покручивания у виска коллег, начал читать Программирование в Erlang. Ф. Чезарини, С. Томпсон. После первых 2-3 глав выбрал в качестве helloworld решить problem1 на projecteuler на Erlang. Минут через 30 насилия над моим императивным мозгом выдавил:

-module(problem001).
-export([solve/1]).

% solve routine calculates sum of all natural numbers <= N which are multiples of 3 or 5

solve(N) when N == 0 ->
    0;
solve(N) when N rem 3 == 0 ->
    N + solve(N-1);
solve(N) when N rem 5 == 0 ->
    N + solve(N-1);
solve(N) ->
    solve(N-1).

highlight.js

Давно хотел научиться по-человечески подсвечивать код на своих страничках. Взял первое попавшееся - highlight.js

Как пользоваться:

1. Добавляем перед </head> строчки:

   <link rel="stylesheet" href="http://yandex.st/highlightjs/7.3/styles/default.min.css">
   <script src="http://yandex.st/highlightjs/7.3/highlight.min.js"></script>
   <script type="text/javascript">
       hljs.initHighlightingOnLoad();
   </script>

2. Вместо default.min.css можно указать какой-нибудь другой стиль. Например, solarized_dark.min.css. Список стилей можно посмотреть здесь
3. Оборачиваем блоки с кодом в пару тегов <pre><code> ... </code></pre>. Язык определяется автоматически.

Примеры:

Python

#!/usr/bin/env python
import sys, os

def foo():
    pass

C++

#include <iostream>
using namespace std;

int main() {
    cout << "Hello, World!" << endl;
    return 0;
}