算法是决定代码运行速度的重要原因,将一个指数复杂度或者O(n2)复杂度的流程简化为线性复杂度可以为性能带来质的提升。选择合适的算法后,同样有一些可以进行优化的地方,本文简要探讨一些算法优化手段。代码示例采用Python,但思路适用于各种语言。

减少每次循环执行的操作

假如我们要遍历列表nums的元素,执行一些操作dosth,如果使用while循环:

# 循环一
i = 0
while i < len(nums):
    dosth(nums[i])
    i += 1

上述循环执行过程中,每次都要执行:

  • 计算nums的长度
  • i与计算结果进行比较
  • 真值判断:将比较结果与True进行比较
  • 获得nums[i]的值
  • nums[i]执行操作
  • i加1

实际上nums的长度在这个过程中是不变的,根本没有必要每次都进行计算,因此代码可以改为:

# 循环二
i = 0
j = len(nums)
while i < j:
    dosth(nums[i])
    i += 1

这样每次循环过程中就不必计算nums的长度了。同时,很多情况下我们并不在意循环是从前往后还是从后往前,这个时候我们就可以利用语言特性省略while条件判断中的比较操作:

# 循环三
i = len(nums)
while i:
    dosth(nums[i-1])
    i -= 1

由于Python将0以外的数字视为True,这样也就省略了每次的比较操作,但还有一个对i的操作,是否也可以省略掉呢?我们应该使用for循环:

# 循环四
for num in nums:
    dosth(num)

到这里,每次循环执行的操作就只剩下:

  • 获得num的值
  • num执行操作

减少每次循环的操作可有效优化代码,但是当循环复杂度大于O(n)时,减少循环次数就是优化代码的更有效方法了,这时我们应该优先减少循环的复杂度。

优化条件语句

如果我们对一个数据呈正态分布的列表数据scores进行处理,用条件语句的话:

if score < 60:
    print('不及格')
elif 60 < score < 90:
    print('良好')
else:
    print('优秀')

由于数据呈正态分布,大部分score分布在60-90之间,对这些数据,每次处理之前都要进行三次比较,通过将大概率语句放置在前边可有效减少比较操作:

if 60 < score < 90:
    print('良好')
elif score > 90:
    print('优秀')
else:
    print('不及格')

另一个优化条件语句的方式是使用嵌套条件语句,比如如下的代码:

if score < 40:
    print('惨不忍睹')
elif score < 60:
    print('还需努力')
elif score < 80:
    print('马马虎虎')
else:
    print('非常优秀')

这个表达式中,最多需要进行3次判断,我们用嵌套语句改造这段代码:

if score < 60:
    if score < 40:
        print('惨不忍睹')
    else:
        print('还需努力')
else:
    if score < 80:
        print('马马虎虎')
    else:
        print('非常优秀')

改造后的代码,最多只需要2次条件判断。它的思路就是二分法。但是如果嵌套太多的话,代码的可读性会大打折扣。

递归

初学编程的时候,当我用写出第一个斐波那契数列计算函数后:

# 条件语句一
def fib(n):
    if n <= 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

满心欢喜地敲入

fib(100)

然后我就发现解释器直接进入无响应状态。仔细想想,为了计算fib(100),需要调用fib函数的次数为 2100 级别,(作为对比,可观测宇宙内的恒星数量大概在 273 ~ 280)。

记忆化

仔细观察就发现,这个算法进行了大大大大大量的重复计算,如果我们将计算结果缓存起来,避免重复计算,就可以大大提升效率:

def fib(n, values={1: 1, 2: 2}):
    if n not in values:
        values[n] = fib(n-1) + fib(n-2)
    return values[n]

然后执行:

fib(100)
fib(1000)

都可以瞬间计算,但是

fib(3000)

RecursionError: maximum recursion depth exceeded

出现了递归错误,在没有数据缓存的时候,计算fib(3000)仍然要递归调用到fib(1),调用深度太深。

使用迭代

递归操作是可以转为迭代操作的,如下是迭代版本的斐波那契数列函数:

def fib(n):
    a = b = 1
    for _ in range(n):
        a, b = b, a+b
    return a

这个函数的算法复杂的为O(n),即便计算fib(10000),也只需要进行10000(约213)次操作。

C中的连续赋值

在 C 中,连续赋值执行顺序是从右到左,如下边语句:

