加快在Python中将string配对成对象

我试图find一种有效的方法将包含整数点的数据行组合在一起,并将它们存储为Python对象。 数据由XY坐标点组成,用逗号分隔的string表示。 如(x_1, y_1), (x_2, y_2), ...等等必须配对,然后存储为一个对象列表,其中每个点是一个对象。 下面的函数get_data生成这个示例数据:

 def get_data(N=100000, M=10): import random data = [] for n in range(N): pair = [[str(random.randint(1, 10)) for x in range(M)], [str(random.randint(1, 10)) for x in range(M)]] row = [",".join(pair[0]), ",".join(pair[1])] data.append(row) return data 

我现在的parsing代码是:

 class Point: def __init__(self, a, b): self.a = a self.b = b def test(): import time data = get_data() all_point_sets = [] time_start = time.time() for row in data: point_set = [] first_points, second_points = row # Convert points from strings to integers first_points = map(int, first_points.split(",")) second_points = map(int, second_points.split(",")) paired_points = zip(first_points, second_points) curr_points = [Point(p[0], p[1]) \ for p in paired_points] all_point_sets.append(curr_points) time_end = time.time() print "total time: ", (time_end - time_start) 

目前,这要花费将近7秒钟的时间,十万分之一,这似乎效率很低。 部分效率低下似乎源于计算first_pointssecond_pointspaired_points – 并将其转换为对象。

效率低下的另一部分似乎是build立all_point_sets 。 取出all_point_sets.append(...)行似乎使代码从大约7秒变成2秒!

这怎么能加快呢? 谢谢。

跟随感谢大家的伟大的build议 – 他们都是有益的。 但即使进行了所有改进,处理100,000个条目仍然需要3秒左右的时间。 我不确定为什么在这种情况下,这不仅仅是瞬间的,而且是否有其他表示方式可以立即使用。 在Cython中编码会改变什么? 有人可以提供一个例子吗? 再次感谢。

简单地运行与pypy有很大的不同

 $ python pairing_strings.py total time: 2.09194397926 $ pypy pairing_strings.py total time: 0.764246940613 

禁用gc没有帮助pypy

 $ pypy pairing_strings.py total time: 0.763386964798 

命名为“点”的组合更糟糕

 $ pypy pairing_strings.py total time: 0.888827085495 

使用itertools.imap和itertools.izip

 $ pypy pairing_strings.py total time: 0.615751981735 

使用int和迭代器的memoized版本来避免压缩

 $ pypy pairing_strings.py total time: 0.423738002777 

这是我完成的代码。

 def test(): import time def m_int(s, memo={}): if s in memo: return memo[s] else: retval = memo[s] = int(s) return retval data = get_data() all_point_sets = [] time_start = time.time() for xs, ys in data: point_set = [] # Convert points from strings to integers y_iter = iter(ys.split(",")) curr_points = [Point(m_int(i), m_int(next(y_iter))) for i in xs.split(",")] all_point_sets.append(curr_points) time_end = time.time() print "total time: ", (time_end - time_start) 

在处理大量对象的创build时,通常可以使用的最大性能增强是closures垃圾回收器。 每一代对象,垃圾回收器遍历内存中的所有活动对象,寻找周期中的一部分但不被活动对象指向的对象,因此符合回收内存的条件。 有关信息,请参阅Doug Helmann的PyMOTW GC文章 (更多信息可能会在Google和某些确定中find)。 垃圾收集器默认每700个左右的对象创build但不是回收,随后的几代运行时间稍微减less(我忘记了确切的细节)。

使用标准元组而不是Point类可以节省一些时间(使用一个namedtuple在两者之间),而巧妙的拆包可以节省一些时间,但是最大的收益可以通过在创build批次之前closuresgc来实现你知道的物体不需要被打开,然后再打开。

