Встреча LUG-а в сентябре 2011 (для первокурсников)

Тема в разделе "Группа пользователей Линукс МИФИ - MEPhI Linux Use", создана пользователем DmitryEfanov, 30 авг 2011.

  1. RPG

    RPG Активный корумчанин

    Были бы сырцы - на досуге займемся
  2. AlexKuk

    AlexKuk Корумчанин

    Вот то, что было написано на докладе http://dl.dropbox.com/u/1705348/Ticket%20s...20--%20Sage.pdf
    Код для генерации графика сверху бесследно утерян =)

    Кстати, я почти совсем перешёл на ipython http://ipython.org/ , чтобы что-нибудь посчитать или график построить. Отличная штука, всем советую
  3. RPG

    RPG Активный корумчанин

    ЙаЗмейко?

    Все-таки у питона сумасшедший синтаксис. Я привык даже к begin-end языкам, но к этому, похоже, придется долго привыкать. Без камментов издали похоже что читаешь стихи Маяковского^_^

    Чур я пишу на lua:) Давно хотел его JIT потестить
  4. Brainiac

    Brainiac О_0

    блин...я пропустил мероприятие... черт...
  5. katarsis

    katarsis Активный корумчанин

    ^_^
  6. RPG

    RPG Активный корумчанин

    AlexKuk, сколько у тебя вариантов получилось? Как ни крути у меня либо 10к с хвостиком или если с делением - 40к, но никак не 11 тысяч про которые ты говорил на встрече.

    Да кстати считает очень медленно даже с jit - 1 билет за 0.1 сек. Но 1000 билетов за 27 сек. Думаю инициализация время съедает тоже, но все равно небыстро.
  7. AlexKuk

    AlexKuk Корумчанин

    Если в билетике 6 цифр, то есть 42 способа расставить скобочки http://oeis.org/search?q=42&sort=&...h&go=Search и 3**5 способов расставить там операции (+ - *), получается 10 206 вариантов. Так что у тебя всё правильно получается.

    А как ты скобочки генерировал? Есть супер умные быстрые способы, про них ещё Кнут писал.
  8. RPG

    RPG Активный корумчанин

    Алгоритм полностью эквивалентен твоему^_^ Бинарные деревья, нагенерил все перестановки знаков и прогнал билет.
  9. AlexKuk

    AlexKuk Корумчанин

    А можешь показать код и сказать какой у тебя проц.

    У меня как раз лежит на полке четвёртый том Кнута, который весь про комбинаторную генерацию =) Может быть когда-нибудь сделаю быструю реализуцию на Питоне и сравним.
  10. RPG

    RPG Активный корумчанин

    Код:
    local ticket = {1, 1, 1, 2, 5, 7}
    
    local operations = {
    function (a, b) return a + b end,
    function (a, b) return a - b end,
    function (a, b) return a * b end,
    function (a, b) return a / b end,
    }
    
    local operation = {}
    local floor = math.floor
    local pow = math.pow
    for i = 0, math.pow(#operations, #ticket - 1) do
    operation[i] = {}
    for j = 1, #ticket do
    operation[i][j] = operations[floor(i/pow(#operations, j-1))%#operations+1]
    end
    end
    
    local operations_str = {
    '+', '-', '*', '/'
    }
    
    BinaryTrees = function(vert)
    if vert == 0 then
    return {false}
    else
    local buf = {}
    for leften = 0, vert - 1 do
    local righten = vert - leften - 1
    for _, left in pairs(BinaryTrees(leften)) do
    for _, right in pairs(BinaryTrees(righten)) do
    table.insert(buf, {left, right})
    end
    end
    end
    return buf
    end
    end
    
    local c, opc, oper, operbuf
    
    local op = function(a,b)
    opc = opc + 1
    return operbuf[opc](a, b)
    end
    
    local aa, bb
    EvalTree = function(tree)
    if tree == false then
    c = c + 1
    return ticket[c-1]
    else
    return op(EvalTree(tree[1]), EvalTree(tree[2]))
    end
    end
    
    local op_str = function(a,b)
    opc = opc + 1
    return '('.. a .. operations_str[math.floor(oper/math.pow(#operations, opc-1))%#operations+1] .. b ..')'
    end
    
    EvalTreePrint = function(tree)
    if tree == false then
    c = c + 1
    return ticket[c-1]
    else
    return op_str(EvalTreePrint(tree[1]), EvalTreePrint(tree[2]))
    end
    end
    
    local trees = BinaryTrees(#ticket-1)
    local n
    for ticket_num = 100000, 101000 do
    n = ticket_num
    for i = 1, #ticket do
    ticket[#ticket-i+1] = n % 10
    n = floor(n/10)
    end
    for _, v in ipairs(trees) do
    for i = 0, math.pow(#operations, 5) do
    c, opc = 1, 0
    oper = i
    operbuf = operation[i]
    if EvalTree(v) == 100 then
    c, opc = 1, 0
    print(ticket_num, EvalTreePrint(v))
    end
    end
    end
    end 
    $ time luajit -O3 ticket.lua >result

    real 0m22.694s
    user 0m22.525s
    sys 0m0.108s

    $ time lua ticket.lua > result

    real 3m57.287s
    user 3m54.115s
    sys 0m2.432s

    C jit-компиляцией заметно быстрее.
    Процессор - одноядрёный PIV 3.2 GHz, память DDR 3200

    Кнутовский алгоритм было бы неплохо увидеть, но тогда справедливости ради нужно будет провести эту оптимизацию и мне.
  11. RPG

    RPG Активный корумчанин

    Во дела... Реализация на си - 30 секунд то же действие. Конечно, и там и там есть куда оптимизировать, но луа приятно поражает.
  12. AlexKuk

    AlexKuk Корумчанин

    Я не верю. Можно код? Там где-то не оптимально наверное =)
  13. RPG

    RPG Активный корумчанин

    Да, не совсем. Дело в том что я считал на флотах из-за деления. Убрал деление и сделал си на интах - 5 секунд на рассчет 4000 билетов, луа тратит на тот же расчет 20 сек. Учитывая, что язык луа не поддерживает никаких типов кроме double, большущий респект этому языку. Скрипт работающий почти со скоростью си - добавим к этому размер интерпретатора в 300 кб - получаем великую встраиваемую вещь.

    Плюс прикрутил к си мантру с указателями, зато работает в 2 раза быстрее:
    operation = (int (**)(int, int))malloc(sizeof(int (*)(int, int))*max*(SIZE-1));
    :crazy:

    оптимизация луа осложняется тем что я немного фигею с того факта, что если в луа сделать оптимизацию рекурсии (уменьшил число рекурсивных вызовов, убрал лишний вызов функции) - скорость упала в 2 раза, а если наоборот, сделать много-много мелких вызовов - работает очень быстро. Возможно, слишком сложная рекурсия мешает жит-компилятору оптимизировать код, не знаю... Я уж молчу про то что объявление переменной внутри функции в луа приводит к увеличению времени на три секунды.

    ЗЫ приручу специфичную для luajit оптимизацию - посмотрим как изменится. Дело в тому что новое расширение позволяет работать не только с типом double, но и и int и вообще со всем что возможно в си. Можете считать меня фанатом прототипных языков программирования, но lua и JavaScript просто гениальные штуки.
  14. AlexKuk

    AlexKuk Корумчанин

    Можешь код показать? строка перед смайликом интригует
  15. AlexKuk

    AlexKuk Корумчанин

    Мне кажется 1000 билетиков должно меньше секунды твоём проце решаться
  16. RPG

    RPG Активный корумчанин

    1000 решается за секунду, так и есть, цифры для 4000 билетиков.
    Код на си:
    Код:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct tree {
    struct tree *left;
    struct tree *right;
    } tree;
    
    #define SIZE 6
    #define OPS 3
    #define dbg(var) printf("%d\n", var)
    
    int operation_add(int a, int b) {return a + b;}
    int operation_sub(int a, int b) {return a - b;}
    int operation_mul(int a, int b) {return a * b;}
    int operation_div(int a, int b) {return a / b;}
    
    const char * operations_str = "+-*/";
    
    char str[64];
    
    int (*operations[4])(int, int) = {&operation_add, &operation_sub, &operation_mul, &operation_div};
    int (**operation)(int, int);
    
    char ticket[6];
    
    int powi(int base, unsigned int exponent)
    {
    int res = 1, i;
    for (i = 0; i < exponent; i++) {
    res *= base;
    }
    return res;
    }
    
    //грязный хак: заранее посчитанные размеры массивов... Нет ну не прикручивать же вектор ради этого
    const int btree_size[] = {1, 1, 2, 5, 14, 42};
    
    tree ** BinaryTrees(int vert)
    {
    tree ** buf;
    tree ** left;
    tree ** right;
    int leften, righten, i, j, k = 0;
    if(vert == 0)
    {
    return NULL;
    }
    else
    {
    buf = (tree**)malloc(sizeof(tree*) * btree_size[vert]);
    for(leften = 0; leften < vert; leften++)
    {
    righten = vert - leften - 1;
    left = BinaryTrees(leften);
    right = BinaryTrees(righten);
    for (i = 0; i < btree_size[leften]; i++)
    {
    for (j = 0; j < btree_size[righten]; j++)
    {
    buf[k] = (tree*)malloc(sizeof(tree));
    buf[k]->left = left ? left[i] : NULL;
    buf[k]->right = right ? right[j] : NULL;
    k++;
    }
    }
    }
    return buf;
    }
    }
    
    int oper, c, opc;
    int EvalTree(tree * t)
    {
    int a, b;
    if(t == NULL) {
    return ticket[c++];
    } else {
    a = EvalTree(t->left);
    b = EvalTree(t->right);
    return operation[oper*(SIZE-1)+opc++](a, b);
    }
    }
    
    char * EvalTreePrint(tree * t)
    {
    char *a, *b, *buf;
    if(t == NULL) {
    buf = (char*)malloc(sizeof(char)+1);
    sprintf(buf, "%d", ticket[c]);
    c++;
    } else {
    a = EvalTreePrint(t->left);
    b = EvalTreePrint(t->right);
    buf = (char*)malloc(sizeof(char)*(strlen(a) + strlen(b))+4);
    sprintf(buf, "(%s%c%s)", a, operations_str[(oper/powi(OPS, opc++))%OPS], b);
    free(a);
    free(b);
    }
    return buf;
    }
    
    int main()
    {
    tree ** trees = BinaryTrees(SIZE - 1);
    int max = powi(OPS, SIZE - 1);
    int ticket_num, n, i, j, eval;
    char * buf;
    operation = (int (**)(int, int))malloc(sizeof(int (*)(int, int))*(max)*(SIZE-1));
    for (i = 0; i < max; i++)
    for (j = 0; j < SIZE-1; j++)
    operation[i*(SIZE-1)+j] = operations[(i/powi(OPS, j))%OPS];
    for(ticket_num = 100000; ticket_num <= 104000; ticket_num++)
    {
    n = ticket_num;
    for (i = 0; i < SIZE; i++) {
    ticket[SIZE - i - 1] = n % 10;
    n /= 10;
    }
    for (i = 0; i < btree_size[SIZE-1]; i++) 
    {
    for (j = 0; j < max; j++)
    {
    oper = j;
    opc = c = 0;
    eval = EvalTree(trees[i]);
    if(eval == 100)
    {
    opc = c = 0;
    buf = EvalTreePrint(trees[i]);
    printf("%d\t%s\n", ticket_num, buf);
    free(buf);
    }
    }
    }
    }
    }
  17. AlexKuk

    AlexKuk Корумчанин

    Чтобы не получилось, что наши программы делают разные вещи, я решил, написать тесты. В https://gist.github.com/1268117 файл вида: на первой строке число тестов N, на следующиx N строках тесты вида: через пробел 6 цифр билетика, пробел, число способов сделать из этого билетика число 100 с помощью операций + - *

    RPG, если хочешь, можешь проверить свои проги. Чтобы не показалось, что я меняю правила на ходу, хочу заметить, что я даже близко не начинал писать свою реализацию. Тесты получились из проги, которая была написана на докладе.
  18. RPG

    RPG Активный корумчанин

    Что-то я не понял. В чем суть теста? Тест, это когда на программу подается вход и должен получиться заранее известный выход. У меня, например, обе проги генерируют идентичные файлы, в качестве теста - генерация всех билетиков от 100000 до 104000
  19. AlexKuk

    AlexKuk Корумчанин

    Всё верно. Только теперь будут билетики не от 100000 до 104000, а 1000 случайных и нужно не выводить все ответы, а просто посчитать их количество для каждого билетика. Это нужно чтобы не париться с выводом. То есть даётся 1000 заранее известных билетиков и 1000 заранее известных ответов.

    Если есть идеи, как решить задачу подсчёта решений без приведения самих решений не использую перебор, который мы сейчас используем, хотел бы он них услышать.
  20. RPG

    RPG Активный корумчанин

    Сейчас пока этим не занимаюсь - пока делай на питоне/йапитоне - посмотрим что получится. Если у него есть жит - совсем хорошо.

    Насчет перебора - есть идея кэш результата - ведь по большому счету 10299 и 12099 одинаковы и львиную долю билетов можно не считать. Но ради чистоты эксперимента я перебираю всё подряд.

    Подведу итоги (от 10000 до 104000):
    lua - 35 секунд
    luajit без jit - 14 секунд
    luajit - 14 секунд
    C - 4.66 сек.

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

Поделиться этой страницей