Comments 25
а ссылку на pdf можно, а то так можно забыть с чего начал:-)
Спасибо.
Наверное, так, без оговорок, не совсем.верно писать?
Алгоритм O(n), оптимально использующий кэш, может победить алгоритм O(log n), использующий кэш плохо
При больших n вряд-ли.
Есть еще важный фактор, который не отражен в чистой O нотации - длина единичной операции.
O(1) может быть настолько дорогим для каждого элемента, что его победит перебор по массиву O(n)
Хэш таблицы используют, ну, хэши (которые может требоваться вычислять) и таблицы (в смысле сложную внутреннюю организацию с чанками), в то время как последовательный перебор массива очень прост и хорошо дружит с кешем.
В итоге простыми экспериментами можно найти, до какого количества элементов выгоднее использовать массивы, и это может быть на удивление большое число.
Там, где надо реально быстро находить элемент массива по его содержимому, используются аппаратные ассоциативные запоминающие устройства.
Почему же не отражён? По определению O(1) - какая-то константа. Алгоритм, выполняющийся за O(1) может выполняться хоть мгновенно, хоть 2 года.
Элемент массива 4 байта, sizeof(node_t) 12 байт (если указатель x64) плюс служебные данные при выделении памяти, т.е. надо в 4-5 раз больше памяти для связного списка. Даже если все элементы списка в куче будут последовательно друг-за-другом, то для 10К элементов только чтение из памяти потребует лишние 3-4М тактов.
Невнимательно прочитал, там 100К элементов, тогда лишние 30-40М тактов.
Для чистоты эксперимента я бы сравнивал список не с массивом int[], а с массивом node_t[], так хотя бы расход памяти сопоставимый. Иначе ускорение за счет меньшей сложности алгоритма нейтрализуется бОльшим объемом используемой памяти.
Так накладные расходы списка по памяти - плата за "дешёвые" вставки в середину. Если их убрать, то это уже не список
Я к тому чтобы автор привел тест к более корректному виду, а то взял какой-то девайс с медленной памятью, сравнивает чтение для двух разных типов хранилищ, отличающихся в 5 раз по объему используемой памяти, и делает вывод: " O(log n) смогло победить O(1) "
Имеенно платформозависимая сложность и исследуется...
Если тормозит память, то надо оптимизировать работу с памятью. Как вариант можно ускорить двоичный поиск за счет промежуточного индекса размером в несколько кэшлиний: как понял у автора сортированный массив ~500 элементов, разбиваем его на блоки по 4 (индексы 0-3, 4-7 и т.д.) всего 125 блоков, далее делаем массив куда пишем ID первого устройства в блоке, это и есть индекс, он займет всего 8 кэшлиний. Для поиска сначала ищем в индексе равное или ближайшее меньшее ID, индекс (i) найденного элемента будет номером блока, далее если ID совпало то берем array[i*4], если меньше проверяем ID в array[i*4+2], затем если там ID больше то array[i*4+1] иначе array[i*4+3].
В данном случае индекс с большой вероятностью будет в кэше, т.к. он не большой и к нему будет постоянное обращение.
Сложность обоих O(n). В учебниках написано, что их показатели будут схожими
В моих учебниках писали, что сложность O(n) значит, что при увеличении n в два раза время работы вырастет в два раза.
В остальном, вы всё верно указали. Когда писались учебники по алгоритмам память была относительно быстрой, а самой дорогой операцией было ветвление. По-этому, для реальной (а не теоретической) производительности надо было оптимизировать именно ветвления. Теперь память в 10 раз (в лучшем случае) медленнее процессора и именно правильное обращение с памятью является ключевым для достижения высокой производительности
Двоичный поиск занимает O(log n), что теоретически хуже, чем O(1). Так написано в учебниках. Мой преподаватель алгоритмов был бы разочарован. ...
Они подразумевают, что все операции доступа к памяти стоят одинаково. Они подразумевают, что операции выполняются изолированно. Они подразумевают работу на идеальном компьютере, которого не существует.
Конечно преподаватель будет разочарован, у O-нотации другой смысл. Она ничего не подразумевает. Она описывает асимптотику и не говорит про реальное время. Она отвечает на вопрос "как изменится вычислетельная сложность алгоритма при изменении размера входных данных, когда n достаточно большое"
При фиксированном N O-нотация не обещает, что O(1) будет быстрее O(log N). Она обещает, что в пределе при N стремящемся к бесконечности, O(1) будет быстрее.
Доказательство того, что какая-нибудь quick sort в среднем работает за O(N log N), уже довольно сложное, если там пытаться ещё какие-то особенности процессора учитывать, то это будет ад. Вдобавок один и тот же математический алгоритм (типа хеш-таблиц) можно сильно по-разному сделать и получить сильно разную производительность. А ещё в зависимости от входных данных одна и та же хеш-таблица тоже будет иметь разную производительность. Одна и та же хеш-таблица с 70% заполненности и с 10% будет иметь сильно разное количество коллизий и скорость работы.
Например, есть подходы типа perfect hash: https://en.wikipedia.org/wiki/Perfect_hash_function - там коллизий вообще не будет и поиск в таблице гарантированно за O(1)
Время загрузки должно было находиться в пределах 100 мс, но превышало это значение на три порядка.
То есть время загрузки составляло около 100 секунд?
Но в результате загрузчик оказался на 40% быстрее.
То есть новый загрузчик с бинарным поиском выполнялся за 60 секунд, и тогда наступило счастье?
В оригинале не на три порядка, а в три раза.
Будьте внимательнее.
Прикольная статья, за 20 лет я смотрю ничего не изменилось 😃. Крис Касперский по этой теме целую книгу написал "Техника оптимизации программ. Эффективное использование памяти".
Вот +1000 про уровни кэша. Если нужна число дробилка, то компактный цикл со сложностью n! даёт фору сложности n2 при n до 8. Добавьте в алгоритм немного жадности и 8 превратится в 80-200.
Дешёвые по числу итерацией алгоритмы почти всегда кушают существенно больше памяти как для команд так и для данных.
Для баз данных история аналогичная. Бинарный индекс обеспечивает логарифмическую сложность при поиске, но вставка и чтение с определённого объёма начинают стоить в разы дороже при использовании индекса.
Если честно, выглядит так, как будто пример взят не из практики, а придуман. Про то, что пройтись по списку дольше, чем по массиву из-за кэш промахов да, понятно. Как это связано с исходным тезисом про хеш-таблицы и бинарный поиск? Может пример какой-нибудь? Полагаю, что не будет, потому что как раз на практике у бинарного бинарного поиска хуже паттерн обращений к памяти, чем у хеш-таблицы.
Если нужен реальный пример грамотной работы с кэшем -- замена бинарного дерева поиска на B-дерево, в котором размер узла может быть выставлен в соответствие размеру кэш линии.
Тут достаточно только "примерно пятьсот элементов". Остальную часть статьи можете удалить, это и так известно всем программистам. Напомню, что log2(500) ~ 9, а в хэш-таблице не именно 1 операция, как минимум ещё вычисление хэша, которое опускают при больших N.
Ну и добавлю, что хэш-таблица может в качестве контейнера вполне себе использовать плоский массив с той же частотой кэш-промахов, особенно если количество элементов заранее известно либо не сильно меняется в процессе. Единственный минус - большее потребление памяти.
Структуры данных на практике. Глава 1: Разрыв в производительности