Ускорение сопряжения строк в объекты в Python

Ответ 1

Простое выполнение с 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

namedtuple for Point делает его хуже

$ pypy pairing_strings.py 
total time:  0.888827085495

используя itertools.imap, и itertools.izip

$ pypy pairing_strings.py 
total time:  0.615751981735

Использование memoized версии 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)

Ответ 2

Когда вы занимаетесь созданием большого количества объектов, часто самое большое повышение производительности, которое вы можете использовать, это отключить сборщик мусора. Каждое "поколение" объектов сборщик мусора пересекает все живые объекты в памяти, ищет объекты, которые являются частью циклов, но не заострены живыми объектами, поэтому они могут быть использованы для восстановления памяти. См. статью Doug Helmann PyMOTW GC для получения некоторой информации (более того, возможно, можно найти с Google и некоторым определением). Сборщик мусора запускается по умолчанию каждые 700 или около того объектов, созданных, но не восстановленных, причем последующие поколения работают несколько реже (я забываю точные детали).

Использование стандартного кортежа вместо класса Point может сэкономить вам некоторое время (с использованием namedtuple находится где-то посередине), а умная распаковка может сэкономить вам некоторое время, но наибольшее усиление может быть достигнуто, выключив 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

Ответ 3

Я бы

• используйте 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

Это код, который я использовал для чтения данных в 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,9 с в моей системе, но это не совсем сопоставимо, так как данные не считываются из файла, и вы создали экземпляры 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 и индексирование, это будет быстрее, если вам действительно нужна итерация (см. также этот ответ),

Ответ 4

Более быстрый метод, используя 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, но может быть неверным для вашего реального набора данных.

Ответ 5

Я получил 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.

Ответ 6

• make Point a namedtuple (~ 10% ускорение):

  from collections import namedtuple
  Point = namedtuple('Point', 'a b')
  

• распаковывать во время итерации (~ 2-4% ускорения):

  for xs, ys in data:
  

• используйте n -аргументную форму map, чтобы избежать zip (~ 10% ускорения):

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

Учитывая, что наборы точек коротки, генераторы, вероятно, переполнены, поскольку они имеют более высокие фиксированные накладные расходы.

Ответ 7

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

poking вокруг дальше я могу приблизительно сломать некоторые из ресурсов процессора

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

Я бы ожидал, что может быть улучшение, если бы cython смог прочитать файл csv (или любой другой) напрямую, вместо того, чтобы траться через объект Python.

Ответ 8

Вы можете сбрить несколько секунд:

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

Ответ 9

Данные представляют собой разделенный вкладкой файл, который состоит из списков запятой разделенные целые числа.

Используя образец 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
...

Затем я злоупотреблял C-оптимизированным анализом через JSON:

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.

Ответ 10

Как вы привязаны к тому, чтобы ваши координаты были доступны как атрибуты .x и .y? К моему удивлению, мои тесты показывают, что самый большой одноразовый приемник - это не призывы к list.append(), а построение объектов Point. Они занимают в четыре раза больше, чем кортеж, и их много. Просто заменив Point(int(x), int(y)) кортежем (int(x), int(y)) в вашем коде, выбритом на 50% от общего времени выполнения (Python 2.6 на Win XP). Возможно, у вашего текущего кода все еще есть возможность оптимизировать это?

Если вы действительно настроены на доступ к координатам с помощью .x и .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

Ответ 11

Я не знаю, можно ли многое сделать.

Вы можете использовать генератор, чтобы избежать дополнительных распределений памяти. Это дает мне примерно 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
)

Ответ 12

Поскольку время для встроенных функций, таких как zip(a,b) или map(int, string.split(",")) для массивов длиной 2000000, является незначительным, я должен предположить, что самая трудоемкая операция добавляется.

Таким образом, правильный способ решения проблемы состоит в том, чтобы рекурсивно объединить строки:
10 строк из 10 элементов в большую строку
10 строк из 100 элементов
10 строк из 1000 элементов

и, наконец, до zip(map(int,huge_string_a.split(",")),map(int,huge_string_b.split(",")));

Затем просто тонкая настройка, чтобы найти оптимальную базу N для метода append и conquer.

Ответ 13

Здесь есть много хороших ответов. Одной из сторон этой проблемы, которая не была рассмотрена до сих пор, является разница между затратами времени и времени между различными реализациями итератора в python.

Существует эссе, проверяющее эффективность разных итераторов с учетом преобразования между строками в эссе Python.org: list2str. Имейте в виду, что, когда я сталкивался с подобными проблемами оптимизации, но с разной структурой данных и размерами, результаты, представленные в эссе, не все расширялись с равной скоростью, поэтому стоит проверить различные реализации итераторов для вашего конкретного варианта использования.