一些代码:

 def orig_test_gc_off(): import time data = get_data() all_point_sets = [] import gc gc.disable() time_start = time.time() for row in data: point_set = [] first_points, second_points = row # Convert points from strings to integers first_points = map(int, first_points.split(",")) second_points = map(int, second_points.split(",")) paired_points = zip(first_points, second_points) curr_points = [Point(p[0], p[1]) \ for p in paired_points] all_point_sets.append(curr_points) time_end = time.time() gc.enable() print "gc off total time: ", (time_end - time_start) def test1(): import time import gc data = get_data() all_point_sets = [] time_start = time.time() gc.disable() for index, row in enumerate(data): first_points, second_points = row curr_points = map( Point, [int(i) for i in first_points.split(",")], [int(i) for i in second_points.split(",")]) all_point_sets.append(curr_points) time_end = time.time() gc.enable() print "variant 1 total time: ", (time_end - time_start) def test2(): import time import gc data = get_data() all_point_sets = [] gc.disable() time_start = time.time() for index, row in enumerate(data): first_points, second_points = row first_points = [int(i) for i in first_points.split(",")] second_points = [int(i) for i in second_points.split(",")] curr_points = [(x, y) for x, y in zip(first_points, second_points)] all_point_sets.append(curr_points) time_end = time.time() gc.enable() print "variant 2 total time: ", (time_end - time_start) orig_test() orig_test_gc_off() test1() test2() 

一些结果:

 >>> %run /tmp/flup.py total time: 6.90738511086 gc off total time: 4.94075202942 variant 1 total time: 4.41632509232 variant 2 total time: 3.23905301094 

我会

  • 对这个问题使用numpy数组(如果这仍然不够快, Cython将是一个选项)。
  • 将点存储为一个vector,而不是单Point实例。
  • 依靠现有的parsing器
  • (如果可能的话)parsing数据一次,并将其存储为二进制格式,如hdf5进行进一步的计算,这将是最快的select(见下文)

Numpy内置了读取文本文件的函数,例如loadtxt 。 如果将数据存储在结构化数组中,则不一定需要将其转换为另一种数据types。 我将使用在numpy之上build立的图书馆pandas 。 处理和处理结构化数据更方便一些。 Pandas有自己的文件parsing器read_csv

为了计算时间,我把数据写到了一个文件中,就像你原来的问题(它是基于你的get_data )一样:

 import numpy as np import pandas as pd def create_example_file(n=100000, m=20): ex1 = pd.DataFrame(np.random.randint(1, 10, size=(10e4, m)), columns=(['x_%d' % x for x in range(10)] + ['y_%d' % y for y in range(10)])) ex1.to_csv('example.csv', index=False, header=False) return 

这是我用来读取pandas.DataFrame的数据的pandas.DataFrame

 def with_read_csv(csv_file): df = pd.read_csv(csv_file, header=None, names=(['x_%d' % x for x in range(10)] + ['y_%d' % y for y in range(10)])) return df 

(请注意,我假定文件中没有标题,所以我必须创build列名称。)

读取数据是快速的,它应该是更有效的内存(见这个问题 ),数据存储在一个数据结构中,你可以进一步使用一个快速,vector化的方式:

 In [18]: %timeit string_to_object.with_read_csv('example.csv') 1 loops, best of 3: 553 ms per loop 

在开发分支中有一个新的基于C的parsing器 ,在我的系统上需要414 ms。 你的testing在我的系统上花费的时间是2.29秒,但是它并没有真正的可比性,因为数据不是从文件中读取的,而是你创build的Point实例。

如果您曾经读过数据,可以将其存储在hdf5文件中:

 In [19]: store = pd.HDFStore('example.h5') In [20]: store['data'] = df In [21]: store.close() 

下一次你需要的数据,你可以从这个文件,这是非常快的读取它:

 In [1]: store = pd.HDFStore('example.h5') In [2]: %timeit df = store['data'] 100 loops, best of 3: 16.5 ms per loop 

但是,只有在多次需要相同的数据的情况下才适用。

在进行进一步的计算时,使用基于numpy的大数据集的数组将会具有优势。 如果你可以使用vector化的numpy函数和索引, Cython不一定会更快,如果你真的需要迭代,它会更快(参见这个答案 )。

更快的方法,使用Numpy(加速大约7倍 ):

 import numpy as np txt = ','.join(','.join(row) for row in data) arr = np.fromstring(txt, dtype=int, sep=',') return arr.reshape(100000, 2, 10).transpose((0,2,1)) 

性能比较:

 def load_1(data): all_point_sets = [] gc.disable() for xs, ys in data: all_point_sets.append(zip(map(int, xs.split(',')), map(int, ys.split(',')))) gc.enable() return all_point_sets def load_2(data): txt = ','.join(','.join(row) for row in data) arr = np.fromstring(txt, dtype=int, sep=',') return arr.reshape(100000, 2, 10).transpose((0,2,1)) 

