ARTS(18)

Algorithm

环型链表

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
输入head =
输出2

示意图

这个问题可以分为两步处理:

  1. 链表中是否有环
  2. 如何发现链表中环的第一个节点

对于是否有环很容易解决,使用两个指针fast_pointerslow_pointer,其中fast_pointer每次前进2次,slow_pointer每次前进1次,如果fast_pointer==null,表明无环;如果fast_pointer==slow_pointer表明有环。
如果有环,那么slow_pointer或者fast_pointer必然在环中,那么可以通过再走一圈,计数环中节点的数N。接下来重新开始fast_pointerslow_pointer,首先fast_pointer向前前进N步,然后fast_pointerslow_pointer每次同步向前一步,一旦fast_pointer==slow_pointer表明该位置就是入环的节点。

func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    first, second := head, head
    isCycle := false
    for {
        if first.Next != nil {
            first = first.Next
        }
        if second.Next == nil {
            break
        }else{
            second = second.Next
        }
        if second.Next == nil {
            break
        }else{
            second = second.Next
        }
        if first == second {
            isCycle = true
            break
        }
    }
    if isCycle == false {
        return nil
    }
    size := cycleSize(first)
    second = head
    for size > 0 {
        second = second.Next
        size --
    }
    first = head
    for first != second {
        first = first.Next
        second = second.Next
    }
    return first
}

func cycleSize(node *ListNode) int {
    cur := node
    num := 1
    for {
        cur = cur.Next
        if cur == node {
            break
        }else{
            num ++
        }
    }
    return num
}

2 Review

Exception Handling Considered Harmful
异常检查有害
最近很多语言诸如Java,Python和Ruby等,选择使用异常检查作为它们错误处理的基本方法,取代了传统的返回错误值的方法。我认为这种将来开发语言的趋势是错误的,主要有一下两个原因:

  1. 异常处理引入了可能的在每一行中的代码出现的错误导致的控制流错误。这样隐藏的控制流转移可能性导致大部分程序员会忽视,甚至专家。当这样的忽视发生,一旦异常被抛出,程序中的状态就会被破坏,状态将会导致不一致而且很难被预测。
  2. 异常处理对当前的大部分高并发编程模型不够友好(比如fork/join,线程池或者任务队列,CSP/Actor 模型等),因为异常处理是在单线程中使用回归方式处理异常,在那里执行的路径,简单来讲就是单路径。

2.1 好的意图

异常处理原来是用来解决传统的使用返回错误码的方式解决错误问题方式中的一些常见的问题。
首先,将处理错误码从正常代码中剥离出来,这样的代码将会变得更加有序,更加整洁。而且很方便代码跟踪因为没有必要的干扰。
第二点,通过将错误发生的地方和错误处理的地方分隔开来,哪怕中间又很多次函数调用。这样就能处理来自库函数中很深处的异常也能处理,将异常传播到应用程序,而不用一系列错误检查机制和返回码写入。这样避免的库中包含的具体或者泛型的错误设计倾向,因为一旦这样做就会过多的陷入到细节中。
最后一点,异常可以看做是半预测(semi-predicate)问题的解决方案,对于某些操作每一个返回值都是有效的但是错误必须要通过其他方式展示出来,或者是不直接方式。比如引用传递参数错误或者是内部在对象内部包含成功/失败状态。
为了解决上述问题,异常处理采用了一种叫做回滚(rollback)方式来处理错误,当一个错误发生时候一个异常被抛出,它让运行时系统开始通过解开调用栈回滚所有操作,销毁所有的局部变量,直到合适的错误处理机制块抓住(catch),然后从这里开始执行。
这种方法的根本好处是代码中错误发生的地方就被抛出,在异常捕获的地方或者处理地方,可以很容易的不理会错误发生。没有必要显式地处理这些错误,而且局部变量在调用栈在解开的过程中被销毁。
听上去不错,是的嘛?

2.2 隐藏控制流和腐败的状态

