В этом сообщении Почему обработка отсортированного массива выполняется быстрее, чем случайный массив, в нем говорится, что ветвь предсказания является причиной повышения производительности в отсортированных массивах.
Но я просто попробовал пример с помощью Python; и я думаю, что нет никакой разницы между отсортированными и случайными массивами (я пробовал как bytearray, так и массив, а также использовать line_profile для профилирования вычислений).
Я что-то пропустил?
Вот мой код:
from array import array
import random
array_size = 1024
loop_cnt = 1000
# I also tried 'array', and it almost the same
a = bytearray(array_size)
for i in xrange(array_size):
a.append(random.randint(0, 255))
#sorted
a = sorted(a)
@profile
def computation():
sum = 0
for i in xrange(loop_cnt):
for j in xrange(size):
if a[j] >= 128:
sum += a[j]
computation()
print 'done'