load_1在我的机器上运行1.52秒; load_2运行时间为0.20秒,提高了7倍。 这里要注意的一点是,要求你(1)事先知道所有事物的长度,(2)每行都包含相同数量的点。 对于您的get_data输出,这是真实的,但对于您的真实数据集可能不是这样。

我通过使用数组获得了50%的改进,并且在访问时持久化构造了Point对象。 我也“开槽”Point对象以获得更好的存储效率。 但是,元组可能会更好。

如果可能的话,改变数据结构也可能有帮助。 但这永远不会是瞬间的。

 from array import array class Point(object): __slots__ = ["a", "b"] def __init__(self, a, b): self.a = a self.b = b def __repr__(self): return "Point(%d, %d)" % (self.a, self.b) class Points(object): def __init__(self, xs, ys): self.xs = xs self.ys = ys def __getitem__(self, i): return Point(self.xs[i], self.ys[i]) def test3(): xs = array("i") ys = array("i") time_start = time.time() for row in data: xs.extend([int(val) for val in row[0].split(",")]) ys.extend([int(val) for val in row[1].split(",")]) print ("total time: ", (time.time() - time_start)) return Points(xs, ys) 

但是,当处理大量数据时,我通常会使用numpy N维数组(ndarray)。 如果原始数据结构可能被改变,那么这可能是最快的。 如果它可以被结构化为线性读取x,y对,然后重新塑造ndarray。

  1. 使Point一个namedtuple (~10%加速):

     from collections import namedtuple Point = namedtuple('Point', 'a b') 
  2. 在迭代期间解压缩(加速〜2-4%):

     for xs, ys in data: 
  3. 使用map n argumentforms来避免zip(加速〜10%):

     curr_points = map(Point, map(int, xs.split(',')), map(int, ys.split(',')), ) 

鉴于点集合很短,发电机可能是矫枉过正的,因为它们具有较高的固定开销。

cython能够把速度提高5.5倍

 $ python split.py total time: 2.16252303123 total time: 0.393486022949 

这是我使用的代码

split.py

 import time import pyximport; pyximport.install() from split_ import test_ def get_data(N=100000, M=10): import random data = [] for n in range(N): pair = [[str(random.randint(1, 100)) for x in range(M)], [str(random.randint(1, 100)) for x in range(M)]] row = [",".join(pair[0]), ",".join(pair[1])] data.append(row) return data class Point: def __init__(self, a, b): self.a = a self.b = b def test(data): all_point_sets = [] for row in data: point_set = [] first_points, second_points = row # Convert points from strings to integers first_points = map(int, first_points.split(",")) second_points = map(int, second_points.split(",")) paired_points = zip(first_points, second_points) curr_points = [Point(p[0], p[1]) \ for p in paired_points] all_point_sets.append(curr_points) return all_point_sets data = get_data() for func in test, test_: time_start = time.time() res = func(data) time_end = time.time() print "total time: ", (time_end - time_start) 

split_.pyx

 from libc.string cimport strsep from libc.stdlib cimport atoi cdef class Point: cdef public int a,b def __cinit__(self, a, b): self.a = a self.b = b def test_(data): cdef char *xc, *yc, *xt, *yt cdef char **xcp, **ycp all_point_sets = [] for xs, ys in data: xc = xs xcp = &xc yc = ys ycp = &yc point_set = [] while True: xt = strsep(xcp, ',') if xt is NULL: break yt = strsep(ycp, ",") point_set.append(Point(atoi(xt), atoi(yt))) all_point_sets.append(point_set) return all_point_sets 

进一步探讨我可以近似地分解一些cpu资源

  5% strsep() 9% atoi() 23% creating Point instances 35% all_point_sets.append(point_set) 

如果cython能够直接从csv(或其他)文件中读取,而不是通过一个Python对象进行拖拽,那么可能会有一些改进。

你可以刮几秒钟:

 class Point2(object): __slots__ = ['a','b'] def __init__(self, a, b): self.a = a self.b = b def test_new(data): all_point_sets = [] for row in data: first_points, second_points = row r0 = map(int, first_points.split(",")) r1 = map(int, second_points.split(",")) cp = map(Point2, r0, r1) all_point_sets.append(cp) 

这给了我

 In [24]: %timeit test(d) 1 loops, best of 3: 5.07 s per loop In [25]: %timeit test_new(d) 1 loops, best of 3: 3.29 s per loop 

