这种O(N)方法是在Javascript中遍历这个链表时避免while循环的唯一方法吗？

r3i60tvu 于 2023-01-29 发布在 Java

关注(0)|答案(2)|浏览(110)

我有一个数据结构，本质上是一个存储在状态中的链表。它代表了一个基本对象的更改流（补丁）。它是通过键链接的，而不是通过对象引用链接的，以允许我简单地串行化和反串行化状态。
它看起来像这样：

const latest = 'id4' // They're actually UUIDs, so I can't sort on them (text here for clarity)
const changes = {
  id4: {patch: {}, previous: 'id3'},
  id3: {patch: {}, previous: 'id2'},
  id2: {patch: {}, previous: 'id1'},
  id1: {patch: {}, previous: undefined},
}

有时候，用户选择运行一个开销很大的计算，结果会返回到状态。我们没有对应于每个更改的结果，而只有部分更改的结果。因此，结果可能如下所示：

const results = {
  id3: {performance: 83.6},
  id1: {performance: 49.6},
}

给定changes数组，我需要得到与changes列表顶端 * 最接近 * 的结果，在本例中是results.id3。
我写了一个while循环来完成这个任务，目前它非常健壮：

let id = latest
    let referenceId = undefined
    while (!!id) {
      if (!!results[id]) {
        referenceId = id
        id = undefined
      } else {
        id = changes[id].previous
      }
    }

这个方法是O（N）的，但这是病态的情况：我希望有一个很长的更改列表，但是结果更新相当频繁，这样您只需后退几步就可以找到匹配的结果。

While循环容易受到攻击

遵循Gene Krantz的伟大工作（阅读他的书"Failure is not an option"，了解为什么NASA从不使用递归!），我尽量避免在代码库中使用while循环：他们往往容易犯无心的错误。
例如，在这里，创建一个无限循环所需的全部操作就是执行delete changes.id1。
因此，我希望避免这个漏洞，而不是无法检索任何结果，因为不返回性能值是可以处理的;但用户的应用挂起真的很糟糕!

我尝试过的其他方法

复杂度O（N）
为了避免while循环，我考虑将changes对象排序到一个按链表排序的数组中，然后简单地循环通过它。
问题是我必须先遍历整个变更列表，才能得到排序后的数组，因为我没有存储排序键（这会违反链表的点，因为你不能再做O（1）插入）。
这不是一个繁重的操作，把一个id推到一个数组上，但仍然是O（N）。

这个问题

有没有一种方法可以不使用while循环，也不使用O（N）方法将链表转换为普通数组，就可以遍历这个链表？

JavaScript

来源：https://stackoverflow.com/questions/75246230/is-this-on-approach-the-only-way-of-avoiding-a-while-loop-when-walking-this-li

2条答案

按热度按时间

h7appiyu1#

由于您只需要在末尾追加，并且可能从末尾删除，因此所需的结构是 stack。在JavaScript中，实现堆栈的最佳数据结构是数组--使用它的push和pop特性。
所以你可以这样做：

const changes = []; 

function addChange(id, patch) {
    changes.push({id, patch});
}

function findRecentMatch(changes, constraints) {
    for (let i = changes.length - 1; i >= 0; i--) {
        const {id} = changes[i];
        if (constraints[id]) return id;
    }
}

// Demo
addChange("id1", { data: 10 });
addChange("id2", { data: 20 });
addChange("id3", { data: 30 });
addChange("id4", { data: 40 });

const results = {
  id3: {performance: 83.6},
  id1: {performance: 49.6},
}

const referenceId = findRecentMatch(changes, results);
console.log(referenceId);  // id3

根据您对referenceId的处理方式，您可能希望findRecentMatch返回changes中的 index 而不是change-id本身，这使您仍然可以检索id，但也可以裁剪changes列表以在该“版本”处结束（就好像你弹出了到那个点的所有条目，但随后在一个操作中）。

赞(0）回复(0）举报 2023-01-29

vmdwslir2#

在写出这个问题的时候，我意识到，与其完全避免while循环，不如添加一个执行计数和一个转义窗口，这样就足够了。
这个解决方案使用Object.keys()，它是严格O（N）的，所以 * 技术上 * 不是问题的正确答案-但它非常快。
如果我需要更快的速度，我可以将changes重构为map而不是一般对象，然后访问changes.sizex 1 e1f1x

let id = latest
    let referenceId = undefined
    const maxLoops = Object.keys(changes).length
    let loop = 0
    while (!!id && loop < maxLoops) {
      loop++
      if (!!results[id]) {
        referenceId = id
        id = undefined
      } else {
        id = changes[id].previous
      }
    }

赞(0）回复(0）举报 2023-01-29

我来回答

这种O(N)方法是在Javascript中遍历这个链表时避免while循环的唯一方法吗？

While循环容易受到攻击

我尝试过的其他方法

这个问题

2条答案

相关问题

热门标签

最新问答