a = b = c = 3

其实相当于

a = (b = (c = 3))

首先执行c = 3,该表达式的值为 3,然后执行b = (c = 3);b赋值为 3,该表达式值为 3;最后执行a = (b = (c = 3)),a 赋值为 3。

Python中的连续赋值问题

长期以来我都将 Python 中的连续赋值以上述方法对待,但其实并不是这样的。看下边这段代码:

foo = [0]
bar = foo
foo[0] = foo = [1]

print(foo)
print(bar)

如果按 C 中的连续赋值处理方式进行处理,那么在连续赋值语句中将:

  • 首先执行foo = [1],结果就是foo指向了一个新建的对象,而barfoo原对象的一个引用,bar值将保持原值([0])

  • 然后执行foo[0] = (foo = [1])也即foo[0] = [1]

结果应该是输出

[[1]]
[0]

而实际输出确是

[1]
[[1]]

Python连续赋值研究

那么到底是怎么回事呢,借助dis模块我们来一探究竟:

>>> import dis
>>> dis.dis('foo[0] = foo = [1]')
  1         0 LOAD_CONST               0 (1)
            3 BUILD_LIST               1
            6 DUP_TOP
            7 LOAD_NAME                0 (foo)
           10 LOAD_CONST               1 (0)
           13 STORE_SUBSCR
           14 STORE_NAME               0 (foo)
           17 LOAD_CONST               2 (None)
           20 RETURN_VALUE

注意这几行

  • 6 DUP_TOP将构建的列表在栈顶复制了一份

  • 13 STORE_SUBSCR14 STORE_NAME 0 (foo): python首先执行的是将栈顶的 [1] 赋值给 foo[1],而 foo 正是原对象,然后才将另一个 [1] 赋值给 foo, 结果就是原对象(同时也是 bar 指向的对象)变成了 [[1]] 然后 foo 被赋予新值 [1]。

所以 Python 中的连续赋值其实是下边的顺序:

  • 首先构建要赋值的对象

  • 将对象在栈顶进行一份复制,然后将复制的值赋给第一个变量

  • 将对象在栈顶进行一份复制,然后将复制的值赋给第二个变量

  • ……

  • 将对象赋值给最后一个变量

整个赋值是从左向右的。

ps:交换变量赋值

顺便看一下交换变量赋值的原理

>>> dis.dis('a, b = b, a')
  1           0 LOAD_NAME                0 (b)
              3 LOAD_NAME                1 (a)
              6 ROT_TWO
              7 STORE_NAME               1 (a)
             10 STORE_NAME               0 (b)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE
  • 首先将变量 b 的值推入栈

  • 然后将变量 a 的值推入栈

  • 交换栈顶的两元素(结果是 b 的值位于栈顶)

  • 栈顶的值(b)赋值给变量 a

  • 栈顶的值(a)赋值给变量 b

参考


框架中的网格布局

在框架中使用网格系统(Bootstrap):

<!-- Stack the columns on mobile by making one full-width and the other half-width -->
<div class="row">
  <div class="col-xs-12 col-md-8">.col-xs-12 .col-md-8</div>
  <div class="col-xs-6 col-md-4">.col-xs-6 .col-md-4</div>
</div>

问题:

  • 基于特定框架,也就是必须要使用框架才能使用网格布局

  • 基于文档结构 + 类名而不是由 CSS 来控制布局

使用 CSS 模拟网格布局

浮动布局

  • 固定宽度的网格。问题是宽度固定,不能随设备尺寸改变而自适应。而且必须计算每个元素所占宽度。

  • 流式网格。使用百分比来进行表示,同样需要大量计算。

弹性盒子?

弹性盒子的问题也是一个一维的布局,是用来处理一条线上(行或者列)的布局的。

CSS 原生网格

CSS 即将可以原生支持网格布局,目前版本的 Chrome(56) 和 Firefox(51)默认还未支持,接下来的版本即将支持。完整的支持列表可以看这里

相关学习资料

我们都知道在函数体内使用yield关键字将会使函数返回一个生成器对象,在英文字典中,yield不仅有“生产”(produce)的意思,还有“屈服,让步”(give way)的意思,因此python最开始也使用了生成器的关键字yield来处理协程(coroutine)。但是不同的是,协程中yield关键字通常出现于表达式的右侧,例如received = yield value;协程不仅可以生成数据(或者不生成数据),也可以接收数据。理解协程中的yield,要把yield看做是用来执行控制流的,而不是生成数据的。

