I compared two functions with performance.now(), so I supposed that the second function would be better than first one but it happens the other way around. I don't know why this happen? same1 has into for loop an indexOf and splice function which each one represent a O(n), so we have a O(n^2). In same2 I apply Frecuency Counter Pattern, with three for loops which represent O(3N).
Should be second function faster than first one, isn't it?
function same1(arr1, arr2) {
// compare length of both arrays
if (arr1.length !== arr2.length) return false
for (let i = 0; i < arr1.length; i++) {
const indexArra2 = arr2.indexOf(arr1[i] ** 2);
if (indexArra2 === -1) return false;
arr2.splice(indexArra2, 1);
}
return true;
}
function same2(arr1, arr2) {
if (arr1.length !== arr2.length) return false;
let arrObj1 = {};
let arrObj2 = {};
// { 1: 1, 2: 2, 3: 1 }
for(let val of arr1) {
arrObj1[val] = (arrObj1[val] || 0) + 1;
}
// { 1: 1, 4: 2, 9: 1 }
for(let val of arr2) {
arrObj2[val] = (arrObj2[val] || 0) + 1;
}
for(key in arrObj1) {
if(!(key ** 2 in arrObj2)) {
return false;
}
if(arrObj2[key ** 2] !== arrObj1[key]) {
return false;
}
}
return true;
}
const t0 = performance.now();
same1([1,2,3,2], [9,1,4,4]);
const t1 = performance.now();
const t2 = performance.now();
same2([1,2,3,2], [9,1,4,4]);
const t3 = performance.now();
console.log(`Call to same1 took ${t1 - t0} milliseconds.`);
console.log(`Call to same2 took ${t3 - t2} milliseconds.`);
Aucun commentaire:
Enregistrer un commentaire