std::shared_ptr aliasing constructor

Когда пишешь на С++, каждый день открываешь для себя что-то новое. Надоело держать это в себе. Хочется поделиться открытиями с миром :) Сегодня я открыл для себя std::shared_ptr aliasing constructor. Итак, пример кода (взят из книги The C++ Std. Library - Tutorial and Ref. 2nd ed):

struct X {
    int a;
};
shared_ptr px(new X);
shared_ptr pi(px, &px->a);  // здесь мы в действительности создаем шаред-пойнтер на экземпляр X,
                                 // но декорируем его как указатель на поле объекта

Это, конечно же, дает плюс-плюс несколько способов выстрелить себе в ногу. Например, так (пример из той же книги):

shared_ptr sp1(new X);
shared_ptr sp2(sp1, new X); // ERROR: delete for this X will never be called

sp1.reset();                   // deletes first X; makes sp1 empty
shared_ptr sp3(sp1,new X);  // use_count()==0, but get()!=nullptr

Project Euler - Problem 17 (Erlang solution)

Решение problem 17 на projecteuler

#!/usr/bin/env escript
-export([main/1]).

to_human_readable(Num) when Num < 10 ->
    case Num of
        0 -> "";
        1 -> "one";
        2 -> "two";
        3 -> "three";
        4 -> "four";
        5 -> "five";
        6 -> "six";
        7 -> "seven";
        8 -> "eight";
        9 -> "nine"
    end;
to_human_readable(Num) when Num < 20 ->
    case Num of
        10 -> "ten";
        11 -> "eleven";
        12 -> "twelve";
        13 -> "therteen";
        14 -> "fourteen";
        15 -> "fifteen";
        16 -> "sixteen";
        17 -> "seventeen";
        18 -> "eighteen";
        19 -> "nineteen"
    end;
to_human_readable(Num) when Num < 100 ->
    Decades = Num div 10,
    SDecades = case Decades of
        2 -> "twenty";
        3 -> "thirty";
        4 -> "forty";
        5 -> "fifty";
        6 -> "sixty";
        7 -> "seventy";
        8 -> "eighty";
        9 -> "ninety"
    end,
    Suf = string:concat(" ", to_human_readable(Num rem 10)),
    string:concat(SDecades, Suf);
to_human_readable(Num) when Num < 1000 ->
    Hundreds = Num div 100,
    SHundreds = string:concat(to_human_readable(Hundreds), " hundred"),
    Rest = Num - Hundreds * 100,
    case Rest of
        0 -> SHundreds;
        Rest ->
            Tmp = string:concat(SHundreds, " and "),
            string:concat(Tmp, to_human_readable(Rest))
    end;
to_human_readable(Num) when Num =:= 1000 ->
    "one thousand".

calc_size([H | Tail]) ->
    case H of
        32 -> calc_size(Tail);
        _ -> 1 + calc_size(Tail)
    end;
calc_size([]) ->
    0.

solve(N) ->
    Str = to_human_readable(N),
    Size = calc_size(Str),
    io:format("~p: ~p (size=~p)~n", [N, Str, Size]),
    case N of
        1 -> Size;
        _ -> Size + solve(N-1)
    end.

main(_) ->
    io:fwrite("Running problem017...~n"),
    N = 1000,
    Res = solve(N),
    io:format("Answer: ~w~n", [Res]),
    io:fwrite("Done.~n").

Project Euler - Problem 7

Решение problem7 на projecteuler

Brute-force Python solution

#!/usr/bin/env python

import math

def is_prime(num):
    if num in [2, 3, 5, 7, 11, 13]:
        return True
    min_div = math.trunc(num ** .5)
    for divisor in xrange(min_div, num - 1):
        if num % divisor == 0:
            return False
    return True

def find_nth_prime(index_of_prime_to_find):
    cur_idx = 1
    num = 2
    while (cur_idx < index_of_prime_to_find):
        num += 1
        if is_prime(num):
            cur_idx += 1
    return num

def main():
    res = find_nth_prime(10001)
    print 'Answer: %s' % res

if __name__ == '__main__':
    main()

Время:

real 0m53.172s
user 0m53.096s
sys 0m0.049s

Brute-force Erlang solution

#!/usr/bin/env escript
-export([main/1]).

is_prime_ex(N, CurDivisor) when CurDivisor < N ->
    Rem = N rem CurDivisor,
    case Rem of
        0 -> false;
        _ -> is_prime_ex(N, CurDivisor + 1)
    end;
