История изменений
Исправление former_anonymous, (текущая версия) :
Если nums помещается в L1, а set вытесняется в L2, то вот и потеря производительности. Если мы итерируем по set вместо nums, то весь set помещается в L1, и более мы никуда не лезем. Отсюда и прирост производительности в 50 раз
Исходная версия former_anonymous, :
Если nums помещается в L2, а set вытесняется в L3, то вот и потеря производительности. Если мы итерируем по set вместо nums, то весь set помещается в L2, и более мы никуда не лезем. Более того, части set могут быть помещены в L1, т.к. нашему алгоритму нравится когда данные отсортированы и он их итерирует по очереди. Это значит, что большие части set-а могут быть помещены в L1, и алгоритм их с удовольствием обработает все что есть. Когда данные из L1 закончились, то естественным образом загружаются следующие, и т.д. Отсюда и прирост производительности в 50 раз