mercredi 23 septembre 2020

Compare performance of two function applying a pattern

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