Skip to content

Instantly share code, notes, and snippets.

@nicolasembleton
Last active July 28, 2021 12:57
Show Gist options
  • Save nicolasembleton/af8e8c09928c6911fe188e1a302c3bdf to your computer and use it in GitHub Desktop.
Save nicolasembleton/af8e8c09928c6911fe188e1a302c3bdf to your computer and use it in GitHub Desktop.
Benchmark of the multiple ways to find min and max in a large List in Dart
import 'dart:math';
import 'package:stats/stats.dart';
class Benchmark {
Benchmark({this.UPPER_BOUND = 100000, this.withSlow = false}) {
reset();
}
int UPPER_BOUND;
bool withSlow;
Map<String, Function> testsFunctions = {
'smallestUsingForLoopVar': findMinUsingForLoopVar,
'biggestUsingForLoopVar': findMaxUsingForLoopVar,
'smallestUsingForLoopGenericType': findMinUsingForLoopGenericType,
'biggestUsingForLoopGenericType': findMaxUsingForLoopGenericType,
'smallestUsingReverseForLoopVar': findMinUsingReverseForLoopVar,
'biggestUsingReverseForLoopVar': findMaxUsingReverseForLoopVar,
'smallestUsingReverseForLoopGenericType': findMinUsingReverseForLoopGenericType,
'biggestUsingReverseForLoopGenericType': findMaxUsingReverseForLoopGenericType,
};
Map<String, Function> slowTestsFunctions = {
'smallestUsingForEachLoop': findMinUsingForEachLoop,
'biggestUsingForEachLoop': findMaxUsingForEachLoop,
'smallestUsingReduce': findMinUsingReduce,
'biggestUsingReduce': findMaxUsingReduce,
'smallestUsingFold': findMinUsingFold,
'biggestUsingFold': findMaxUsingFold,
};
Map<String, Function> get tests {
if(withSlow) return {}..addAll(testsFunctions)..addAll(slowTestsFunctions);
return testsFunctions;
}
late Map<String, List<double>> usingForLoopData;
List<T> generateList<T extends num>({String type = 'int'}) {
var el = <T>[];
var rng = Random();
for(var i=0; i<UPPER_BOUND;i++) {
if(type == 'double') {
// double
el.add((rng.nextDouble() * UPPER_BOUND) as T);
} else {
// int
el.add(rng.nextInt(UPPER_BOUND) as T);
}
}
return el;
}
void addMeasurementToList({required String testKey, required double elapsed, bool andPrint = false}) {
assert(usingForLoopData.containsKey(testKey), true);
usingForLoopData[testKey]!.add(elapsed);
if(andPrint) {
print('$testKey, elapsed: $elapsed');
}
}
Stats getStatsForKey(key) {
return Stats.fromData(usingForLoopData[key] as List<num>).withPrecision(3);
}
Map<String, dynamic> getStats() {
return { for (var key in tests.keys) key : getStatsForKey(key)};
}
// Reset counters
void reset() {
usingForLoopData = { for (var value in tests.keys) value : [] };
}
}
void main() {
print('Benchmarking min / max finders');
// Good number for testing: 10000000
// Reasonable number for good quality output: 388805700
// rng.nextInt(429496729);
// Biggest possible number: 4294967296
var UPPER_BOUND = 10000000;
var BENCHMARKING_ROUNDS = 250;
var benchmark = Benchmark(UPPER_BOUND: UPPER_BOUND, withSlow: false);
var stopwatch = Stopwatch()..start();
print('UPPER_BOUND: $UPPER_BOUND');
print('BENCHMARKING_ROUNDS: $BENCHMARKING_ROUNDS');
print('**** INT suite ****');
var listInt = benchmark.generateList(); // List<int>
print('List<int> created, elapsed: ${stopwatch.elapsedMilliseconds/1000}');
stopwatch.reset(); // reset the watch
benchmark.tests.keys.forEach((element) {
// Run tests
for(var i=0;i<BENCHMARKING_ROUNDS;i++) {
benchmark.tests[element]!.call(listInt);
var elapsed = stopwatch.elapsedMilliseconds/1000;
benchmark.addMeasurementToList(testKey: element, elapsed: elapsed, andPrint: false);
stopwatch.reset();
}
print('$element: ${benchmark.getStatsForKey(element)}');
});
print('**** DOUBLE suite ****');
benchmark.reset();
var listDouble = benchmark.generateList(type: 'double'); // List<double>
print('List<double> created, elapsed: ${stopwatch.elapsedMilliseconds/1000}');
stopwatch.reset();
benchmark.tests.keys.forEach((element) {
// Run tests
for(var i=0;i<BENCHMARKING_ROUNDS;i++) {
benchmark.tests[element]!.call(listDouble);
var elapsed = stopwatch.elapsedMilliseconds/1000;
benchmark.addMeasurementToList(testKey: element, elapsed: elapsed, andPrint: false);
stopwatch.reset();
}
print('$element: ${benchmark.getStatsForKey(element)}');
});
// Unsurprisingly, sort is VERY slow. 20x forEach, which is itself very slow.
// Not running the tests for sanity sake, but feel free to if you want to see.
//List el2_min = List.from(el);
//List el2_max = List.from(el);
//print('Cloning the list for modifying methods: elapsed: ${stopwatch.elapsedMilliseconds/1000}');
//stopwatch.reset();
//int smallestUsingSort = findMinUsingSort(el2_min);
//print('Find min using sort ($smallestUsingSort), elapsed: ${stopwatch.elapsedMilliseconds/1000}');
//stopwatch.reset();
//int biggestUsingSort = findMaxUsingSort(el2_max);
//print('Find max using sort ($biggestUsingSort), elapsed: ${stopwatch.elapsedMilliseconds/1000}');
//stopwatch.reset();
}
num findMinUsingForLoopVar(List el) {
var smallest = el.first;
for (var i = 0; i < el.length; i++) {
if (el[i] < smallest) {
smallest = el[i];
}
}
return smallest;
}
num findMaxUsingForLoopVar(List el) {
var biggest = el.first;
for (var i = 0; i < el.length; i++) {
if (el[i] > biggest) {
biggest = el[i];
}
}
return biggest;
}
T findMinUsingForLoopGenericType<T extends num>(List el) {
var smallest = el.first as T;
for (var i = 0; i < el.length; i++) {
if (el[i] < smallest) {
smallest = el[i];
}
}
return smallest;
}
T findMaxUsingForLoopGenericType<T extends num>(List el) {
var biggest = el.first;
for (var i = 0; i < el.length; i++) {
if (el[i] > biggest) {
biggest = el[i];
}
}
return biggest;
}
num findMinUsingReverseForLoopVar(List el) {
var smallest = el.first;
for (var i = el.length-1; i >= 0; i--) {
if (el[i] < smallest) {
smallest = el[i];
}
}
return smallest;
}
num findMaxUsingReverseForLoopVar(List el) {
var biggest = el.first;
for (var i = el.length-1; i >= 0; i--) {
if (el[i] > biggest) {
biggest = el[i];
}
}
return biggest;
}
T findMinUsingReverseForLoopGenericType<T extends num>(List el) {
var smallest = el.first as T;
for (var i = el.length-1; i >= 0; i--) {
if (el[i] < smallest) {
smallest = el[i];
}
}
return smallest;
}
T findMaxUsingReverseForLoopGenericType<T extends num>(List el) {
var biggest = el.first as T;
for (var i = el.length-1; i >= 0; i--) {
if (el[i] > biggest) {
biggest = el[i];
}
}
return biggest;
}
num findMinUsingSort(List el) {
el.sort();
return el.first;
}
num findMaxUsingSort(List el) {
el.sort();
return el.last;
}
num findMinUsingForEachLoop(List el) {
var smallest = el.first;
el.forEach((val) => {
if(val < smallest) {smallest = val}
});
return smallest;
}
num findMaxUsingForEachLoop(List el) {
var biggest = el.first;
el.forEach((val) => {
if(val > biggest) {biggest = val}
});
return biggest;
}
num findMinUsingFold(List el) {
return (el as List<num>).fold(el.first, min);
}
num findMaxUsingFold(List el) {
return (el as List<num>).fold(el.first, max);
}
num findMinUsingReduce(List el) {
return (el as List<num>).reduce(min);
}
num findMaxUsingReduce(List el) {
return (el as List<num>).reduce(max);
}
@nicolasembleton
Copy link
Author

