在不同的语境中,this代表不同的对象。

全局上下文

在全局上下文中(任何函数体外), this 指代全局对象。

console.log(this === window);
// true

函数上下文

在函数内部, this的值取决于函数是如何被调用的。

直接调用

function say() {
    return this
}
say() === window
// true

而在严格模式下,this在进入运行环境时设置,将是undefined。

function say2() {
    "use strict";
    return this
}
say2() === undefined
// true

作为方法

如果函数作为一个对象的方法,则this指代调用此方法的对象。注意箭头函数在{}定义对象 中的不同表现。

var dog = {
    name: "Tom",
    bark: function() {
        return this
    },
    walk: () => {
        return this
    },
    head: {
        name: "Tom's head",
        shake: function() {
            return this.name + " shaking"
        }
    }
}
dog.bark() === dog
// true
dog.walk() === window
// true

即使方法是之后才指定为对象的属性。

dog.run = function() {
    return this.name + " running"
}
dog.run()
// Tom running

this指向其最近的对象。

dog.head.shake()
// Tom's head shaking

另外构造函数中的函数(包括箭头函数)则指向产生的对象本身。

function Dog() {
    this.walk = () => {
        return this
    }
    this.bark = function() {
        return this
    }
}
var d = new Dog()
d.bark() === d
// true

d.walk === d
// true

call 与 apply、bind

call() 方法可用于指定函数体内的this对象。 apply() 指定this,并且第二个数组参数的各项作为函数的参数。

function greet(greeting) {
    return greeting + this.fname + " " + this.lname
}
var tom = {fname: "Tom", lname: "Jerry"}
greet.call(tom, "Hello ")
// Hello Tom Jerry
greet.apply(tom, ["Hi~ "])
// Hi~ Tom Jerry

bind()方法返回一个新的函数,函数体与函数相同,但this被永久地绑定。

greet = greet.bind(tom)
greet("Hello ")
// Hello Tom Jerry

箭头函数

对于箭头函数,this值一旦确定,就会一直保持不变。

var name = "Jerry",
say = (() => this.name),
tom = {
    name: "Tom",
    say: say,
    walk: function() {
        var inwalk = () => this.name + " walking"
        return inwalk
    }
}

say() === "Jerry"
// true

tom.say() === "Jerry"
// true

say.call(tom) === "Jerry"
// true

say.bind(tom)() === "Jerry"
// true

var globalwalk = tom.walk()
globalwalk()
// Tom walking

globalwalk.bind(window)
globalwalk()
// Tom walking

DOM事件处理函数中的this

当函数作为DOM时间处理函数时,this指向触发事件的元素。

var element = document.getElementById('id1')
element.onclick = function(e) {
    console.log(this === e.currentTarget) // 总是 true
    console.log(this === e.target) // 当currenrTarget === target
}

行内事件处理函数中的this

<button onclick="alert(this)">Click</buttom>

上述代码的this指向<button> DOM对象。 注意只有外层的this被如此设置。

<button onclick="alert((function(){return this})())"

上述代码的this未指定所以其值默认为全局对象(window / global)。

Python中的闭包与局部作用域一文最后,我们用函数默认参数代替闭包,实现了记忆化。这篇文章就更深入的研究一下Python中的函数默认参数。

关于默认参数

下列代码的运行结果可能会让很多刚接触Python的同学感到意外

def foo(li=[]):
    li.append(1)
    return li

###############
>>> foo()
[1]
>>> foo([5])
[5, 1]
>>> foo()
[1, 1]
>>> foo()
[1, 1, 1]

通常我们认为foo()应该返回[1],是因为我们认为在每次函数调用时li都是[],而事实上不是。stackoverflow上有一个很好的解释————作为第一类对象的函数对象,在其首次定义时默认参数就作为函数对象的“成员数据”而存在了,后续的状态修改自然会影响其值。而在Fluent Python一书中对此也有很清晰的解释(十分推荐这本书):

