OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Воскресенье, 20 Сентябрь, 2020 13:46

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




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Скорость вычислений в BlackBox vs Java
СообщениеДобавлено: Воскресенье, 27 Ноябрь, 2005 19:57 
Задумался я, что лучше использовать (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 
Администратор

Зарегистрирован: Вторник, 15 Ноябрь, 2005 01:14
Сообщения: 4443
Откуда: Россия, Орёл
Я бы не сказал, что модуль Integers подходит для вычислительных целей (возможно следует посмотреть специфические подсистемы на http://www.zinnamturm.de). Скорее, это учебный модуль.

Разница в скорости объясняется просто. В Java класс BigInteger поддерживается непосредственно виртуальной машиной, предполагаю, что там все тщательно оптимизированно. В ББ, модуль полностью выполнен на верхнем уровне, причем используются достаточно ресурсоемкие (для таких вещей) операции, например NEW.

Думаете Java работает быстро? Сревните с Maple. 20000! он считает (на моей машине) за 0,2 с. При том что ваш пример у меня работает 18 с, следовательно ваша машина быстрее моей.

Maple использует распространяемую по GPL библиотеку GMP. Сия штуковина написана на жуткой смеси C и Ассемблера и пересобирается под конкретный процессор со всей оптимизацией. Думаю, быстрее ее ничего нет. Теоретически ее можно привезать к ББ (как ДЛЛ). Если сделаете это и поделитесь опытом, выразим вам большую благодарность, т. к. проблема актуальна. :)

Другой вариант, написать для ББ модуль с CODE вставками.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Понедельник, 28 Ноябрь, 2005 14:22 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Борис Рюмшин писал(а):
Сревните с Maple. 20000! он считает (на моей машине) за 0,2 с.


Mathematica 5.0 сосчитала за 0.02 сек (Athlon 1700+)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Понедельник, 28 Ноябрь, 2005 14:46 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1298
А у меня СLisp за 0.06c. Правда это встроенный факториал. Честно написанный считался 1.4с.

BlackBox - те же 14.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Понедельник, 28 Ноябрь, 2005 16:20 
Администратор

Зарегистрирован: Вторник, 15 Ноябрь, 2005 01:14
Сообщения: 4443
Откуда: Россия, Орёл
Ну, дык зависит еще от того как с библиотекой работать. Насколько я помню, числа в Maple хранятся во внутреннем формате. Для того чтобы обратиться к GMP, их нужно преобразовать к соотв. формату. При инсталяции мапл определяет тип процессора и ставит GMP специально для него. Mathematica похоже имеет оптимизированное монолитное вычислительное ядро, которое она ставит под конкретный процессор.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Понедельник, 28 Ноябрь, 2005 17:33 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1298
Вот, попробовал 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 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Борис Рюмшин писал(а):
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).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Среда, 30 Ноябрь, 2005 17:46 

Зарегистрирован: Среда, 30 Ноябрь, 2005 11:46
Сообщения: 46
Сергей Губанов писал(а):
Mathematica 5.0 сосчитала за 0.02 сек (Athlon 1700+)

Mathematica 5.0 - ДЕМОН. Нужно было построить график достаточно сложной функции. Поставил MatLab, MathCAD, Mathematica.
Быстрее всего справился в Математике(прекрасный туториал), в Маткаде вообще не разобрался - хелп весь запутанный, а Матлаб вообще завис на построении графика.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

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


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

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


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

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2020, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB