@lordekar

Чем обоснован экспоненциальный рост времени выполнения куска кода при увеличении размера массива в 10 раз?

Имеется код на Java
package com.company;

public class Main {

    public static void main(String[] args) {
        //Runtime runtime = Runtime.getRuntime();
        int k = 10000;
        int[] A = new int[100];
        long startTime = System.currentTimeMillis();
        for(int i = 0; i < A.length; i++){
            A[i] = (int)(Math.random() * k);
        }
        long timeSpent = System.currentTimeMillis() - startTime;
        System.out.println("Time: " + timeSpent);
    }
}

При увеличении размера массива A время его заполнения растет экспоненциально. Хотя, вроде бы, должно быть линейным.
Шаги от 100 до 1 000 000
ad72503293f14c06ab00d4cdf9fa0167.png
  • Вопрос задан
  • 459 просмотров
Решения вопроса 1
enq3
@enq3
Android engineer at #ITX5
Скорее всего все упирается в кэш процессора, второй способ в 10 раз быстрее первого. В случае (int)(Math.random() * k) прирост по скорости будет в 2 раза:
class Test {
	public static void main(String[] args) {
 
		int k = 10000;
		long st, en;
		int[] A;
		int length = 100000;
 
		A = new int[length];
		st = System.nanoTime();
		for (int i = 0; i < length; i++)
		{
			A[i] = k;
		}
		en = System.nanoTime();
		System.out.println("\nOne time=" + (en - st) / 1000000.d + " msc");
 
		int cache = 10000;
		A = new int[length];
		int[] temp = new int[cache];
		st = System.nanoTime();
		for (int N = 0; N < length; N+=cache) {
			for (int i = 0; i < cache; i++) {
				temp[i] = k;
			}
			System.arraycopy(temp, 0, A, N, temp.length);
		}
		en = System.nanoTime();
		System.out.println("\nTwo time=" + (en - st) / 1000000.d + " msc");
 
	}
}

Попробовать тут: ideone.com/Py6A4S

Статья: rus-linux.net/MyLDP/hard/memory/memory-03-11.html
Цитата:
Более удивительной по сравнению с производительностью при чтении является производительность при записи и копировании. Производительность при записи даже для рабочих наборов с небольшими размерами, никогда не поднимается выше 4 байтов за цикл. Это указывает на то, что в таких процессорах Netburst, Intel решила использовать в кэш-памяти L1d режим с прямой записью (Write-Through), при котором скорость, очевидно, ограничена скорость работы кэш-памяти L2. Это также означает, что производительность теста копирования, в котором данные копируются из одной области памяти в другую непересекающуюся области памяти, не намного хуже. Следовательно, требуемые операций чтения выполняются намного быстрее и могут частично перекрываться с операциями записи. Самым интересными деталями измерения записи и копирования является низкая производительность в случае, как только становится мало кэш-памяти L2. Производительность падает до 0,5 байта за цикл! Это значит, что операции записи в десять раз медленнее, чем операции чтения. Это означает, что оптимизация этих операций еще более важна для выполнения программы.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Shultc
@Shultc
RnD Developer
Сделайте систему логирования: Записывайте в файл время происшествия каждого события. Между какими двумя событиями время расти начнёт, там и проблема.
Анекдот

Дорожно-ремонтное предприятие где-то во Франции приняло на работу корсиканца. Поручили ему наносить краской разметку на асфальтовой дороге. В первый день он нанес 50 м разметки. Во второй 30. В третий - 15. А в четвертый день - только 5. Возмущенный прораб приехал и спрашивает - почему дескать производительность все хуже с каждым днем ? Последовал ответ: а как же иначе ? - ведь чем дальше продвигаешься вперед с нанесенной разметкой, тем дальше ходить до ведра с краской...
Ответ написан
@MoonMaster
Программист и этим все сказано
Скорее всего решение в этом месте
for(int i = 0; i < A.length; i++){
            A[i] = (int)(Math.random() * k);
        }

Потому что random он не совсем генерирует случайное число. При больших итерация в силу вступает ЗБЧ (закон больших чисел). То есть есть вероятность, что в вашем массиве будут числа различные на какую то константу, а может и вообще быть в пределах некоторого диапазона
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bell Integrator Ульяновск
До 400 000 ₽
Bell Integrator Ижевск
До 400 000 ₽
Bell Integrator Хабаровск
До 400 000 ₽
19 июн. 2024, в 16:19
100000 руб./за проект
19 июн. 2024, в 16:10
1500 руб./в час
19 июн. 2024, в 16:09
1500 руб./в час