Run results for: parleto

Run details:

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36

Browser: Chrome 131

Operating system: Windows

Device Platform: Desktop

Date tested: one year ago

Test name	Executions per second
S1	553392.2 Ops/sec
S2	1206181.2 Ops/sec

HTML Preparation code:

<!--your preparation HTML code goes here-->

Script Preparation code:

    const expenses = {
        '2023-01': {
            '01': {
                food: [22.11, 43, 11.72, 2.2, 36.29, 2.5, 19],
                fuel: [210.22],
            },
            '09': {
                food: [11.9],
                fuel: [190.22],
            },
        },
        '2023-03': {
            '07': {
                food: [20, 11.9, 30.2, 11.9],
            },
            '04': {
                food: [10.2, 11.5, 2.5],
                fuel: [],
            },
        },
        '2023-04': {},
    };

    function getFirstSunday(monthOfYear) {
        let firstSunday = 1;
        const weekday = new Date(`${monthOfYear}-01`).getDay();
        if (weekday !== 0) {
            // Offsetujemy dzień, bo getDay() zwraca 0 dla niedzieli
            firstSunday = 8 - weekday;
        }
        return firstSunday;
    }

    function solution1(expenses) {
        let result = null;
        let allExpenses = [];

        for (const monthOfYear in expenses) {
            const month = expenses[monthOfYear];
            const daysWithExpenses = Object.keys(month).map(Number);
            const firstSunday = getFirstSunday(monthOfYear);
            const daysUpToFirstSunday = daysWithExpenses.filter(
                day => day <= firstSunday
            );
            if (daysUpToFirstSunday.length === 0) continue;
            for (const day of daysUpToFirstSunday) {
                const allDayExpenses = month[`0${day}`];
                for (const dayExpenses of Object.values(allDayExpenses)) {
                    for (const expense of dayExpenses) {
                        allExpenses.push(expense);
                    }
                }
            }
        }
        // Jeśli nie ma wydatków to nie ma z czego liczyć medianę, więc zwracamy null
        if (allExpenses.length === 0) return result;
        allExpenses.sort((a, b) => a - b);

        const midIndex = Math.floor(allExpenses.length / 2);
        if (allExpenses.length % 2 === 0) {
            const midValue1 = allExpenses[midIndex - 1];
            const midValue2 = allExpenses[midIndex];
            result = (midValue1 + midValue2) / 2;
        } else {
            result = allExpenses[midIndex];
        }

        return result;
    }

    function findMedian(arr) {
        const midIndex = Math.floor(arr.length / 2);

        if (arr.length % 2 === 1) return quickSelect(arr, midIndex);
        return (
            (quickSelect(arr, midIndex - 1) + quickSelect(arr, midIndex)) / 2
        );
    }

    function quickSelect(arr, k) {
        return quickSelectHelper(arr, 0, arr.length - 1, k);
    }

    function quickSelectHelper(arr, left, right, k) {
        if (left === right) return arr[left];

        const pivotIndex = partition(arr, left, right);

        if (k === pivotIndex) return arr[k];
        if (k < pivotIndex)
            return quickSelectHelper(arr, left, pivotIndex - 1, k);
        return quickSelectHelper(arr, pivotIndex + 1, right, k);
    }

    function partition(arr, left, right) {
        const pivot = arr[right];
        let i = left - 1;

        for (let j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }

        [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
        return i + 1;
    }

    function solution2(expenses) {
        let result = null;
        let allExpenses = [];

        for (const monthOfYear in expenses) {
            const month = expenses[monthOfYear];
            const firstSunday = getFirstSunday(monthOfYear);

            for (const day in month) {
                if (Number(day) > firstSunday) continue;
                const allDayExpenses = month[day];
                for (const dayExpenses of Object.values(allDayExpenses)) {
                    if (dayExpenses.length === 0) continue;
                    for (const expense of dayExpenses) {
                        allExpenses.push(expense);
                    }
                }
            }
        }
        // Jeśli nie ma wydatków to nie ma z czego liczyć medianę, więc zwracamy null
        if (allExpenses.length === 0) return null;

        // Kalkulujemy medianę używając algorytmu Quick Select
        // Obrałem daną metodologię, gdyż jest to algorytm najczęściej operujący ze złożonością O(n)
        // Jest to zatem bardziej optymalny sposób, niż zwykłe sortowanie arraya i wybranie z niego środkowych elementów
        // Minusem jest nieco bardziej skomplikowany kod oraz rzadki przypadek, w którym złożoność algorytmu wynosi O(n^2)
        result = findMedian(allExpenses);
        return result;
    }

Tests:

S1
solution1(expenses);
S2
solution2(expenses);

S1

S2