python协程的历史

python协程最早的实现是在python2.5中,自此可以在表达式中使用yield关键字了,同时为生成器实现了.send(value)方法用于向yield表达式传递数据,.throw()方法用于抛出异常,.close()方法用于终结。具体描述在PEP 342中。

之后由于嵌套生成器的缘故,在python3.3中实现对协程进行了改进(见PEP 380):

  • 生成器现在可以返回值了,之前在生成器内返回值会触发SyntaxError

  • 新的yield from语法使得复杂的、嵌套的生成器代码更加简洁。

使用同一个关键字很容易让人迷惑,因此在python3.5,python借鉴了其他语言,添加了两个新的关键字asyncawait用来处理协程,使得协程代码更容易让人理解。

初步了解协程

>>> def simple_coroutine():
    print("What's your name?")
    name = yield
    print("Hello", name, ", where are you from?")
    nation = yield
    print("OK, I see")

##############################
>>> coro = simple_coroutine()
>>> coro
<generator object simple_coroutine at 0x01156480>       #1
>>> next(coro)                                          #2
What's your name?
>>> coro.send("Li Yan")                                 #3
Hello Li Yan , where are you from?
>>> coro.send("China")
OK, I see
Traceback (most recent call last):                      #4
  File "<pyshell#79>", line 1, in <module>
    coro.send("China")
StopIteration

#1显示,调用函数返回的是一个生成器对象。#2使用next()方法是因为生成器此时还未启动,它并未在一个yield等待因此我们还不能向它传递数据,调用next()后生成器就会启动。#3我们调用生成器的.send()方法,使得协程内yield等于'Li Yan',然后协程继续运行,直到再次遇到yield或者自身终止。#4处协程(生成器)运行到了最后,就如生成器一般表现一样,触发了StopIteration错误。

协程的四个状态

每个协程可能处于四个状态,我们来观察一下:

>>> from inspect import getgeneratorstate
>>> coro = simple_coroutine()
>>> getgeneratorstate(coro)
'GEN_CREATED'
>>> next(coro)
What's your name?
>>> getgeneratorstate(coro)
'GEN_SUSPENDED'
>>> coro.send('Li Yan')
Hello Li Yan , where are you from?
>>> getgeneratorstate(coro)
'GEN_SUSPENDED'
>>> coro.send('China')
OK, I see
Traceback (most recent call last):
  File "<pyshell#92>", line 1, in <module>
    coro.send('China')
StopIteration
>>> getgeneratorstate(coro)
'GEN_CLOSED'

除了'GEN_CREATED','GEN_SUSPENDED','GEN_CLOSED',还有'GEN_RUNNING',不过我们很少观察到此状态。

上述整个过程运行流程如下:

通过coro = simple_coroutine()我们得到了一个协程(生成器),此时它处于'GEN_CREATED'状态,我们还不能向它传递值,通过调用next(coro)启动协程,直到运行到yield暂停,等待我们传入数据,coro.send('Li Yan')使yield赋值为'Li Yan',name获得值'Li Yan',并继续运行直到下一个yield,在我们传入数据'China'之后,nation获得值'China'并继续运行,直到触发了StopIteration,此时协程处于'GEN_CLOSED'状态。

使用协程实现平均数函数

Python中的闭包与局部作用域一文中,我们使用闭包实现了一个平均数函数,每次接收一个参数,返回之前每次调用传给它的所有参数的平均值。这里我们用协程来实现

def averager():
    total = 0
    count = 0
    average = None
    while True:
        new = yield average
        total += new
        count += 1
        average = total / count

####################
>>> avg = averager()
>>> next(avg)
>>> avg.send(10)
10.0
>>> avg.send(11)
10.5

使用协程,我们不必使用闭包,也不必声明非局部变量(nonlocal)。但是这个协程是个无限循环,所以我们应该如何停止该协程呢?

协程终止与异常处理

要终止一个协程,最直接的办法是传递一个错误的参数(例如向avg传递一个字符串),协程内部触发错误而未得到处理,协程就将终止。

>>> avg.send('foo')
Traceback (most recent call last):
  File "<pyshell#110>", line 1, in <module>
    avg.send('foo')
  File "<pyshell#103>", line 7, in averager
    total += new