通过回滚来处理异常的方式最大的问题是许多操作并不是简单地销毁局部对象(或者是通过垃圾回收来处理堆对象)。经典的操作就是I/O,你不能将输出到屏幕上的内容回收,取消用户的输入或者回复已经输入到文件中的内容,亦或者撤回已发送的网络包,这才是问题所在。
但是这仅仅是冰山一角,这仅仅是那些非本地副作用代码中的一个。更普通的例子就是更普通的状态,任何让共享的数据结构修改的代码,无论是如何展开栈和销毁局部对象都不能撤回之前的修改。事实上,在任何一个异常频繁的环境中,任何改变都有可能导致异常,所以几乎不可能编写一个安全的异常处理处理函数。
考虑那些并没有考虑到的异常抛出,它修改了很大的数据结构。那么程序员编写正确的处理逻辑来捕获这个异常的可能性有多大呢?亦或者撤销或者恢复这些已做的改变有多大?大部分情况下是可能性非常低,大部分情况下程序员在一开始都不会去考虑这个问题,因为这个异常是非常隐晦的,在代码中并没有显示地给出。一旦异常发生,它会导致整个代码的控制发生改变,跳转到它被捕获的地方,这回导致之前的修改的数据结构变得不完整。
任何通过共享数据修改的算法,从本质上将都不能认为是异常安全的,除非这个语言提供其他形式的事务机制(比如SQL的提交机制),亦或者程序员通过拷贝数据的形式模拟类似事务行为,但是这样做是非常繁琐的而且也不可行性,尤其是针对大对象或者复杂的数据结构。
所以如果你正在修改数据,异常发生了,代码会离开正在操作的数据导致数据处理半状态。这样做是非常非常危险的,因为这样做会带来沉默数据腐败(slient data corruption)问题,在大部分情况下,任何清晰可见的错误信号,甚至是程序终止都是目前处理沉默数据腐败的最主要可行的方法。现在所有的异常检查的方法都没有清晰的错误型号,大部分代码目前来看都是忽略异常,并且假设接下来的代码会捕获并且处理它们。
因此这个依赖异常检查的编码风格仅仅是增加了这样的趋势

使用简单、可生产性和简单分析的错误,然后让它们变成一个很难debug的腐败。

强制使用返回码来处理异常是正确地处理方式,因为它强制程序来思考任何错误发生的可能性。这是关键点,但是事实上将代码切分成错误检查是不幸的,但是为了操作的正确性,这一点牺牲是必须的。而异常的方式往往让程序员,甚至是鼓励他们忽视错误的可能性,而且假设在某一个地方会有异常处理。
为了编写异常安全的代码,在重要的每一行代码,程序员都要考虑到错误的可能性并且考虑回滚等,确保代码正确地清理而且让每一件事情保持在合适的,稳定的状态。也就是说它们不能让数据结构处于半修改,不能让文件或者网络连接处于打开状态。它需要大量的时间和精力,也需要高度的纪律来让每件事正确处理,对于遗忘或者忽视异常是非常容易的。
核心问题在于它隐藏了控制流程,一个著名的笑话是一个神奇的编程语言结构叫做comefrom,它是goto语句的反义词,它是这样做的,在程序中任何地方申明comefrom 20,在任何适合执行到20行的时候,就会跳转到comefrom代码的地方。这个例子就是说明控制流发生变化。异常处理也引入这中隐藏控制流的做法,而且这个发生在每一行关键代码处,每一个方法、函数调用出,每一个对象的构造或者操作符的重载。

2.3 与并行编程不兼容

