OberonCore https://forum.oberoncore.ru/ |
|
Скорость вычислений в BlackBox vs Java https://forum.oberoncore.ru/viewtopic.php?f=26&t=30 |
Страница 1 из 1 |
Автор: | Гость [ Воскресенье, 27 Ноябрь, 2005 19:57 ] |
Заголовок сообщения: | Скорость вычислений в BlackBox vs Java |
Задумался я, что лучше использовать (BlackBox или Java), если по ходу дела требуется много и упорно считать (в основном целочисленная арифметика большой точности). Почему выбор из этих двух? Просто на Java есть опыт, а Компонентный Паскаль легко освоить. В BlackBox есть модуль Integers. Делаем простой тест: считаем факториал 20000 в BlackBox и Java. Получаем что Java быстрее в три раза. На моей машине время вычислений такое: Java 4 sec, BlackBox 14 sec. Java Код: import java.math.*; public class Main { public static void main(String[] args) { long start = System.currentTimeMillis(); BigInteger res = fact(20000); long stop = System.currentTimeMillis(); System.out.println(stop - start); } private static BigInteger fact(int n) { BigInteger res = BigInteger.ONE; BigInteger i = res.add(BigInteger.ONE); for(int j=2; j<=n; j++) { res = res.multiply(i); i = i.add(BigInteger.ONE); } return res; } BlackBox Код: MODULE FactTest;
IMPORT StdLog, Dates, Integers; VAR BigOne: Integers.Integer; PROCEDURE Write( x: Integers.Integer); VAR i: INTEGER; BEGIN IF Integers.Sign(x) < 0 THEN StdLog.String("-") END; i := Integers.Digits10Of(x); IF i # 0 THEN REPEAT DEC(i); StdLog.Char(Integers.ThisDigit10(x, i)) UNTIL i = 0 ELSE StdLog.String("0") END END Write; PROCEDURE Fact(n: INTEGER): Integers.Integer; VAR i: INTEGER; x, y: Integers.Integer; BEGIN i := 2; x := BigOne; y := Integers.Sum(BigOne, BigOne); WHILE i <= n DO x := Integers.Product(x, y); y := Integers.Sum(y, BigOne); INC(i) END; RETURN x; END Fact; PROCEDURE TimeToInt(t: Dates.Time): INTEGER; BEGIN RETURN t.hour * 3600 + t.minute * 60 + t.second; END TimeToInt; PROCEDURE TestDate*; VAR t: Dates.Time; n1, n2: INTEGER; m: Integers.Integer; BEGIN Dates.GetTime(t); n1 := TimeToInt(t); m := Fact(20000); Dates.GetTime(t); n2 := TimeToInt(t); (* Write(m); StdLog.Ln; *) StdLog.Int(n2 - n1); StdLog.Ln END TestDate; BEGIN BigOne := Integers.Long(1); END FactTest. FactTest.TestDate Хотелось бы понять, с чем это связано, с неэффективной реализацией алгоритмов в BlackBox или время тратится на работу с памятью? |
Автор: | Борис Рюмшин [ Понедельник, 28 Ноябрь, 2005 01:57 ] |
Заголовок сообщения: | |
Я бы не сказал, что модуль Integers подходит для вычислительных целей (возможно следует посмотреть специфические подсистемы на http://www.zinnamturm.de). Скорее, это учебный модуль. Разница в скорости объясняется просто. В Java класс BigInteger поддерживается непосредственно виртуальной машиной, предполагаю, что там все тщательно оптимизированно. В ББ, модуль полностью выполнен на верхнем уровне, причем используются достаточно ресурсоемкие (для таких вещей) операции, например NEW. Думаете Java работает быстро? Сревните с Maple. 20000! он считает (на моей машине) за 0,2 с. При том что ваш пример у меня работает 18 с, следовательно ваша машина быстрее моей. Maple использует распространяемую по GPL библиотеку GMP. Сия штуковина написана на жуткой смеси C и Ассемблера и пересобирается под конкретный процессор со всей оптимизацией. Думаю, быстрее ее ничего нет. Теоретически ее можно привезать к ББ (как ДЛЛ). Если сделаете это и поделитесь опытом, выразим вам большую благодарность, т. к. проблема актуальна. ![]() Другой вариант, написать для ББ модуль с CODE вставками. |
Автор: | Сергей Губанов [ Понедельник, 28 Ноябрь, 2005 14:22 ] |
Заголовок сообщения: | |
Борис Рюмшин писал(а): Сревните с Maple. 20000! он считает (на моей машине) за 0,2 с.
Mathematica 5.0 сосчитала за 0.02 сек (Athlon 1700+) |
Автор: | Trurl [ Понедельник, 28 Ноябрь, 2005 14:46 ] |
Заголовок сообщения: | |
А у меня СLisp за 0.06c. Правда это встроенный факториал. Честно написанный считался 1.4с. BlackBox - те же 14. |
Автор: | Борис Рюмшин [ Понедельник, 28 Ноябрь, 2005 16:20 ] |
Заголовок сообщения: | |
Ну, дык зависит еще от того как с библиотекой работать. Насколько я помню, числа в Maple хранятся во внутреннем формате. Для того чтобы обратиться к GMP, их нужно преобразовать к соотв. формату. При инсталяции мапл определяет тип процессора и ставит GMP специально для него. Mathematica похоже имеет оптимизированное монолитное вычислительное ядро, которое она ставит под конкретный процессор. |
Автор: | Trurl [ Понедельник, 28 Ноябрь, 2005 17:33 ] |
Заголовок сообщения: | |
Вот, попробовал MultiMath. Код: PROCEDURE Fact(n:INTEGER):MM.Integer;
VAR s : MM.Integer; BEGIN s:=MM.One(); WHILE n > 1 DO MM.ScaleUp(s,n); DEC (n) END; RETURN s; END Fact; Fact(20000) считало 2с. |
Автор: | Сергей Губанов [ Понедельник, 28 Ноябрь, 2005 19:19 ] |
Заголовок сообщения: | |
Борис Рюмшин писал(а): Mathematica похоже имеет оптимизированное монолитное вычислительное ядро, которое она ставит под конкретный процессор.
Справедливости ради, объясню почему Mathematica чрезвычайно быстро вычисляет факториалы. Тут дело не только в очень хорошей реализации ее библиотек, тут выше берите - дело в алгоритме. Как известно, существует метод быстрого умножения длинных чисел, который имеет сложность O(N*Log(N)) вместо O(N*N), где N-число разрядов в числе. Так, вот оказывается факториалы тоже можно вычислять "достаточно быстро". Пусть: N - количество чисел которые нужно перемножить. 1) Сначала делаем попарные умножения 1-разрядных чисел (под разрядом здесь условно понимаю машинное слово), т.е. N/2 умножений сложность каждого равна 1. 2) Потом полученные 2-разрядные числа опять умножаем попарно, получая 4-разрядные, выполнив при этом N/4 двухразрядных умножений. 3) Повторяем пока всё не перемножилось. Сложность(N) = N/2*S(1) + N/4*S(2) + N/8*S(4) + N/16*S(8) +...+ 1*S(N/2) = Sum[(N*S[2^(p-1)])/2^p, {p, 1, Log2[2*N]-1}] S(k) - сложность умножения k-разрядных чисел. Если использовать обычное умножение в столбик, то S(k) = k^2 и ускорения не будет (а будет O(N^2)). Но можно использовать быстрое умножение. S(k) = k*Log(k), тогда (если я ничего тут не напутал), получаем сложность O(N*Log2[N]*Log2[N/2]) вместо O(N^2). |
Автор: | starant [ Среда, 30 Ноябрь, 2005 17:46 ] |
Заголовок сообщения: | |
Сергей Губанов писал(а): Mathematica 5.0 сосчитала за 0.02 сек (Athlon 1700+)
Mathematica 5.0 - ДЕМОН. Нужно было построить график достаточно сложной функции. Поставил MatLab, MathCAD, Mathematica. Быстрее всего справился в Математике(прекрасный туториал), в Маткаде вообще не разобрался - хелп весь запутанный, а Матлаб вообще завис на построении графика. |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |