iOS程序员对算法的要求

算法和数据结构(鉴于二者的关联,以下统称算法),对于程序员的重要性一直是个具有争议性的话题。有一些程序员内心对算法有着天然的排斥,面试当中一旦考察算法知识,会被不少程序员吐槽,但有部分公司又一直在坚持这种做法。我且以一个iOS程序员的视角,谈下自己粗浅的看法。

不懂算法并不妨碍成为一名iOS程序员,大家关心的是:掌握算法知识和成为一名优秀程序员之间的关系。在我看来,二者是非充分但必要的联系。至少适度的掌握算法知识是成为一名优秀程序员的必要前提,当然也包括iOS程序员。其重要性简单来说可以归为以下三点:

  • 平常编写iOS代码虽然很少遇到算法层面的考量,不过一旦遭遇特定算法问题,没有算法基础会成为无法跨越的障碍。
  • 算法有助于养成“程序员”思维,或者说“计算机”思维。这种思维方式和习惯对寻求编程问题的解决方案十分重要,让我们更加接近程序的真相。
  • 算法能锻炼脑力,养成刨根问底的习惯。

我必须承认一点,算法并不是第一次遇见就能爱上的玩意,初次接触会好奇,深入了解会头疼。我和算法的初会到建立基础的算法知识体系花了不少时间,从入门到放弃而后再入门。

平常写代码,其实会时不时的遇到算法相关的问题,只不过可能被选择性的忽视或避开了。我可以举两个简单的例子:

例一:检查通讯录的变化并上传服务器

为了检测iOS系统通讯录的变化,每次收到改变通知的时候,我们需要将Device当中的通讯录取出来和Database当中的通讯录进行对比,确认是否有新的改变,有的同学会写出如下代码:

    for (MyContact* deviceContact in deviceContacts) {
       BOOL exists = false;
       for (MyContact* dbContact in dbContacts) {
           if ([deviceContact isEqual:dbContact] == true) {
               exists = true;
           }
       }
       if (exists == false) {
           [dbContacts addObject:deviceContact];
       }
   }

假设设备有1000+通讯录记录(并不少见),这两层的for就是1,000,000次循环,不经意间就埋了个性能问题的坑,如果了解如何计算时间复杂度,知道hash表,针对这种场景就能写出更优质的代码。无序集合,有序集合,哈希表查询元素的问题是算法当中基础的基础。哈希表查询元素的时间复杂度是我面试常问的问题。

例二:数据库建表时索引的用处

有些程序员没听过索引是什么,有些从前辈那里得知索引可以加快查询但对原理却不甚了解,掌握这些常用技巧背后的理论知识才能做到合理使用,比如为什么我们不对表的每一个field都建立索引呢?理解索引是通过「新建表」配合「B+树」来实现快速查询的,就能很好明白索引这项利器的优和劣。索引也是我面试时的必问问题之一。

算法同时还是个锻炼脑力的好方式,我之前的文章中介绍个一个小Tip可以保持每天脑力充沛:早上在进入工作状态之前解决一个小问题。算法问题是个不错的选择,算法都比较独立而且针对性强。比如排序算法当中的QuickSort算法,空闲的时候把思路重理一遍,甚至用代码敲出来,就像每天晚上做俯卧撑一样,对大脑的锻炼十分有效,下面一小段伪代码摘自WikiPedia的QuickSort介绍:

algorithm quicksort(A, lo, hi) is
   if lo < hi then
       p := partition(A, lo, hi)
       quicksort(A, lo, p – 1)
       quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
   pivot := A[hi]
   i := lo        // place for swapping
   for j := lo to hi – 1 do
       if A[j] ≤ pivot then
           swap A[i] with A[j]
           i := i + 1
   swap A[i] with A[hi]
   return i

虽然一共只有14行,你能一目了然的看清解决思路吗?尤其是partition函数,短短7行代码就描述了一段精妙的思路,程序员的乐趣不就在此嘛。

上一篇:【python-字典】判断python字典中key是否存在的


下一篇:C#学习笔记(三)——流程控制