The problem is that each default value is evaluated when the function is defined — i.e. usually when the module is loaded — and the default values become attributes of the function object. So if a default value is a mutable object, and you change it, the change will affect every future call of the function.

我们一旦定义了函数,默认参数值就成了函数对象属性的一部分,对于可变默认参数值的修改将会影响后续的函数调用。我们通过两个函数来验证这一点:

不可变默认参数

def unmutable(var=1):
    print(id(var), var)
    var += 1
    print(id(var), var)

####################
>>> unmutable()
1626866128 1       #1
1626866160 2       #2
>>> unmutable(2)
1626866160 2       #3
1626866192 3       #4
>>> unmutable()
1626866128 1       #5
1626866160 2       #6
  • #1#2 对比可知,对不可变对象进行修改后,var其实已经是另外一个对象了
  • #3显示var不是默认对象。
  • #5 显示再次调用var仍然是原对象。

可变默认参数

def mutable(var=[]):
    print(id(var), var)
    var.append(1)
    print(id(var), var)

######################
>>> mutable()
2326890888520 []       #1
2326890888520 [1]      #2
>>> mutable([2])
2326898722504 [2]      #3
2326898722504 [2, 1]   #4
>>> mutable()
2326890888520 [1]      #5
2326890888520 [1, 1]   #6
  • #1#2 对比可知,对可变对象进行修改后,var仍为原对象。
  • #3显示var不是默认对象。
  • #5 显示再次调用var仍为原对象,但其值已经改变。

再看下边的代码

def mutorno(var=[]):
    print(id(var), var)
    var = var+[1]
    print(id(var), var)

######################
>>> mutorno()
2326987935304 []        #1
2326987885384 [1]       #2
  • var进行赋值后,var已经不再是原对象了。

至此我们可以总结:如果默认参数为不可变对象,在函数体内对该参数的修改都将导致参数名指向另外一个对象,而原对象的值不变;若为可变对象,对其进行的修改将直接影响原对象的值,而对其重新赋值将导致参数名指向另一个对象。

Python的参数传递机制

i = 1
def f(obj):
    obj += 1
>>> f(i)
>>> i
1

li = []
def g(obj):
    obj += [1]
>>> g(li)
>>> li
[1]

如果Python是按引用传递,那f函数调用后i的值应该为2;如果Python是按值传递,那g函数调用后li的值应该为[]。那么Python的参数传递机制到底是什么呢?

Fluent Python一书中将其描述为共享传递(call by sharing)

如果Python是按引用传递,那f函数调用后i的值应该为2;如果Python是按值传递,那g函数调用后li的值应该为[]。那么Python的参数传递机制到底是什么呢?

Fluent Python一书中将其描述为共享传递(call by sharing),

The only mode of parameter passing in Python is call by sharing. That is the same mode used in most OO languages, including Ruby, SmallTalk and Java. Call by sharing means that each formal parameter of the function gets a copy of each reference in the arguments. In other words, the parameters inside the function become aliases of the actual arguments.
The result of this scheme is that a function may change any mutable object passed as a parameter, but it cannot change the identity of those objects, i.e. it cannot replace altogether an object with another.
———— fluent Python

也就是在f函数中,obj 和 i 都是对同一个对象的引用,g 函数中,li 和 obj 都是对同一个对象的引用。而由于 int 类型为不可变对象,在函数体内对其修改将使其变为另一个对象的引用,修改的是另一个对象,因此原对象是不变的。而 list 类型为可变的,+= 是 in place 操作,直接修改了原对象的值。

这一点和JavaScript的基本对象/引用对象传递参数机制类似,在传递基本对象时表现为按值传递,传递引用对象时表现为按引用传递。但JavaScript的参数传递机制只有按值传递,

ECMAScript中的所有参数传递都是值,不可能通过引用传递参数。
基本类型值指的是简单的数据段,而引用类型值指那些可能由多个值构成的对象。
————JavaScript 高级程序设计 第三版

stackoverflow上有一个解释也将JavaScript的参数传递机制解释为call by sharing。

