Автор Тема: Решаем задачки. :)  (Прочитано 93325 раз)

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #15 : Сентябрь 27, 2011, 10:48:53 am »
К сожалению, время уменьшилось не в два раза на моём двухядернике ((
А ты как запускал?
У меня получилось 6 секунд, то есть раза в два быстрее прежних решений (по тактам сответственно так же).
Это сильно зависит от того, какие ещё проги в фоне работают. У меня  дома видимо тестам как раз они и мешали -- всякие оперы, чаты и прочая...
Возможно и от процессора тоже зависит...
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #16 : Сентябрь 27, 2011, 10:52:16 am »
Потестировал на i5.  4 ядра.

Имеем:
$ time echo 1374386913280000 | ./Main -N
Нет
Time = 0:0:4.124

real 0m4.132s
user 0m4.100s
sys 0m0.030s

$ time echo 1374386913280000 | ./MainPar -N
Нет
Time = 0:0:4.189

real 0m4.196s
user 0m4.164s
sys 0m0.029s


$ time echo 1374386913280000 | ./MainConc -N
Нет
Time = 0:0:5.284

real 0m5.292s
user 0m4.877s
sys 0m0.128s

$ time echo 1374386913280000 | ./a.out
No

real 0m0.792s
user 0m0.788s
sys 0m0.005s

Теперь отгадайте, который из них написан на Си? :-)
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #17 : Сентябрь 27, 2011, 11:00:56 am »
Потестировал на i5.  4 ядра.

Теперь отгадайте, который из них написан на Си? :-)

нипанятно. хаскельные варианты (которые c par и forkOS) запускались с ключами +RTS -N -RTS или без них?
кто-му же эти варианты расчитаны на два ядра, для 4-х их надо немного переделать )

а сишный вариант без изменений или заточен на многопоточность?
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #18 : Сентябрь 27, 2011, 11:18:53 am »
нипанятно. хаскельные варианты (которые c par и forkOS) запускались с ключами +RTS -N -RTS или без них?
кто-му же эти варианты расчитаны на два ядра, для 4-х их надо немного переделать )
В логах же видно с какими аргументами запускались программы.

а сишный вариант без изменений или заточен на многопоточность?
Си полностью однопоточный. Просто теперь он работает с 64битными целыми.

#include <stdlib.h>
#include <stdio.h>

typedef int64_t nat;

int main()
{
    nat n;
    scanf("%llu", &n);
    nat d,res=n-1;
    for (d=2; d<n && d<=n/d; d++)
        if (!(n%d)) res-=d+n/d;
    printf(!res ? "Yes\n" : "No\n");
    return 0;
}
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #19 : Сентябрь 27, 2011, 11:23:40 am »
Гм. Значит просто -N не достаточно? Почему же у меня дома работало. Вот свежие результаты:
$ time echo 1374386913280000 | ./Main +RTS -N -RTS
Нет
Time = 0:0:4.966

real 0m4.980s
user 0m5.803s
sys 0m0.329s

$ time echo 1374386913280000 | ./MainPar +RTS -N -RTS
Нет
Time = 0:0:3.611

real 0m3.619s
user 0m7.365s
sys 0m0.213s

$ time echo 1374386913280000 | ./MainConc +RTS -N -RTS
Нет
Time = 0:0:3.764

real 0m3.773s
user 0m7.767s
sys 0m0.243s

Кстати, сложность задачи от значения аргумента зависит не линейно. Соответственно у Си-решения такое же время исполнения как у хаскель-решения получается если увеличить аргумент не в 10 а в 100 раз.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #20 : Сентябрь 27, 2011, 02:02:42 pm »
Кстати, сложность задачи от значения аргумента зависит не линейно. Соответственно у Си-решения такое же время исполнения как у хаскель-решения получается если увеличить аргумент не в 10 а в 100 раз.

не понял. в обоих решениях O(n^0.5)...
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #21 : Сентябрь 27, 2011, 02:07:29 pm »
Кстати, сложность задачи от значения аргумента зависит не линейно. Соответственно у Си-решения такое же время исполнения как у хаскель-решения получается если увеличить аргумент не в 10 а в 100 раз.

не понял. в обоих решениях O(n^0.5)...
Это и есть не линейная зависимость :-)
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

kemiisto

  • Jr. Member
  • **
  • Сообщений: 64
    • Просмотр профиля
    • kemiisto.ru
Re: Решаем задачки. :)
« Ответ #22 : Сентябрь 28, 2011, 11:12:06 am »
Фаллометрию тут устроили! :D

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #23 : Сентябрь 28, 2011, 02:05:59 pm »
Задачи дурацкие, непонятно какие умения они должны развивать. Уровень решения на КП - ниже плинтуса.
Правда, книгу я не читал. ("Сам я Пастернака не читал, но, как честный советский человек, "... и.т.п.)

