|
ru.perl
- RU.PERL ----------------------------------------------------------------------
From : Alexander Babanov 2:5020/5609.69 19 Apr 2001 03:42:45
To : Ruslan Bondarev
Subject : Re: Perl:10% из массива
--------------------------------------------------------------------------------
Юґullo Ruslan!
AB>> Вероятно, по крайней мере мне в голову пришла аналогичная мысль =8) С
AB>> другой стороны они наверняка использовали сишный генератор, а у него
AB>> цикл много больше, чем 2**15... А модуля с другим генератором я не
AB>> нашел :(
RB> Math::Random, Math::TrulyRandom. Они, по-моему, дают задержку и
RB> поэтому выиграша это может не дать.
Зависит от того, написаны ли они на эхотаге или на сях. Во втором случае
особой задержки быть не должно.
RB> Хотел попробовать, но АктивСтейт не считает этот модуль важным для
RB> разработчиков
Вот-вот, я забыл сказать, что искал не на CPAN, а ppm'ом. Сейчас посмотрю,
что входит в комплект PerlMagic'а...
RB> (компилировать облом), а под фрей мне это делать было бессмысленно, так
RB> как там и без Мат:Рандом у 5.005 перла 31-битный период.
...блин, и в PerlMagic'е 15 бит :( И Math::*Random нет :( Правда установка
CPAN'овских модулей вроде попроще. Пора перетягивать фидо под Mandrake...
RB> ps: А теперь клубника. Прогнал я, Саша, все три алгоритма под фрей.
RB> --
RB> кнут
RB> the code took: 6 wallclock secs ( 5.74 usr + 0.02 sys = 5.77 CPU)
RB> 100000 сорт the code took: 9 wallclock secs ( 8.72 usr + 0.12 sys = 8.84
RB> CPU) 100001 бабанов the code took: 3 wallclock secs ( 2.42 usr + 0.10 sys
RB> = 2.52 CPU) 100000 -- Результат на лице. (о: Hа сто тысяч твой алгортм дал
RB> 5000 рестартов, откуда следует, что число рестартов примерно 5% от размера
RB> (50 на 1000). O(1.05*n)
Hадо же :) Кстати, O(1.05*N) == O(N)
...Впрочем, стоило ожидать: алгоритм из Кнута не портит массив и годится для
однопроходной выборки из большого файла с известным числом элементов.
Единственный недостаток - требует в среднем 2*N/3 вычислений random. Красивый
однострочник с sort имеет сложность O(N*log(N)), даже если опустить финальную
сортировку. Основной недостаток моего алгоритма - подпорченый исходный массив,
не знаю можно ли этого избежать без накладных расходов.
CYa!!!
ЪДВїЪДВВВДДДщщъъ ЪДВВВДї ЪїЪДВДДДДДДДДщщъъ ЪДДДД 2:5020/5609.69 ДДДї
іВіАґДЕ ґBabanov іВі ґВі іАґВіST BERSERKER і babanov@earthlink.net і
... Еще наше поколение будет жить при Виагре! [предп. из писем Ильича к HКК]
---
* Origin: Our governor can beat up your governor! (2:5020/5609.69)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
