Benchmark: LIS-test2 - MeasureThat.net

HTML Preparation code:

<script src="//cdnjs.cloudflare.com/ajax/libs/seedrandom/3.0.5/seedrandom.min.js">
</script>

AخA
 
<script src="//cdnjs.cloudflare.com/ajax/libs/seedrandom/3.0.5/seedrandom.min.js">
</script>

Script Preparation code:

function shuffle(array) {
    var myrng = new Math.seedrandom('hello.');

    let currentIndex = array.length, temporaryValue, randomIndex;

    // While there remain elements to shuffle...
    while (0 !== currentIndex) {

        // Pick a remaining element...
        randomIndex = Math.floor(myrng() * currentIndex);
        currentIndex -= 1;

        // And swap it with the current element.
        temporaryValue = array[currentIndex];
        array[currentIndex] = array[randomIndex];
        array[randomIndex] = temporaryValue;
    }

    return array;
}

var N = 1000;
var original_array = Array.from(Array(N).keys());
var shuffled_array = shuffle(original_array.slice(0));

​x
 
function shuffle(array) {    var myrng = new Math.seedrandom('hello.');​    let currentIndex = array.length, temporaryValue, randomIndex;​    // While there remain elements to shuffle...    while (0 !== currentIndex) {​        // Pick a remaining element...        randomIndex = Math.floor(myrng() * currentIndex);        currentIndex -= 1;​        // And swap it with the current element.        temporaryValue = array[currentIndex];        array[currentIndex] = array[randomIndex];        array[randomIndex] = temporaryValue;    }​    return array;}​var N = 1000;var original_array = Array.from(Array(N).keys());var shuffled_array = shuffle(original_array.slice(0));​

Tests:

splice

function longest_increasing_subsequence (input) {
    const from_array = Array.from(Array(input.length).keys());
    let result_array = [], indexes = [];

    let n = input.length;

    if (n === 0) {
        return [];
    }

    let d = new Array(n).fill(1);
    let p = new Array(n).fill(-1);

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (input[j] < input[i] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1;
                p[i] = j;
            }
        }
    }

    let ans = d[0], pos = 0;
    for (let i = 1; i < n; i++) {
        if (d[i] > ans) {
            ans = d[i];
            pos = i;
        }
    }

    while(pos != -1) {
        // result_array.push(input[pos]);
        indexes.push(pos);
        pos = p[pos];
    }
    // result_array.reverse()
    indexes.reverse()

    // console.log(`Longest increasing sequence: ${result_array}`);
    console.log(`Longest increasing indexes: ${indexes}`);
    for (let i = indexes.length -1; i >= 0; i--) {
        input.splice(indexes[i],1);
        from_array.splice(indexes[i],1);
    }

    return [from_array, input];
}

function find_moves_step_one(from_array, to_array) {
    for (let i = 0; i < from_array.length; i++) {
        for (let j = i+1; j < from_array.length; j++) {
            if(from_array[j] >= from_array[i]) {
                from_array[j]--;
            }
        }
    }
    for (let i = to_array.length - 1; i >= 0; i--) {
        for (let j = i-1; j >= 0; j--) {
            if(to_array[j] > to_array[i]) {
                to_array[j]--;
            }
        }
    }
    return [from_array, to_array];
}

function find_moves_step_two(from_array, to_array) {
    let increase_in_i = 0;
    for (let i = 0; i < to_array.length; i++) {
        for (let j = to_array.length - 1; j >= i+1; j--) {
            if(from_array[j] < to_array[i]) {
                increase_in_i++;
            } else {
                from_array[j]++;
            }
        }
        to_array[i] += increase_in_i;
        increase_in_i = 0;
    }
    return [from_array, to_array];
}

function find_target_index(from_array, to_array) {
    if(JSON.stringify(from_array) == JSON.stringify(to_array)) {
        return [];
    } else {
        const target_index_arr = Array(from_array.length).fill(0);
        let index_found;
        from_array.forEach(function(item, index) {
            index_found = to_array.indexOf(item);
            if(index_found !== -1) {
                target_index_arr[index] = index_found;
            } else {
                //TODO make something dude! its not normal
            }
        });
        return target_index_arr;
    }
}

function move(array, from_array, to_array) {
    let item;
    for(let i = 0; i < from_array.length; i++) {
        if(from_array[i] > to_array[i]) {
            item = array[from_array[i]];
            for(let j = from_array[i] - 1; j >= to_array[i]; j--) {
                array[j+1] = array[j];
            }
            array[to_array[i]] = item;
        } else if(to_array[i] > from_array[i]) {
            item = array[from_array[i]];
            for(let j = from_array[i]; j <= to_array[i]; j++) {
                array[j] = array[j+1];
            }
            array[to_array[i]] = item;
        }
    }
    return array;
}

