Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Script to test three algorithms for SQL-based area search
var mysql = require('mysql'),
assert = require('assert'),
util = require('util'),
sys = require('sys');
var client = mysql.createClient({
user: 'root',
password: null,
database: 'tests'
});
/* ===== test configuration ===== */
var test = {
locations: 200,
limits: [1, 5, 10, 20, 50, 100, 150, 200]
//limits: [1, 5]
};
var testrange = {
lat: [47.4, 55.0],
lon: [5.9, 15.0]
};
var highestLimit = test.limits.slice(-1)[0];
/* ===== create tests ===== */
diffLat = testrange.lat[1]-testrange.lat[0];
diffLon = testrange.lon[1]-testrange.lon[0];
testcases = [];
for (var i = 0; i < test.locations; i++) {
testcases.push({
lat: testrange.lat[0] + Math.random()*diffLat,
lon: testrange.lon[0] + Math.random()*diffLon
});
}
/* ===== helper functions ===== */
function allIn(array, testArray) {
for (var i = 0; i < array.length; i++) {
if (testArray.indexOf(array[i]) === -1)
return false;
}
return true;
}
function exactQuery(coords, limit, cb) {
var start = (new Date()).getTime();
client.query('SELECT id, (acos(sin('+coords.lat+'*Pi()/180)*sin(lat*Pi()/180)+cos('+coords.lat+'*Pi()/180)*cos(lat*Pi()/180)*cos(('+coords.lon+'-lon)*Pi()/180))) as distance FROM coords ORDER BY distance ASC LIMIT '+limit,
function(err, results, fields) {
assert.ifError(err);
cb(Math.round(((new Date()).getTime()-start)/1));
});
}
function pythagoras(coords, exact, limit, cb) {
var start = (new Date()).getTime();
client.query('SELECT id FROM coords ORDER BY SQRT(POW(('+coords.lat+'-lat), 2)+POW(('+coords.lon+'-lon), 2)) ASC LIMIT '+limit, function(err, results) {
assert.ifError(err);
var r = [];
for (var i = 0; i < results.length; i++) {
r.push(results[i].id);
}
if (allIn(exact, r)) {
var timeDiff = Math.round(((new Date()).getTime()-start)/1);
cb(limit, timeDiff);
} else {
pythagoras(coords, exact, limit+1, cb);
}
});
}
function advancedPythagoras(coords, exact, limit, cb) {
var start = (new Date()).getTime();
client.query('SELECT id FROM coords ORDER BY SQRT(POW(('+coords.lat+'-lat)/70, 2)+POW(('+coords.lon+'-lon)/110, 2)) ASC LIMIT '+limit, function(err, results) {
assert.ifError(err);
var r = [];
for (var i = 0; i < results.length; i++) {
r.push(results[i].id);
}
if (allIn(exact, r)) {
var timeDiff = Math.round(((new Date()).getTime()-start)/1);
cb(limit, timeDiff);
} else {
advancedPythagoras(coords, exact, limit+1, cb);
}
});
}
var testResults = {};
function doEnd() {
/* Output as CSV */
console.log('Testcase; Lon; Lat; Limit; Exact:Time; Pythagoras:Limit; Pythagoras:Time; AdvancedPythagoras:Limit; AdvancedPythagoras:Time');
for (var testcase in testResults) {
for (var i = 0; i < test.limits.length; i++) {
console.log(''+testcase+';'+testcases[testcase].lon+';'+testcases[testcase].lat+';'+test.limits[i]+';'+testResults[testcase]['exact'][test.limits[i]]['time']+';'+testResults[testcase]['pythagoras'][test.limits[i]]['end']+';'+testResults[testcase]['pythagoras'][test.limits[i]]['time']+';'+testResults[testcase]['advancedPythagoras'][test.limits[i]]['end']+';'+testResults[testcase]['advancedPythagoras'][test.limits[i]]['time']);
}
}
setTimeout(function() {
process.exit(0);
}, 2000);
}
function runExact(testcases, ix, limits, ixl, cb) {
if (ixl >= limits.length) {
cb();
return;
}
exactQuery(testcases[ix], limits[ixl], function(time) {
testResults[ix]['exact'][limits[ixl]] = { time: time };
runExact(testcases, ix, limits, ixl+1, cb);
});
}
function runPythagoras(testcases, ix, exact, limits, ixl, cb) {
if (ixl >= limits.length) {
cb();
return;
}
pythagoras(testcases[ix], exact.slice(0, limits[ixl]), limits[ixl], function(l, time) {
testResults[ix]['pythagoras'][limits[ixl]] = { end: l, time: time };
runPythagoras(testcases, ix, exact, limits, ixl+1, cb);
});
}
function runAdvancedPythagoras(testcases, ix, exact, limits, ixl, cb) {
if (ixl >= limits.length) {
cb();
return;
}
advancedPythagoras(testcases[ix], exact.slice(0, limits[ixl]), limits[ixl], function(l, time) {
testResults[ix]['advancedPythagoras'][limits[ixl]] = { end: l, time: time };
runAdvancedPythagoras(testcases, ix, exact, limits, ixl+1, cb);
});
}
function runTestcase(testcases, ix, cb) {
if (ix >= testcases.length) {
cb();
return;
}
testResults[ix] = {
pythagoras: {},
advancedPythagoras: {},
exact: {}
};
// get exact results
var exact = [];
client.query('SELECT id, (acos(sin('+testcases[ix].lat+'*Pi()/180)*sin(lat*Pi()/180)+cos('+testcases[ix].lat+'*Pi()/180)*cos(lat*Pi()/180)*cos(('+testcases[ix].lon+'-lon)*Pi()/180))) as distance FROM coords ORDER BY distance ASC LIMIT '+highestLimit,
function(err, results, fields) {
assert.ifError(err);
for (var i = 0; i < results.length; i++) {
exact.push(results[i].id);
}
runExact(testcases, ix, test.limits, 0, function() {
runPythagoras(testcases, ix, exact, test.limits, 0, function() {
runAdvancedPythagoras(testcases, ix, exact, test.limits, 0, function() {
runTestcase(testcases, ix+1, cb);
});
});
});
});
}
/* ===== perform tests ===== */
//util.log("Start tests");
runTestcase(testcases, 0, function() {
doEnd();
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.