is_prime_ex(N, CurDivisor) when CurDivisor =:= N ->
    true.

is_prime(N) ->
    MinDivisor = erlang:round( math:sqrt(N) ),
    is_prime_ex(N, MinDivisor).

calc_nth_prime(IndexOfPrimeToFind, CurIndex, N) when CurIndex =:= IndexOfPrimeToFind ->
    N - 1;
calc_nth_prime(IndexOfPrimeToFind, CurIndex, N) when CurIndex < IndexOfPrimeToFind ->
    NewIndex = case is_prime(N) of
        true ->
            io:format("CurIndex=~p N=~p~n", [CurIndex+1, N]),
            CurIndex + 1;
        false ->
            CurIndex
    end,
    calc_nth_prime(IndexOfPrimeToFind, NewIndex, N + 1).

main(_) ->
    io:fwrite("Running problem007...~n"),
    IndexOfPrimeToFind = 10001,
    Res = calc_nth_prime(IndexOfPrimeToFind, 1, 2),
    io:format("Answer: ~w~n", [Res]),
    io:fwrite("Done.~n").

Время:

real 70m52.613s
user 70m18.016s
sys 0m4.075s

Concurrent brute-force Erlang solution

#!/usr/bin/env escript
-export([main/1]).

is_prime_ex(N, CurDivisor) when CurDivisor < N ->
    Rem = N rem CurDivisor,
    case Rem of
        0 -> false;
        _ -> is_prime_ex(N, CurDivisor + 1)
    end;
is_prime_ex(N, CurDivisor) when CurDivisor =:= N ->
    true.

is_prime(N) ->
    MinDivisor = erlang:round( math:sqrt(N) ),
    is_prime_ex(N, MinDivisor).

slave_proc(MasterPID) ->
    ChildPID = self(),
    receive
        {stop} -> ChildPID;
        {calc_is_prime, N} ->
            %io:format("[SLAVE]: {calc_is_prime, ~p}~n", [N]),
            Res = is_prime(N),
            MasterPID ! {is_prime_result, ChildPID, N, Res},
            %io:format("[SLAVE]: Result: {is_prime_result, ~p, ~p, ~p}~n", [ChildPID, N, Res]),
            slave_proc(MasterPID);
        Message ->
            io:format("[SLAVE]: Invalid message format: ~p~n", [Message])
    end.

create_pool(_MasterPID, Size) when Size =:= 0 ->
    [];
create_pool(MasterPID, Size) when Size > 0 ->
    SlavePID = spawn(fun() -> slave_proc(MasterPID) end),
    [SlavePID, create_pool(MasterPID, Size - 1)].

run_pool([], _N) ->
    true;
run_pool([SlavePID, Pool], N) ->
    SlavePID ! {calc_is_prime, N},
    run_pool(Pool, N + 1),
    true.

calc_prime(IndexOfPrimeToFind, CurPrimeIndex, N, _MaxCalculatedN) when CurPrimeIndex =:= IndexOfPrimeToFind ->
    N - 1;
calc_prime(IndexOfPrimeToFind, CurPrimeIndex, N, MaxCalculatedN) when CurPrimeIndex < IndexOfPrimeToFind ->
    receive
        {is_prime_result, ChildPID, N, true} ->
            io:format("[MASTER]: N=~p CurPrimeIndex=~p MaxCalculatedN=~p ~n", [N, CurPrimeIndex, MaxCalculatedN]),
            ChildPID ! {calc_is_prime, MaxCalculatedN + 1},
            calc_prime(IndexOfPrimeToFind, CurPrimeIndex + 1, N + 1, MaxCalculatedN + 1);
        {is_prime_result, ChildPID, N, false} ->
            ChildPID ! {calc_is_prime, MaxCalculatedN + 1},
            calc_prime(IndexOfPrimeToFind, CurPrimeIndex + 0, N + 1, MaxCalculatedN + 1)
    after
            1 ->
                calc_prime(IndexOfPrimeToFind, CurPrimeIndex, N, MaxCalculatedN)
    end.

main(_) ->
    io:fwrite("Running problem007...~n"),
    IndexOfPrimeToFind = 10001,
    PoolSize = 1000,

    MasterPID = self(),
    Pool = create_pool(MasterPID, PoolSize),
    run_pool(Pool, 2),
    Res = calc_prime(IndexOfPrimeToFind, 1, 2, PoolSize),

    io:format("Answer: ~w~n", [Res]),
    io:fwrite("Done.~n").

