Есть интересная особенность, которую часто замечают программисты, особенно новички, при работе с языками программирования. Обработка отсортированного массива данных обычно происходит быстрее, чем обработка неотсортированного.
Допустим, у вас есть массив чисел, который вы хотите пройти и суммировать определенные элементы. Например, все числа, которые больше или равны 128. Было замечено, что если массив отсортировать перед этой операцией, то она будет выполняться быстрее.
public class Main
{
public static void main(String[] args)
{
// Генерация данных
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
data = rnd.nextInt() % 256;
// !!! С этим следующий цикл выполняется быстрее
Arrays.sort(data);
// Тест
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
for (int c = 0; c < arraySize; ++c)
{ // Основной цикл.
if (data >= 128)
sum += data;
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}
Возникает вопрос: почему это происходит? Ведь суммирование независимых элементов не должно зависеть от порядка этих элементов.
Ответ на этот вопрос связан с особенностями работы процессора и его кэша. Современные процессоры используют предсказатель ветвления, который пытается предсказать, какие ветви кода будут выполнены, и заранее загружает необходимые данные в кэш. Если предсказатель ветвления угадывает правильно, то всё происходит быстро. Если он ошибается, происходит так называемый «промах кэша», и процессору приходится ждать, пока данные будут загружены из оперативной памяти.
При обработке отсортированного массива, предсказатель ветвления работает более эффективно, потому что данные расположены более предсказуемо. Это позволяет процессору загружать данные в кэш заранее и избегать «промахов кэша», что значительно увеличивает скорость обработки.
Важно помнить, что время, затраченное на сортировку массива, может существенно превышать выигрыш в скорости обработки. Поэтому этот подход стоит использовать только в тех случаях, когда массив обрабатывается многократно.
Добавить комментарий