TypeError: unsupported operand type(s) for +=: 'int' and 'str'
>>> getgeneratorstate(avg)
'GEN_CLOSED'

自python2.5引入.throw().close()方法后,可以更方便地控制协程了,

def averager():
    total = 0
    count = 0
    average = None
    while True:
        new = yield average
        try:
            total += new
            count += 1
        except TypeError:
            print('Wrong value')
        else:
            average = total / count

#####################
>>> avg = averager()
>>> next(avg)
>>> avg.send(10)
10.0
>>> avg.send('foo')
Wrong value
10.0
>>> avg.send(11)
10.5
>>> avg.close()
>>> getgeneratorstate(avg)
'GEN_CLOSED'

使协程返回值

对于上述平均数函数,我们可能并不关心中间每次计算的平均数,而只关心最终的平均数,自python3.3后,协程可以返回特定值了。

def averager2():
    total = 0
    count = 0
    average = None
    while True:
        new = yield
        if new == None:
            break
        total += new
        count += 1
        average = total / count
    return {'count': count, 'average': average}

#########################
>>> avg2 = averager2()
>>> next(avg2)
>>> avg2.send(10)
>>> avg2.send(11)
>>> avg2.send(12)
>>> avg2.send(None)
Traceback (most recent call last):
  File "<pyshell#143>", line 1, in <module>
    avg2.send(None)
StopIteration: {'count': 3, 'average': 11.0}

我们使用avg2.send(None)终止协程,并希望返回一个携带数据的字典,但我们看到数据最终是作为StopIteration错误的值返回的。那么我们如何获得返回的值呢?

>>> try:
    avg2.send(None)
except StopIteration as exc:
    data = exc.value

>>> data
{'count': 3, 'average': 11.0}

为了获得协程返回的数据,这是一个迂回的办法,幸好PEP 380yield from可以自动帮我们处理这种情况:使用yield from,解释器不仅自动处理了StopIteration,并且是StopIterationvalue属性成为yield from表达式的值。这就像是使用for来处理可迭代对象(Iterable)一样。

使用 yield from

生成器中的 yield from

如果只是用于产生值,yield from 可以更直观地替代 for 循环中的 yield,例如:

def gen():
    for c in 'ABCDE':
        yield c

可以写作:

def gen():
    yield from 'ABCDE'

如果 yield from 只是作为一个语法糖类似的功能的话,python 可能也不会接受它作为新的语言特性。它真正的作用是delegating generator :最外层的 caller(PEP380 使用的术语,指调用 delegating generator 的对象) 传递数据给 delegating generator ,实际上通过 delegating generator 传递给了subgenerator,而 subgenerator 生成的数据反过来通过 delegating generator 传递回 caller。

如果 subgenerator 有返回值,则 delegating generator 会自动处理StopIteration,并将返回值赋予 yield from 表达式。

# 作为 subgenerator 
def averager():
    '''上一节介绍的平均协程程序,此处为 subgenerator '''
    total = 0
    count = 0
    average = None
    while True:
        # caller 传递的数据将传递到这里
        new = yield
        # 用于终结 while 循环
        if new == None:
            break
        total += new
        count += 1
        average = total / count
    # 生成器返回值
    return {'count': count, 'average': average}

#  delegating generator 
def grouper(results, key):
    ''' delegating generator '''
    while True:
        # 所有从 caller 传递的数据都通过 yield from 传递给 subgenerator 
        # 直到 subgenerator 停止并返回,返回值将赋值给result[key]
        results[key] = yield from averager()

# caller
def main(data):
    '''客户端代码,也就是 caller'''
    results = {}
    for key, values in data.items():
        # group 是一个生成器对象,可以像协程一样操作它
        group = grouper(results, key)
        # 启动协程
        next(group)
        for value in values:
            # 传递数据,数据将传递到 new = yield, grouper 不会接触到改数据
            group.send(value)
        # 结束 subgenerator ,使 delegating generator 继续运行
        group.send(None)
    report(results)

def report(results):
    for key, result in results.items():
        group, unit = key.split(';')
        print('{:2} {:5} averaging {:.2f}{}'.format(
            result['count'], group, result['average'], unit
        ))

