М
Е
Д
И
А
П
Л
Е
Й
> test
> test
Music
test
test
test
Test
test
tgytgtygyg
Test
test
oiuoiu
test
111
test
sndh
test
test
test
> чо?
>работает лучше на d-арной куче, потому что тогда будет выполняться меньше длинных прыжков, и это перевешивает то, что в d-арной куче утапливание элемента делается дороже, чем в бинарной куче (за O(d · log_d N))
Нет.
Математически оптимальной с точки зрения минимизации количества операций при утоплении — d × logdN — является куча с арностью, равной числу e (по тому же принципу, что google:оптимальное основание системы счисления), ближайшей целой к которой является арность 3.
В реализации утопления на 4-куче количество сравнений будет РАВНО количеству сравнений на 2-куче: так совпало, что 22 = 4, поэтому относительно 2-кучи в 4-куче с удвоением ёмкости узла 2→4 уполовинивается её высота log2N→log4N. Однако на практике 4-куча всегда будет быстрее, и это обусловлено в первую очередь её дружественностью к кэшу. Пока d × sizeof(item) ≤ cache_line_size, где sizeof(item) — обычно 4 (int или указатель на 32-битной платформе) или 8 (long или указатель на 64-битной платформе), а cache_line_size — обычно 64, прыжок на следующий уровень будет генерировать только один промах кэша L1, таким образом, утопление в 4-куче выполняет столько же сравнений, но с уполовиненным числом L1-промахов. (Ну и присваиваний/обменов, но это ерунда — и да, кстати, здесь снова не обязательно свапать элемент с ребёнком/родителем до финиша, достаточно сдвигать всё на пути и присвоить исходный элемент в итоговую позицию: вместо e a b c → a e b c → a b e c → a b c e делать _ a b c → (item = e) → a a b c → a b b c → a b c c → a b c e).
>тратя одно сэкономленное сравнение на каждом уровне, и надеяться, что оно окупится
А оно окупится, потому что мы топим не полностью произвольный элемент, а только что достанный с самого дна.
>работает лучше на d-арной куче, потому что тогда будет выполняться меньше длинных прыжков, и это перевешивает то, что в d-арной куче утапливание элемента делается дороже, чем в бинарной куче (за O(d · log_d N))
Неправда.
Математически оптимальной, а именно минимизирующей количество сравнений при утоплении — d × logdN, является куча с арностью d, равной числу e (по тому же принципу, что google:оптимальное основание системы счисления). Ближайшая к ней целая арность — 3, не 2.
В реализации же утопления на 4-куче количество сравнений будет РАВНО количеству сравнений на 2-куче: так совпало, что 22 = 4, поэтому с удвоением ёмкости узла 2→4 уполовинивается высота кучи log2N→log4N. Однако на практике 4-куча всегда быстрее, и это обусловлено в первую очередь её дружественностью к кэшу. Пока d × sizeof(item) ≤ cache_line_size, где sizeof(item) — обычно 4 (int или указатель на 32-битной платформе) или 8 (long или указатель на 64-битной платформе), а cache_line_size — обычно 64, прыжок на следующий уровень будет генерировать только один промах L1-кэша, таким образом, утопление в 4-куче выполняет столько же сравнений, сколько в 2-куче, но с уполовиненным числом L1-промахов, ну и присваиваний/обменов. И да, здесь снова не обязательно просвапывать элемент до финиша, оптимальнее сдвинуть всё на пути и присвоить исходный элемент в итоговую позицию, иными словами, вместо e a b c → a e b c → a b e c → a b c e делать (item = e); _ a b c → a a b c → a b b c → a b c c → a b c e.
>HTMLTag
>HTMLPairedTag extends HTMLTag
Забудьте про перспективу и прямые линии наследование, пожалуйста, навсегда здесь достаточно полей.
testtest
testtest
testtest
testtest
/fet/