Re: radix sort

From

Valentin Davydov ()

To

Илья Кантор

Date

2002-11-19T09:31:20Z

Area

RU.ALGORITHMS

From: Valentin Davydov <val@sqdp.trc-net.co.jp>

>   From: "Илья Кантор" <ilia@manual.ru>
>   Date: Mon, 18 Nov 2002 07:37:54 +0300
>
>Одного понять не могу: почему при переходе от short к long сабж замедляется в
>2 раза, а при переходе от long к long long(8байт инт) - в 3.5-4 раза ?
>
>Думаю, может быть связано с чем-то низкоуровневым, но с чем ?

С разрядностью шины данных какого-нибудь кэша.

>Делаются полностью одинаковые проходы для типа long - по нулевому, первому,
>второму, затем третьему байтам числа.
>
>Если тип long long - то, соответственно, от нулевого до 7го байта.. Проходов в
>2 раза больше, скорость должна в 2 раза упасть.. Но не в 3.5-4 же..

Храни младшие и старшие половины в отдельных массивах, а не в перемежку.

Вал. Дав.
--- ifmail v.2.15dev5
 * Origin: St. Petersburg State University (2:5020/400)