アルゴリズム設計の基礎をより深く理解する-jsチュートリアル-php.cn

アルゴリズム設計の基礎をより深く理解する

王林

リリース： 2023-08-31 17:09:02

オリジナル

1189 人が閲覧しました

アルゴリズム設計の基礎をより深く理解する

この記事では、アルゴリズム設計の原則について詳しく説明します。私が何を言っているのか分からない場合は、読み続けてください。

「アルゴリズム」という言葉を聞くと、次の 3 つのうちのいずれかで反応するかもしれません:

あなたはコンピューターサイエンスを学んだので、私たちが議論していることはすぐにわかり、理解できるでしょう。
アルゴリズムが Google や Facebook などの企業の主力製品であることは知っていますが、その言葉が何を意味するのかはよくわかりません。
アルゴリズムについて知っていることすべてが高校時代の微積分の悪夢を思い出させるため、恐怖で逃げたり隠れたりします。

あなたが後者の 2 つのうちの 1 つである場合、この記事はあなたのためのものです。

アルゴリズムとは正確には何ですか?

アルゴリズムは必ずしも特殊な種類の操作である必要はありません。これらは概念的なものであり、特定の目標を達成するためにコード内で実行する一連の手順です。

アルゴリズムは、単に「タスクを達成するための命令」として定義されることがよくあります。「レシピ」とも呼ばれます。 The Social Network では、ザッカーバーグは Facemash を機能させるアルゴリズムを必要としていました。映画を見た人なら、マークの寮の窓に走り書きされた方程式のようなものを見た覚えがあるでしょう。しかし、この走り書きされた代数は、マークの単純な「ホットオアノット」ウェブサイトとどのような関係があるのでしょうか?

アルゴリズムは確かに命令です。おそらく、より正確に説明すると、アルゴリズムはタスクを効率的に実行するためのパターンです。ザッカーバーグの Facemash は、グループ全体と比較して誰かの魅力を判断するために使用される投票サイトですが、ユーザーは 2 人のどちらかしか選択できません。マーク・ザッカーバーグ氏は、どの人が互いに一致するかを決定し、その人の過去の履歴と以前の候補者に基づいて投票の価値を評価する方法を決定するアルゴリズムを必要としています。これには、単に全員の投票を数えるよりもさらに直感が必要です。

たとえば、負の数に 1 を加算し、正の数から 1 を減算し、0 については何もしないアルゴリズムを作成するとします。次のようなことを行うことができます (JavaScript スタイルの疑似コードを使用):

リーリー

「これは関数だ」と自分に言い聞かせているかもしれません。その通りです。アルゴリズムは必ずしも特殊なタイプの操作である必要はありません。これらは概念的なものであり、特定の目標を達成するためにコード内で実行する一連の手順です。

それでは、なぜそれらが重要なのでしょうか?明らかに、数値に 1 を加算または減算することは非常に簡単です。

しかし、検索について話しましょう。数値の配列から数値を検索するには、どうしますか?簡単な方法は、数値を反復処理して、各数値を検索している数値と照合することです。しかし、これは効率的な解決策ではなく、完了までにかかる時間の範囲が広いため、大規模な検索セットに拡張する場合には不安定で信頼性の低い検索方法となります。

リーリー

幸いなことに、検索を使えばもっとうまくできます。

なぜ非効率なのでしょうか?

優れたアルゴリズム設計者になるためには、アルゴリズムを深く理解し、評価すること以上に優れた方法はありません。

配列に 50,000 のエントリがあり、ブルートフォース検索 (つまり、配列全体を反復して検索) を実行するとします。最良の場合、検索しているエントリは 50,000 エントリの配列の最初のエントリになります。ただし、最悪の場合、アルゴリズムが完了するまでに最良の場合よりも 50,000 倍の時間がかかります。

それでは何が良いのでしょうか?

代わりに、二分検索を使用して検索できます。これには、配列をソートし (自分で理解してもらいます)、次に配列を半分に分割し、検索番号が配列の中央のマークより大きいか小さいかを確認することが含まれます。それがソートされた配列の中央のマークより大きい場合、検索された数値は配列の一部ではないため、前半は破棄できることがわかります。また、配列の外側の境界を定義し、検索された数値がこれらの境界の外側に存在するかどうかをチェックし、存在する場合は複数の反復操作を取得し、それらを単一の反復操作に変換することによって、多くの作業を削減することもできます (ブルートフォースアルゴリズムの場合) 50,000 回の操作が必要です)。

リーリー

かなり複雑そうに聞こえます

