Run results for: LIS-test2

Run details:

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

Browser: Chrome 99

Operating system: Linux

Device Platform: Desktop

Date tested: 2 years ago

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

HTML Preparation code:

<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));

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)) }
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) }

splice

last