关于'Bug-O'表示法

Posted on | Edited on | In , |

当你在编写对性能敏感的代码时，最好记住他的算法复杂性。它通常表达用 Big-O 表示法表示。

Big-O 衡量代码在向其投入更多数据时会变慢多少。例如，如果一个排序算法具有 O(n2) 的复杂度，则排序 ×50 倍以上的项目大致将变慢 502 = 2,500 倍。Big O 不会给你一个确切的数字，但它可以帮助你理解算法如何拓展。

一些例子：O(n), O(n log n), O(n2), O(n!)。

但是, 这篇文章与算法或性能无关，它主要描述关于 API 和调试的。事实证明，API 设计涉及一些考虑因素非常类似。

我们大部分时间都用于查找和修复代码中的错误。大多数开发人员希望能够更快的发现错误。尽管最终可能是个令人满意的结果，但是如果你已经实施了开发路线中的某些内容，那么花费整天的时间来追逐单个的错误会很糟糕。

调式经验会影响我们对抽象、库和工具的选择。一些 API 和语言设计使得错误变得不可能。有些则会导致错误无穷无尽，但是该如何分辨呢？

关于 API 的许多在线讨论主要关注美学，却没有谈到很多在实际项目中使用 API 的感觉。

我有一个指标可以帮助我思考这个问题。我管它叫 Bug-O 表示法：

🐞(n)

Big-O描述了随着输入的增长，算法慢了多少，也描述了随着代码库的增长，API 速度慢了多少。

例如，思考以下代码，它会随着时间的推移使用node.appendChild()，node.removeChild()手动更新 DOM，且不会指明具体的结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function trySubmit() {
  // Section 1
  let spinner = createSpinner();
  formStatus.appendChild(spinner);
  submitForm()
    .then(() => {
      // Section 2
      formStatus.removeChild(spinner);
      let successMessage = createSuccessMessage();
      formStatus.appendChild(successMessage);
    })
    .catch((error) => {
      // Section 3
      formStatus.removeChild(spinner);
      let errorMessage = createErrorMessage(error);
      let retryButton = createRetryButton();
      formStatus.appendChild(errorMessage);
      formStatus.appendChild(retryButton);
      retryButton.addEventListener('click', function() {
        // Section 4
        formStatus.removeChild(errorMessage);
        formStatus.removeChild(retryButton);
        trySubmit();
      });
    });
}

这段代码的问题并非它“很丑”，我们也不是在讨论着是否符合美学。问题是，如果代码中存在问题，我该从何开始排查。

根据回调和事件触发的顺序，程序中可能采用的代码路径组合数量可能会爆炸。某些情况下，可能会展示正确匹配的信息。但也可能看到多个提示，故障和错误信息同时存在，更有可能崩溃。

此功能有 4 个不同的部分，且顺序也不固定。粗略估算他们可能有 4×3×2×1 = 24 种不同顺序的运行方式。如果我在添加四个代码段，他将是 8×7×6×5×4×3×2×1——四万种组合。如果尝试调试，那么祝你好运。

换句话说，Bug-O 这种表示法就是 🐞(n!)，其中n是触及 DOM 的代码段的数量。是的，这会是一个因素，尽管我在这里使用的方法不太科学。在实践中并非所有转换都是可能的，但这些戏份中的每一个都可能运行多次。🐞(¯(ツ)/¯)这样做可能会更准确，但它任很糟糕。我们应该做的更好。

为了改进代码中的 Bug-O，我们可以限制可能的状态和结果的数量。我们不需要任何库来执行此操作，这只是在我们的代码上强制执行某些结构可以解决的。以下就是其中的一种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
let currentState = {
  step: 'initial', // 'initial' | 'pending' | 'success' | 'error'
};

function trySubmit() {
  if (currentState.step === 'pending') {
    // Don't allow to submit twice
    return;
  }
  setState({ step: 'pending' });
  submitForm
    .then(() => {
      setState({ step: 'success' });
    })
    .catch((error) => {
      setState({ step: 'error', error });
    });
}

function setState(nextState) {
  // Clear all existing children
  formStatus.innerHTML = '';

  currentState = nextState;
  switch (nextState.step) {
    case 'initial':
      break;
    case 'pending':
      formStatus.appendChild(spinner);
      break;
    case 'success':
      let successMessage = createSuccessMessage();
      formStatus.appendChild(successMessage);
      break;
    case 'error':
      let errorMessage = createErrorMessage(nextState.error);
      let retryButton = createRetryButton();
      formStatus.appendChild(errorMessage);
      formStatus.appendChild(retryButton);
      retryButton.addEventListener('click', trySubmit);
      break;
  }
}

这样代码可能会看起来不太一样，甚至显得有些冗长。但这个思路下，调试会非常简单：

1
2
3
4
function setState(nextState) {
  // Clear all existing children
  formStatus.innerHTML = '';
  // ... the code adding stuff to formStatus ...

通过在执行任何操作之前清除表单状态来保证我们的 DOM 操作始终从头开始。这就是我们如何对抗不可避免的熵（entropy） — 拒绝让错误堆积。这就相当于“关闭再打开”编码，它的效果非常的好。

如果在输出中出现错误，我们只需要考虑一个退一步——上一次 setState 的调用。调试渲染结果的 Bug-O 是 🐞(n)，其中n是渲染代码路径的数量。这里只有四个（因为我们在switch中只有四个case）。

我们在设置状态时，任然存在竞争条件，但调试它们会更容易，因为我们可以记录检查每个中间状态。我们还可以明确禁止任何不需要的转换：

1
2
3
4
5
function trySubmit() {
  if (currentState.step === 'pending') {
    // Don't allow to submit twice
    return;
  }

当然，总是要权衡重置 DOM 是必要的。每次都要过分删除或重建 DOM 会破坏其内部状态，失去焦点，并在较大的应用程序中导致可怕的性能问题。

这也是为什么像是 React 这样的库会很有帮助。因为它们总是让你在开始重建 UI 的范例中思考，而不必这么做：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
function FormStatus() {
  let [state, setState] = useState({
    step: 'initial',
  });

  function handleSubmit(e) {
    e.preventDefault();
    if (state.step === 'pending') {
      // Don't allow to submit twice
      return;
    }
    setState({ step: 'pending' });
    submitForm
      .then(() => {
        setState({ step: 'success' });
      })
      .catch((error) => {
        setState({ step: 'error', error });
      });
  }

  let content;
  switch (state.step) {
    case 'pending':
      content = <Spinner />;
      break;
    case 'success':
      content = <SuccessMessage />;
      break;
    case 'error':
      content = (
        <>
          <ErrorMessage error={state.error} />
          <RetryButton onClick={handleSubmit} />
        </>
      );
      break;
  }

  return <form onSubmit={handleSubmit}>{content}</form>;
}

代码可能会有区别，但原理是相同的。组件抽象强制执行边界，会让你知道页面上是否有其他代码可以混淆其 DOM 或状态。
组件化有利于减少 Bug-O。

事实上，如果任何值在 React app 中看起来不对，你都可以通过在 React 树中逐一查看其上方组件的代码来追踪来源。无论应用程序大小，追踪到的渲染值是 🐞(树的层级)。

**下次你看到关于 API 的讨论时，想想在常见的调试任务中 🐞(n)是怎样的？**现在的那些 API 和原则中，你熟悉的那些如何呢？Redux，CSS，inheritance——它们都有自己的 Bug-O。

原文链接： The “Bug-O” Notation