LINUX.ORG.RU

Python vs Lisp. Расстановка точек


0

1

питон:

den@ira-desktop:~/work/test$ time python -O test.py 
('answer: ', 39)

real	0m33.035s
user	0m32.890s
sys	0m0.084s
den@ira-desktop:~/work/test$

clisp:

den@ira-desktop:~/work/test$ time clisp test.lsp
39

real	2m44.491s
user	2m42.970s
sys	0m1.464s
den@ira-desktop:~/work/test$

def test():
    r = 0
    for i in range(0, 10000):
        for j in range(0, 10000):
            r = (r + (i * j) % 100) % 47
    return r
r = test()
print("answer: ", r)
(defun test ()
    (setq r 0)
    (dotimes (i 10000 r)
        (dotimes (j 10000 r)
            (setq r (mod (+ r (mod (* i j) 100)) 47))
        )
    )
)

(write (test))

а теперь докажите, что лисп не тормознутое УГ

Ответ на: комментарий от cathode

> На таком количестве ключей строить хэштаблицу тупо.

Разработчики хэш-таблицы могу это учесть, нет? Кстати, насчёт 50-80 это ты загнул...

archimag ★★★
()
Ответ на: комментарий от tailgunner

>> Правда, мой пойнт был не совсем в этом.

Мы же про динамическое связывание в пистоне говорим и про поиск нужного метода по dict?

cathode
()
Ответ на: комментарий от cathode

> Хэш по такому количеству данных будет проигрывать списку типа plista-а только в путь.

пруф или не было. (Пруф того, что хэш структура будет проигрывать какому-либо списку по поиску точного значения)

qnikst ★★★★★
()
Ответ на: комментарий от cathode

>> Правда, мой пойнт был не совсем в этом.

Мы же про динамическое связывание в пистоне говорим

Насчет «нас» - ХЗ, а я говорю о добавочных накладных расходах в Питоне на ООП по сравнению с процедурным стилем.

tailgunner ★★★★★
()
Ответ на: комментарий от archimag

>> Разработчики хэш-таблицы могу это учесть, нет?

Это от них не зависит. Зависит от алгоритма хэширования конкретного класса.

cathode
()
Ответ на: комментарий от cathode

> Я исходил из практики лиспового plist и hash-table.

Ты хочешь сказать, что в CL такие медленные хэш-таблицы? Подобное утверждение нуждается в обосновании.

archimag ★★★
()
Ответ на: комментарий от cathode

RTFM на тему того, как работает хэш список.

qnikst ★★★★★
()
Ответ на: комментарий от dave

>> Там хэш (говорят, очень эффективный), так что вряд ли хуже O(log n).

Это уже много.

Мы говорим о добавочных расходах, или об абсолютных?

tailgunner ★★★★★
()
Ответ на: комментарий от qnikst

>> Пруф того, что хэш структура будет проигрывать какому-либо списку по поиску точного значения

Хэш дается всевышним или его надо считать?

cathode
()
Ответ на: комментарий от cathode

> Это от них не зависит. Зависит от алгоритма хэширования

конкретного класса.


В Pythone? Или где? И что мешает хэш-таблице держать данные в линейном списке до достижения некоего порога?

archimag ★★★
()
Ответ на: комментарий от archimag

>> Ты хочешь сказать, что в CL такие медленные хэш-таблицы? Подобное утверждение нуждается в обосновании.

Еще раз объясняю. Хэш надо считать. Пройтись по cons-ам при их малом количестве можно быстрее чем подсчитать хэш. Что неясного?

cathode
()
Ответ на: комментарий от cathode

> Хэш надо считать. Пройтись по cons-ам при их малом количестве можно быстрее чем подсчитать хэш. Что неясного?

Неясно, почему не учитывается операция сравнения. Сравнить 32-бит хэши быстрее, чем сравнить строки, а хэш вычисляется за 1 проход по 1-й строке.

tailgunner ★★★★★
()
Ответ на: комментарий от cathode

> Пройтись по cons-ам при их малом количестве можно быстрее

