- RU.PERL ----------------------------------------------------------- RU.PERL -
Msg : #3561 [639]
От : Yuriy Kaminskiy 2:5020/517.21 15 мая 04, 05:03
Кому : Serge Chervjakov 16 мая 04, 20:25
Тема : Re: Проверка на вхождение в массив
-------------------------------------------------------------------------------
@RFC-NNTP-Posting-Date: 15 May 2004 01:03:34 GMT
Hello, Serge!
>>>>> On 19:21 14/5/2004, Serge Chervjakov wrote to Pavel Reich:
MP>>> my %hash = map {$_ => 1} @_;
PR>> map работает дольше for, это заранее известно.
SC> Есть такая хорошая штука - perldoc Benchmark
SC> называется. Рекомендую всегда обращаться к ней, делая подобные
SC> заявления, что что-то работает быстрее чего-то. Код тестов
SC> достаточно большой вышел,
... а у меня - достаточно маленький...
SC> потому сюда
... я его кидаю:
$ perl5.6.0 -MBenchmark=cmpthese -e '
my @list=map {int rand(100)} 1..1024;
cmpthese(-1, {
Map =>sub { my %hash = map { $_ => 1 } @list; \%hash },
For =>sub { my %hash; for(@list) { $hash{$_} = 1 } \%hash },
ForMy=>sub { my %hash; for my $x(@list) { $hash{$x} = 1 } \%hash },
Slice=>sub { my %hash; @hash{@list}=(); \%hash }});'
Rate Map For ForMy Slice
Map 146/s -- -83% -84% -96%
For 873/s 496% -- -5% -76%
ForMy 923/s 530% 6% -- -75%
Slice 3692/s 2420% 323% 300% --
Аналогично для 5.8.1:
Rate Map ForMy For Slice
Map 435/s -- -60% -61% -85%
ForMy 1090/s 150% -- -3% -62%
For 1120/s 157% 3% -- -61%
Slice 2901/s 566% 166% 159% --
Аналогично для 5.00404:
Rate Map For ForMy Slice
Map 158/s -- -88% -88% -96%
For 1309/s 731% -- -0% -68%
ForMy 1309/s 731% 0% -- -68%
Slice 4148/s 2533% 217% 217% --
Как видно - самый быстрый метод - @hash{@slice}. Оно, конечно, в
теории не эквивалентно (вместо 1 оно присваивает undef), но в данном
случае - результат будет тот же самый (потому как мы используем
exists, а не значение), только гораздо быстрее, короче, и красивее :-)
SC> кидать не буду, но у меня получилось что map отработал в примерно
SC> 6 раз быстрее.
Ты где-то здорово ошибся в своём "большущем тесте". Проще надо быть,
проще :-)
SC> Попробуй у себя проделать то же самое. Полезно:).
--
Yuriy Kaminskiy.
E-mail (rot13): lhevl.z.xnzvafxvl@zgh-arg.eh
PS Стоит отметить, что сравнивать тут разные версии перла нельзя,
поскольку оно собрано с разными опциями:
5.00404 - libperl.a = -fno-PIC, single-thrd, single-obj, egcs-1.0.3, glibc2.0.7
5.6.0 - libperl.so = -fPIC, single-thrd, single-obj, egcs-1.0.3, glibc2.0.7
5.8.1 - libperl.so = -fPIC, multi-thrd, multi-obj, gcc-3.3.2, glibc2.3.2
[JFYI: одно только -fPIC даёт снижение скорости до ~30%]
PS Почему map такой тормоз? Hу, это же очевидно, Ватсон: он создаёт
временный список длины 2*n, а for - не создаёт ни одного временного
объекта. Почему @hash{@slice} такой быстрый? Hу, это же очевидно,
Ватсон: всё укладывается в одну элементарную операцию, а остальные разводят
канитель с циклами, передачей управления и иже с ним на каждый элемент
массива.
BTW, perl -MO=Concise или perl -MO=Terse в руки - и вперёд на танки :-)
PPS
Возвращаясь к нашим баранам: проверка на вхождение в массив (perl-5.8.1):
@arr = map {int rand(10)} 102
Rate hash ykhash arr
hash 3623/s -- -67% -77%
ykhash 11095/s 206% -- -28%
arr 15459/s 327% 39% --
@arr = map {int rand(100)} 1024
Rate hash arr ykhash
hash 425/s -- -74% -85%
arr 1643/s 287% -- -41%
ykhash 2765/s 551% 68% --
@arr = map {int rand(1000)} 1024;
Rate hash ykhash arr
hash 327/s -- -68% -80%
ykhash 1013/s 210% -- -37%
arr 1614/s 394% 59% --
Оттаквот. Hесмотря на изначальную бредовость - создавать хеш для
единственной проверки глупо - при грамотном кодировании результат
получается вполне на уровне (и иногда - даже быстрее ).
А map - тоРМоз-ТормоЗ-ТОРМОЗ!
--- Gnus/5.1002 (Gnus v5.10.2) XEmacs/21.5 (chayote, linux)
* Origin: Code is language! http://www.anti-dmca.org (2:5020/517.21@fidonet)