人们常将闭包与匿名函数混淆,因为在函数体内定义函数并不十分常见,直到我们要用到匿名函数,而只有在嵌套函数的情况下讨论闭包才有意义。

事实上,闭包与匿名函数并无关系。闭包指的是函数包含一个扩展的作用域,该作用域内的非全局变量不是在该函数体内定义,但该函数可以引用这些变量,即使这些变量离开了创建它的环境。它与函数是否匿名无关。 segmentfault上有一个形象的解释: 闭包是自带运行环境的函数

作用域相关

在继续讨论闭包之前,先来看一看Python中作用域容易让人疑惑的一些地方。

def p(a):
    print(a)
    print(b)

######################
>>> p(1)
1
Traceback (most recent call last):
  File "<pyshell#17>", line 1, in <module>
    p(1)
  File "<pyshell#16>", line 3, in p
    print(b)
NameError: name 'b' is not defined

很容易理解,b并未定义。

b = 2

###############
>>> p(1)
1
2

上述代码运行正常。

b=2
def p2(a):
    print(a)
    print(b)
    b=3

################
>>> p2(1)
1
Traceback (most recent call last):
  File "<pyshell#22>", line 1, in <module>
    p2(1)
  File "<pyshell#19>", line 3, in p2
    print(b)
UnboundLocalError: local variable 'b' referenced before assignment

上述代码print(b)是在局部变量b定义之前调用的,我们很容易认为print(b)中的b是全局变量b,但事实却不是如此。在Python中,万物皆对象,function也是first-class object,这也就意味着在函数p2定义时,就决定了b是局部变量,在调用print(b)时,将会尝试获取局部变量b,而此时局部变量b还未定义,因此出错。

我们来用dis模块查看函数调用过程中都发生了什么。

from dis import dis
>>> dis(p)
  2           0 LOAD_GLOBAL              0 (print)
              3 LOAD_FAST                0 (a)
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
              9 POP_TOP

  3          10 LOAD_GLOBAL              0 (print)
             13 LOAD_GLOBAL              1 (b)
             16 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             19 POP_TOP
             20 LOAD_CONST               0 (None)
             23 RETURN_VALUE

>>> dis(p2)
  2           0 LOAD_GLOBAL              0 (print)
              3 LOAD_FAST                0 (a)
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
              9 POP_TOP

  3          10 LOAD_GLOBAL              0 (print)
             13 LOAD_FAST                1 (b)
             16 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             19 POP_TOP

  4          20 LOAD_CONST               1 (3)
             23 STORE_FAST               1 (b)
             26 LOAD_CONST               0 (None)
             29 RETURN_VALUE

注意这两行:

  • 13 LOAD_GLOBAL 1 (b)
  • 13 LOAD_FAST 1 (b)

可见在函数p中,print(b)使用全局变量,而函数p2中,使用的是局部变量。

闭包

假如我们需要定义一个函数,该函数每次接收一个参数,返回之前每次调用传给它的所有参数的平均值。我们首先尝试使用可调用类实例来实现。

class Averager:
    def __init__(self):
        self.values = []

    def __call__(self, new_value):
        self.values.append(new_value)
        return sum(self.values) / len(self.values)

#####################
>>> avg = Averager()
>>> avg(10)
10
>>> avg(11)
10.5

我们使用了实例属性来存储所有传递进来的参数值,下边我们将使用函数来实现。

def get_avg():
    values = []
    def avg(value):
        values.append(value)
        return sum(values) / len(values)
    return avg

#####################
>>> avg = get_avg()
>>> avg(10)
10
>>> avg(11)
10.5

当我们调用avg(value)时,get_avg的作用域已经不再存在了,但我们仍然可以获得values的值。values在avg的作用域内作为自由变量(free variable)存在,自由变量意味着values并未绑定avg的作用域。我们来研究avg函数/对象:

