Elegante Möglichkeit, zusammenhängendes Subarray innerhalb eines Arrays in JavaScript zu finden?

Question

Ich wollte eine Funktion schreiben, um ein zusammenhängendes Subarray innerhalb eines gegebenen Arrays von einem gegebenen Startindex zu finden und den Index des Subarrays innerhalb des Arrays zurückzugeben, wenn es gefunden wird, und -1, wenn es nicht gefunden wird. Dies ist vergleichbar mit String.indexOf, aber für Arrays und Subarrays anstelle von Strings und Substrings.

Das ist mein Arbeitscode:

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

Und das sind meine Tests und ihre erwarteten Werte:

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

Mein Code die Tests besteht, aber wie Sie sehen können, verwendet es einen boolean Wert found in der inneren Schleife, die nur meine unordentliche, Ad-hoc-Möglichkeit der Fortsetzung einer äußeren Schleife aus einer verschachtelten Schleife ist. Gibt es eine sauberere Art, es zu schreiben? Ich schaute in Array.prototype.findIndex, aber es ist eine experimentelle Technologie im Moment, so dass ich es nicht verwenden kann. Ich möchte eine Methode, die in den meisten Browsern funktioniert. Ich weiß, dass auf der Mozilla-Seite ein "Polyfill" -Code-Snippet geschrieben ist, aber das ist sogar länger als mein aktueller Code und wird aufgrund der Funktionsaufrufe langsamer sein, also würde ich es lieber vermeiden.

Mein primäres Ziel für diese Funktion ist Leistung (der Sub-Arrays sehr klein sein, so dass ich glaube, dass Boyer-Moore string search algorithm oder tries mit einem bisschen übertrieben ist), und dann mein zweites Ziel ist Eleganz meiner Umsetzung. Mit diesen zwei Zielen möchte ich wissen, ob es eine bessere Möglichkeit gibt, diesen Code zu schreiben, oder ob es irgendwelche JavaScript-Funktionen oder -Funktionen gibt, die mir fehlen, die mir helfen könnten, den booleschen Wert zu vermeiden.

JSFiddle, wenn es hilft jemand: http://jsfiddle.net/qc4zxq2p/

Answer 1

es irgendwelche JavaScript oder Funktionen verfügt dass ich fehle, dass mir helfen, die found boolean

Ja vermeiden konnte, können Sie eineverwenden 210 auf der äußeren Schleife:

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

Answer 2

Dies ist die gleiche wie Sie ist, verniedlicht nur ein bisschen (zumindest meiner Ästhetik):

var find_csa = function (arr, subarr, from_index) { 
    from_index = from_index || 0; 

    var i, found, j; 
    var last_check_index = arr.length - subarr.length; 
    var subarr_length = subarr.length; 

    position_loop: 
    for (i = from_index; i <= last_check_index; ++i) { 
     for (j = 0; j < subarr_length; ++j) { 
      if (arr[i + j] !== subarr[j]) { 
       continue position_loop; 
      } 
     } 
     return i; 
    } 
    return -1; 
}; 

Answer 3

Die innere Schleife auf eine einzige Zeile reduziert werden kann every das Array-Methode:

if(subarr.every(function(e, j) { return (e === arr[i + j]); }) 
    return i; 

oder (ES6 Vorschlag):

if(subarr.every((e, j) => (e === arr[i + j]))) 
    return i; 

Aber Dies kann nur ein Kuriosum oder ein Bildungsbeispiel sein, es sei denn, Sie interessieren sich nicht für die Leistung.

Answer 4

Innerhalb der Schleife können Sie die found Variable beseitigen und vermeiden so weitermachen:

for (j = 0; j < subarr.length; ++j) { 
    if (arr[i + j] !== subarr[j]) break; 
} 
/* 
* the above loop breaks in two cases: 
* normally: j === subarr.length 
* prematurely: array items did not match 
* we are interested in kowing if loop terminated normally 
*/ 
if (j === subarr.length) return i; 

---

gesagt haben, dass hier meine Lösung mit Array.join und String.indexOf ist.Das ist nur gut für die Reihe von Zahlen:

function find_csa(arr, subarr, from_index) { 
    from_index |= 0; 
    if (subarr.length === 0) { 
     return from_index; 
    } 
    var haystack = "," + arr.slice(from_index).join(",") + ",", 
     needle = "," + subarr.join(",") + ",", 
     pos = haystack.indexOf(needle); 
    if (pos > 0) { 
     pos = haystack.substring(1, pos).split(",").length + from_index; 
    } 
    return pos; 
} 
console.log("All tests should return true"); 
console.log(find_csa([1, 2, 3, 4, 5], [1, 2, 3]) === 0); 
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], [6]) === -1); 
console.log(find_csa([1, 2, 3, 4, 5], [1, 3]) === -1); 
console.log(find_csa([6, 6, 6, 7], [6, 6, 7]) === 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([1, 2, 3, 4, 5], [], 1) === 1); 

Answer 5

Lese erste Diskussion auf Basis von zerkms Satz, ich war daran interessiert, eine Lösung zu versuchen JSON.stringify verwenden, trotz der ungünstigen Meinungen.

Dann habe ich endlich eine Lösung, die alle Tests richtig besteht.
Wahrscheinlich nicht die schnellere Methode, aber sicher die kürzeste:

var find_csa = function (arr, subarr, from_index) { 
    var start=from_index|0, 
     needle=JSON.stringify(subarr), 
     matches=JSON.stringify(arr.slice(start)). 
     match(new RegExp('^\\[(.*?),?'+ 
     needle.substr(1,needle.length-2).replace(/([\[\]])/g,'\\$1') 
    )); 
    return !!matches?(matches[1].length?matches[1].split(',').length:0)+start:-1; 
} 

Der obige Code akzeptiert Arrays von Arrays, wie Shashank vorgeschlagen, doch irgendwie Elemente enthalten Kommas zu verarbeiten.

Also habe ich eine andere Lösung entwickelt, die auch Kommas akzeptiert (Danke an Steven Levithan für die elegant tip über while(str!=(str=str.replace(regexp,replacement)));).

Aber es ist nur zum Spaß, da:

• der Code ist nicht so kurz, jetzt ... Seufz!
• es verbraucht wahrscheinlich viele CPU-Zeit
• es nicht richtig mit leeren Elementen funktioniert (sie werden ignoriert)
• Ich vermute (und nicht tiefer zu graben habe :-) es mit komplexen Objekten scheitern könnte als
Artikel

Wie auch immer, hier ist es:

var find_csa = function (arr, subarr, from_index) { 
    var start=from_index|0, 
     commas=new RegExp('(?:(\')([^,\']+),([^\']+)\'|(")([^,"]+),([^"]+))"'), 
     strip_commas='$1$2$3$1$4$5$6$4', 
     haystack=JSON.stringify(arr.slice(start)), 
     needle=JSON.stringify(subarr).replace(/^\[(.*)\]$/,'$1'); 
    while(haystack!=(haystack=haystack.replace(commas,strip_commas))); 
    while(needle!=(needle=needle.replace(commas,strip_commas))); 
    matches=haystack.match(new RegExp('^\\[(.*?),?'+needle.replace(/([\[\]])/g,'\\$1'))); 
    return !!matches?(matches[1].length?matches[1].split(',').length:0)+start:-1; 
}