Итак, ситуация такая: я решал задачу, которая возвращает время в милисекундах, требующееся для заполнения коллекции типа LinkedList (в нулевой сегмент). Кстати, да, это на порядок быстрее происходит, чем для ArrayList, но речь идет не об этом.
Я стал исследовать, как меняется время работы программы, например, для 1000 элементов, для 10000 элементов, итд. public static void main(String[] args)
{
System.out.println(getTimeMsOfInsert(new LinkedList()));
}
public static long getTimeMsOfInsert(List list)
{
long currentTime = new Date().getTime();
insert10000( list );
return new Date().getTime() - currentTime;
}
public static void insert10000(List list)
{
for (long i=0;i<10000000;i++)
{
list.add(0, new Object());
}
}
И получил такой результат
10^4 элементов работал 2 ms
10^5 элементов работал 15ms
10^6 элементов работал 187ms
10^7 элементов работал 2,327 секунд
И теперь, внимание - я ожидал, что для 10^8 элементов алгоритм будет работать примерно 20 секунд...
однако на деле:
10^8 элементов работал 202,215 секунд
Дополнительная информация:
процессор core i7 4810MQ (2,8 GHz)
6 MB кэш памяти
32 GB оперативной памяти
Win8 64
Во время выполнения программы с 10^8 элементами я запустил диспетчер задач - процессор пахал на 100%, несколько сотен Мегабайт оперативной памяти заполнялись.
Вопросы:
1 - почему при переходе от 10^7 к 10^8 элементам алгоритм увеличивает время работы не на 1, а на 2 порядка?
Моя гипотеза такова: закончился кэш процессора и массив пошел в оперативную память. Но неужели в моем распоряжении несколько МБ кэша процессора, при условии, что помимо IDEA ничего не запущено?
2 - есть ли возможность сократить время работы алгоритма до примерно 20 секунд?
3 - сколько примерно будет программа вычислять 10^9 элементов?
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