>>> avg.__code__.co_varnames
('value',)
>>> avg.__code__.co_freevars
('values',)
>>> avg.__closure__
(<cell at 0x000001BAFF2E1AC8: list object at 0x000001BAFF3174C8>,)
>>> avg.__closure__[0].cell_contents
[10,11]

如此我们就实现了闭包,使变量在其作用域不再存在的情况下依然存在。函数保持与其定义时的自由变量的绑定,并且可以在之后继续使用

还是作用域

注意到上述函数实现在每次计算时都要计算values的所有值的和,我们可能想要优化一下。

def get_avg():
    count = 0
    total = 0
    def avg(value):
        count += 1
        total += value
        return total / count
    return avg

####################
>>> avg = get_avg()
>>> avg(10)
Traceback (most recent call last):
  File "<pyshell#33>", line 1, in <module>
    avg(10)
  File "<pyshell#31>", line 5, in avg
    count += 1
UnboundLocalError: local variable 'count' referenced before assignment

可是却又出错了?提示说明得很清楚:在局部变量赋值之前对其进行了引用。这是因为对于 int 类型变量,count += 1 等于 count = count + 1, count成为了avg的局部变量。而在之前我们使用的列表,并未进行赋值操作,因此values是自由变量。

解决这个问题,只要声明 count 和 total 为非局部变量即可。

def get_avg():
    count = 0
    total = 0
    def avg(value):
        nonlocal count, total
        count += 1
        total += value
        return total / count
    return avg

不用闭包实现avg函数

通常,在Python中使用可变数据作为函数默认参数会被认为是危险的,因为可变默认参数数据存储于function object的__default__属性中,一旦对其进行修改,默认值就不再是定义时的值了。但我们可以利用这点实现记忆化。

def avg(n, values=[]):
    values.append(n)
    return sum(values) / (len(values))

def avg(n, dic={"total":0, "count":0}):
    dic["count"] += 1
    dic["total"] += n
    return dic["total"] / dic["count"]

今天在使用 Vue.js 的列表渲染时,写了一个菲波那切数列函数,在输入数字 n 后,网页将渲染菲波那切数列的前 n 项,使用了ES6语法中的解构赋值,结果函数出现了一些问题:

function fibonacci(n) {
  var nums = []
  var a = b = 1
  for (let i = 0; i < n; i++) {
    [a, b] = [b, a + b]
    nums.push(a)
  }
  return nums
}

console.log(fibonacci(5))
// outputs: [1, 2, 3, 5, 8]

上述函数运行正常,然后我调换了其中两句代码的顺序,函数变成如下:

function fibonacci2(n) {
  var nums = []
  var a = b = 1
  for (let i = 0; i < n; i++) {
    nums.push(a)
    [a, b] = [b, a + b]
  }
  return nums
}

console.log(fibonacci2(5))
// outputs: [1, 1, 1, 1, 1]

函数并未返回预期的菲波那切数列,仔细检查了也没有发现语法错误,在Chrome和FireFox的开发者工具中以及node.js环境下运行都是输出[1, 1, 1, 1, 1]。最终还是在stackoverflow解决了问题:因为nums.push(a)后边没有加分号,于是语句被解析成了nums.push(a)[a, b] = [b, a + b],这是一个合法的JavaScript语句,却不能实现菲波那切数列,于是就出错了。

所以错误都是源于一个分号。

真正会导致上下行解析出问题的 token 有 5 个:括号,方括号,正则开头的斜杠,加号,减号。我还从没见过实际代码中用正则、加号、减号作为行首的情况,所以总结下来就是一句话:一行开头是括号或者方括号的时候加上分号就可以了,其他时候全部不需要。其实即使是这两种情况,在实际代码中也颇为少见。
——尤雨溪(Vue.js 作者)

1.冒泡排序

O(n) = n2

冒泡排序通过n-1趟比较,第i趟比较需进行n-i次比较,共需进行n(n-1)/2次比较, 时间复杂度为n2

def bubble_sort(table):
    length = len(table)
    for i in range(length-1):
        for j in range(length-1-i):
            if table[j] > table[j+1]:
                table[j], table[j+1] = table[j+1], table[j]

