33

我试图找到一种有效的方法来将包含整数点的数据行配对在一起,并将它们存储为 Python 对象。数据由坐标点XY坐标点组成,以逗号分隔的字符串表示。这些点必须成对,例如(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

我现在的解析代码是:

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)

目前,100,000 个点需要将近 7 秒,这似乎非常低效。部分低效率似乎源于对和- 的计算first_points以及将它们转换为对象。second_pointspaired_points

效率低下的另一部分似乎是all_point_sets. 取出all_point_sets.append(...)线似乎使代码从〜7秒变为2秒!

如何加快速度?谢谢。

跟进感谢大家的好建议-他们都很有帮助。但即使进行了所有改进,处理 100,000 个条目仍然需要大约 3 秒。我不确定为什么在这种情况下它不仅仅是即时的,以及是否有另一种表示可以使它即时。在 Cython 中编码会改变事情吗?有人可以举个例子吗?再次感谢。

4

13 回答 13

20

在处理大量对象的创建时,通常可以使用的最大性能增强是关闭垃圾收集器。每一“代”对象,垃圾收集器都会遍历内存中的所有活动对象,寻找属于循环的一部分但活动对象未指向的对象,从而有资格进行内存回收。有关一些信息,请参阅Doug Helmann 的 PyMOTW GC 文章(更多信息可能可以通过 google 和一些决心找到)。默认情况下,垃圾收集器每 700 个左右创建但未回收的对象运行一次,后续生成的运行频率稍低(我忘记了确切的细节)。

使用标准元组而不是 Point 类可以节省一些时间(使用命名元组介于两者之间),巧妙的拆包可以节省一些时间,但在创建批次之前关闭 gc 可以获得最大的收益您知道不需要 gc'd 的对象,然后再将其重新打开。

一些代码:

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
于 2012-10-17T04:26:16.613 回答
15

简单地用 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 的记忆版本和迭代器来避免 zip

$ 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)
于 2012-10-22T09:48:21.527 回答
9

我会

  • 使用numpy数组来解决这个问题(Cython如果这仍然不够快,将是一个选项)。
  • 将点存储为向量而不是单个Point实例。
  • 依赖现有的解析器
  • (如果可能)解析数据一次,然后以二进制格式(如 hdf5)存储以进行进一步计算,这将是最快的选择(见下文)

Numpy 内置了读取文本文件的函数,例如loadtxt. 如果您将数据存储在结构化数组中,则不一定需要将其转换为另一种数据类型。我将使用Pandas,它是基于numpy. 处理和处理结构化数据更方便一些。Pandas有自己的文件解析器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

这是我用来读取 a 中数据的代码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

(请注意,我假设您的文件中没有标题,因此我必须创建列名。)

读取数据速度很快,它应该更节省内存(请参阅这个问题),并且数据存储在一个数据结构中,您可以以一种快速、矢量化的方式进一步使用:

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

开发分支中有一个新的基于 C 的解析器,在我的系统上需要 414 毫秒。您的测试在我的系统上花费了 2.29 秒,但实际上并没有可比性,因为数据不是从文件中读取的,而是您创建了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当您进行进一步计算时,使用具有大型数据集的基于数组将具有优势。Cython如果您可以使用矢量化numpy函数和索引,不一定会更快,如果您真的需要迭代,它会更快(另请参见这个答案)。

于 2012-10-21T19:51:43.690 回答
8

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

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输出,但可能不适用于您的真实数据集。

于 2012-10-23T22:45:00.597 回答
7

通过使用数组和一个在访问时懒惰地构造 Point 对象的持有者对象,我得到了 50% 的改进。我还“开槽”了 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。

于 2012-10-21T01:41:26.247 回答
6
  1. 进行(约 10%Pointnamedtuple加速):

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

    for xs, ys in data:
    
  3. 使用n-argument 形式map来避免 zip(约 10% 加速):

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

鉴于点集很短,生成器可能是矫枉过正,因为它们具有更高的固定开销。

于 2012-10-17T04:01:37.947 回答
6

cython 能够将速度提高 5.5 倍

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

这是我使用的代码

分裂.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 对象拖网,我希望可能会有改进。

于 2012-10-24T06:51:11.843 回答
2

您对将坐标作为.x.y属性访问的依附程度如何?令我惊讶的是,我的测试表明最大的单一时间接收器不是对 的调用list.append(),而是Point对象的构造。它们构建一个元组需要四倍的时间,而且数量很多。只需在代码中替换Point(int(x), int(y))为元组即可(int(x), int(y))节省超过 50% 的执行时间(Win XP 上的 Python 2.6)。也许您当前的代码仍有优化空间?

如果您真的打算使用.xand访问坐标.y,您可以尝试使用collections.namedtuple. 它不如普通元组快,但似乎比代码中的 Pair 类快得多(我在对冲,因为单独的时序基准给了我奇怪的结果)。

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

如果你需要走这条路,从元组派生一个类也是值得的(比普通元组的成本最低)。如果需要,我可以提供详细信息。

PS我看到@MattAnderson 很久以前就提到过对象元组问题。但这是一个重大影响(至少在我的盒子上),甚至在禁用垃圾收集之前。

               Original code: total time:  15.79
      tuple instead of Point: total time:  7.328
 namedtuple instead of Point: total time:  9.140
于 2012-10-25T22:25:47.053 回答
2

您可以剃掉几秒钟:

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

通过预先分配空间,我可以间歇性地再缩短 0.3 秒,all_point_sets但这可能只是噪音。当然还有让事情变得更快的老式方法:

localhost-2:coding $ pypy pointexam.py
1.58351397514
于 2012-10-17T04:02:34.087 回答
2

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

使用示例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 优化解析:

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 上获得最大收益。

于 2012-10-22T14:00:27.167 回答
1

我不知道你能不能做很多事情。

您可以使用生成器来避免额外的内存分配。这给了我大约 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
]

如果你继续迭代这个大列表,那么你可以把它变成一个生成器。这将分散解析 CSV 数据的成本,因此您不会受到很大的前期打击。

all_point_sets = (
    [Point(int(x), int(y)) for x, y in itertools.izip(xs.split(','), ys.split(','))]
    for xs, ys in data
)
于 2012-10-17T03:19:52.717 回答
0

这里有很多很好的答案。然而,目前尚未解决的这个问题的一方面是 python 中各种迭代器实现之间的列表到字符串的时间成本差异。

在Python.org 的文章中,有一篇文章测试了不同迭代器在列表到字符串转换方面的效率:list2str。请记住,当我遇到类似的优化问题,但具有不同的数据结构和大小时,本文中提供的结果并没有以相同的速度扩展,因此值得为您的特定用例测试不同的迭代器实现。

于 2012-10-25T16:48:37.237 回答
0

由于内置函数(例如长度为 2000000 的数组zip(a,b)map(int, string.split(","))数组)所花费的时间可以忽略不计,我不得不假设最耗时的操作是append

因此,解决问题的正确方法是递归连接字符串:
10 个 10 个元素的字符串到一个更大的字符串
10 个 100 个元素的字符串 10
个 1000 个元素的字符串

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

然后只需微调即可找到追加和征服方法的最佳基数 N。

于 2012-10-25T06:07:11.610 回答