как избежать подстрок - PullRequest
Новая
       3

как избежать подстрок

6 голосов
/ 20 декабря 2010

В настоящее время я обрабатываю разделы строки следующим образом: 

for (i, j) in huge_list_of_indices:
    process(huge_text_block[i:j])

Я хочу избежать накладных расходов на генерацию этих временных подстрок.Есть идеи?Возможно, оболочка, которая каким-то образом использует смещения индекса?В настоящее время это мое узкое место.

Обратите внимание, что process () - это еще один модуль Python, который ожидает ввод строки.

Редактировать:

Несколько человек сомневаются в наличии проблемы.Вот некоторые примеры результатов: 

import time
import string
text = string.letters * 1000

def timeit(fn):
    t1 = time.time()
    for i in range(len(text)):
        fn(i)
    t2 = time.time()
    print '%s took %0.3f ms' % (fn.func_name, (t2-t1) * 1000)

def test_1(i):
    return text[i:]

def test_2(i):
    return text[:]

def test_3(i):
    return text

timeit(test_1)
timeit(test_2)
timeit(test_3)

Вывод: 

test_1 took 972.046 ms
test_2 took 47.620 ms
test_3 took 43.457 ms

Ответы [ 6 ]

8 голосов
/ 02 декабря 2011

Я думаю, что вы ищете буферы .

Характеристика буферов состоит в том, что они «нарезают» объект, поддерживающий интерфейс буфера , не копируя его содержимое , но по существу открывая «окно» для содержимого нарезанного объекта. Более подробное техническое объяснение доступно здесь . Выдержка:

Объекты Python, реализованные в C, могут экспортировать группу функций, называемых «буферным интерфейсом». Эти функции могут использоваться объектом для представления своих данных в необработанном байтово-ориентированном формате. Клиенты объекта могут использовать буферный интерфейс для прямого доступа к данным объекта, без необходимости сначала копировать их.

В вашем случае код должен выглядеть примерно так: 

>>> s = 'Hugely_long_string_not_to_be_copied'
>>> ij = [(0, 3), (6, 9), (12, 18)]
>>> for i, j in ij:
...     print buffer(s, i, j-i)  # Should become process(...)
Hug
_lo
string

НТН!

3 голосов
/ 20 декабря 2010

Обертка, которая использует смещения индекса для объекта mmap, может работать, да.

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

1 голос
/ 03 декабря 2011

Если вы используете Python3, вы можете использовать буфер протокола и представления памяти.Предполагая, что текст хранится где-то в файловой системе: 

f = open(FILENAME, 'rb')
data = bytearray(os.path.getsize(FILENAME))
f.readinto(data)

mv = memoryview(data)

for (i, j) in huge_list_of_indices:
    process(mv[i:j])

Проверьте также эту статью.Это может быть полезно.

0 голосов
/ 04 декабря 2011

Пример, который дает OP, даст почти наибольшую разницу в производительности между нарезкой и невозможностью нарезки.

Если обработка на самом деле делает что-то, что занимает значительное время, проблема может вряд ли существует.

Факт в том, что ОП должна сообщить нам, что делает процесс. Наиболее вероятный сценарий - это что-то значимое, и поэтому он должен профилировать свой код.

Адаптировано из примера op: 

#slice_time.py

import time
import string
text = string.letters * 1000
import random
indices = range(len(text))
random.shuffle(indices)
import re


def greater_processing(a_string):
    results = re.findall('m', a_string)

def medium_processing(a_string):
    return re.search('m.*?m', a_string)                                                                              

def lesser_processing(a_string):
    return re.match('m', a_string)

def least_processing(a_string):
    return a_string

def timeit(fn, processor):
    t1 = time.time()
    for i in indices:
        fn(i, i + 1000, processor)
    t2 = time.time()
    print '%s took %0.3f ms %s' % (fn.func_name, (t2-t1) * 1000, processor.__name__)

def test_part_slice(i, j, processor):
    return processor(text[i:j])

def test_copy(i, j, processor):
    return processor(text[:])

def test_text(i, j, processor):
    return processor(text)

def test_buffer(i, j, processor):
    return processor(buffer(text, i, j - i))

if __name__ == '__main__':
    processors = [least_processing, lesser_processing, medium_processing, greater_processing]
    tests = [test_part_slice, test_copy, test_text, test_buffer]
    for processor in processors:
        for test in tests:
            timeit(test, processor)

А потом беги ... 

