Операция выполнена!
Закрыть
info@vsetut.pro
О проекте
Вернуться
[Перевод] Миф о RAM
22.12.2024 09:02:14 | Хабр
Хабы: Программирование, Алгоритмы, Серверная оптимизация, Совершенный код

Миф о RAM — это верование о том, что память современного компьютера напоминает идеальную память с произвольным доступом. Кэш люди считают оптимизацией для малых данных: если они умещаются в L2, то будут обрабатываться быстрее; если нет, то тут уж ничего не поделаешь.

Вероятнее всего, что самым быстрым разбиения данных будет такой код (я использую в качестве псевдокода Python; можете представить, что я пишу это на вашем любимом низкоуровневом языке):

groups = [[] for _ in range(n_groups)]

for element in elements:

groups[element.group].append(element)

Он и в самом деле линеен (то есть асимптотически оптимален), и мы всё равно должны выполнять доступ к произвольным индексам, так что кэш здесь нам ни в чём бы не помог.

В реальности, когда количество групп высоко, такой код не задействует большую часть производительности, а некоторые асимптотически более медленные алгоритмы могут выполнять сегментирование гораздо быстрее. В основном они применяются в базах данных на диске, но, как ни странно, полезны даже в случае данных в RAM.

Читать далее
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2024 - vsetut.pro