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

Question

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

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

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

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

Answer 1

Вы знаете сложность времени для каждого рассматриваемого алгоритма. Например, сортировка пузырьков занимает 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 (nn), а нормальным случаем является O (n log (n))

Answer 2

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

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, но это будет не очень точно.

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