使用回滚或者展开方式处理异常或多或少的是因为有线性的调用链来展开,亦或者是可以通过某种方式回滚至调用者来发现最近能够捕获异常块。但是这个对于任何并行编程模型都是不行的,这导致了异常处理的方式不能在多核机器中使用,然而并行编程时代才是未来。
甚至考虑到最简单的并行模型-直接的并行fork/join,比如并行地处理一个数组中的全部元素。问题是非常明确,但是如果你fork出20个线程而且仅仅只有一个线程抛出的异常,你会怎么做?回滚展开fork出来的进程,并且杀掉其余的19个线程,伴随着数据的损坏?展开其中一个线程并且让其余19个线程继续运行,但是在展开的过程中,哪一个对象应该被销毁呢?让程序员在catch块中添加fork操作?
原来越多的并行模型,异常处理再一次好像并不适宜现在的模型。比如说如今现在最实用的并行模型是使用线程工作池,每一个线程执行一笑部分工作,通常称之为任务或者操作,它们被存储在一个工作队列中并且被依次被分配到线程池中,直到所有的线程完成的当前的任务。使用异常处理似乎在这里似乎不太可能,因为每个工作任务都和调用者进行分离。展开调用栈这个概念在这里似乎不太可能。
更复杂的并行编程的模式,比如在CSP中的异步消息处理,这个与线程池和任务队列有相似的地方,但是这个属性被隐藏在语言中了。再一次,因为伴随着消息中对象和执行者通常是异步的,所以没有明显执行路径来展开,对于异常处理机制就无法再适用了。
最后,因为异常跳出了控制机制,不使用正常的调用/返回机制。它们不适合在CSP或者actor并行模型中使用。你可以很容易的返回错误码通过网络的字节流,但是通过正常的数据通道却很难抛出异常。虽然精心设计的运行系统可以做到,但是这是个可行的方法吗?
基本事实就是回滚/展开的概念在并行情况下并不适宜,甚至简单的fork/join模型,更不用说复杂的并行模型。

2.4 异常的异常

大部分异常处理的拥护者都承认最佳异常的使用是罕见的,换句话说,你应该在所有的日常生活着都应该使用错误码,只有在那些不会发生错误的地方使用异常。或许我夸大的这个概念,但是你应该知道这一点。
我个人认为我们讨论的异常应该都是那些系统本应该不会发生的错误,比如内容分配出错,运行栈使用完毕,其他一些资源使用完毕或者内存访问非法。我们本不应该在应用程序中包含这些错误,因为这些错误非常罕见,并且无法恢复。复杂度可分为有用和无用两种,从安全角度增加复杂度是无用的复杂度。
我们应该假设应用程序在一个拥有无限资源的机器上运行,这个就让应用程序变得更加简单也减少错误的倾向。如果物理资源被消耗,这应该是操作系统的问题而不是应用程序的责任。
但是有些人会说

对于那些内嵌的设备,它们确实有资源的限制,那该怎么办?

答案就是看看这些嵌入式设备究竟是要做什么。我们已经有一个嵌入式设备,它的功能就是无线热点,打印服务,音乐服务或者是NAS服务。既然有了特定的程序运行在嵌入式设备中,就应该让这这个服务死掉对于超出之外的移动设备。

2.5 最后

一个事实就是如果你在异常处理的地方排除了正常的异常,就跟传统的返回错误值是一样的处理。只要异常不抛出,这个系统工作是正常的。正如Michael Grier所说的:

异常只有在没有人处理的时候才起作用

我坚信这是语言设计的问题,确认99%的C++代码都不是异常安全的,同样的道理还有Object-C, Java等等。其中包含的问题不单单是内存泄漏,未关闭的文件和网络,还有修改的共享数据或者数据库状态。
我提议所有的编程语言设计者都应该放弃异常处理。异常处理并没有起作用,并没有和宣称的那样带来好处。现实中的所有例子都没有正确处理异常,对于使用返回值来说又变得分彩非常冗余。没有人从异常使用中获益,而且仅仅是增加了出错的可能性。使用返回值错误码是有效的,而且也能能够工作。

Tips

  • du -h --max-depth=1 可以展示文件夹大小

  • 英语名称性从句
    • 使用 that 名词性从句: That Peter do not study makes his parents unhappy.
    • 使用 whether 特殊疑问句的从句:I don't known whether they will arrive on time.
    • 特殊疑问句句,恢复动词位置的从句: I have no idea about How much the price is.

Share

在软件开发过程中,对于新的需求,不需要立马编写代码(技术上的问题都能解决),做到以下几点

  • 可行的方案;
  • 方案是否正确处理所有可能结果;
  • 方案的流程图;
  • 潜在的风险;
  • 结论;
Comments
Write a Comment