2.插入排序

O(n) = n2

插入排序在排序第i个数时,前i-1个数已经完成排序,插入后完成前i个数的排序。 最优情况下只需进行n-1次比较,时间复杂度O(n),平均时间复杂度n2

def insertion_sort(table):
    length = len(table)
    for i in range(length):
        j = i
        current = table[i]
        while j>0 and table[j-1]>current:
            table[j] = table[j-1]
            j -= 1
        table[j] = current

3.希尔排序

(最优)O(n) = nlog2n

希尔排序基于以下事实:插入排序对已排序表效率较高。按照从大到小不同的步长对表进行 插入排序即实现了希尔排序。根据步长不同时间复杂度不同,目前已知最优步长由Sedgewick 提出 : (1, 5, 19, 41, 109,...)

def shell_sort(table, steps = [109, 41, 19, 5, 1]):
    length = len(table)
    for step in steps:
        for i in range(step, length):
            j = i
            current = table[i]
            while j >= step and table[j-step] > current:
                table[j] = table[j-step]
                j -= step
            table[j] = current

4.快速排序

(平均)O(n) = nlogn

快速排序首先选择一个项,将小于该项的置于左侧,大于该项的置于右侧,然后分别对 左右两侧进行快速排序。快速排序效率很高。

影响快速排序的一个因素是中枢项的选择。如果选择首个项作为中枢项,那对一个排序 较好的表进行快速排序效率将十分低下,因此选用首、尾、中间三项中间值作为中枢项。

def quick_sort(table, left=0, right=None):
    if right == None:
        right = len(table) - 1
    center = (left+right) //2
    # 选择中枢项
    if table[left] > table[center]:
        table[left], table[center] = table[center], table[left]
    if table[center] > table[right]:
        table[center], table[right] = table[right], table[center]
    if table[left] > table[center]:
        table[left], table[center] = table[center], table[left]
    # 如果表大小小于3,到此已完成排序
    if right-left <= 2:
        return
    # 将中枢项置于表倒数第二个项
    table[center], table[right-1] = table[right-1], table[center]
    pivot = table[right-1]

    i = left
    j = right - 1

    while True:
        i += 1
        j -= 1
        # 从左开始找到大于中枢项的项
        while table[i] < pivot:
            i += 1
        # 从右开始找到小于中枢项的项
        while table[j] > pivot:
            j -= 1
        # 如果小项位于大项右侧,交换两项
        if i < j:
            table[i], table[j] = table[j], table[i]
        else:
            break
    # 以中枢项为界,左侧均小于中枢项,右侧均大于中枢项。
    table[i], table[right-1] = table[right-1], table[i]
    # 分别对左右区进行快速排序
    quick_sort(table, left, i-1)
    quick_sort(table, i+1, right)

5.归并排序

O(n) = nlogn

归并排序需要额外的O(n)空间复杂度。

def merge_sort(table, left=0, right=None):
    if right == None:
        right = len(table) - 1
    # 单个项直接返回
    if right-left < 1:
        return
    middle = (left+right)//2
    # 先将表分为左右两区,分别对左右两区实现排序。
    merge_sort(table, left, middle)
    merge_sort(table, middle+1, right)
    # 然后合并左右两区
    i = left
    j = middle + 1
    current = left
    sortedTable = []
    while current <= right:
        # 如果右侧表已全部归并完成 或 左侧表最小项小于右侧表最小项,且左侧表还未归并完成
        if j > right or (table[i]<table[j])  and i <= middle:
            sortedTable.append(table[i])
            i += 1
        else:
            sortedTable.append(table[j])
            j += 1
        current += 1
    table[left:right+1] = sortedTable

6.堆排序

O(n) = nlogn

利用Python内置模块heapq可以快速实现堆排序,不过为了完整实现,此处将首先实现堆数据结构,此处默认是优先队列,即根部为最小元素。堆排序需要O(n)的空间复杂度。

