|
ru.linux
- RU.LINUX ---------------------------------------------------------------------
From : Ilya Teterin 2:5020/400 16 Nov 2002 14:06:50
To : Valentin Nechayev
Subject : Re: компиляция ядра
--------------------------------------------------------------------------------
Sat Nov 16 2002 09:29, Valentin Nechayev wrote to Ilya Teterin:
IT>> А я намекал, что измерение скорости в "исполнениях пустого цикла"
IT>> совершенно бессмысленно, потому что оно для компилятора может быть
IT>> любым, вплоть до никакого...
VN> А может и ненулевым. Зачем ты это "намекаешь", когда по описанию четко
VN> было видно, что это не так?
Чтобы сподвигнуть на сравнение производительности по более объективным
параметрам :)
IT>> А когда в массиве длинной несколько миллионов записей делают линейный
IT>> поиск, это тоже хорошо замедляет. Подозреваю, что проблема той считалки
IT>> - именно в этом. И если бы те же самые люди ее написали на перле,
IT>> скорее всего, она работала бы быстрее, в перловских хешах, надеюсь, не
IT>> линейным поиском данные ищутся.
VN> Ага. То есть ты не знаешь. Hо утверждаешь. Спасибо, мне все ясно.
Прошу прощения, если я что-то "утрвердил", я нечаянно и больше не буду :)
Единственное, что достоверно известно - в перле есть нечто под называнием
"хеши", что наталкивает на мысли, что поиск в них осуществляется по такому
алгоритму: берется хеш-функция от ключа, и это дает индекс значения (с
точностью до столкновений хеша). При практических любых значениях ключа (за
исключением разве что специально выбранных) поиск значения по ключу с помощью
этого алгоритма имеет сложность O(1). При достаточно длинных входных данных
это компенсирует _любую_ тормознутость интерпретатора по сравнению с
компилятором, если программа на компиляторе ищет значение по ключу с помощью
линейного поиска.
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