чем подсчитать хэш.


50-80 это малое количество? И ещё раз, что запрещает хэш-таблице искать соответствие в линейном списке при малом количестве элементов?

archimag ★★★
()
Ответ на: комментарий от tailgunner

> Неясно, почему не учитывается операция сравнения. Сравнить 32-бит хэши быстрее, чем сравнить строки, а хэш вычисляется за 1 проход по 1-й строке.

А в лиспе symbols, а не строки, поэтому сравнивается тоже 32 хэш.

anonymous
()
Ответ на: комментарий от cathode

Его надо считать.
поиск по хэшу это:
1 действие - вычесление хэша
1 действие - нахождение целочисленного остатка от деления на размер хранилица
k действие - нахождение значения если есть несколько одинак остатков по скольку алгоритмом создания хэш таблицы гарантируется, что это значение не больше 0.05n, где n - кол-во аргументов. И программист может улучшить это значение выбирая функцию хэширования.

Итого 1+1+0.05*n в _худшем_ случае. В общем случае это O(1).

Жду обоснованного комментария в пользу plist (я не знаю чем он отличается от обычного листа)

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

> Жду обоснованного комментария в пользу plist

Если в списке всего один элемент, то надо всего лишь проверить тот ли это или нет. Это как бы понятно, что при малом количестве элементов линейный поиск будет быстрее.

Только к чему вся эта арифметика? Я что-то не пойму...

archimag ★★★
()
Ответ на: комментарий от archimag

Человек утверждает:

Хэш по такому количеству данных будет проигрывать списку типа plista-а только в путь


я привёл доказательство, что в общем случае хэш будет быстрее списка
(1 операция хэширования, 1 операция деления по модулю, и 0-0.05N операций сравнения хэша (числа)), против 1-N операций сравнения строк). Попутно сказав как хэш список работает, а то такое очучение, что чувтсвуется его непонимание данной структуры.

При это я не рассматривал экстремальные случаи 1-2-? элемента

Только к чему вся эта арифметика? Я что-то не пойму...


А что ещё, разве, что кроме бэнчмарка может служить доказательством?
Утверждение «личный опыт показал»?

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

>> 1 действие - вычесление хэша

1 действие - нахождение целочисленного остатка от деления на размер хранилица

Ты напоминаешь ту блондинку, котрая ответила на вопрос «какова вероятность встретить динозавра» - 50%, можно встретить, можно нет. Ты хоть себе представляешь сколько операций стоит за «1 действие - вычесление хэша»???

cathode
()
Ответ на: комментарий от Deleted

> Это и есть основная проблема всех ЪЯП. Чтобы начать понимать код на них, эти языки нужно изучить хотя бы до какого-то начального уровня.

Это, увы, справедливо по отношению к любому языку вообще. Даже к псевдокоду в старых учебниках.

Я вот например раньше не знал python (недели две назад начал изучать) и до сих пор не знаю ruby. И тем не менее я был способен чисто интуитивно понимать бОльшую часть чужого кода на python'е и ruby.

Ну так ты ведь уже знал другие языки программирования. Зная один, поймешь и другой.

А вот с perl'ом, lisp'ом и haskell'ем такой фокус не проходит.

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

anonymous
()
Ответ на: комментарий от cathode

>> Монада в программировании — это абстракция линейной цепочки связанных вычислений.

Неправильное определение.

в наше время каждый младенец знает, что монада в категории - это моноид в категории её эндофункторов

jtootf ★★★★★
()
Ответ на: комментарий от bibi

> Завершения аналога на руби так и не смог дождаться

Естественно. Руби при переполнении целых прозрачно переходит на BigInteger. ))

LamerOk ★★★★★
()
Ответ на: комментарий от tailgunner

и IIRC, хэш-значение питоновского объекта вычисляется при его создании и не меняется за время жизни.

Неважно, вообще все это обсасывалось в лохматом merits of lisp vs python, в частности alex mizrahi объяснял, почему питоновский диспатч будет тормознее лиспового почти всегда.


