算法复杂性“Bug-O”表示法 — Overreacted
栏目: JavaScript · 发布时间: 5年前
内容简介：在编写对性能敏感的代码时，最好记住它的算法复杂性。它通常用Big-O衡量代码在向其投入更多数据时会变慢多少。例如，如果排序算法具有O（一些例子：O（
在编写对性能敏感的代码时，最好记住它的算法复杂性。它通常用 Big-O表示法表示 。
Big-O衡量代码在向其投入更多数据时会变慢多少。例如，如果 排序 算法具有O（ n 2 ）复杂度，则排序×50倍以上的项目将大约为50 2 =慢2,500倍。Big O不会给你一个确切的数字，但它可以帮助你理解算法如何扩展。
一些例子：O（ n ），O（ n log n ），O（ n 2 ），O（ n！ ）。
但是，这篇文章与算法或性能无关。它是关于API和调试的。事实证明，API设计涉及非常类似的考虑因素。
我们的大部分时间都用于查找和修复代码中的错误。大多数开发人员希望更快地发现错误。尽管最终可能令人满意，但是如果您已经实施了路线图中的某些内容，那么花费一整天时间来追逐单个错误是很糟糕的。
调试经验会影响我们对抽象，库和 工具 的选择。一些API和语言设计使得错误变得不可能。有些则会产生无穷无尽错误，如何分辨？
我有一个指标可以帮助我思考这个问题。我把它称为 Bug-O 表示法。
Big-O描述了随着输入增长，算法减慢了多少。Bug-O描述了随着你的代码的增长，API让你减缓多少。
例如，考虑一下这个代码，它会随着时间的推移使用node.appendChild()，node.removeChild()手动更新DOM，且这两个函数没有明确的结构：
function trySubmit() {
<font><i>// Section 1</i></font><font>
let spinner = createSpinner();
formStatus.appendChild(spinner);
submitForm().then(() => {
</font><font><i>// Section 2</i></font><font>
formStatus.removeChild(spinner);
let successMessage = createSuccessMessage();
formStatus.appendChild(successMessage);
}).<b>catch</b>(error => {
</font><font><i>// Section 3</i></font><font>
formStatus.removeChild(spinner);
let errorMessage = createErrorMessage(error);
let retryButton = createRetryButton();
formStatus.appendChild(errorMessage);
formStatus.appendChild(retryButton)
retryButton.addEventListener('click', function() {
</font><font><i>// Section 4</i></font><font>
formStatus.removeChild(errorMessage);
formStatus.removeChild(retryButton);
trySubmit();
});
})
}
</font>
这段代码的问题并不在于它“丑陋”。我们不是在谈论美学。问题是，如果此代码中存在错误，我不知道从哪里开始查找。
根据回调和事件触发的顺序，该程序可能采用的代码路径数量会出现组合爆炸。在其中一些中，我会看到正确的信息。在其他情况下，我会看到多个微调器，故障和错误消息，并可能崩溃。
此功能有4个不同的部分，不保证其顺序。我的非科学计算告诉我，他们可以运行4×3×2×1 = 24个不同的顺序。如果我再添加四个代码段，它将是8×7×6×5×4×3×2×1 - 四万组合。祝你好运调试。
换句话说，这种方法的Bug-O是BUg（ n！ ），其中n是触及DOM的代码段的数量。是的，这是一个因素。当然，我在这里并不是很科学。在实践中并非所有转换都是可能的。但另一方面，这些细分中的每一个都可以运行多次。
为了改进此代码的Bug-O，我们可以限制可能的状态和结果的数量。我们不需要任何库来执行此操作。这只是在我们的代码上强制执行某些结构的问题。这是我们可以做到的一种方式：
let currentState = {
step: 'initial', <font><i>// 'initial' | 'pending' | 'success' | 'error'</i></font><font>
};
function trySubmit() {
<b>if</b> (currentState.step === 'pending') {
</font><font><i>// Don't allow to submit twice</i></font><font>
<b>return</b>;
}
setState({ step: 'pending' });
submitForm.then(() => {
setState({ step: 'success' });
}).<b>catch</b>(error => {
setState({ step: 'error', error });
});
}
function setState(nextState) {
</font><font><i>// Clear all existing children</i></font><font>
formStatus.innerHTML = '';
currentState = nextState;
<b>switch</b> (nextState.step) {
<b>case</b> 'initial':
<b>break</b>;
<b>case</b> 'pending':
formStatus.appendChild(spinner);
<b>break</b>;
<b>case</b> 'success':
let successMessage = createSuccessMessage();
formStatus.appendChild(successMessage);
<b>break</b>;
<b>case</b> 'error':
let errorMessage = createErrorMessage(nextState.error);
let retryButton = createRetryButton();
formStatus.appendChild(errorMessage);
formStatus.appendChild(retryButton);
retryButton.addEventListener('click', trySubmit);
<b>break</b>;
}
}
</font>
此代码可能看起来不太相似。它甚至有点冗长。但由于这个思路，调试起来非常简单：
function setState(nextState) {
<font><i>// Clear all existing children</i></font><font>
formStatus.innerHTML = '';
</font><font><i>// ... the code adding stuff to formStatus ...</i></font><font>
</font>
通过在执行任何操作之前清除表单状态，我们确保我们的DOM操作始终从头开始。这就是我们如何对抗不可避免的 熵 - 不要让错误累积起来。这是相当于“关闭再打开”的编码，它的效果非常好。
如果在输出中出现错误，我们只需要考虑一个退一步-以前的setState电话。调试渲染结果的Bug-O是Bug（n），其中n是渲染代码路径的数量。这里只有四个（因为我们在a中有四个案例switch）。
我们在设置状态时可能仍然存在竞争条件，但调试它们更容易，因为可以记录和检查每个中间状态。我们还可以明确禁止任何不需要的转换：
当然，总是重置DOM需要权衡。每次都过分删除和重新创建DOM会破坏其内部状态，失去焦点，并在较大的应用程序中导致可怕的性能问题。
这就是像React这样的库包可以提供帮助的原因。它们让您在总是从头开始重新创建UI的范例中思考，而不必这样做：
function FormStatus() {
let [state, setState] = useState({
step: 'initial'
});
function handleSubmit(e) {
e.preventDefault();
<b>if</b> (state.step === 'pending') {
<font><i>// Don't allow to submit twice</i></font><font>
<b>return</b>;
}
setState({ step: 'pending' });
submitForm.then(() => {
setState({ step: 'success' });
}).<b>catch</b>(error => {
setState({ step: 'error', error });
});
}
let content;
<b>switch</b> (state.step) {
<b>case</b> 'pending':
content = <Spinner />;
<b>break</b>;
<b>case</b> 'success':
content = <SuccessMessage />;
<b>break</b>;
<b>case</b> 'error':
content = (
<>
<ErrorMessage error={state.error} />
<RetryButton onClick={handleSubmit} />
</>
);
<b>break</b>;
}
<b>return</b> (
<form onSubmit={handleSubmit}>
{content}
</form>
);
}
</font>
代码可能看起来不同，但原理是相同的。组件抽象强制执行边界，以便您知道页面上没有其他代码可以混淆其DOM或状态。组件化有助于减少Bug-O。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