In [494]: run slice_time.py
test_part_slice took 68.264 ms least_processing
test_copy took 42.988 ms least_processing
test_text took 33.075 ms least_processing
test_buffer took 76.770 ms least_processing
test_part_slice took 270.038 ms lesser_processing
test_copy took 197.681 ms lesser_processing
test_text took 196.716 ms lesser_processing
test_buffer took 262.288 ms lesser_processing
test_part_slice took 416.072 ms medium_processing
test_copy took 352.254 ms medium_processing
test_text took 337.971 ms medium_processing
test_buffer took 438.683 ms medium_processing
test_part_slice took 502.069 ms greater_processing
test_copy took 8149.231 ms greater_processing
test_text took 8292.333 ms greater_processing
test_buffer took 563.009 ms greater_processing

Примечания:

Да, я попробовал оригинальный тест OP_1 OP со слайсом [i:], и он стал намного медленнее, что сделало его тест еще более пустым.

Интересно, что буфер почти всегда работает немного медленнее, чем нарезка. На этот раз есть один, где это лучше, хотя! Реальный тест ниже, и буфер, кажется, работает лучше для больших подстрок, в то время как нарезка работает лучше для маленьких подстрок.

И, да, у меня есть некоторая случайность в этом тесте, поэтому проверь и посмотри разные результаты :). Также может быть интересно изменить размер 1000-х.

Так, может быть, некоторые другие верят вам, но Я не , поэтому я хотел бы узнать кое-что о том, что обработка делает и как вы пришли к выводу: " Нарезка - это проблема."

В моем примере я профилировал обработку среды, увеличил множитель string.letters до 100000 и увеличил длину срезов до 10000. Также ниже приведен один с фрагментами длиной 100. Я использовал для них cProfile (намного меньше накладных расходов, чем профиль !). 

