javascript - 是否有一种搜索算法可以一直搜索有序列表，直到所有值都相等？

Question

我在 JavaScript 中有一个带有四个键的对象。每个键都存储一个包含值的数组。它看起来像这样:

{
  one: [...],
  two: [...],
  three: [...],
  four: [...]
}

假设数组中的每个元素都是“Test”类的一个对象，它有一个名为“complete”的 bool 键。

如果我选择从数组三开始，我需要找到第一次出现的 Test.complete 等于 true。如果在数组三中发现该事件，假设我从该对象返回该值/其他一些值。如果该事件不在数组三中，则我需要遍历四、一和二(按此顺序)。如果我从 2 开始，然后循环遍历 2、3、4 和 1(按此顺序)。

假设页面上有一个按钮将此 complete 值切换为 true，在某些时候将不再有 false 剩下的值，这就是我想停止循环遍历这些测试对象数组的地方。

我知道我可以使用 Object.keys(obj) 来访问键，并且可能有一个返回顺序的函数 ['one', 'two', 'three' , 'four'] 我需要根据起始数组进行循环。

是否存在我可以直接使用或针对此用例轻松修改的现有搜索算法？我有一个使用递归的实现，但它不会一直循环并一直循环直到所有 Test.complete 值都为 true。

Answer 1

要事第一。在数据结构看起来像您想要的那样之前，您不能让循环阻塞执行。无论循环多少次，单个函数调用总是会看到相同的对象。您需要做的是等待下一次报价，然后再次调用该函数，例如使用 setTimeout。这也意味着要等待您的函数完成，您需要使用回调或 promise ，而不是 return。

这是行不通的:

function waitLoop(obj) {
   while (notDone) {
      ...
   }
   return;
}
waitLoop(myObj); // Blocks until done

相反，您需要采用以下方法:

var obj = ...;
function waitLoop(callback) { // Note that callback is a function!
   ...
   if (notDone) {
       setTimeout(function () {
           waitLoop(callback);
       }, 0); // setTimeout(..., 0) waits until the next tick
   } else {
       callback();
   }
}

waitLoop(function () {
    // Do something here when waitLoop is done
});

这是 Javascript 中异步执行的基础知识。您还可以阅读 promises，这是一个类似的概念，但界面略有不同。

关于你的问题。看起来你想继续返回第一个找到的值，然后继续循环。这意味着您需要有一个可以在每次迭代中调用的回调，并返回一个值或返回它已完成循环。你应该这样做:

var obj = ...;
function waitUntilComplete(callback) {
    let keyOrder = ['three', 'four', 'one', 'two'];
    for (let k = 0; k < keyOrder.length; k++) {
        let a = obj[keyOrder[k]];
        for (let k = 0; k < a.length; k++) {
            let testResult = Test.complete(a[k]));
            if (testResult) {
                // Send back the value and end execution
                callback(false, a[k]);
                setTimeout(function (){
                    waitUntilComplete(callback);
                }, 0);
                return;
            }
        }
    }

    // Complete!
    callback(true, null);
}

waitUntilComplete(function (done, returnValue) {
    if (!done) {
        // Do what you want with returnValue
    } else {
        // Done, Test.complete returns false for all values!
    }
});

还有一件事需要解释:tick。但是，让我们回到基础。 Javascript 是单线程的，有一个事件队列。队列开始为空。有时会发生事件:您单击具有事件处理程序的按钮、setTimeout 触发或您的文档完成加载。在这些情况下，事件被推送到事件队列中。您可以将“事件”视为一个函数。毕竟，您将事件处理程序注册为函数。该函数被推送到队列中。然后呢？没有什么。它只是坐在队列中。运行时会不时醒来并开始循环遍历事件队列，按顺序调用所有函数。这就是我们所说的 tick。

这应该可以帮助您理解为什么您不能拥有在等待某些外部事件时阻塞的函数。因为所有事件——按钮点击、超时等——都被推送到队列中。但是在当前函数返回之前，运行时不会调用队列中的下一个函数!阻止功能会阻止其他一切发生。

这就是为什么我们使用回调以及为什么我使用 setTimeout 来安排下一个循环。上面的 waitUntilComplete 将遍历所有数组一次，然后它将安排在下一个 tick 中进行新的调用。这让所有其他排队的事件发生，以便 obj 有机会在循环之间更新。