Rating@Mail.ru

Форум по операционной системе GNU/Linux и свободному программному обеспечению


Текущее время: 16 дек 2017, 21:44

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.
Автор Сообщение
Непрочитанное сообщениеДобавлено: 24 авг 2014, 14:12 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10265
Откуда: Харьков
Виктория писал(а):
В качестве вычислительных я бы остановилась на прямых методах решения СЛАУ - метод Гаусса с выбором главного элемента или метод Гаусса-Жордана, например.
Цитата:
И ещё: какой ещё другой класс задач может использоваться для сравнения?

Алгоритмы сортировки, может быть? Пузырьковая сортировка и метод Гаусса часто используются в обработке числовых данных, всем известны и вроде не являются уж совсем простыми.


1. С сортировкой идея хорошая. Хотя это и не вычислительная задача. Но это и есть ещё один класс задач - обменные задачи в памяти. Степерь сложности (роста) пузырьковой сортировки, как мне помниться, O(n^2), что очень плохо для практики, но может быть недостаточно для получения измеримых времён выполнения. Надо пробовать.

2. С вычислительными задачами вы как-то своим сообщениям меня подтолкнули ;-) , сразу возник хороший вариант: вычисление автокорреляционной функции или Фурье преобразование, только не по алгоритму БПФ, быстрому, а "в лоб", там тоже O(n^2).

3. Что касаемо "метод Гаусса с выбором главного элемента или метод Гаусса-Жордана" - то я просто не помню что это. Лет 30-35 назад знал, сейчас забыл за ненадобностью.
Вы ссылочку киньте на какой-пибудь популярный вики? ;-)
Думаю, что такой же подобной задачей будет, из той же области, обращение квадратной матрицы (?).


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 24 авг 2014, 18:03 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 28 дек 2012, 14:05
Сообщения: 113
Откуда: Самара
Olej писал(а):
...
3. Что касаемо "метод Гаусса с выбором главного элемента или метод Гаусса-Жордана" - то я просто не помню что это. Лет 30-35 назад знал, сейчас забыл за ненадобностью.
Вы ссылочку киньте на какой-пибудь популярный вики? ;-)
Думаю, что такой же подобной задачей будет, из той же области, обращение квадратной матрицы (?).

Метод Гаусса на Википедии
или На Machinelearning


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 25 авг 2014, 12:08 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10265
Откуда: Харьков
Olej писал(а):
Есть ещё вопрос:
- скоростные характеристики любого языка и его исполняющей системы будут радикально зависеть от класса решаемых задач ... об этом уже много говорилось;
- предыдущее сравнение - это механизм вызовов функций (с передачей параметров etc. ...), то что там рекурсия - это не столь важно;
- интересно бы такое же параллельное сравнение на других классах задач...
- наприер, на сугубо вычислительных, с вещественной математикой, может что-то из области вычисления математических спец. функций рядами ... но нужно работу большой производительности, что-то из рядов с плохой сходимостью, хорошо бы ещё с зависмостью вычислительной сложности O(n) высокого порядка, где n, скажем, 1/eps, а eps - точность, величина сходимости (1e5, 1e7, 1e9, ...).


Мне эту "задачку", в такой постановке, подкинули редакторы при публикации этих заметок на IBM DeveloperWorks.
Не сам придумал :lol:


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 25 авг 2014, 12:12 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10265
Откуда: Харьков
Виктория писал(а):
Цитата:
И ещё: какой ещё другой класс задач может использоваться для сравнения?

Алгоритмы сортировки, может быть? Пузырьковая сортировка


Сделал! ;-)

Пока сравнение только 3-х языков, которые меня на сейчас интересуют: C, C++, Go.
И разных компиляторов: GCC + Clang для C, GCCGO + GoLang для Go.

Makefile:
Код:
TASK = sort_c sort_cc sort_cl sort_go sort_gc

all: $(TASK)

%: %.c
        gcc -Wall -O0 $< -o $@
%: %.cc
        g++ -Wall -O0 $< -o $@
%: %.go
        gccgo -Wall $< -g -O0 -o $@

