Получение максимальных данных, которые может обрабатывать алгоритм за определенный промежуток времени

Question

Хорошо, что это второй раз, когда я получил упражнение, где мне нужно определить (в данном случае речь идет о алгоритмах сортировки), сколько чисел я могу сортировать с помощью определенного алгоритма (на моем собственном компьютере), чтобы алгоритм работал ровно через минуту.

Это практическое упражнение, это означает, что я должен генерировать достаточно чисел, чтобы он работал так долго. Теперь я спрашиваю себя, так как у меня не было этой проблемы за все десять лет программирования: как я могу это сделать? Моя первая попытка была немного грубой, что привело к мгновенному StackOverflow.

Я мог бы создать массив (или несколько) и заполнить их случайными числами, но определить, сколько из них закончится за одну минуту, было бы ужасной долгой задачей, так как вам всегда нужно было ждать.

Что я могу сделать, чтобы эффективно узнать об этом? Измеряя разницу между, скажем, 10 и 20 числами, и подсчитайте, сколько потребуется, чтобы заполнить минуту? Звучит просто, но алгоритмы (особенно алгоритмы сортировки) редко линейны.

Answer 1

Вы могли бы использовать что-то вроде этого:

long startTime = System.getCurrentTimeMillis(); 
int times = 0; 
boolean done = false; 
while(!done){ 
//run algorithm 
times++; 
if(System.getCurrentTimeMillis()-startTime >= 60000) 
    done = true; 
} 

Или, если вы не хотите долго ждать, вы можете можете заменить 60000 на 1000, а затем умножить на 60 раз, это не будет очень точно.

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

Answer 2

Вы знаете временную сложность для каждого рассматриваемого алгоритма. Например, сортировка пузырьков занимает O (n * n). Сделайте относительно небольшой прогон образца - D = 1000 записей, измерьте время, которое требуется (T миллисекунды). Например, требуется 15 секунд = 15000 миллисекунд.

Теперь с большей или меньшей точностью вы можете ожидать, что записи D * 2 будут обработаны в 4 раза медленнее. И наоборот - вам нужно около D * sqrt (60000/T) записей для их обработки за 1 минуту. Например, вам нужен D * sqrt (60000/15000) = D * sqrt (4) = D * 2 = 2000 записей.

Этот метод не является достаточно точным, чтобы получить точное число, и в большинстве случаев точное количество записей не задано, оно колеблется от запуска до запуска. Также для многих алгоритмов время, которое требуется, зависит от значений в вашем наборе записей. Например, наихудший случай для быстрой сортировки - O (n n), в то время как нормальный случай - O (n log (n))