Время на 4-ядерном Core i7:

real 23m2.769s
user 173m25.874s
sys 2m14.798s

Время на 16-ядерном сервере:

real    15m14.150s
user    464m56.428s
sys     5m46.956s

Project Euler - Problem 6 (Erlang solution)

Решение problem6 на projecteuler

#!/usr/bin/env escript
-export([main/1]).

calc_sum_of_squares(N) when N > 1 ->
    N*N + calc_sum_of_squares(N-1);
calc_sum_of_squares(N) when N =:= 1 ->
    1.

main(_) ->
    io:fwrite("Running problem005...~n"),
    N = 100,
    SquareOfSums = N * N * (N + 1) * (N + 1) div 4,
    Res = SquareOfSums - calc_sum_of_squares(N),
    io:format("Answer: ~w~n", [Res]),
    io:fwrite("Done.~n").

Project Euler - Problem 4 (Erlang solution)

Решение problem4 на projecteuler

#!/usr/bin/env escript
-export([main/1]).

int2list_ex(N, List) ->
    case N of
        _ when N < 10 -> [N | List];
        _ -> int2list_ex(N div 10, [N rem 10 | List])
    end.

int2list(N) ->
    int2list_ex(N, []).

is_palindrome([]) ->
    true;
is_palindrome([First | Tail]) ->
    RTail = lists:reverse(Tail),
    case RTail of
        [] -> true;
        [Last | Middle] when First =:= Last ->
            is_palindrome(Middle);
        [_ | _] ->
            false
    end.

is_palindrome_num(N) ->
    is_palindrome( int2list(N) ).

solve(I, J, Max, Res) ->
    ISP = is_palindrome_num(I * J),
    NewRes = case ISP of
        true -> max(Res, I * J);
        false -> Res
    end,
    case [I, J] of
        [Max, Max] -> NewRes;
        [_, Max] -> solve(I+1, Max, Max, NewRes);
        [Max, _] -> solve(0, J+1, Max, NewRes);
        [_, _] -> solve(I+1, J, Max, NewRes)
    end.

main(_) ->
    io:fwrite("Running problem004...~n"),
    io:format("Answer: ~p~n", [solve(1, 1, 999, 0)]),
    io:fwrite("Done.~n").

Время на Core i7:

 $> time ./problem004.erl
Running problem004...
Answer: 906609
Done.

real 0m52.486s
user 0m52.398s
sys 0m0.074s

Project Euler - Problem 5 (Erlang solution)

Решение problem5 на projecteuler

#!/usr/bin/env escript
-export([main/1]).

is_evenly_divisible(Num) ->
    case Num of
        _ when Num rem 20 =/= 0 -> false;
        _ when Num rem 19 =/= 0 -> false;
        _ when Num rem 18 =/= 0 -> false;
        _ when Num rem 17 =/= 0 -> false;
        _ when Num rem 16 =/= 0 -> false;
        _ when Num rem 15 =/= 0 -> false;
        _ when Num rem 14 =/= 0 -> false;
        _ when Num rem 13 =/= 0 -> false;
        _ when Num rem 12 =/= 0 -> false;
        _ when Num rem 11 =/= 0 -> false;
        _ when Num rem 9 =/= 0 -> false;
        _ when Num rem 8 =/= 0 -> false;
        _ when Num rem 7 =/= 0 -> false;
        _ when Num rem 6 =/= 0 -> false;
        _ when Num rem 3 =/= 0 -> false;
        _ -> true
    end.

find_smallest_evenly_divisible(N) ->
    IsED = is_evenly_divisible(N),
    case IsED of
        true -> N;
        false -> find_smallest_evenly_divisible(N+20)
    end.

main(_) ->
    io:fwrite("Running problem005...~n"),
    Res = find_smallest_evenly_divisible(20),
    io:format("Answer: ~w~n", [Res]),
    io:fwrite("Done.~n").

Время на Core i7:

 $> time ./problem005.erl
Running problem005...
Answer: 232792560
Done.

real 1m20.883s
user 1m19.928s
sys 0m0.958s

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

Сегодня узнал красивый алгоритм возведения в степень. Образованным людям, наверное, это не интересно, но я поделюсь впечатлениями. Итак, мы хотим вычислить 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;
}