sort_cl: sort_c.c
        clang -O0 $< -o $@

sort_gc: sort_go.go
        go build -o $@ -compiler gc $<

clean:
        rm -f $(TASK)


Выполнение:
Код:
$ time ./sort_c 20000
199990000

real   0m1.500s
user   0m1.494s
sys   0m0.000s

$ time ./sort_cc 20000
199990000

real   0m19.007s
user   0m18.946s
sys   0m0.009s

$ time ./sort_cl 20000
199990000

real   0m1.451s
user   0m1.447s
sys   0m0.001s

$ time ./sort_go 20000
199990000

real   0m2.303s
user   0m2.295s
sys   0m0.006s

$ time ./sort_gc 20000
199990000

real   0m1.141s
user   0m1.140s
sys   0m0.000s


Вложения:
sort.19.tgz [2.51 КБ]
Скачиваний: 378
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 25 авг 2014, 12:51 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10265
Откуда: Харьков
Olej писал(а):
Выполнение:


- То, что C++ отстаёт от остальных участников практически на порядок — это указывает только на нечестность такого сравнения: код на C++ написан с использованием средств STL, шаблонного типа vector<long long> и итераторов, в то время, как все остальные варианты — прямой адресацией элементов массива. Такая реализация в C++ сделана специально, чтобы показать гибкость STL механизмов.

- Удивила компиляция кода C компилятором Clang: результаты лучше, чем у GCC (по крайней мере, без вовлечения оптимизации).

- Язык Go (в варианте GCC) если и уступает C по скорости, то только порядка 50%, при том предоставляя гибкость и выразительную мощность соизмеримую с C++ с использованием STL (см. код).

- Окончательно удивил результат, показанный Go из проекта Clang (родной проект развития Go) — такой код оказался быстрее, чем код C компилированный GCC (базовая связка для проектов Linux)!


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 26 авг 2014, 01:53 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10265
Откуда: Харьков
Lepton писал(а):
Скриптовый язык Tcl

[fibo.tcl]
Код:
proc tcl::mathfunc::fib {n} {
  if { $n < 2 } {
     return 1
} else {
     return [expr {fib($n-1) + fib($n-2)}]
  }
}
puts [tcl::mathfunc::fib [lindex $argv 0]]


Код:
time nice -9 tclsh fibo.tcl 30
1346269

real    0m2.042s
user    0m2.014s
sys     0m0.016s


Сделал между делом оценивание скорости такого решения.
Средние (из нескольких) показателей:
Код:
[Olej@modules speed]$ time ./fibo.tcl 30
1346269

real   0m0.830s
user   0m0.830s
sys   0m0.000s

Код:
[Olej@modules speed]$ time ./fibo_c 30
1346269

real   0m0.005s
user   0m0.004s
sys   0m0.000s

По сравнению с C компилированной программой это раз в 160 медленнее.
Olej писал(а):
Итого, 18 рассмотренных пока реализации раскладываются по вот таким логарифмическим кластерам:
Код:
Фактор скорости    Язык
1 ... 2           C, GCC C++, Go
2 ... 5           Cobj C++, PureBasic
5 ... 10          Ocaml
10 ... 20         Java
20 ... 50         Lua, Scheme, Haskell
50 ... 100        Python 2, Ruby, JavaScript, Scala
100 ... 200       Perl, Python 3, PHP
200 ... 500       bash


Т.е. Tcl где-то в одном кластере с Perl, Python 3, PHP.


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 26 авг 2014, 13:32 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 28 дек 2012, 14:05
Сообщения: 113
Откуда: Самара
Olej писал(а):
- например, на сугубо вычислительных, с вещественной математикой, может что-то из области вычисления математических спец. функций рядами ... но нужно работу большой производительности, что-то из рядов с плохой сходимостью, хорошо бы ещё с зависмостью вычислительной сложности O(n) высокого порядка, где n, скажем, 1/eps, а eps - точность, величина сходимости (1e5, 1e7, 1e9, ...).