data = {
    'girls;kg':
        [40.9, 38.5, 44.3, 42.2, 45.2, 41.7, 44.5, 38.0, 40.6, 44.5],
    'girls;m':
        [1.6, 1.51, 1.4, 1.3, 1.41, 1.39, 1.33, 1.46, 1.45, 1.43],
    'boys;kg':
        [39.0, 40.8, 43.2, 40.8, 43.1, 38.6, 41.4, 40.6, 36.3],
    'boys;m':
        [1.38, 1.5, 1.32, 1.25, 1.37, 1.48, 1.25, 1.49, 1.46],
}

# 运行上述代码
>>> main(data)
 9 boys  averaging 1.39m
10 girls averaging 42.04kg
 9 boys  averaging 40.42kg
10 girls averaging 1.43m

描述一下整个 main 函数运行流程:

  • 每个外层 for 循环生成一个新的 grouper 实例,也就是 delegating generator
  • next(group) 启动 delegating generator ,并在调用 subgenerator 之后在 yield from 处暂停
  • 内层 for 循环直接将数据传递给 subgenerator ,与此同时 delegating generator 仍在 yield from 处暂停
  • 当内层 for 循环结束时,group仍然在 yield from 处暂停,所以results[key]赋值还未完成
  • 传递 None 给 delegating generator (实际上传递给了 subgenerator )以终结 subgenerator ,并使 delegating generator 继续运行,完成赋值
  • 外层 for 循环继续运行,生成新的 grouper 实例,上一个 grouper 被垃圾回收

TO BE CONTINUED


参考


我的首个微信小程序尝试,以及一点看法。

小程序开发

微信小程序的代码架构还是比较清晰的,根目录下 app.js 用于注册小程序,app.json 是小程序的配置文件, app.wxss 是样式表文件。

简单起见,我就选择了MovieRank这个项目,一是后端 API 和前端结构都是现成的。

在 pages 文件夹内创建 index 文件夹用于起始页面(也就只有这一个页面),然后在 app.json 的 pages 中注册页面"pages": ["pages/index/index"],index.wxml 类似于 html 文档, index.js 可通过 Page 函数注册页面,该函数接收一个对象参数,指定页面初始数据、生命周期函数、事件处理函数等。 index.wxss 是样式表文件,兼容大部分 CSS 语法。

由于小程序的 API 比较类似 Vue.js,所以整个开发过程配合查看官方 API 很快就完成了,这是结果:

主页面:

index

条件选择:

picker

初试感受

由于只是初次尝试,大部分功能还未熟悉,只谈一谈初试的感受:

  • 结构和逻辑清晰,可以集中精力到逻辑层面的开发。

  • 不支持其他框架扩展。这一点可能也是好处,可以统一小程序兼容性与用户体验。

  • 不支持个人开发者注册,不知道后续会不会开放。

  • 一点不足:目前的主流前端框架(Vue.js, AngularJS)大多使用双向数据绑定,小程序是单向数据绑定,通过事件侦听来处理视图层的数据改变,因此可能需要编写很多事件处理函数。

小程序(Web App)与 Native App

小程序正式发布当天,很多人宣称可以卸载本地 App 了,又有人说小程序不可能取代 App。小程序的优点是无需下载,随开随用,不占内存,其本质是一个 Web App。而关于Web App,Google 多年前就有 Chrome App,甚至还有主要运行 Web App 的操作系统 Chrome OS。Chrome Store 上也有成千上万的 App,可在去年8月 Google 却宣布将在接下来两年停止对 Chrome App 的支持,鼓励开发者将 Chrome App 搬迁到 Web 上。但这个停止支持其实是随着技术进步,标准的统一,Google 鼓励去开发跨浏览器、兼容性更好的 Web App:Progressive Web Apps

Progressive Web Apps 是结合了 web 和 原生应用中最好功能的一种体验。对于首次访问的用户它是非常有利的, 用户可以直接在浏览器中进行访问,不需要安装应用。随着时间的推移当用户渐渐地和应用建立了联系,它将变得越来越强大。它能够快速地加载,即使在比较糟糕的网络环境下,能够推送相关消息, 也可以像原生应用那样添加至主屏,能够有全屏浏览的体验。
- 你的首个 Progressive Web App

未来如何不敢妄言,但小程序以及 Progressive Web App 肯定会促进 Web 技术的发展,Web App 也肯定会有越来越好的体验。

ps:源码

参考