test_part_slice took 77338.285 ms medium_processing
         31200019 function calls in 77.338 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   77.338   77.338 <string>:1(<module>)
        2    0.000    0.000    0.000    0.000 iostream.py:63(write)
  5200000    8.208    0.000   43.823    0.000 re.py:139(search)
  5200000    9.205    0.000   12.897    0.000 re.py:228(_compile)
  5200000    5.651    0.000   49.475    0.000 slice_time.py:15(medium_processing)
        1    7.901    7.901   77.338   77.338 slice_time.py:24(timeit)
  5200000   19.963    0.000   69.438    0.000 slice_time.py:31(test_part_slice)
        2    0.000    0.000    0.000    0.000 utf_8.py:15(decode)
        2    0.000    0.000    0.000    0.000 {_codecs.utf_8_decode}
        2    0.000    0.000    0.000    0.000 {isinstance}
        2    0.000    0.000    0.000    0.000 {method 'decode' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  5200000    3.692    0.000    3.692    0.000 {method 'get' of 'dict' objects}
  5200000   22.718    0.000   22.718    0.000 {method 'search' of '_sre.SRE_Pattern' objects}
        2    0.000    0.000    0.000    0.000 {method 'write' of '_io.StringIO' objects}
        4    0.000    0.000    0.000    0.000 {time.time}


test_buffer took 58067.440 ms medium_processing
         31200103 function calls in 58.068 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   58.068   58.068 <string>:1(<module>)
        3    0.000    0.000    0.000    0.000 __init__.py:185(dumps)
        3    0.000    0.000    0.000    0.000 encoder.py:102(__init__)
        3    0.000    0.000    0.000    0.000 encoder.py:180(encode)
        3    0.000    0.000    0.000    0.000 encoder.py:206(iterencode)
        1    0.000    0.000    0.001    0.001 iostream.py:37(flush)
        2    0.000    0.000    0.001    0.000 iostream.py:63(write)
        1    0.000    0.000    0.000    0.000 iostream.py:86(_new_buffer)
        3    0.000    0.000    0.000    0.000 jsonapi.py:57(_squash_unicode)
        3    0.000    0.000    0.000    0.000 jsonapi.py:69(dumps)
        2    0.000    0.000    0.000    0.000 jsonutil.py:78(date_default)
        1    0.000    0.000    0.000    0.000 os.py:743(urandom)
  5200000    6.814    0.000   39.110    0.000 re.py:139(search)
  5200000    7.853    0.000   10.878    0.000 re.py:228(_compile)
        1    0.000    0.000    0.000    0.000 session.py:149(msg_header)
        1    0.000    0.000    0.000    0.000 session.py:153(extract_header)
        1    0.000    0.000    0.000    0.000 session.py:315(msg_id)
        1    0.000    0.000    0.000    0.000 session.py:350(msg_header)
        1    0.000    0.000    0.000    0.000 session.py:353(msg)
        1    0.000    0.000    0.000    0.000 session.py:370(sign)
        1    0.000    0.000    0.000    0.000 session.py:385(serialize)
        1    0.000    0.000    0.001    0.001 session.py:437(send)
        3    0.000    0.000    0.000    0.000 session.py:75(<lambda>)
  5200000    4.732    0.000   43.842    0.000 slice_time.py:15(medium_processing)
        1    5.423    5.423   58.068   58.068 slice_time.py:24(timeit)
  5200000    8.802    0.000   52.645    0.000 slice_time.py:40(test_buffer)
        7    0.000    0.000    0.000    0.000 traitlets.py:268(__get__)
        2    0.000    0.000    0.000    0.000 utf_8.py:15(decode)
        1    0.000    0.000    0.000    0.000 uuid.py:101(__init__)
        1    0.000    0.000    0.000    0.000 uuid.py:197(__str__)
        1    0.000    0.000    0.000    0.000 uuid.py:531(uuid4)
        2    0.000    0.000    0.000    0.000 {_codecs.utf_8_decode}
        1    0.000    0.000    0.000    0.000 {built-in method now}
       18    0.000    0.000    0.000    0.000 {isinstance}
        4    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {locals}
        1    0.000    0.000    0.000    0.000 {map}
        2    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'close' of '_io.StringIO' objects}
        1    0.000    0.000    0.000    0.000 {method 'count' of 'list' objects}
        2    0.000    0.000    0.000    0.000 {method 'decode' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {method 'extend' of 'list' objects}
  5200001    3.025    0.000    3.025    0.000 {method 'get' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'getvalue' of '_io.StringIO' objects}
        3    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
  5200000   21.418    0.000   21.418    0.000 {method 'search' of '_sre.SRE_Pattern' objects}
        1    0.000    0.000    0.000    0.000 {method 'send_multipart' of 'zmq.core.socket.Socket' objects}
        2    0.000    0.000    0.000    0.000 {method 'strftime' of 'datetime.date' objects}
        1    0.000    0.000    0.000    0.000 {method 'update' of 'dict' objects}
        2    0.000    0.000    0.000    0.000 {method 'write' of '_io.StringIO' objects}
        1    0.000    0.000    0.000    0.000 {posix.close}
        1    0.000    0.000    0.000    0.000 {posix.open}
        1    0.000    0.000    0.000    0.000 {posix.read}
        4    0.000    0.000    0.000    0.000 {time.time}

Меньшие кусочки (длина 100). 

test_part_slice took 54916.153 ms medium_processing
         31200019 function calls in 54.916 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   54.916   54.916 <string>:1(<module>)
        2    0.000    0.000    0.000    0.000 iostream.py:63(write)
  5200000    6.788    0.000   38.312    0.000 re.py:139(search)
  5200000    8.014    0.000   11.257    0.000 re.py:228(_compile)
  5200000    4.722    0.000   43.034    0.000 slice_time.py:15(medium_processing)
        1    5.594    5.594   54.916   54.916 slice_time.py:24(timeit)
  5200000    6.288    0.000   49.322    0.000 slice_time.py:31(test_part_slice)
        2    0.000    0.000    0.000    0.000 utf_8.py:15(decode)
        2    0.000    0.000    0.000    0.000 {_codecs.utf_8_decode}
        2    0.000    0.000    0.000    0.000 {isinstance}
        2    0.000    0.000    0.000    0.000 {method 'decode' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  5200000    3.242    0.000    3.242    0.000 {method 'get' of 'dict' objects}
  5200000   20.268    0.000   20.268    0.000 {method 'search' of '_sre.SRE_Pattern' objects}
        2    0.000    0.000    0.000    0.000 {method 'write' of '_io.StringIO' objects}
        4    0.000    0.000    0.000    0.000 {time.time}


test_buffer took 62019.684 ms medium_processing
         31200103 function calls in 62.020 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   62.020   62.020 <string>:1(<module>)
        3    0.000    0.000    0.000    0.000 __init__.py:185(dumps)
        3    0.000    0.000    0.000    0.000 encoder.py:102(__init__)
        3    0.000    0.000    0.000    0.000 encoder.py:180(encode)
        3    0.000    0.000    0.000    0.000 encoder.py:206(iterencode)
        1    0.000    0.000    0.001    0.001 iostream.py:37(flush)
        2    0.000    0.000    0.001    0.000 iostream.py:63(write)
        1    0.000    0.000    0.000    0.000 iostream.py:86(_new_buffer)
        3    0.000    0.000    0.000    0.000 jsonapi.py:57(_squash_unicode)
        3    0.000    0.000    0.000    0.000 jsonapi.py:69(dumps)
        2    0.000    0.000    0.000    0.000 jsonutil.py:78(date_default)
        1    0.000    0.000    0.000    0.000 os.py:743(urandom)
  5200000    7.426    0.000   41.152    0.000 re.py:139(search)
  5200000    8.470    0.000   11.628    0.000 re.py:228(_compile)
        1    0.000    0.000    0.000    0.000 session.py:149(msg_header)
        1    0.000    0.000    0.000    0.000 session.py:153(extract_header)
        1    0.000    0.000    0.000    0.000 session.py:315(msg_id)
        1    0.000    0.000    0.000    0.000 session.py:350(msg_header)
        1    0.000    0.000    0.000    0.000 session.py:353(msg)
        1    0.000    0.000    0.000    0.000 session.py:370(sign)
        1    0.000    0.000    0.000    0.000 session.py:385(serialize)
        1    0.000    0.000    0.001    0.001 session.py:437(send)
        3    0.000    0.000    0.000    0.000 session.py:75(<lambda>)
  5200000    5.399    0.000   46.551    0.000 slice_time.py:15(medium_processing)
        1    5.958    5.958   62.020   62.020 slice_time.py:24(timeit)
  5200000    9.510    0.000   56.061    0.000 slice_time.py:40(test_buffer)
        7    0.000    0.000    0.000    0.000 traitlets.py:268(__get__)
        2    0.000    0.000    0.000    0.000 utf_8.py:15(decode)
        1    0.000    0.000    0.000    0.000 uuid.py:101(__init__)
        1    0.000    0.000    0.000    0.000 uuid.py:197(__str__)
        1    0.000    0.000    0.000    0.000 uuid.py:531(uuid4)
        2    0.000    0.000    0.000    0.000 {_codecs.utf_8_decode}
        1    0.000    0.000    0.000    0.000 {built-in method now}
       18    0.000    0.000    0.000    0.000 {isinstance}
        4    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {locals}
        1    0.000    0.000    0.000    0.000 {map}
        2    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'close' of '_io.StringIO' objects}
        1    0.000    0.000    0.000    0.000 {method 'count' of 'list' objects}
        2    0.000    0.000    0.000    0.000 {method 'decode' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {method 'extend' of 'list' objects}
  5200001    3.158    0.000    3.158    0.000 {method 'get' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'getvalue' of '_io.StringIO' objects}
        3    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
  5200000   22.097    0.000   22.097    0.000 {method 'search' of '_sre.SRE_Pattern' objects}
        1    0.000    0.000    0.000    0.000 {method 'send_multipart' of 'zmq.core.socket.Socket' objects}
        2    0.000    0.000    0.000    0.000 {method 'strftime' of 'datetime.date' objects}
        1    0.000    0.000    0.000    0.000 {method 'update' of 'dict' objects}
        2    0.000    0.000    0.000    0.000 {method 'write' of '_io.StringIO' objects}
        1    0.000    0.000    0.000    0.000 {posix.close}
        1    0.000    0.000    0.000    0.000 {posix.open}
        1    0.000    0.000    0.000    0.000 {posix.read}
        4    0.000    0.000    0.000    0.000 {time.time}
0 голосов
/ 03 декабря 2011

процесс (огромный_текст_блока [i: j])

Я хочу избежать издержек генерации этих временных подстрок .
(...)
Обратите внимание, что process () - это еще один модуль Python, который ожидает строку в качестве ввода .

Полностью противоречивы.
КакМожете ли вы представить, чтобы найти способ не создавать то, что требуется для функции?!

0 голосов
/ 01 декабря 2011

Может быть, обертка, которая использует смещения индекса, действительно то, что вы ищете. Вот пример, который делает работу. Возможно, вам придется добавить дополнительные проверки на срезы (для переполнения и отрицательных индексов) в зависимости от ваших потребностей. 

#!/usr/bin/env python

from collections import Sequence
from timeit import Timer

def process(s):
    return s[0], len(s)

class FakeString(Sequence):
    def __init__(self, string):
        self._string = string
        self.fake_start = 0
        self.fake_stop = len(string)

    def setFakeIndices(self, i, j):
        self.fake_start = i
        self.fake_stop = j

    def __len__(self):
        return self.fake_stop - self.fake_start

    def __getitem__(self, ii):
        if isinstance(ii, slice):
            if ii.start is None:
                start = self.fake_start
            else:
                start = ii.start + self.fake_start
            if ii.stop is None:
                stop = self.fake_stop
            else:
                stop = ii.stop + self.fake_start
            ii = slice(start,
                       stop,
                       ii.step)
        else:
            ii = ii + self.fake_start
        return self._string[ii]

def initial_method():
    r = []
    for n in xrange(1000):
        r.append(process(huge_string[1:9999999]))
    return r

def alternative_method():
    r = []
    for n in xrange(1000):
        fake_string.setFakeIndices(1, 9999999)
        r.append(process(fake_string))
    return r


if __name__ == '__main__':
    huge_string = 'ABCDEFGHIJ' * 100000
    fake_string = FakeString(huge_string)

    fake_string.setFakeIndices(5,15)
    assert fake_string[:] == huge_string[5:15]

    t = Timer(initial_method)
    print "initial_method(): %fs" % t.timeit(number=1)

, что дает: 

initial_method(): 1.248001s  
alternative_method(): 0.003416s
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...