Gain a deeper understanding of the fundamentals of algorithm design

This article will delve into the principles of algorithm design. If you don’t know what I’m referring to, keep reading!

When you hear the word "algorithm," you might respond in one of three ways:

1. You will immediately know and understand what we are discussing because you studied computer science.
2. You know algorithms are the workhorse of companies like Google and Facebook, but you’re not quite sure what the word means.
3. You run and hide in fear because everything you know about algorithms reminds you of your high school calculus nightmares.

If you are one of the latter two, then this article is for you.

---

What exactly is an algorithm?

Algorithms are not necessarily a special type of operation. They are conceptual, a set of steps you take in your code to achieve a specific goal.

Algorithms are often defined simply as "instructions to accomplish a task." They are also called "recipes". In The Social Network, Zuckerberg needed an algorithm to make Facemash work. If you've seen the movie, you probably remember seeing what looked like a scrawled equation on Mark's dormitory window. But what does this scrawled algebra have to do with Mark’s simple “Hot or Not” website?

Algorithms are indeed instructions. Perhaps a more accurate description is that algorithms are patterns for accomplishing tasks efficiently. Zuckerberg's Facemash is a polling site used to determine someone's attractiveness relative to an entire group, but users can only choose between two people. Mark Zuckerberg needs an algorithm to decide which people match each other and how to evaluate the value of a vote based on that person's previous history and previous contenders. This requires more intuition than simply counting everyone's votes.

For example, suppose you want to create an algorithm that adds 1 to any negative number, then subtracts 1 from any positive number, and does nothing with 0. You can do something like this (using JavaScript-style pseudocode):

function addOrSubtractOne(number){
    if (number < 0) {
        return number + 1
    } else if (number < 0) {
        return number - 1
    } else if (number == 0) {
        return 0;
    }
}

You might be saying to yourself: "This is a function." You'd be right. An algorithm is not necessarily a special type of operation. They are conceptual - a set of steps you take in your code to achieve a specific goal.

So why are they important? Obviously, adding or subtracting 1 to a number is a fairly simple matter.

But let’s talk about search. To search for a number in an array of numbers, what would you do? A simple way is to iterate over the number, checking each number against the number you are searching for. But this is not an efficient solution, and the range of possible completion times is wide, making it an unstable and unreliable search method when scaling to large search sets.

function naiveSearch(needle, haystack){
    for (var i = 0; i < haystack.length; i++){
        if (haystack[i] == needle) { return needle; }
    }
    return false;
}

Fortunately, we can do better with search.

Why is it inefficient?

There is no better way to become a better algorithm designer than to deeply understand and appreciate algorithms.

Suppose your array has 50,000 entries and you do a brute force search (i.e. search by iterating over the entire array). In the best case, the entry you are searching for will be the first entry in an array of 50,000 entries. However, in the worst case, the algorithm will take 50,000 times longer to complete than in the best case.

So what’s better?

Instead, you can search using binary search. This involves sorting the array (I'll let you figure it out for yourself), then splitting the array in half and checking if the search number is greater or less than the middle mark in the array. If it is greater than the middle mark of the sorted array, then we know that the first half can be discarded since the searched number is not part of the array. We can also reduce a lot of work by defining the outer bounds of the array and checking if the searched number exists outside these bounds, and if it does, we take multiple iteration operations and transform them into a single iteration operation (in Brute Force Algorithms requires 50,000 operations).

sortedHaystack = recursiveSort(haystack);
function bSearch(needle, sortedHaystack, firstIteration){
    if (firstIteration){
        if (needle > sortedHaystack.last || needle < sortedHaystack.first){
            return false;
        }
    }
    if (haystack.length == 2){
        if (needle == haystack[0]) {
            return haystack[0];
            } else {
            return haystack[1];
            }
    }
    if (needle < haystack[haystack.length/2]){
        bSearch(needle, haystack[0..haystack.length/2 -1], false);
    } else {
        bSearch(needle, haystack[haystack.length/2..haystack.length], false);
    }
}

Sounds quite complicated

Take the seemingly complex nature of a single binary search algorithm and apply it to billions of possible links (like via Google search). Beyond that, let's apply some sort of ranking system to these link searches to give an order of responding pages. Even better, apply some kind of seemingly random "suggestion" system based on an AI social model designed to identify people you might want to add as friends.

This gives us a clearer understanding of why algorithms are more than just fancy names for functions. At their best, they are smart, efficient ways to accomplish something that is more intuitive than the most obvious solution. They can turn tasks that might take years on a supercomputer into tasks that can be done in seconds on a mobile phone.

How does the algorithm apply to me?

For most of us developers, we don't design high-level abstract algorithms every day.

幸运的是，我们站在前辈开发人员的肩膀上，他们编写了本机排序函数，并允许我们以有效的方式使用 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 中实现的相同函数不同。在评论中分享它们！

The above is the detailed content of Gain a deeper understanding of the fundamentals of algorithm design. For more information, please follow other related articles on the PHP Chinese website!