Problem
i have the following json object
const file = [
{
"seatNumber": "1A",
"price": "£19.99",
"available": true,
"disabilityAccessible": true
},
{
"seatNumber": "2A",
"price": "£19.99",
"available": false,
"disabilityAccessible": false
},
{
"seatNumber": "3A",
"price": "£19.99",
"available": false,
"disabilityAccessible": false
},
{
"seatNumber": "4A",
"price": "£19.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "5A",
"price": "£19.99",
"available": false,
"disabilityAccessible": false
},
{
"seatNumber": "1B",
"price": "£12.99",
"available": true,
"disabilityAccessible": true
},
{
"seatNumber": "2B",
"price": "£12.99",
"available": false,
"disabilityAccessible": false
},
{
"seatNumber": "3B",
"price": "£12.99",
"available": false,
"disabilityAccessible": false
},
{
"seatNumber": "4B",
"price": "£12.99",
"available": false,
"disabilityAccessible": false
},
{
"seatNumber": "5B",
"price": "£12.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "1C",
"price": "£12.99",
"available": true,
"disabilityAccessible": true
},
{
"seatNumber": "2C",
"price": "£12.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "3C",
"price": "£12.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "4C",
"price": "£12.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "5C",
"price": "£12.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "1D",
"price": "£12.99",
"available": true,
"disabilityAccessible": true
},
{
"seatNumber": "2D",
"price": "£12.99",
"available": false,
"disabilityAccessible": false
},
{
"seatNumber": "3D",
"price": "£12.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "4D",
"price": "£12.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "5D",
"price": "£12.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "1E",
"price": "£8.99",
"available": true,
"disabilityAccessible": true
},
{
"seatNumber": "2E",
"price": "£8.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "3E",
"price": "£8.99",
"available": false,
"disabilityAccessible": false
},
{
"seatNumber": "4E",
"price": "£8.99",
"available": true,
"disabilityAccessible": false
},
{
"seatNumber": "5E",
"price": "£8.99",
"available": false,
"disabilityAccessible": false
}
]
I am trying to display seatNumber of the cheapest objects. so far i have the following which works but would like to know if there is a better way following big o notation in es6 format
const seats = file.filter( seat => seat.price.replace(/[^0-9.-]+/g,"") == Math.min(...file.map(function ( seat ) { return Number(seat.price.replace(/[^0-9.-]+/g,"")) }) ) ).map(seat => seat.seatNumber);
console.log(seats)
output is
[ '1E', '2E', '3E', '4E', '5E' ]
Solution
Following the little big O.
You ask
“…if there is a better way following big o notation…” (?)
Big O notation is a formalized mathematical convention used to express how a function (mathematical function) behaves as it approaches infinity.
It is used in computer science to classify an algorithms complexity in regard to a definable input metric, usually the size of the input array when dealing with arrays.
You can not “follow” big O notation as it provides no insight into how to reduce an algorithms complexity apart from a comparison.
Find the big O
To classify your function using Big O, first we need to make it at least readable, and convert it to a function. See snippet.
Now count the number of times the function loops over each item in the input array data. Experience lets you do this in your head, but to demonstrate we modify the function to count every time you handle an item in the input array.
Because we need to fit a curve we need at least 3 different input sizes which I do with some random data.
function bestSeats(data) {
var c = 0; // the counter
const seats = data.filter( seat =>
(c++, // count the filter iterations
seat.price.replace(/[^0-9.-]+/g, "") == Math.min(
...data.map(function ( seat ) {
c += 2; // this counts as two
// once each to map to the arguments of Math.min
// once each to find the min
return Number(seat.price.replace(/[^0-9.-]+/g, ""))
}
)
))).map(seat => (
c++, // count each result
seat.seat
));
return "O(n) = O(" + data.length + ") = " + c;
}
function randomData(size) {
const data = [];
while (size--) { data.push({seat:size, price: "$"+(Math.random() * 100 | 0)})}
return data;
}
console.log("Eval complexity A:" + bestSeats(randomData(10)));
console.log("Eval complexity B:" + bestSeats(randomData(100)));
console.log("Eval complexity C:" + bestSeats(randomData(500)));The 3 points we can use to find the curve that best fits
O(10) ~= 211
O(100) ~= 20,102
O(500) ~= 500,005
Experience tells me it’s a polynomial of some (not too high) order. Using a graphing calculator I found a reasonable fits at 2.15 making your functions big O complexity
O(n2.15)
Which is insanely inefficient. OMDG!!!!
So keeping
“…in es6 format” (?)
in mind a cleaner more readable, less CO2 producing sea level rising approach is to do a two pass scan of the seats. The first pass finds the min price, the second extracts the min price seat numbers.
This example uses for of loops rather than the Array methods like filter and map, because these array methods have a nasty way of blinding people to the insane level of complexity of what they do, and for of is a little quicker and often allows better optimizations than the array methods, so it’s win win for for of
Examples in O(n) linear time.
function bestSeats(seats) {
var min = Infinity, minVal;
const result = [];
for (const seat of seats) {
const price = Number(seat.price.slice(1));
if (price < min) {
min = price;
minVal = seat.price;
}
}
for (const seat of seats) {
if (seat.price === minVal) { result.push(seat.seatNumber) }
}
return result;
}
And if you must use the array methods.
function bestSeats(seats) {
const price2Num = seat => Number(seat.price.slice(1));
const min = (min, seat) => price2Num(seat) < min ? price2Num(seat) : min;
const minPrice = "$" + seats.reduce(min, Infinity);
return seats.filter(seat => seat.price === minPrice).map(seat => seat.seatNumber);
}