Про Хаскель: сам до сих пор не могу переделать свое мышление в функциональное, но, чем дальше, тем больше убеждаюсь, что программы на нем синтезируются (т.е. пишутся) с помощью вдохновения, озарения, догадки и т.п. Нет рабочего инструмента, который бы позволял профессионалу в любом состоянии гарантированно выдавать результат. Который не сильно отличался бы у разных людей.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #24 : Сентябрь 28, 2011, 02:34:56 pm »
2Geniepro:

Так какой вариант решения второй задачи закинуть в репозиторий? Решение должно быть с одной стороны эффективным, а с другой - легко понимабельным (все же для новичков это делается) и требующим минимума плясок с бубном при компиляции и запуске. То есть оно не должно требовать скриптов компиляции, компилироваться должно как-то так: "ghc MyCoolSolution.hs".

Как ответишь - закину всю пачку решений хаскелевских.

PS. Решения на других языках приветствуются.
PPS. 2kemiisto: новые задачки из книжки также приветствуются :-)
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

DIzer

  • Гость
Re: Решаем задачки. :)
« Ответ #25 : Сентябрь 28, 2011, 02:53:00 pm »
Задачи дурацкие, непонятно какие умения они должны развивать. Уровень решения на КП - ниже плинтуса.
  Базовой алгоритмизации для новичков.
Цитировать
Правда, книгу я не читал. ("Сам я Пастернака не читал, но, как честный советский человек, "... и.т.п.)
Оно и видно, даже название книги не  удосужились прочитать. Да я бы не сказал что  "честный советский человек", скорее "недалекий"
Цитировать
Про Хаскель: сам до сих пор не могу переделать свое мышление в функциональное, но, чем дальше, тем больше убеждаюсь, что программы на нем синтезируются (т.е. пишутся) с помощью вдохновения, озарения, догадки и т.п. Нет рабочего инструмента, который бы позволял профессионалу в любом состоянии гарантированно выдавать результат. Который не сильно отличался бы у разных людей.
При отсутствии реальной потребности в таких решениях, может помочь лишь природная любознательность(в редких случаях тщеславие). Увы с годами последняя увядает (сужу по себе).
« Последнее редактирование: Сентябрь 28, 2011, 02:56:48 pm от DIzer »

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #26 : Сентябрь 28, 2011, 02:57:24 pm »
Оно и видно, даже название книги не  удосужились прочитать.
Откуда это следует?

DIzer

  • Гость
Re: Решаем задачки. :)
« Ответ #27 : Сентябрь 28, 2011, 03:00:01 pm »
Оно и видно, даже название книги не  удосужились прочитать.
Откуда это следует?
Из первого вашего высказывания.

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #28 : Сентябрь 28, 2011, 03:16:05 pm »
Оно и видно, даже название книги не  удосужились прочитать.
Откуда это следует?
Из первого вашего высказывания.
Т.к. название я прочитал, то по факту вывод неверный. Клеветы, в общем  :)
Про Хаскель: сам до сих пор не могу переделать свое мышление в функциональное, но, чем дальше, тем больше убеждаюсь, что программы на нем синтезируются (т.е. пишутся) с помощью вдохновения, озарения, догадки и т.п. Нет рабочего инструмента, который бы позволял профессионалу в любом состоянии гарантированно выдавать результат. Который не сильно отличался бы у разных людей.
При отсутствии реальной потребности в таких решениях, может помочь лишь природная любознательность(в редких случаях тщеславие). Увы с годами последняя увядает (сужу по себе).
Реальные потребности, а также мои или ваши любознательность и тщеславие здесь не при чем. Я говорю о том, что из-за отсутствия инструмента решения разных людей могут сильно различаться очень сильно. Вот в этой шутке http://www.willamette.edu/~fruehr/haskell/evolution.html очень много "не шутки".

DIzer

  • Гость
Re: Решаем задачки. :)
« Ответ #29 : Сентябрь 28, 2011, 03:26:52 pm »
Цитировать
Т.к. название я прочитал, то по факту вывод неверный. Клеветы, в общем  :)
Вы меня поняли - значит небезнадежны  ;)
Цитировать
Реальные потребности, а также мои или ваши любознательность и тщеславие здесь не при чем. Я говорю о том, что из-за отсутствия инструмента решения разных людей могут сильно различаться очень сильно. Вот в этой шутке http://www.willamette.edu/~fruehr/haskell/evolution.html очень много "не шутки".
Не понимаю - о каких различия в решениях вы говорите, и причем здесь они (различия)? Я лично говорю про то, что "нафига мне изучать новый яп, если мне текущих знаний и навыков хватает на то чтобы справиться с любой интересной(в широком смысле)  проблемой"
Да это прямой оффтоп... предлагаю завершить ЭТУ дискуссию в ЭТОЙ ветке.
« Последнее редактирование: Сентябрь 28, 2011, 03:30:24 pm от DIzer »