如果代码没有进一步优化，则无法通过质询

Question

我无法通过这个编码挑战:代码挑战:https://www.codewars.com/kata/550f22f4d758534c1100025a/train/javascript

因为我的代码太慢。我不确定我的代码的哪一部分导致了这个问题。这就是为什么我需要帮助来优化它。

function dirReduc(arr){
if (arr.length === 0 || arr.length === 1) return [];
let lengthTracker = arr.length;
for (let i = 0; i < arr.length; i++) { 
if (lengthTracker > arr.length) {
lengthTracker = arr.length;
i = 0;
}
switch(arr[i]) {
case "NORTH":
arr[i-1] === "SOUTH"? arr.splice(i-1,2) : 
arr[i+1] === "SOUTH"? arr.splice(i,2) : null
break;
case "SOUTH":
arr[i-1] === "NORTH"? arr.splice(i-1,2) : 
arr[i+1] === "NORTH"? arr.splice(i,2) : null
break;
case "EAST":
arr[i-1] === "WEST"? arr.splice(i-1,2) : 
arr[i+1] === "WEST"? arr.splice(i,2) : null
break;
case "WEST":
arr[i-1] === "EAST"? arr.splice(i-1,2) : 
arr[i+1] === "EAST"? arr.splice(i,2) : null
break;
}
i===arr.length-1? i=0:null
}
return arr;
}

Answer 1

拼接是很昂贵的。我们可以形成一个递归式，假设函数已经正确地约简了列表的下一部分:

function matches(a, b){
return (a == "NORTH" && b == "SOUTH") ||
(b == "NORTH" && a == "SOUTH") ||
(a == "EAST" && b == "WEST") ||
(b == "EAST" && a == "WEST");
}

function f(A, i=0){
if (i == A.length)
return [];

const rest = f(A, i + 1);
const [head,...tail] = rest;

if (head){
if (matches(A[i], head))
return tail;
else
return [A[i]].concat(rest);
}

return [A[i]];
}

Answer 2

我看到了几个问题。首先，正如我在评论中提到的，拼接长数组是昂贵的，并且使您的算法成为O(n^2)。简单而快速的方法是使用一个读点和一个写点将元素一次一个地复制到自己的单元格中，只是跳过湮灭，然后在最后使用一次splice将未复制的单元格从数组的末端修剪掉。这将使它成为O(n)。

其次，您的代码正在向前和向后寻找匹配，这既不必要又可能令人困惑。最后，不需要switch (...)，因为所有分支都做同样的事情。

以下是我将如何使用您的代码来完成此任务，更改上述内容并在注释中注明。

function dirReduc(arr){
if (arr.length === 0 || arr.length === 1) return [];
let lengthTracker = 0;                  // the write-point
for(let i = 0; i < arr.length; i++) {   // i is the read-point
if(lengthTracker == 0) {
// if no output, copy readpoint to write-point and advance
arr[lengthTracker++] = arr[i];
} else {
// replaces switch()
if (((arr[lengthTracker-1] === "NORTH") && (arr[i] === "SOUTH"))
|| ((arr[lengthTracker-1] === "SOUTH") && (arr[i] === "NORTH"))
|| ((arr[lengthTracker-1] === "EAST") && (arr[i] === "WEST"))
|| ((arr[lengthTracker-1] === "WEST") && (arr[i] === "EAST"))) {
lengthTracker--;    // annihilate by decrementing the writepoint
} else {
// copy readpoint to writepoint and advance
arr[lengthTracker++] = arr[i];
}
}
}
//trim the array to only include what was written
arr.splice(lengthTracker);
return arr;
}