const target_index_arr = find_target_index(shuffled_array.slice(0), original_array.slice(0));
if(target_index_arr.length > 0) {
    console.log(`target index array: ${target_index_arr}`);
    const [from_array, to_array] = longest_increasing_subsequence(target_index_arr.slice(0));
    const [from_after_step1, to_after_step1] = find_moves_step_one(from_array.slice(0), to_array.slice(0))
    const [from_after_step2, to_after_step2] = find_moves_step_two(from_after_step1.slice(0), to_after_step1.slice(0))
}

 
function longest_increasing_subsequence (input) {    const from_array = Array.from(Array(input.length).keys());    let result_array = [], indexes = [];​    let n = input.length;​    if (n === 0) {        return [];    }​    let d = new Array(n).fill(1);    let p = new Array(n).fill(-1);​    for (let i = 0; i < n; i++) {        for (let j = 0; j < i; j++) {            if (input[j] < input[i] && d[i] < d[j] + 1) {                d[i] = d[j] + 1;                p[i] = j;            }        }    }​    let ans = d[0], pos = 0;    for (let i = 1; i < n; i++) {        if (d[i] > ans) {            ans = d[i];            pos = i;        }    }​    while(pos != -1) {        // result_array.push(input[pos]);        indexes.push(pos);        pos = p[pos];    }    // result_array.reverse()    indexes.reverse()​    // console.log(`Longest increasing sequence: ${result_array}`);    console.log(`Longest increasing indexes: ${indexes}`);    for (let i = indexes.length -1; i >= 0; i--) {        input.splice(indexes[i],1);        from_array.splice(indexes[i],1);    }​    return [from_array, input];}​function find_moves_step_one(from_array, to_array) {    for (let i = 0; i < from_array.length; i++) {        for (let j = i+1; j < from_array.length; j++) {            if(from_array[j] >= from_array[i]) {                from_array[j]--;            }        }    }    for (let i = to_array.length - 1; i >= 0; i--) {        for (let j = i-1; j >= 0; j--) {            if(to_array[j] > to_array[i]) {                to_array[j]--;            }        }    }    return [from_array, to_array];}​function find_moves_step_two(from_array, to_array) {    let increase_in_i = 0;    for (let i = 0; i < to_array.length; i++) {        for (let j = to_array.length - 1; j >= i+1; j--) {            if(from_array[j] < to_array[i]) {                increase_in_i++;            } else {                from_array[j]++;            }        }        to_array[i] += increase_in_i;        increase_in_i = 0;    }    return [from_array, to_array];}​function find_target_index(from_array, to_array) {    if(JSON.stringify(from_array) == JSON.stringify(to_array)) {        return [];    } else {        const target_index_arr = Array(from_array.length).fill(0);        let index_found;        from_array.forEach(function(item, index) {            index_found = to_array.indexOf(item);            if(index_found !== -1) {                target_index_arr[index] = index_found;            } else {                //TODO make something dude! its not normal            }        });        return target_index_arr;    }}​function move(array, from_array, to_array) {    let item;    for(let i = 0; i < from_array.length; i++) {        if(from_array[i] > to_array[i]) {            item = array[from_array[i]];            for(let j = from_array[i] - 1; j >= to_array[i]; j--) {                array[j+1] = array[j];            }            array[to_array[i]] = item;        } else if(to_array[i] > from_array[i]) {            item = array[from_array[i]];            for(let j = from_array[i]; j <= to_array[i]; j++) {                array[j] = array[j+1];            }            array[to_array[i]] = item;        }    }    return array;}​const target_index_arr = find_target_index(shuffled_array.slice(0), original_array.slice(0));if(target_index_arr.length > 0) {    console.log(`target index array: ${target_index_arr}`);    const [from_array, to_array] = longest_increasing_subsequence(target_index_arr.slice(0));    const [from_after_step1, to_after_step1] = find_moves_step_one(from_array.slice(0), to_array.slice(0))    const [from_after_step2, to_after_step2] = find_moves_step_two(from_after_step1.slice(0), to_after_step1.slice(0))}

last

function longest_increasing_subsequence (input) {
    const from_array = Array.from(Array(input.length).keys());
    let result_array = [], indexes = [];

    let n = input.length;

    if (n === 0) {
        return [];
    }

    let d = new Array(n).fill(1);
    let p = new Array(n).fill(-1);

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (input[j] < input[i] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1;
                p[i] = j;
            }
        }
    }

    let ans = d[0], pos = 0;
    for (let i = 1; i < n; i++) {
        if (d[i] > ans) {
            ans = d[i];
            pos = i;
        }
    }

    while(pos != -1) {
        // result_array.push(input[pos]);
        indexes.push(pos);
        pos = p[pos];
    }
    // result_array.reverse()
    indexes.reverse()

    // console.log(`Longest increasing sequence: ${result_array}`);
    console.log(`Longest increasing indexes: ${indexes}`);
    for (let i = indexes.length -1; i >= 0; i--) {
        input.splice(indexes[i],1);
        from_array.splice(indexes[i],1);
    }

    return [from_array, input];
}

