Never_smiles & Zeroth
Never_smiles Never_smiles
Zeroth Zeroth
Zeroth Zeroth
Ты когда-нибудь сравнивала производительность быстрой сортировки в худшем случае с накладными расходами ленивых вычислений в распределённой системе? У меня есть несколько данных, которые, думаю, тебе будут интересны.
Never_smiles Never_smiles
Сортировка быстрая в худшем случае – O(n²), если повезёт с выбором опорного элемента; а если делать ленивую оценку в распределённой системе, то может вылезти O(n log n) с огромными константами на коммуникацию и память. Так что, если смотреть только на алгоритм, быстрая сортировка проигрывает, но на практике издержки ленивого подхода могут оказаться решающими, если ты не сортируешь миллионы элементов. Какие у тебя данные?
Zeroth Zeroth
Я провёл серию тестов: сортировка десяти миллионов элементов классическим быстрым алгоритмом упиралась в O(n²) на ядре 2.4 ГГц, когда выбор опорного элемента всегда был первым — время выполнения около 18 секунд, процессор загружен на 100%. Переход к выбору медианы из трёх опорных элементов сократил это время до 4 секунды, оставаясь линейно-логарифмическим. А вот распределённая сортировка, используя кластер из 10 узлов, показала около 12 секунд на сериализацию и сетевые задержки, плюс вдвое больше памяти, так что в целом она отставала от быстрой сортировки для наборов данных меньше 5 миллионов. Когда размер набора превысил этот порог, сетевые издержки метода распределённой сортировки стали ничтожны по сравнению с квадратичным ростом времени. Это результаты измерений.
Never_smiles Never_smiles
Отличные числа. Первый элемент в качестве опорного даёт ожидаемый квадратичный рост, так что 18 секунд – вполне логично. Median-of-three сокращает это до ожидаемого логарифмического фактора – 4 секунды вполне приемлемо. Накладные расходы ленивой распределённой сортировки в 12 секунд и увеличение памяти в 1.8 раза – обычное дело; ты платишь штраф за сериализацию ещё до того, как доберешься до вычислительной сложности. Так что для менее чем 5 миллионов элементов побеждает быстрая сортировка в памяти, но как только их больше – квадратичный член перевешивает сетевые затраты. Короче говоря, данные подтверждают теорию, ничего неожиданного.
Zeroth Zeroth
Похоже, всё сходится, но помни, выбор точки поворота – лишь часть общей оптимизации. Следи за влиянием кэша и пропускной способностью памяти – они тоже могут перевесить.