堆的实现

class Min:
    '''作为最小根元素'''
    def __lt__(self, other):
        return True
    def __gt__(self, other):
        return False
    def __repr__(self):
        return '-'
class Heap:
    '''堆的实现'''
    def __init__(self, values=None):
        self.nodes = [Min()]
        if values != None:
            for value in values:
                self.insert(value)
    @property
    def size(self):
        return len(self.nodes)-1
    def findMin(self):
        return self.nodes[1]
    def insert(self, newValue):
        self.nodes.append(newValue)
        i = self.size
        while self.nodes[i] < self.nodes[i//2]:
            self.nodes[i], self.nodes[i//2] = self.nodes[i//2], self.nodes[i]
            i = i//2
    def deleteMin(self):
        i = 1
        last = self.nodes[self.size]
        while 2*i <= self.size:
            if 2*i+1 <= self.size:
                smaller = 2*i if self.nodes[2*i] < self.nodes[2*i+1] else 2*i+1
            else:
                smaller = 2*i
            if self.nodes[smaller] < last:
                self.nodes[i], self.nodes[smaller] = self.nodes[smaller], self.nodes[i]
                i = smaller
            else:
                break
        self.nodes[i], self.nodes[self.size] = last, self.nodes[i]
        return self.nodes.pop()

堆排序

def heap_sort(table):
    heaptable = Heap(table)
    table[:] = [heaptable.deleteMin() for _ in range(heaptable.size)]

7.神奇的猴子排序

O(n) = n·n!

既然猴子连莎士比亚的作品都能写出来,排个序应该也不是大问题 :-)。

import random
def monkey_sort(table):
    while not all(table[i] <= table[i+1] for i in range(len(table) - 1)):
        random.shuffle(table)

8.各排序算法性能比较

测试环境:

  • windows 10 专业版 x64
  • Intel(R) Core(TM) i7 2.50GHz
  • 12GB
  • Python3.5.2 x64

分析:

# 希尔排序使用步长序列[16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1]
sorts = [bubble_sort, insertion_sort, shell_sort, quick_sort, merge_sort, heap_sort]
def check(n):
    print("# 大小为", n, "的列表排序\n")
    print("# {0:<16}{1:<7}".format("排序算法", "用时"))
    l = [random.randint(0, n) for _ in range(n)]
    for sort in sorts:
        cl = l[:]
        t0 = time.time()
        sort(cl)
        t1 = time.time()
        print("{0:<20}{1:<7.5f}s".format(sort.__name__, t1-t0))
    t2 = time.time()
    sl = sorted(l)
    t3 = time.time()
    print("{0:<20}{1:<7.5f}s".format('tim_sort', t3-t2))

>>> check(1000)
# 大小为 1000 的列表排序

# 排序算法            用时 
bubble_sort         0.11205s
insertion_sort      0.08113s
shell_sort          0.00490s
quick_sort          0.00781s
merge_sort          0.02362s
heap_sort           0.03619s
tim_sort            0.00097s

>>> check(10000)
# 大小为 10000 的列表排序

# 排序算法            用时 
bubble_sort         13.63518s
insertion_sort      8.40691s
shell_sort          0.05669s
quick_sort          0.02346s
merge_sort          0.08884s
heap_sort           0.16795s
tim_sort            0.00293s

# 冒泡与插入排序时间上涨过快,后续将不再分析这两个排序算法

>>> check(100000)
# 大小为 100000 的列表排序

# 排序算法            用时 
shell_sort          0.80093s
quick_sort          0.43970s
merge_sort          0.84578s
heap_sort           3.01096s
tim_sort            0.03910s

>>> check(500000)
# 大小为 500000 的列表排序

# 排序算法            用时 
shell_sort          6.46414s
quick_sort          2.54591s
merge_sort          4.98013s
heap_sort           15.10598s
tim_sort            0.31891s

可见快速排序在数据量较大时明显优于其他排序算法,而Python内置timsort则明显优于未经优化的快速排序。


参考: