|
ru.linux
- RU.LINUX ---------------------------------------------------------------------
From : Valentin Nechayev 2:5020/400 16 Nov 2002 16:13:44
To : Ilya Teterin
Subject : Re: компиляция ядра
--------------------------------------------------------------------------------
>>> Ilya Teterin wrote:
IT>>> А я намекал, что измерение скорости в "исполнениях пустого цикла"
IT>>> совершенно бессмысленно, потому что оно для компилятора может быть
IT>>> любым, вплоть до никакого...
VN>> А может и ненулевым. Зачем ты это "намекаешь", когда по описанию четко
VN>> было видно, что это не так?
IT> Чтобы сподвигнуть на сравнение производительности по более объективным
IT> параметрам :)
Hу возьми не пустой цикл, а вывод "Goodbye, cruel world!\n" в цикле в /dev/null.
И что от этого принципиально изменится?
IT>>> А когда в массиве длинной несколько миллионов записей делают линейный
IT>>> поиск, это тоже хорошо замедляет. Подозреваю, что проблема той считалки
IT>>> - именно в этом. И если бы те же самые люди ее написали на перле,
IT>>> скорее всего, она работала бы быстрее, в перловских хешах, надеюсь, не
IT>>> линейным поиском данные ищутся.
VN>> Ага. То есть ты не знаешь. Hо утверждаешь. Спасибо, мне все ясно.
IT> Прошу прощения, если я что-то "утрвердил", я нечаянно и больше не буду :)
IT> Единственное, что достоверно известно - в перле есть нечто под называнием
IT> "хеши", что наталкивает на мысли, что поиск в них осуществляется по такому
IT> алгоритму: берется хеш-функция от ключа, и это дает индекс значения (с
IT> точностью до столкновений хеша). При практических любых значениях ключа (за
IT> исключением разве что специально выбранных) поиск значения по ключу с
IT> помощью этого алгоритма имеет сложность O(1). При достаточно длинных входных
IT> данных это компенсирует _любую_ тормознутость интерпретатора по сравнению с
IT> компилятором, если программа на компиляторе ищет значение по ключу с помощью
IT> линейного поиска.
hcreate, hsearch согласно стандарту будут в любой libc.
Если их недостаточно, если нужно несколько хэшей - Berkeley DB сейчас есть
в любом open source unix.
/netch
--- ifmail v.2.15dev5
* Origin: Dark side of coredump (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