function find_moves_step_one(from_array, to_array) {
    for (let i = 0; i < from_array.length; i++) {
        for (let j = i+1; j < from_array.length; j++) {
            if(from_array[j] >= from_array[i]) {
                from_array[j]--;
            }
        }
    }
    for (let i = to_array.length - 1; i >= 0; i--) {
        for (let j = i-1; j >= 0; j--) {
            if(to_array[j] > to_array[i]) {
                to_array[j]--;
            }
        }
    }
}

function find_moves_step_two(from_array, to_array) {
    let increase_in_i = 0;
    for (let i = 0; i < to_array.length; i++) {
        for (let j = to_array.length - 1; j >= i+1; j--) {
            if(from_array[j] < to_array[i]) {
                increase_in_i++;
            } else {
                from_array[j]++;
            }
        }
        to_array[i] += increase_in_i;
        increase_in_i = 0;
    }
}

function find_target_index(from_array, to_array) {
    if(JSON.stringify(from_array) == JSON.stringify(to_array)) {
        return [];
    } else {
        const target_index_arr = Array(from_array.length).fill(0);
        let index_found;
        from_array.forEach(function(item, index) {
            index_found = to_array.indexOf(item);
            if(index_found !== -1) {
                target_index_arr[index] = index_found;
            } else {
                //TODO make something dude! its not normal
            }
        });
        return target_index_arr;
    }
}

function move(array, from_array, to_array) {
    let item;
    for(let i = 0; i < from_array.length; i++) {
        if(from_array[i] > to_array[i]) {
            item = array[from_array[i]];
            for(let j = from_array[i] - 1; j >= to_array[i]; j--) {
                array[j+1] = array[j];
            }
            array[to_array[i]] = item;
        } else if(to_array[i] > from_array[i]) {
            item = array[from_array[i]];
            for(let j = from_array[i]; j <= to_array[i]; j++) {
                array[j] = array[j+1];
            }
            array[to_array[i]] = item;
        }
    }
    return array;
}

