在JavaScript中在数组中查找连续子数组的优雅方法? [英] Elegant way to find contiguous subarray within an array in JavaScript?

问题描述

我想编写一个函数，从给定的起始索引中查找给定数组中的连续子数组，如果找到，则返回该数组中子数组的索引；如果未找到，则返回-1.这与String.indexOf相似，但是用于数组和子数组而不是字符串和子字符串.

这是我的工作代码:

var find_csa = function (arr, subarr, from_index) {
    if (typeof from_index === 'undefined') {
        from_index = 0;
    }

    var i, found, j;
    for (i = from_index; i < 1 + (arr.length - subarr.length); ++i) {
        found = true;
        for (j = 0; j < subarr.length; ++j) {
            if (arr[i + j] !== subarr[j]) {
                found = false;
                break;
            }
        }
        if (found) return i;
    }
    return -1;
};

这些是我的测试及其期望值:

console.log(find_csa([1, 2, 3, 4, 5], [2, 3, 4]) === 1);
console.log(find_csa([1, 2, 3, 4, 5], [5]) === 4);
console.log(find_csa([1, 2, 3, 4, 5], [1, 3]) === -1);
console.log(find_csa([1, 2, 3, 4, 5], [42]) === -1);
console.log(find_csa([1, 2, 3, 4, 5], []) === 0);
console.log(find_csa([3, 4, 3, 4, 3, 4], [3, 4, 3], 1) === 2);
console.log(find_csa([6, 6, 6, 7], [6, 6, 7]) === 1);
console.log(find_csa([12, 9, 16, 42, 7, 866, 3], [16, 42, 7, 866]) === 2);

我的代码通过了测试，但是正如您所看到的，它在内部循环中使用了布尔值found，这只是我从嵌套循环中继续进行外部循环的一种凌乱的即席方式.有没有更干净的书写方式?我查看了 Array.prototype.findIndex ，但是目前，这是一项实验性技术，因此我无法使用.我想要一种适用于大多数浏览器的方法.我知道在Mozilla页面上有一个"polyfill"代码段，但是比我当前的代码还要长，并且由于函数调用会变慢，所以我宁愿避免使用它.

我对该功能的主要目标是 performance (子数组非常小，因此我相信使用尝试是一点点矫kill过正)，然后我的次要目标是实现的优雅.考虑到这两个目标，我想知道是否有更好的方式编写此代码，或者是否缺少任何JavaScript功能，可以帮助我避免使用found布尔值.

JSFiddle是否对任何人有帮助: http://jsfiddle.net/qc4zxq2p/

解决方案

我是否缺少任何JavaScript功能，可以帮助我避免使用found布尔值

是的，您可以在外循环上使用标签 :

function find_csa(arr, subarr, from_index) {
    var i = from_index >>> 0,
        sl = subarr.length,
        l = arr.length + 1 - sl;

    loop: for (; i<l; i++) {
        for (var j=0; j<sl; j++)
            if (arr[i+j] !== subarr[j])
                continue loop;
        return i;
    }
    return -1;
}

I wanted to write a function to find a contiguous subarray within a given array from a given starting index and return the index of the subarray within the array if it's found, and -1 if it's not found. This is similar to String.indexOf, but for arrays and subarrays instead of strings and substrings.

This is my working code:

var find_csa = function (arr, subarr, from_index) {
    if (typeof from_index === 'undefined') {
        from_index = 0;
    }

    var i, found, j;
    for (i = from_index; i < 1 + (arr.length - subarr.length); ++i) {
        found = true;
        for (j = 0; j < subarr.length; ++j) {
            if (arr[i + j] !== subarr[j]) {
                found = false;
                break;
            }
        }
        if (found) return i;
    }
    return -1;
};

And these are my tests and their expected values:

console.log(find_csa([1, 2, 3, 4, 5], [2, 3, 4]) === 1);
console.log(find_csa([1, 2, 3, 4, 5], [5]) === 4);
console.log(find_csa([1, 2, 3, 4, 5], [1, 3]) === -1);
console.log(find_csa([1, 2, 3, 4, 5], [42]) === -1);
console.log(find_csa([1, 2, 3, 4, 5], []) === 0);
console.log(find_csa([3, 4, 3, 4, 3, 4], [3, 4, 3], 1) === 2);
console.log(find_csa([6, 6, 6, 7], [6, 6, 7]) === 1);
console.log(find_csa([12, 9, 16, 42, 7, 866, 3], [16, 42, 7, 866]) === 2);

My code passes the tests, but as you can see, it uses a boolean value found in the inner loop which is just my messy, ad-hoc way of continuing an outer loop from a nested loop. is there a cleaner way of writing it? I looked into Array.prototype.findIndex but it is an experimental technology at the moment so I can't use it. I want a method that works in most browsers. I know there is a "polyfill" code snippet written on the Mozilla page, but that is even longer than my current code and it will be slower due to the function calls, so I'd rather avoid it.

My primary goal for this function is performance (the subarrays will be very small, so I believe that using Boyer-Moore string search algorithm or tries is a tad overkill), and then my secondary goal is elegance of my implementation. With those two goals in mind, I would like to know if there is a better way of writing this code, or if there are any JavaScript features or functions that I'm missing that could help me avoid the found boolean.

JSFiddle if it helps anyone: http://jsfiddle.net/qc4zxq2p/

解决方案

Are there any JavaScript features or functions that I'm missing that could help me avoid the found boolean

Yes, you can use a label on your outer loop:

function find_csa(arr, subarr, from_index) {
    var i = from_index >>> 0,
        sl = subarr.length,
        l = arr.length + 1 - sl;

    loop: for (; i<l; i++) {
        for (var j=0; j<sl; j++)
            if (arr[i+j] !== subarr[j])
                continue loop;
        return i;
    }
    return -1;
}

这篇关于在JavaScript中在数组中查找连续子数组的优雅方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！