如何跳出两层循环


起步

Python 中如果跳出嵌套的循环?这是大家都会遇到的问题。python 语法并不支持 break n 的语句,break 只能跳出一层循环。

要跳出两层循环,一般的处理方式是,把第二层循环包装成函数,利用函数的返回进行判断并退出。又或者设置个布尔变量来标记循环的结束。

直到我看到 pycon2013 中的一种优雅的处理方式,视频见:https://www.youtube.com/watch?v=EnSu9hHGq5o


算法-计算小数组在大数组中的索引


前言

大数组:[1,2,3,4,5,6]

小数组:[4,5]

我们需要快速得到小数组在大数组中的索引位置,本例中结果是3

算法思路

1. 暴力,嵌套for循环

function match(arr1,arr2){
  var n = arr1.length
  var m = arr2.length
  f1:
  for(var i=0;i<n;i++){
    if(arr1[i]===arr2[0]){
      f2:
      for(var j=1;j<m;j++){
        if(arr1[i+j]!==arr2[j])continue f1;
      }
      return i
    }
  }
  return -1
}


Python内核阅读(二十五):信号处理机制


起步

Python处理信号是在 signal 模块中,这个模块其实是纯python代码对 _signal 的封装。要想知道Python解释器本身如何处理信号以及如何实现的,还需要去了解 signalmodule.c 。其中,比较需要了解的是python解释器与操作系统有关信号的交互。

大体上,Python解释器不太可能会操作系统发出的信号立即做回调。因为Python的Opcode操作是原子操作,不允许被中断。所以Python解释器对信号做一层封装,并做好标记,待时机得当的时候来检查并触发相关的回调函数。


字符串匹配算法介绍及js字符串indexOf源码探究


前言

之前学过的字符串匹配算法,一种是朴素算法,一种是KMP算法。

朴素算法即暴力,两层for循环,算法复杂度O(n*m)

function match(s1,s2){
  var n = s1.length
  var m = s2.length
  f1:
  for(var i=0;i<n;i++){
    if(s1[i]===s2[0]){
      f2:
      for(var j=1;j<m;j++){
        if(s1[i+j]!==s2[j])continue f1;
      }
      return i
    }
  }
  return -1
}

KMP 的实现比较巧妙,下文会提到,我们先来介绍一种新的算法 Rabin-Karp

最近在分析 adblockplus.js 源码的时候了解到的

此外还有 有限自动机算法(Finite Automation)、Boyer-Moore 算法、Simon 算法、Colussi 算法、Galil-Giancarlo 算法、Apostolico-Crochemore 算法、Horspool 算法、Shift-Or 算法和 Sunday 算法