Метод бисекции (дихотомии), м.б.? А зачем O(n) высокого порядка? Чтобы оценить возможности распараллеливания?


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 26 авг 2014, 14:21 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10265
Откуда: Харьков
Виктория писал(а):
Olej писал(а):
- например, на сугубо вычислительных, с вещественной математикой, может что-то из области вычисления математических спец. функций рядами ... но нужно работу большой производительности, что-то из рядов с плохой сходимостью, хорошо бы ещё с зависмостью вычислительной сложности O(n) высокого порядка, где n, скажем, 1/eps, а eps - точность, величина сходимости (1e5, 1e7, 1e9, ...).

Метод бисекции (дихотомии), м.б.? А зачем O(n) высокого порядка? Чтобы оценить возможности распараллеливания?


Нет. Всё гораздо прозаичнее ;-) :
- у меня есть 3-4-5 компьютеров очень разного возраста и очень разной производительности...
- у тех, кто захочет повторять тесты могут тоже быть компьютеры с производительностью, отличающейся на порядок...
- при фиксированных n у кого-то тест займёт 0.03 сек. (по time ...) и это не корректно для сравнений, потому как вблизи нижнего предела разрешения временной шкалы...
- а у кого-то при этом же n это займёт 1-2 мин. ... и это очень тоскливое занятие.

Вариацией n хорошо бы вывести время прогона в диапазон 10-100 сек.
А для этого общий объём вычислительной работы (на очень разном оборудовании) вариацией n нужно изменять на 3-4 порядка.

Я не хочу гадать при каких значениях n у меня будет удобоваримое общее время исполнения + не хочу менять n в коде программы с последующей компиляцией, удобно n задавать как параметр командной строки.


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 31 авг 2014, 14:47 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 18 окт 2011, 20:26
Сообщения: 73
Язык программирования Euphoria :-) (для вычисления чисел Фибоначчи)
Код:
$ eui -v
Euphoria Interpreter v4.0.5
   Linux, Using System Memory
   Revision Date: 2012-10-15, Id: 62d94559f849

[fibo.ex]
Код:
include std/convert.e
sequence i = command_line()

function fib(integer n)
if n<2 then return 1 end if
return fib(n-1)+fib(n-2)
end function

printf(1,"%d\n",fib(to_integer(i[$])))


выполнение
Код:
$ time eui fibo.ex 30
1346269

real    0m1.389s
user    0m1.264s
sys     0m0.120s


тут проблема в "отжирании времени" преобразованием аргумента командной строки (comand_line()/to_integer()), без них выполняется быстрее:
[fibo.ex]
Код:
function fib(integer n)
if n<2 then return 1 end if
return fib(n-1)+fib(n-2)
end function
printf(1,"%d\n",fib(30))


выполнение
Код:
$ time eui fibo.ex
1346269

real    0m1.000s
user    0m0.977s
sys     0m0.020s


Для сравнения
Код:
$ gcc --version
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2

$ time ./fibo_c 30
1346269

real    0m0.042s
user    0m0.037s
sys     0m0.005s


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 01 сен 2014, 10:16 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 18 окт 2011, 20:26
Сообщения: 73
Euphoria v4.1.0 (beta)
Код:
$ eui -v
Euphoria Interpreter v4.1.0 development
   64-bit Linux, Using System Memory
   Revision Date: 2014-01-16 02:53:44, Id: 5783:d41527402a7a


Код:
--fibo.ex
include std/convert.e
sequence i = command_line()

function fib(integer n)
if n<2 then return 1 end if
return fib(n-1)+fib(n-2)
end function

printf(1,"%d\n",fib(to_integer(i[$])))
---------------
$ time eui fibo.ex 30
1346269

real    0m0.887s
user    0m0.743s
sys     0m0.141s


Код:
--fibo.ex
function fib(integer n)
if n<2 then return 1 end if
return fib(n-1)+fib(n-2)
end function
printf(1,"%d\n",fib(30))
---------------
$ time eui fibo.ex
1346269

real    0m0.574s
user    0m0.551s
sys     0m0.022s


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB
[ Time : 0.668s | 20 Queries | GZIP : On ]