我间断地通过在all_point_sets预先分配空间来all_point_sets但这可能只是噪音。 当然,还有一种老式的做事方式:

 localhost-2:coding $ pypy pointexam.py 1.58351397514 

如何让你的坐标以.x.y属性被访问? 令我惊讶的是,我的testing表明,最大的单一时间接收器不是对list.append()的调用,而是Point对象的构造。 他们花了四倍的时间来构build一个元组,而且有很多。 在你的代码中简单地用一个元组(int(x), int(y))代替Point(int(x), int(y))超过执行时间的50%(Win XP上的Python 2.6)。 也许你现在的代码还有空间来优化呢?

如果您确实使用.x.y访问坐标,则可以尝试使用collections.namedtuple 。 它没有简单的元组快,但似乎比代码中的Pair类快得多(我是对冲的,因为单独的时序基准给了我奇怪的结果)。

 Pair = namedtuple("Pair", "xy") # instead of the Point class ... curr_points = [ Pair(x, y) for x, y in paired_points ] 

如果你需要走这条路线,那么从元组中派生出一个类(最简单的代价就是简单的元组)也是值得的。 我可以提供详细的要求。

PS我看@MattAnderson早就提到了对象元组的问题。 但是这是一个主要的影响(至less在我的方框中),甚至在禁用垃圾收集之前。

  Original code: total time: 15.79 tuple instead of Point: total time: 7.328 namedtuple instead of Point: total time: 9.140 

数据是一个制表符分隔的文件,它由逗号分隔的整数列表组成。

使用示例get_data()我做了一个.csv文件,像这样:

 1,6,2,8,2,3,5,9,6,6 10,4,10,5,7,9,6,1,9,5 6,2,2,5,2,2,1,7,7,9 7,6,7,1,3,7,6,2,10,5 8,8,9,2,6,10,10,7,8,9 4,2,10,3,4,4,1,2,2,9 ... 

然后,我通过JSON滥用C优化parsing:

 def test2(): import json import time time_start = time.time() with open('data.csv', 'rb') as f: data = f.read() data = '[[[' + ']],[['.join(data.splitlines()).replace('\t', '],[') + ']]]' all_point_sets = [Point(*xy) for row in json.loads(data) for xy in zip(*row)] time_end = time.time() print "total time: ", (time_end - time_start) 

结果在我的盒子上:你的原始test() 〜8s,gc禁用〜6s,而我的版本(包括I / O)分别给出6s和〜4s。 即约〜50%加速。 但是从分析器数据来看,最明显的瓶颈就是对象实例本身,所以Matt Anderson的答案将会为你带来CPython最大的收益。

我不知道你能做多less。

您可以使用生成器来避免额外的内存分配。 这给了我大约5%的加速。

 first_points = (int(p) for p in first_points .split(",")) second_points = (int(p) for p in second_points.split(",")) paired_points = itertools.izip(first_points, second_points) curr_points = [Point(x, y) for x,y in paired_points] 

即使将整个循环折叠成一个大规模的列表理解也没有多大意义。

 all_point_sets = [ [Point(int(x), int(y)) for x, y in itertools.izip(xs.split(','), ys.split(','))] for xs, ys in data ] 

如果你继续迭代这个大列表,那么你可以把它变成一个生成器。 这将分摊parsingCSV数据的成本,所以你不会得到大的前期命中。

 all_point_sets = ( [Point(int(x), int(y)) for x, y in itertools.izip(xs.split(','), ys.split(','))] for xs, ys in data ) 

这里有很多好的答案。 但是,到目前为止,这个问题的一个方面还没有解决,python中的各种迭代器实现之间的列表到string时间成本差异。

有一篇文章testing了不同迭代器在Python.org散文 list2str中的列表到string转换的效率 。 请记住,当我碰到类似的优化问题,但是数据结构和大小不同时,本文提供的结果并没有以相同的速度放大,所以值得为特定的用例testing不同的迭代器实现。

因为对于长度为2000000的数组而言,为zip(a,b)map(int, string.split(","))构build函数所花费的时间可以忽略不计,所以我必须假设最耗时的操作被追加

因此,解决这个问题的正确方法是recursion地连接string:
10个元素的10个string到更大的string
10个100个元素的string
1000个元素的10个string

最后到zip(map(int,huge_string_a.split(",")),map(int,huge_string_b.split(",")));

然后,只需调整即可find追加和征服方法的最佳基数N.