const target_index_arr = find_target_index(shuffled_array, original_array);
if(target_index_arr.length > 0) {
    const [from_array, to_array] = longest_increasing_subsequence(target_index_arr);
    find_moves_step_one(from_array, to_array)
    find_moves_step_two(from_array, to_array)
}

 
function longest_increasing_subsequence (input) {    const from_array = Array.from(Array(input.length).keys());    let result_array = [], indexes = [];​    let n = input.length;​    if (n === 0) {        return [];    }​    let d = new Array(n).fill(1);    let p = new Array(n).fill(-1);​    for (let i = 0; i < n; i++) {        for (let j = 0; j < i; j++) {            if (input[j] < input[i] && d[i] < d[j] + 1) {                d[i] = d[j] + 1;                p[i] = j;            }        }    }​    let ans = d[0], pos = 0;    for (let i = 1; i < n; i++) {        if (d[i] > ans) {            ans = d[i];            pos = i;        }    }​    while(pos != -1) {        // result_array.push(input[pos]);        indexes.push(pos);        pos = p[pos];    }    // result_array.reverse()    indexes.reverse()​    // console.log(`Longest increasing sequence: ${result_array}`);    console.log(`Longest increasing indexes: ${indexes}`);    for (let i = indexes.length -1; i >= 0; i--) {        input.splice(indexes[i],1);        from_array.splice(indexes[i],1);    }​    return [from_array, input];}​function find_moves_step_one(from_array, to_array) {    for (let i = 0; i < from_array.length; i++) {        for (let j = i+1; j < from_array.length; j++) {            if(from_array[j] >= from_array[i]) {                from_array[j]--;            }        }    }    for (let i = to_array.length - 1; i >= 0; i--) {        for (let j = i-1; j >= 0; j--) {            if(to_array[j] > to_array[i]) {                to_array[j]--;            }        }    }}​function find_moves_step_two(from_array, to_array) {    let increase_in_i = 0;    for (let i = 0; i < to_array.length; i++) {        for (let j = to_array.length - 1; j >= i+1; j--) {            if(from_array[j] < to_array[i]) {                increase_in_i++;            } else {                from_array[j]++;            }        }        to_array[i] += increase_in_i;        increase_in_i = 0;    }}​function find_target_index(from_array, to_array) {    if(JSON.stringify(from_array) == JSON.stringify(to_array)) {        return [];    } else {        const target_index_arr = Array(from_array.length).fill(0);        let index_found;        from_array.forEach(function(item, index) {            index_found = to_array.indexOf(item);            if(index_found !== -1) {                target_index_arr[index] = index_found;            } else {                //TODO make something dude! its not normal            }        });        return target_index_arr;    }}​function move(array, from_array, to_array) {    let item;    for(let i = 0; i < from_array.length; i++) {        if(from_array[i] > to_array[i]) {            item = array[from_array[i]];            for(let j = from_array[i] - 1; j >= to_array[i]; j--) {                array[j+1] = array[j];            }            array[to_array[i]] = item;        } else if(to_array[i] > from_array[i]) {            item = array[from_array[i]];            for(let j = from_array[i]; j <= to_array[i]; j++) {                array[j] = array[j+1];            }            array[to_array[i]] = item;        }    }    return array;}​const target_index_arr = find_target_index(shuffled_array, original_array);if(target_index_arr.length > 0) {    const [from_array, to_array] = longest_increasing_subsequence(target_index_arr);    find_moves_step_one(from_array, to_array)    find_moves_step_two(from_array, to_array)}​

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Experimental features:

Memory measurements supported only in Chrome.
For precise memory measurements Chrome must be launched with --enable-precise-memory-info flag.
More information: Monitoring JavaScript Memory

Test case name	Result
splice
last

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 3 years ago)

User agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/99.0.4844.83 Safari/537.36

Browser/OS: Chrome 99 on Linux

View result in a separate tab

Test name	Executions per second
splice	96.9 Ops/sec
last	108.4 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):

I'll take a deep breath and try to decipher the code.

The provided code appears to be a JavaScript solution for solving a problem related to anagrams, specifically finding the longest increasing subsequence in a set of arrays.

Here's a high-level overview of what I see:

The find_moves_step_one function rearranges the elements in two input arrays (from_array and to_array) by decrementing each element until it's within a certain range (i.e., from 0 to length - 1).
The find_moves_step_two function iterates over the to_array and increments the corresponding elements in from_array based on the differences between the indices of matching elements.
The move function rearranges the elements in a third array (array) by shifting elements left or right to create an increasing subsequence.
The code also includes functions for finding the target index of each element in the sorted arrays, as well as executing the necessary steps based on the results.

However, I don't see any specific problem statement or requirements mentioned in the provided code snippet. Could you please provide more context or information about what this code is intended to solve?

One potential issue I notice is that some functions (e.g., find_target_index, move) seem to be incomplete or missing implementation details. Additionally, there are no tests or assertions to verify the correctness of the functions.

If you could provide more information about the problem and any specific requirements or constraints, I'd be happy to help you better understand the code and provide guidance on how to improve it.

LLMs can make mistakes. Check important info.

I'll take a deep breath and try to decipher the code.

The provided code appears to be a JavaScript solution for solving a problem related to anagrams, specifically finding the longest increasing subsequence in a set of arrays.

Here's a high-level overview of what I see:

1. The `find_moves_step_one` function rearranges the elements in two input arrays (`from_array` and `to_array`) by decrementing each element until it's within a certain range (i.e., from 0 to `length - 1`).
2. The `find_moves_step_two` function iterates over the `to_array` and increments the corresponding elements in `from_array` based on the differences between the indices of matching elements.
3. The `move` function rearranges the elements in a third array (`array`) by shifting elements left or right to create an increasing subsequence.
4. The code also includes functions for finding the target index of each element in the sorted arrays, as well as executing the necessary steps based on the results.

One potential issue I notice is that some functions (e.g., `find_target_index`, `move`) seem to be incomplete or missing implementation details. Additionally, there are no tests or assertions to verify the correctness of the functions.

If you could provide more information about the problem and any specific requirements or constraints, I'd be happy to help you better understand the code and provide guidance on how to improve it.

Related benchmarks:

LIS-test2 (version: 1)

Comparing performance of: splice vs last

Created: 4 years ago by: Registered User

Jump to the latest result