(message (Hello 'Kay)
(you :wrote n '(8 Dec 2006 08:03:18 -0800))
(

KS> http://www.sbcl.org/manual/Handling-...dling-of-Types

KS> If you'd read the docs of the tools you admire you might find the
KS> answers yourself.

SBCL is a COMPILER that explains everything. it's interesting why
INTERPRETER like CLISP is faster.
well, it can be type declarations as well, but maybe something other too..

for example, in languages like Python, PHP and JavaScript, as i understand,
by semantics of the language interpreter MUST use dict to call objects
method -- at any time it can be changed, for any object instance. i'm not
sure whether it has to dynamically resolve package's methods doing lookup in
packages dict.

however, in Common Lisp object methods are dispatched on object types, that
is a special language entity, so as long as new types are not introduced,
interpreter can optimize calls how it wants to. the difference is that while
it's still dynamic, dispatch over types are more controlled/optimizable than
dispatch using dict.
then, symbols in common-lisp package cannot be changed according to spec,
thus compiler/interpreter is safe to do optimizations it wants when sees
that symbols (if we want symbols with same names, we can make other package
with them).

then, Common Lisp standard defines what inlining is. i bet most
optimizations in dynamic languages are not possible if inlining is not
enabled -- since any symbol that is not inlined can change it's meaning in
any time.

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")

anonymous
()
Ответ на: комментарий от anonymous
(message (Hello 'Kay)
(you :wrote  :on '(8 Dec 2006 12:25:09 -0800))
(

 KS> O.K. I agree with what you said about the generic function vs per
 KS> object dictionary dispatch.
 KS> But do the performance differences vanish when only builtin types and
 KS> functions are used to express Python algorithms?

no.
language semantics require python to do dict lookup on each access to some 
global function (or builtin) or variable.
i don't have enough time for in-depth analysis, but here's what's it.
suppose we have

def Fib(n):
   if n < 2:
      return 1
   else:
     return Fib(n -2) + Fib(n-1)

import dis
dis.dis(Fib)

you will see this:
...
21 LOAD_GLOBAL              1 (Fib)
24 LOAD_FAST                0 (n)
27 LOAD_CONST               2 (1)
30 BINARY_SUBTRACT
31 CALL_FUNCTION            1
34 LOAD_GLOBAL              1 (Fib)
37 LOAD_FAST                0 (n)
40 LOAD_CONST               1 (2)
43 BINARY_SUBTRACT
44 CALL_FUNCTION            1
47 BINARY_ADD
48 RETURN_VALUE

now let's check what is LOAD_GLOBAL in ceval.c (i have Python 2.4.1 
sources):

  case LOAD_GLOBAL:
   w = GETITEM(names, oparg);
   if (PyString_CheckExact(w)) {
    /* Inline the PyDict_GetItem() calls.
       WARNING: this is an extreme speed hack.
       Do not try this at home. */
    long hash = ((PyStringObject *)w)->ob_shash;
    if (hash != -1) {
     PyDictObject *d;
     d = (PyDictObject *)(f->f_globals);
     x = d->ma_lookup(d, w, hash)->me_value;
     if (x != NULL) {
      Py_INCREF(x);
      PUSH(x);
      continue;
     }
     d = (PyDictObject *)(f->f_builtins);
     x = d->ma_lookup(d, w, hash)->me_value;
     if (x != NULL) {
      Py_INCREF(x);
      PUSH(x);
      continue;
     }
     goto load_global_error;
    }
   }
   /* This is the un-inlined version of the code above */
   x = PyDict_GetItem(f->f_globals, w);
   if (x == NULL) {
    x = PyDict_GetItem(f->f_builtins, w);
    if (x == NULL) {
      load_global_error:
     format_exc_check_arg(
          PyExc_NameError,
          GLOBAL_NAME_ERROR_MSG, w);
     break;
    }
   }
   Py_INCREF(x);
   PUSH(x);
   continue;
anonymous
()
Ответ на: комментарий от anonymous
so we can see PyDict access. moreover, it's inlined, since it's very 
performance-critical function.
but even inlined PyDict access is not fast at all. ma_lookup is a long and 
hairy function containing the loop.
moreover, we can see that there are two dict lookups -- into globals and 
builins.
lookup into a global hash should about order of magnitude slower than simple 
table fetch, so here's the root of python's slowness.

how lisp can be faster here? lisp has SYMBOLs and well-defined semantics of 
source code parsing.
first source code is processed by reader, that outputs trees of code. each 
variable or function name becomes a SYMBOL object. symbols are typically 
interned into packages, but they don't need to be looked-up in the packages 
in runtime -- in fact, it's not possible at all.
i can read a piece of code and then unintern some symbol from package --  
that will not make that code invalid. packages are used mostly by reader. 
(also, i can have many symbols with same name, if they are not interned --  
and they will be all different objects)
in runtime, lisp has to lookup symbol's function -- but symbol can be 
implemented as a structure, and symbol-function can be just it's field 
access.

one more thing -- you can see lookup into builins, so they are in dict too! 
and you can see that builtins dict is checked only if name is not found in 
globals, so builtins are even slower than globals. that's a reason for 
performance slowdowns too.
one can say that it's the only way to change builtins in runtime. yes, but 
dict lookup is a big price for it (well, if python use symbols, it would be 
faster).
in fact, Common Lisp also allows to redefine "built-in" function -- you can 
define a symbol with a same name as builtin in some package and use it, it 
will "shadow" symbol in the common-lisp package (common-lisp:+). you can 
change symbol-function of this symbol in runtime and do whatever you want. 
but symbols in common-lisp package are immutable. that makes it possible to 
optimize code.

and there's inlining. for example, in fib definition:

(defun fib (n)
    (if (< n 2)
        1
         (+ (fib (- n 2))
             (fib (- n 1)))))

CLISP does not even use symbol FIB in function bytecodes -- it notes that 
it's a recursive function calls, so instead of normal function call it does 
a local jump.


anonymous
()
Ответ на: комментарий от cathode

Размерость операции я для кого оставлял? Вычисление хэша зависит от реализации в конкретном ЯП. Для строки N*k, где N-это кол-во символов, а k - кол-во простых целочисленных операций в алгоритме. P.S. поскольку в языках типа python хэш это unmutable объект, то хэш _уже_ известен при создании строки. В списке все хэши тоже известны, т.е. идёт сравнение integer величин.

Встречный вопрос, сколько операций в сравнении строк? Имхо от 1 до N, где N длина меньшей строки т.е. мат ожидание log(N).

qnikst ★★★★★
()
Ответ на: комментарий от anonymous

> все это обсасывалось в лохматом merits of lisp vs python, в частности alex mizrahi объяснял, почему питоновский диспатч будет тормознее лиспового почти всегда.

Это интересно, но вот честно скажу - мне без разницы, что lookup в Питоне торознее лиспового. В Лиспе вон и компилятор в машкод есть, и что теперь? Я говорил о _дополнительных_ расходах на ООП в Питоне по сравнениию с процедурным стилем в Питоне же.

tailgunner ★★★★★
()
Ответ на: комментарий от anonymous

>Вопрос: на что программы расходуют системные ресурсы?

На сокращение времени разработки. В этом есть и свой позитив: можно быстро что-то опробовать на практике. Если понравилось - переписать уже на языке более низкого уровня, для оптимизации.

anonymous
()
Ответ на: комментарий от cathode

>Есть один интуитивно понятный интерфейс - сиська, все остальное требует изучения.

Сиська - это экземпляр класса. Интерфейс - это сосок.

anonymous
()
Ответ на: комментарий от tailgunner

>Вообще-то классы в Питоне - это килограмм сахара поверх обычных функций, не более

А не килограмм сахара вокруг хэш-таблиц?

dmitry_vk ★★★
()
Ответ на: комментарий от dmitry_vk

>> Вообще-то классы в Питоне - это килограмм сахара поверх обычных функций, не более

А не килограмм сахара вокруг хэш-таблиц?

Методы - это фактически функции; функции к хэш-таблицам отношения не имеют.

tailgunner ★★★★★
()

FAIL

>а теперь докажите, что лисп не тормознутое УГ

(compile 'test) перед (write (test)) и твой пистон сливает где-то на 30-40%.

linuxfan
()
Ответ на: комментарий от tailgunner

>Методы - это фактически функции; функции к хэш-таблицам отношения не имеют.

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

dmitry_vk ★★★
()
Ответ на: FAIL от linuxfan

> (compile 'test) перед (write (test)) и твой пистон сливает где-то на 30-40%.

Ты забыл разлогиниться? :)

anonymous
()
Ответ на: комментарий от Zubok

>Харе гнать на CLISP! :) Хорошая реализация, и я ей доволен. Маленький футпринт, быстрый старт, хорошая межплатформенная переносимость, скромные потребности в памяти.

Яростно плюсую!

linuxfan
()
Ответ на: комментарий от dmitry_vk

>> Методы - это фактически функции; функции к хэш-таблицам отношения не имеют.

Да в питоне хэши везде. Даже доступ к локальным переменным - это всегда доступ к хэш-таблице

В огороде бузина...

Неоптимизируемая у него семантика, поэтому такой питон тормоз.

И семантика оптимизируемая, и интерпретатор достаточно быстрый, и программы не тормозят (хоть на начальную мессагу посмотри). С GIL проблемы, да.

tailgunner ★★★★★
()
Ответ на: комментарий от Zubok

> Маленький футпринт, быстрый старт, хорошая межплатформенная переносимость, скромные потребности

... скромные возможности, убогие скобки

anonymous
()
Ответ на: комментарий от tailgunner

> Я говорил о _дополнительных_ расходах на ООП в Питоне по сравнениию с процедурным стилем в Питоне же.

Правильно ли я понял из той иностранной переписки, что и вызов процедуры тормозной, поскольку все идет через изменяемый dict? Если да, то тогда, быть может, разницы действительно нет :)

dave ★★★★★
()
Ответ на: комментарий от dave

> Правильно ли я понял из той иностранной переписки, что и вызов процедуры тормозной, поскольку все идет через изменяемый dict?

Не вызов, а lookup. Но, в общем, правильно.

tailgunner ★★★★★
()

У меня так

Lisp - не хватило терпения, ждал больше минуты 
Python/Psyco - 2.4 s 
Mono/AOT - 1.12 s 
Java (server,Xbatch) - 0.86 s 
C++ (O6) - 0.70 s

Если увеличить границу по i в 10 раз, то

Lisp - не запускал
Python/Psyco - 23.6 s 
Mono/AOT - 10.1 s 
Java (server,Xbatch) - 7.07 s 
C++ (O6) - 6.91 s

Вот такой бенчмарк на коленке

vertexua ★★★★★
()
Ответ на: комментарий от anonymous

Сиська - это экземпляр класса. Интерфейс - это сосок.

Если уж так глубоко сосать, в смысле копать, то сиська - это фабрика, в смысле что:

 
Nadoi n = SiscaFabrica.new_Nadoi(); 
bool b = n.Drink_Iz_Vedra().achivedPonos(); 
cathode
()
Ответ на: комментарий от dave

> Ужас! Но mercurial почему-то работает быстро... Загадка :)

Он IO-bound, с маленьким критическим модулем на Си - классический питоновский стиль. Нафига вообще нужны эти суперкомпиляторы? :)

tailgunner ★★★★★
()
Ответ на: комментарий от vertexua

> Какой лисп вы предлагаете и как его запускать для лучшей

производительности?


Ну так выше уже всё написали. Запускаешь sbcl, в REPL вбиваешь код, потом там же в REPL (time (test)) и смотришь результат.

archimag ★★★
()
Ответ на: комментарий от archimag

Я создал бинарник в sbcl - этогно не достаточно? Оно минуту работает только на первом тесте, где многие в секунду вложились

vertexua ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.