Во-первых, в тестах есть два набора операций: проверка факторов и регистрация этих факторов.При переключении реализаций с использованием Set вместо ArrayList (в моем переписывании ниже) вместо простого подсчета факторов будет иметь значение.
Во-вторых, я вижу очень большие различия втайминги.Это работает от Eclipse.У меня нет четкого понимания того, что вызывает большие различия.
Мои «извлеченные уроки» должны помнить о том, что именно измеряется.Намерен ли измерить сам алгоритм факторизации (стоимость циклов while плюс арифметические операции)?Следует ли учитывать время записи факторов?
Незначительный технический момент: в этой реализации остро ощущается недостаток multiple-value-setq, который доступен в lisp.Можно было бы скорее выполнить остаток и целочисленное деление как одну операцию, а не записывать их как два отдельных шага.С точки зрения изучения языка и алгоритмов это стоит посмотреть.
Вот временные результаты для трех вариантов реализации факторизации.Первый из исходной (неоптимизированной) реализации, но изменен для использования простого списка вместо более сложного набора времени для хранения факторов.Во-вторых, ваша оптимизация, но все еще отслеживание с использованием списка.Третья - ваша оптимизация, но включающая изменение для подсчета факторов.
18 - 3790 1450 2410 (average of 10 iterations)
64 - 1630 1220 260 (average of 10 iterations)
1091 - 16170 2850 1180 (average of 10 iterations)
1092 - 2720 1370 380 (average of 10 iterations)
4096210 - 28830 5430 9120 (average of 10 iterations, trial 1)
4096210 - 18380 6190 5920 (average of 10 iterations, trial 2)
4096210 - 10072 5816 4836 (average of 100 iterations, trial 1)
4096210 - 7202 5036 3682 (average of 100 iterations, trial 1)
---
Test value [ 18 ]
Warm-up count [ 2 ]
Test count [ 10 ]
Times [non-optimized]
Start [ 1621713914872600 (ns) ]
End [ 1621713914910500 (ns) ]
Delta [ 37900 (ns) ]
Avg [ 3790 (ns) ]
Factors: [2, 3, 3]
Times [optimized]
Start [ 1621713915343500 (ns) ]
End [ 1621713915358000 (ns) ]
Delta [ 14500 (ns) ]
Avg [ 1450 (ns) ]
Factors: [2, 3, 3]
Times [counting]
Start [ 1621713915550400 (ns) ]
End [ 1621713915574500 (ns) ]
Delta [ 24100 (ns) ]
Avg [ 2410 (ns) ]
Factors: 3
---
Test value [ 64 ]
Warm-up count [ 2 ]
Test count [ 10 ]
Times [non-optimized]
Start [ 1621747046013900 (ns) ]
End [ 1621747046030200 (ns) ]
Delta [ 16300 (ns) ]
Avg [ 1630 (ns) ]
Factors: [2, 2, 2, 2, 2, 2]
Times [optimized]
Start [ 1621747046337800 (ns) ]
End [ 1621747046350000 (ns) ]
Delta [ 12200 (ns) ]
Avg [ 1220 (ns) ]
Factors: [2, 2, 2, 2, 2, 2]
Times [counting]
Start [ 1621747046507900 (ns) ]
End [ 1621747046510500 (ns) ]
Delta [ 2600 (ns) ]
Avg [ 260 (ns) ]
Factors: 6
---
Test value [ 1091 ]
Warm-up count [ 2 ]
Test count [ 10 ]
Times [non-optimized]
Start [ 1621687024226500 (ns) ]
End [ 1621687024388200 (ns) ]
Delta [ 161700 (ns) ]
Avg [ 16170 (ns) ]
Factors: [1091]
Times [optimized]
Start [ 1621687024773200 (ns) ]
End [ 1621687024801700 (ns) ]
Delta [ 28500 (ns) ]
Avg [ 2850 (ns) ]
Factors: [1091]
Times [counting]
Start [ 1621687024954900 (ns) ]
End [ 1621687024966700 (ns) ]
Delta [ 11800 (ns) ]
Avg [ 1180 (ns) ]
Factors: 1
---
Test value [ 1092 ]
Warm-up count [ 2 ]
Test count [ 10 ]
Times [non-optimized]
Start [ 1621619636267500 (ns) ]
End [ 1621619636294700 (ns) ]
Delta [ 27200 (ns) ]
Avg [ 2720 (ns) ]
Factors: [2, 2, 3, 7, 13]
Times [optimized]
Start [ 1621619636657100 (ns) ]
End [ 1621619636670800 (ns) ]
Delta [ 13700 (ns) ]
Avg [ 1370 (ns) ]
Factors: [2, 2, 3, 7, 13]
Times [counting]
Start [ 1621619636895300 (ns) ]
End [ 1621619636899100 (ns) ]
Delta [ 3800 (ns) ]
Avg [ 380 (ns) ]
Factors: 5
---
Test value [ 4096210 ]
Warm-up count [ 2 ]
Test count [ 10 ]
Times [non-optimized]
Start [ 1621652753519800 (ns) ]
End [ 1621652753808100 (ns) ]
Delta [ 288300 (ns) ]
Avg [ 28830 (ns) ]
Factors: [2, 5, 19, 21559]
Times [optimized]
Start [ 1621652754116300 (ns) ]
End [ 1621652754170600 (ns) ]
Delta [ 54300 (ns) ]
Avg [ 5430 (ns) ]
Factors: [2, 5, 19, 21559]
Times [counting]
Start [ 1621652754323500 (ns) ]
End [ 1621652754414700 (ns) ]
Delta [ 91200 (ns) ]
Avg [ 9120 (ns) ]
Factors: 4
Вот мое переписывание тестового кода.Наибольший интерес представляют findFactors, findFactorsOpt и findFactorsCount.
package my.tests;
import java.util.ArrayList;
import java.util.List;
public class PrimeFactorsTest {
public static void main(String[] args) {
if ( args.length < 2 ) {
System.out.println("Usage: " + PrimeFactorsTest.class.getName() + " testValue warmupIterations testIterations");
return;
}
int testValue = Integer.valueOf(args[0]);
int warmCount = Integer.valueOf(args[1]);
int testCount = Integer.valueOf(args[2]);
if ( testValue <= 2 ) {
System.out.println("Test value [ " + testValue + " ] must be at least 2.");
return;
} else {
System.out.println("Test value [ " + testValue + " ]");
}
if ( warmCount <= 0 ) {
System.out.println("Warm-up count [ " + testCount + " ] must be at least 1.");
} else {
System.out.println("Warm-up count [ " + warmCount + " ]");
}
if ( testCount <= 1 ) {
System.out.println("Test count [ " + testCount + " ] must be at least 1.");
} else {
System.out.println("Test count [ " + testCount + " ]");
}
timedFactors(testValue, warmCount, testCount);
timedFactorsOpt(testValue, warmCount, testCount);
timedFactorsCount(testValue, warmCount, testCount);
}
public static void timedFactors(int testValue, int warmCount, int testCount) {
List<Integer> factors = new ArrayList<Integer>();
for ( int warmNo = 0; warmNo < warmCount; warmNo++ ) {
factors.clear();
findFactors(testValue, factors);
}
long startTime = System.nanoTime();
for ( int testNo = 0; testNo < testCount; testNo++ ) {
factors.clear();
findFactors(testValue, factors);
}
long endTime = System.nanoTime();
System.out.println("Times [non-optimized]");
System.out.println("Start [ " + startTime + " (ns) ]");
System.out.println("End [ " + endTime + " (ns) ]");
System.out.println("Delta [ " + (endTime - startTime) + " (ns) ]");
System.out.println("Avg [ " + (endTime - startTime) / testCount + " (ns) ]");
System.out.println("Factors: " + factors);
}
public static void findFactors(int n, List<Integer> factors) {
while ( n % 2 == 0 ) {
n /= 2;
factors.add( Integer.valueOf(2) );
}
for ( int factor = 3; factor <= Math.sqrt(n); factor += 2 ) {
while ( n % factor == 0 ) {
n /= factor;
factors.add( Integer.valueOf(factor) );
}
}
if ( n > 2 ) {
factors.add( Integer.valueOf(n) );
}
}
public static void timedFactorsOpt(int testValue, int warmCount, int testCount) {
List<Integer> factors = new ArrayList<Integer>();
for ( int warmNo = 0; warmNo < warmCount; warmNo++ ) {
factors.clear();
findFactorsOpt(testValue, factors);
}
long startTime = System.nanoTime();
for ( int testNo = 0; testNo < testCount; testNo++ ) {
factors.clear();
findFactorsOpt(testValue, factors);
}
long endTime = System.nanoTime();
System.out.println("Times [optimized]");
System.out.println("Start [ " + startTime + " (ns) ]");
System.out.println("End [ " + endTime + " (ns) ]");
System.out.println("Delta [ " + (endTime - startTime) + " (ns) ]");
System.out.println("Avg [ " + (endTime - startTime) / testCount + " (ns) ]");
System.out.println("Factors: " + factors);
}
public static void findFactorsOpt(int n, List<Integer> factors) {
if ( n % 2 == 0 ) {
n /= 2;
Integer factor = Integer.valueOf(2);
factors.add(factor);
while (n % 2 == 0) {
n /= 2;
factors.add(factor);
}
}
for ( int factorValue = 3; factorValue <= Math.sqrt(n); factorValue += 2) {
if ( n % factorValue == 0 ) {
n /= factorValue;
Integer factor = Integer.valueOf(factorValue);
factors.add(factor);
while ( n % factorValue == 0 ) {
n /= factorValue;
factors.add(factor);
}
}
}
if (n > 2) {
factors.add( Integer.valueOf(n) );
}
}
public static void timedFactorsCount(int testValue, int warmCount, int testCount) {
int numFactors = 0;
for ( int warmNo = 0; warmNo < warmCount; warmNo++ ) {
numFactors = findFactorsCount(testValue);
}
long startTime = System.nanoTime();
for ( int testNo = 0; testNo < testCount; testNo++ ) {
numFactors = findFactorsCount(testValue);
}
long endTime = System.nanoTime();
System.out.println("Times [counting]");
System.out.println("Start [ " + startTime + " (ns) ]");
System.out.println("End [ " + endTime + " (ns) ]");
System.out.println("Delta [ " + (endTime - startTime) + " (ns) ]");
System.out.println("Avg [ " + (endTime - startTime) / testCount + " (ns) ]");
System.out.println("Factors: " + numFactors);
}
public static int findFactorsCount(int n) {
int numFactors = 0;
if ( n % 2 == 0 ) {
n /= 2;
numFactors++;
while (n % 2 == 0) {
n /= 2;
numFactors++;
}
}
for ( int factorValue = 3; factorValue <= Math.sqrt(n); factorValue += 2) {
if ( n % factorValue == 0 ) {
n /= factorValue;
numFactors++;
while ( n % factorValue == 0 ) {
n /= factorValue;
numFactors++;
}
}
}
if (n > 2) {
numFactors++;
}
return numFactors;
}
}