将点序列重组为“开始-结束”对组成的序列,是常用的数据处理步骤:根据已有序列 S={s0,s1,s2,…sn},生成对序列
源数据中的第一个元素和第二个元素组成第一对,第二个元素和第三个元素组成第二对,以此类推。进行时域分析时,往往要合并间隔很大的数据,但这里合并相邻的数值就行了。
有了对序列,就可以利用haversine
函数计算出每对中两点间的距离,在地理位置应用中常用这项技术把一条路径上的点转换为一系列线段。
为什么将序列元素组对,而不做如下处理:
begin = next(iterable)
for end in iterable:
compute_something(begin, end)
begin = end
显然,这样也可以将每段数据作为一个“开始-结束”对来处理,但这种方式将处理函数和重组数据的循环紧密绑定在一起了,使得代码难以复用。由于与compute_something()
函数绑定在一起,算法很难单独测试组。
这种组合方式也使得开发者难以修改应用的配置,无法简单地用其他实现代替compute_something()
函数。另外,显式状态和begin
变量的存在使得未来可能的重构复杂化了。当我们想在循环体中增加新特性时,如果去掉其中某个点,很可能导致begin
变量设置错误,包含if
语句的filter()
函数也会导致begin
变量更新出现故障。
为了保证代码可复用,需要把这个简单的组对函数独立出来。长远来看,这符合设计目标:把有用的基础函数(例如这里的组对函数)放在单独的库里,便于我们更快、更有把握地解决遇到的问题。
有很多种方法可以把一条路径上的所有点处理成“开始-结束”形式,下面介绍其中几种方法:
沿着一条路径依次将各个点组对的一个版本如下:
from typing import Iterator, Any
Item_Iter = Iterator[Any]
Pairs_Iter = Iterator[Tuple[float, float]]
def pairs(iterator: Item_Iter) -> Pairs_Iter:
def pair_from(
head: Any,
iterable_tail: Item_Iter) -> Pairs_Iter:
nxt= next(iterable_tail)
yield head, nxt
yield from pair_from(nxt, iterable_tail)
try:
return pair_from(next(iterator), iterator)
except StopIteration:
return iter([])
其核心部分是内部函数pair_from()
,它的参数是可迭代对象的第一个元素和它自身。首先从第二个参数,即可迭代对象中拿出头元素,与第一个参数组成一对作为结果返回,再递归调用自身,返回剩余的数据对。
类型标示要求参数iterator
的类型是Item_Iter
,返回结果的类型是Pairs_Iter
,即元素类型为float
的二元组组成的迭代器。mypy工具通过检查类型标示确保代码可以正常运行。类型标示是在typing
模块中定义的。
输入必须是实现了next()
函数的迭代器,为了处理集合数据,需要使用iter()
函数显式地将集合转换为迭代器。
pairs()
函数内调用了pair_from()
函数,pairs()
负责从参数中得到初始值。当输入参数是空迭代器时,next()
函数的第一次调用将生成一个StopIteration
异常,然后返回一个空的可迭代对象。
Python的迭代递归使用
for
循环处理数据并从递归中返回结果。如果使用看上去更简单的return pair_from(nxt, iterable_tail)
方法,你会发现它不能正确地处理可迭代对象并返回所有值。生成器函数中的递归需要使用yield
从可迭代对象中获取结果,这里使用的是yield from recursive_iter(args)
。如果改用return recursive_iter(args)
,将会返回生成器对象,而不是对函数求值并返回生成的结果。
如果希望使用尾调用优化,可以用生成器表达式代替递归,用for
循环优化递归,下面的函数是沿着路径依次组对的另一个版本:
from typing import Iterator, Any, Iterable, TypeVar
T_ = TypeVar('T_')
Pairs_Iter = Iterator[Tuple[T_, T_]]
def legs(lat_lon_iter: Iterator[T_]) -> Pairs_Iter:
begin = next(lat_lon_iter)
for end in lat_lon_iter:
yield begin, end
begin = end
这个版本的实现处理速度非常快,且不受栈长度限制。它可以处理任何类型的序列,将序列生成器给出的值组对。由于循环体内部没有处理函数,需要时即可复用legs()
函数。
通过TypeVar
函数定义的类型变量T_
用于准确描述legs()
函数重组数据的方式。类型标示指出输入类型决定了输出类型。输入类型是某种类型T_
组成的迭代器,与输出元组的元素类型必须一致,并且不涉及其他转换。
begin
和end
变量保存计算状态,使用有状态变量不符合函数式编程尽量使用不可变数据的要求,因此需要进一步优化。此外,它对函数的使用者是不可见的,是一种Python式混合实现风格。
该函数能生成如下对序列:
list[0:1], list[1:2], list[2:3], ..., list[-2:]
该函数的功能也可表示如下:
zip(list, list[1:])
最后这种表达方式虽然很直观,但只能用于序列对象,而legs()
和pairs()
函数适用于任何可迭代对象,包括序列对象。