Mergesort работает быстрее на больших входах

Question

Я работаю над эмпирическим анализом сортировки сортировки (сортировки строк) для школы, и я столкнулся с странным явлением, которое я не могу объяснить или найти объяснение. Когда я запускаю свой код, я фиксирую время выполнения, используя встроенный метод system.nanotime(), и по какой-то причине при определенном размере ввода, на самом деле принимает меньше времени для выполнения процедуры сортировки, чем с меньшим размером ввода ,

Моего алгоритм только основная сортировка слияния, и мой тестовый код прост тоже:

//Get current system time 
long start = System.nanoTime(); 
//Perform mergesort procedure 
a = q.sort(a); 
//Calculate total elapsed sort time 
long time = System.nanoTime()-start; 

Выхода я за истекшее время при сортировке 900 строк были: 3928492ns Для 1300 строк это было: 3541923ns

С обоими из них в среднем около 20 испытаний, так что это довольно непротиворечиво. После 1300 строк время выполнения продолжает расти, как ожидалось. Я думаю, что может быть некоторый максимальный размер ввода, где это явление наиболее заметно.

Итак, мой вопрос: что может вызвать внезапное увеличение скорости программы? Я думал, что может быть какая-то оптимизация с массивами, содержащими большие объемы данных, хотя 1300 элементов в массиве вряд ли велики.

Некоторая информация:

• Компилятор: Java версии 1.7.0_07
• Алгоритм: Basic рекурсивная сортировка слиянием (с использованием массивов)
• Тип входа: Строки 6-10 символов, перемешиваются (в случайном порядке)

Я ничего не теряю?

Answer 1

Я ничего не теряю?

Вы пытаетесь сделать microbenchmark, но код, который вы опубликовали до сих пор, не похож на хорошо работающий образец. Для этого следуйте приведенным здесь правилам: How do I write a correct micro-benchmark in Java?.

Объяснение того, что ваш код быстрее, объясняется тем, что после некоторых итераций вашего метода JIT будет запускаться, а производительность вашего кода будет оптимизирована, поэтому ваш код будет быстрее, даже при обработке больших данных.

Некоторые рекомендации:

• Используйте несколько массив/список входов с различным размером. Хорошие значения для такого анализа - 100, 1000 (1k), 10000 (10k), 100000 (100k), 1000000 (1 м) и значения случайного размера между ними. Вы получите более точные результаты при выполнении оценок, которые занимают больше времени.
• Использование массивов/списков различных объектов. Создайте POJO и внесите в него интерфейс Comparable, затем выполните свой метод сортировки. Как объяснялось выше, используйте разные значения массивов.

---

не связан с вашим вопросом, но результаты выполнения основаны на JDK используется. Eclipse - это только среда IDE и может работать с разными версиями JDK, например.на моем рабочем месте я использую JDK 6 u30 для работы над проектами в компании, но для личных проектов (например, доказательств концепций) я использую JDK 7 u40.