単一のバイナリ検索アルゴリズムの一見複雑な性質を利用して、それを何十億もの可能なリンク (Google 検索経由など) に適用します。さらに、これらのリンク検索に何らかのランキングシステムを適用して、応答するページの順序を付けてみましょう。さらに良いのは、友達として追加したい人を特定するように設計された AI ソーシャルモデルに基づいた、一見ランダムな「提案」システムを適用することです。

これにより、アルゴリズムが単なる関数の派手な名前以上のものである理由がより明確に理解できるようになります。最良の場合、これらは、最も明白なソリューションよりも直感的に何かを達成するための、賢くて効率的な方法です。スーパーコンピューターでは何年もかかるかもしれないタスクを、携帯電話で数秒で実行できるタスクに変えることができます。

アルゴリズムは私にどのように適用されますか?

私たちのほとんどの開発者は、高レベルの抽象アルゴリズムを毎日設計しているわけではありません。

幸运的是，我们站在前辈开发人员的肩膀上，他们编写了本机排序函数，并允许我们以有效的方式使用 indexOf 搜索字符串中的子字符串。
块引用>
但是我们确实处理我们自己的算法。我们每天创建 for 循环并编写函数；那么好的算法设计原则如何指导这些函数的编写呢？

了解您的输入

算法设计的主要原则之一是，如果可能的话，以输入本身为您完成一些工作的方式构建算法。例如，如果您知道您的输入始终是数字，则不需要对字符串进行异常/检查，或将您的值强制转换为数字。如果您知道 JavaScript 中的 for 循环中的 DOM 元素每次都是相同的，那么您不应该在每次迭代中查询该元素。同样，在 for 循环中，如果可以使用（更接近）简单操作完成相同的操作，则不应使用有开销的便利函数。
// don't do this:
for (var i = 1000; i > 0; i--){
    $("#foo").append("<span>bar</span>");
}

// do this instead
var foo = $("#foo");
var s = "";
for(var i = 1000; i > 0; i--){
    s += "<span>bar</span>";
}
foo.append(s);
ログイン後にコピー
如果您是一名 JavaScript 开发人员（并且使用 jQuery），并且您不知道上述函数在做什么以及它们有何显着不同，那么下一点适合您。

了解您的工具

在最好的情况下，[算法]是聪明、有效的方法来完成比最明显的解决方案更高水平的直觉。

很容易认为这是不言而喻的。然而，“知道如何编写 jQuery”和“理解 jQuery”之间是有区别的。了解您的工具意味着您了解每一行代码的作用，既立即（函数的返回值或方法的效果）又隐式（与运行库函数相关的开销，或者哪一个是最有效的）连接字符串的方法）。要编写出色的算法，了解较低级别函数或实用程序的性能非常重要，而不仅仅是它们的名称和实现。

了解环境

设计高效的算法是一项全身心投入的工作。除了将您的工具理解为一个独立的部分之外，您还必须了解它们与手头的更大系统交互的方式。例如，要完全理解特定应用程序中的 JavaScript，重要的是要了解跨浏览器场景中 JavaScript 的 DOM 和性能、可用内存如何影响渲染速度、您可能与之交互的服务器的结构（及其响应），以及无数其他无形的考虑因素，例如使用场景。

减少工作量

一般来说，算法设计的目标是用更少的步骤完成一项工作。（也有一些例外，例如 Bcrypt 哈希。）编写代码时，请考虑计算机为达到目标而采取的所有简单操作。以下是一个简单的清单，可帮助您开始更高效的算法设计：

使用语言功能来减少操作（变量缓存、链接等）。

尽可能减少迭代循环嵌套。

尽可能在循环外部定义变量。

使用自动循环索引（如果可用）而不是手动索引。

使用巧妙的缩减技术（例如递归分治和查询优化）来最大限度地减少递归过程的规模。

学习先进技术

要成为一名更好的算法设计师，没有比深入理解和欣赏算法更好的方法了。

每周花一两个小时阅读《计算机编程的艺术》。

尝试 Facebook 编程挑战赛或 Google Codejam。

学习使用不同的算法技术解决同一问题。

通过使用较低级别的操作实现语言的内置函数（例如 .sort()）来挑战自己。

结论

如果您在本文开始时还不知道什么是算法，那么希望您现在对这个有点难以捉摸的术语有了更具体的理解。作为专业开发人员，重要的是我们要了解我们编写的代码是可以分析和优化的，而且我们花时间对代码的性能进行分析也很重要。

你发现过什么有趣的算法练习题吗？也许是动态规划“背包问题”，或者“醉酒行走”？或者您可能知道 Ruby 中的一些递归最佳实践与 Python 中实现的相同函数不同。在评论中分享它们！