nicolasembleton commented Jul 28, 2021

Ok I'm happy with where it is now. More refactor, added the slow tests as an option if you want to run them, made all functions generic to any num type and added the benchmark suite for doubles. Good to go.

Final results (most likely) without slow methods:

Benchmarking min / max finders
UPPER_BOUND: 10000000
BENCHMARKING_ROUNDS: 250
**** INT suite ****
List<int> created, elapsed: 0.384
smallestUsingForLoopVar: {count: 250, average: 0.0153, min: 0.013, max: 0.038, median: 0.015, standardDeviation: 0.0019}
biggestUsingForLoopVar: {count: 250, average: 0.0149, min: 0.013, max: 0.024, median: 0.015, standardDeviation: 0.000884}
smallestUsingForLoopGenericType: {count: 250, average: 0.0163, min: 0.014, max: 0.021, median: 0.016, standardDeviation: 0.0011}
biggestUsingForLoopGenericType: {count: 250, average: 0.014, min: 0.012, max: 0.025, median: 0.014, standardDeviation: 0.00176}
smallestUsingReverseForLoopVar: {count: 250, average: 0.0117, min: 0.01, max: 0.016, median: 0.012, standardDeviation: 0.000761}
biggestUsingReverseForLoopVar: {count: 250, average: 0.0162, min: 0.013, max: 0.019, median: 0.016, standardDeviation: 0.00106}
smallestUsingReverseForLoopGenericType: {count: 250, average: 0.0183, min: 0.015, max: 0.021, median: 0.018, standardDeviation: 0.00129}
biggestUsingReverseForLoopGenericType: {count: 250, average: 0.0187, min: 0.015, max: 0.024, median: 0.019, standardDeviation: 0.00139}
**** DOUBLE suite ****
List<double> created, elapsed: 1.335
smallestUsingForLoopVar: {count: 250, average: 0.0705, min: 0.061, max: 0.103, median: 0.069, standardDeviation: 0.00763}
biggestUsingForLoopVar: {count: 250, average: 0.0576, min: 0.049, max: 0.083, median: 0.057, standardDeviation: 0.00385}
smallestUsingForLoopGenericType: {count: 250, average: 0.0511, min: 0.044, max: 0.066, median: 0.051, standardDeviation: 0.00326}
biggestUsingForLoopGenericType: {count: 250, average: 0.057, min: 0.051, max: 0.069, median: 0.057, standardDeviation: 0.00314}
smallestUsingReverseForLoopVar: {count: 250, average: 0.0632, min: 0.058, max: 0.084, median: 0.062, standardDeviation: 0.00432}
biggestUsingReverseForLoopVar: {count: 250, average: 0.0555, min: 0.048, max: 0.067, median: 0.055, standardDeviation: 0.00239}
smallestUsingReverseForLoopGenericType: {count: 250, average: 0.0567, min: 0.05, max: 0.073, median: 0.056, standardDeviation: 0.00327}
biggestUsingReverseForLoopGenericType: {count: 250, average: 0.0412, min: 0.036, max: 0.062, median: 0.041, standardDeviation: 0.00315}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment