[python] медленные операции со строками

Landstreicher

Написал программу, работающую с длинными (> 3000 букв) строками. Наблюдаются очень сильные тормоза. Решил специально проверить:


import time

def test(cnt):

    result = ''

    for l in range(cnt):

        result += 'A'

    return result

def meas(size):

    count = 100

    t1 = time.time

    for i in range(count):

        test(size)

    t2 = time.time

    dt = (t2 - t1) / count

    print 'size', size, 'takes', dt, 'sec', 'relative', 1000000*dt/size

for size in [1000 * pow(2, x) for x in range(6)]:

    meas(size)

Результаты:


size 1000 takes 0.00065493106842 sec relative 0.65493106842

size 2000 takes 0.00159277200699 sec relative 0.796386003494

size 4000 takes 0.003853328228 sec relative 0.963332056999

size 8000 takes 0.0116849112511 sec relative 1.46061390638

size 16000 takes 0.0449378609657 sec relative 2.80861631036

size 32000 takes 0.172980041504 sec relative 5.405626297

Хорошо видна нелинейная (судя по всему, близкая к квадратичной) зависимость
Python, конечно, интерпретируемый язык с динамической типизацией, и все такое, но неужели обработка строки в 32к букв требует 0.17 секунд?

artimon

Видимо старая проблема.
Что б добавить символ в конец строки надо найти конец строки.
Что б найти конец строки нужно пройти строку от начала до конца.

Landstreicher

Нашел исчерпывающий ответ тут

artimon

Кстати по этой же причине, когда одному челу нужно было собрать одну большую строку из множества мелких он сначала все мелкие строки загнал в массив, а потом сделал join (это был JS).

vall

http://www.skymind.com/~ocrow/python_string/

Landstreicher

Раньше бы никогда не подумал, что это может быть быстрее.

artimon

ОК.
Я ошибся в причине тормозов. Впрочем на питоне я не пишу
А фигню с JS я смеху ради проверял. join действительно быстрее. (Начиная с некоторого объёма строк)

Ivan8209

> Что б найти конец строки нужно пройти строку от начала до конца.
Тяжёлое наследство сей.
Кто бы объяснил, на кой чёрт в новых языках до сих пор держать эту ерунду.
---
...Я работаю антинаучным аферистом...

Landstreicher

> Тяжёлое наследство сей.
> Кто бы объяснил, на кой чёрт в новых языках до сих пор держать эту ерунду.
AFAIK, в Python это не верно. Во всяком случае, в строке могут быть любые символы, включая 0.

vall

читай трэд внимательнее.
В Python строки immutable.
при каждом изменении строки создаётся новая строка.

enochka1145

Что ты предлагаешь?

Ivan8209

Правда, что ли?
Ну надо же, в этом мире ещё есть жизнь!
---
...Я работаю антинаучным аферистом...

bleyman

В шарпе вроде тоже у строки где-то вначале длина записана. Точнее, поскольку строка - это объект, у неё по определению есть размер где-то в метаданных.

Andbar

получается, что другие языки начинают потихоньку перенимать паскалевские строки ?

Ivan8209

Почему "паскалевские"?
Фортрановские!
---
...Я работаю антинаучным аферистом...

Marinavo_0507

А чё, в фортране и в паскале уже есть строки?

Ivan8209

Не знаю, как в паскале, а в фортране есть.
Перечень задач, решаемых настоящим программистом, общедоступен.
---
...Я работаю антинаучным аферистом...

Andbar

А чё, в фортране и в паскале уже есть строки?
знаешь-ли... В паскале (во всяком случае, начиная с турбо паскаля какой-то друвнющей версии) со строками работать значительно удобнее, чем в C и других подобных языках.
При чем, в дельфи эта тенденция сохранилась, а ограничения на паскалевскую строку сняты.

Helga87

Про Turbo Pascal согласен, про дельфи - нет. Сколько там типов строк?
ShortString, LongString, WideString, AnsiString, String (который в зависимости от опций компилятора либо ShortString, либо AnsiString PChar (null-terminated string) и еще как-то специально надо было со строками работать, если делаешь свой COM-объект на Delphi. Т.е. в Delphi гемора со строками ровно столько же, сколько и VC++

Marinavo_0507

Это борландовское расширение, к тому же бесполезное, если нужны строки длиннее 255 символов (на машине с 640k памяти вполне осмысленное требование).

Helga87

К этому борландовскому расширению уже сделали еще одно расширение - Free Pascal - в котором сняты эти ограничения. Для практического программирования вещь действительно бессмысленная, но с задачей обучения программированию и функцией "олимпиадного языка" Free Pascal справляется хорошо.

enochka1145

В паскале (во всяком случае, начиная с турбо паскаля какой-то друвнющей версии) со строками работать значительно удобнее, чем в C и других подобных языках.
Это в каких это подобных языках? C++? C#/Java?

bleyman

ЛОЛ.
Паскалевские строки ещё чудовищнее, чем голый char*.
"Строка" представляет собой массив чаров (однобайтных) фиксированной длины, у которого вначале есть ещё один байт - текущая длина. Таким образом строки длиннее 256 символов не бывает. Для добавления к строке одного символа может понадобится менять её тип. Дефолтный "string" эквивалентен "string[256]" и занимает всегда 256 байтов.
Ужоснах!

yolki

ну давай ещё вспомним что было у мелкомягких в их компиляторе в предвиндовую эпоху
в текущем варианте дельфёвые строки на порядок удобнее, чем в C++/Java. про до-диез говорить не буду - не видел.

evgen5555



в текущем варианте дельфёвые строки на порядок удобнее, чем в C++/Java
std::wstring и std::string ещё не отменили.
а про убожество PChar даже вспоминать неохота.

yolki

==> про убожество char* тоже говорить неохота

evgen5555

Дело твоё - у каждого свои вкусы

yolki

В общем, сойдёмся на том, что PChar в удобстве эквивалентен char*, а остальное - дело привычки и "родного" языка программирования.
Думаю, для тебя std::string также удобен, как для меня string.
"Сборная Бразилии по футболу не самый удачный противник сборной Канады по хоккею" ©

bobby

А чем дельфевые строки удобнее, чем строки Java?

bobby

Ну и тот же вопрос про std::string.
Какие-нибудь конкретные аргументы хочется услышать.

yolki

Нельзя просто так менять внутренние символы в строке, например, в Delphi прокатит такой код:


 for i:=1 to Length(S) do

   S[i]:=F(S[i]);

(F - некий функционал char->char)
в Java сходу что-то не могу придумать, как такое реализовать.
только через новую строку типа Q = Q+F(S.charAt(i; - но это как-то убого. она же наращивать эту строку будет.. бее..

Helga87

Для этого есть StringBuilder. Поддерживает все операции, что и строки в Паскале, позволяет получить строку. Разделение на неизменяемый string и изменяемый StringBuilder в Java, .Net и Python введены для того, чтобы со строками можно было безопасно работать из разных потоков

psihodog

Для этого есть StringBuilder. Поддерживает все операции, что и строки в Паскале, позволяет получить строку. Разделение на неизменяемый string и изменяемый StringBuilder в Java, .Net и Python введены для того, чтобы со строками можно было безопасно работать из разных потоков
Скорее для скорости и для других нужд. В жаве есть StringBuffer, который такой же как и StringBuilder, только thread-safe. Собственно, StringBuilder появился совсем недавно, а StringBuffer был и раньше.

Andbar

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

vall

тебе уже объяснили что в паскалевских строках плохо
маленькая длина.
постоянный размер памяти.
хватит уже, всё, сдох паскаль.

Andbar

маленькая длина.
постоянный размер памяти.
я говорю вообще-то про AnsiString и у неё длину нельзя называть маленькой. И про это уже тоже писали, если ты не заметил. И второе утверждение тоже для AnsiString недействительно.

vall

хехе, я даже не знаю кто сейчас мертвее borland pascal или delphi
паскаль хоть в школах используют для обучения, и ещё долго будут использовать.
а вот delphi, хыхыхы

psihodog

Зато в паскале это - стандартный тип, не требующий никаких расширений. В конце концов, обработка подобной строки в любом случае происходит быстрее хотя-бы потому, что всегда исключается продолжительная операция нахождения длины строки.
В жаве StringBuffer и StringBuilder -- стандартные типы. Длина строки там тоже хранится.

yolki

string в Delphi и FreePascal эквивалентны.
то, что Delphi мёртв говорить преждевременно.
То, что Borland продаёт подразделение IDE не означает, что покупатель оного свернёт работы по Delphi. как раз наоборот, имхо свернутся JBuilder и C++Builder
string из BorlandPascal всё-таки был раньше std::string лет на пять и сравнивать их ну совсем не корректно.
то, что некоторые несознательные личности до сих пор пользуют BP это их проблемы

kokoc88

В конце концов, обработка подобной строки в любом случае происходит быстрее хотя-бы потому, что всегда исключается продолжительная операция нахождения длины строки.
А вот это очень интересный момент. Знаешь, обычно в таких случаях соревнуются: пишут программу на создание миллиона строк и сортировки их пузырьком. Пишут на С++, Java, C#, Pascal. Обычно выигрывают C# и Java, если на С++ решают задачу в лоб. Хочешь попробовать?

Marinavo_0507

> Обычно выигрывают C# и Java
И юникод не мешает?

kokoc88

А почему он мешает?

Marinavo_0507

сравнивать дольше

Andbar

string из BorlandPascal всё-таки был раньше std::string лет на пять и сравнивать их ну совсем не корректно.
теперь он называется ShortString и неявно используется в механизме поддержки классов (всё-равно идентификатор не может быть очень длинным).

yolki

Если паскаль - фрипаскаль/delphi, то он выиграет

kokoc88

Ну вот можем попробовать...

kokoc88

В этой задаче сравнение - не самая тяжёлая часть.
Edit: Хотя наверно да, тяжёлая. Ну просто для равнозначности можно поставить условие, чтобы писалось всё в юникоде. На самом деле разве сейчас по-другому пишут программы?

ava3443

> В этой задаче сравнение - не самая тяжёлая часть.
Как в этой - очень тяжёлая
Offtopic: помню, как народ сетовал на тормознутость grep в кажется девятом Redhat Linux - Redhat тогда как раз на UTF-8 перешли

kokoc88

UTF-8 при сравнении строк с английскими буквами будет точно таким же, как ascii.

Julie16

А операции по его разбору - совсем нет. UTF-8 - многобайтная кодировка, и этим все сказано.
PS:
У меня есть уверенность что операции на ascii и UCS-2(4) по скорости не будут сильно отличаться.

vall

У меня есть уверенность что операции на ascii и UCS-2(4) по скорости не будут сильно отличаться.
тут недавно разбирал народ кусок кода из оптимизированного strlen который сразу четыре байта отсчитывал.
так что разница будет.

vall

UTF-8 при сравнении строк с английскими буквами будет точно таким же, как ascii.
и не только с английскими. со всеми.
первый байт символа UTF8 всегда отличается от остальных.
как только нашлось отличие то однозначно определяется символ.

ppplva

Как минимум, в utf-8 строке нельзя быстро найти символ по индексу.

vall

а зачем?
все стандартные функции работают с указателями а не индексами.
да так и удобнее обычно.

ppplva

Потому, отчасти, и работают с указателями, что с индексами нельзя.
Да, еще в utf-8 строке нельзя двигаться против шерсти

Marinavo_0507

> На самом деле разве сейчас по-другому пишут программы?
А большой смысл сортировать юникодные строки?
Это наверное от локали должно зависеть?

Marinavo_0507

> Да, еще в utf-8 строке нельзя двигаться против шерсти
Как это нельзя?
Вроде можно.

Marinavo_0507

> а зачем?
ну мало ли
чтоб вырезать нужный кусок, например
если поле вывода со скроллингом или типа того

vall

Да, еще в utf-8 строке нельзя двигаться против шерсти
первый байт символа UTF8 всегда отличается от остальных.
первый и остальные из разных диапазонов.

vall

если поле вывода со скроллингом или типа того
тогда оно скроллится либо -+1 или сразу до конца.
в любом случае можно сделать за О(1) просто немножно посложнее.
а в винде юникод это всегда 2 байта?
типа они клали на шумеров и древних египтян?
такой большой контингент пользователей упускают.

Andbar

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

Landstreicher

Народ! Кто знает Lisp, напишите, как лучше всего на нем такое сделать (имеется ввиду склеивание большого количества коротких строк в одну).
Хочется для интереса сравнить.
Сам Lisp не знаю. Максимум, чего смог придумать:


(defun append-string (res str)

  (declare (type string str

  (declare (type string res

  (dotimes (i (length str

    (declare (type fixnum i

    (vector-push-extend (char str i) res

(defun concat-many-strings (strs)

  (let* sumlen (reduce #'+ (map 'vector #'length strs

        (res (make-array sumlen :adjustable t :element-type 'character :fill-pointer 0

    (declare (type (simple-array string) strs

    (dotimes (i (length strs

      (declare (type fixnum i

      (append-string res (elt strs i

    res

PS. Если глупость написал - сильно не бейте, никогда раньше Lisp не использовал.

Ivan8209

Emacs:


concat is a built-in function.

(concat &rest SEQUENCES)

Concatenate all the arguments and make the result a string.

The result is a string whose elements are the elements of all the arguments.

Each argument may be a string or a list or vector of characters (integers).

R5RS:


[[library procedure]] (string-append string ...)

Returns a newly allocated string whose characters form the concatenation of the

given strings.

Скорее всего в Common LISP точно так же.
---
...Я работаю...

Landstreicher

Есть встроенная функция concatenate. Но, по непонятным мне причинам, она работает очень медленно:


(defparameter xlen 32000)

(defparameter myarr (make-array xlen :initial-element "ZZ" :adjustable t :element-type 'string :fill-pointer xlen

(defparameter mylist (map 'list #'(lambda (c) c) myarr

CL-USER> (timing (progn (concat-many-strings myarr) nil

;;; Computation took:

;;;  0.03 seconds of real time

;;;  0.027 seconds of run time

NIL

CL-USER> (timing (progn (apply #'concatenate 'string mylist) nil

;;; Computation took:

;;;  8.457 seconds of real time

;;;  8.157 seconds of run time

NIL

Может я что-то делаю не так?

Marinavo_0507

а что у тебя за лисп?

Landstreicher

При запуске пишет такое:
This is SBCL 0.9.9, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

Ivan8209

(define strlist (make-list 32000 "ZZ"
(begin (apply string-append strlist) #f)
У тебя это должно быть как-то так:
(setq strlist (make-list 32000 "ZZ"
(progn (apply 'concatenate strlist) nil)
Насколько слышал, SBCL не самый быстрый.
---
...Я работаю антинаучным аферистом...

Landstreicher

> У тебя это должно быть как-то так:
> (setq strlist (make-list 32000 "ZZ"
> (progn (apply 'concatenate strlist) nil)
В принципе, я тоже самое и делаю (разве что не знал про функцию make-list )
Оно работает, и выдает правильный результат (проверял). Вопрос в другом - почему так медленно
> Насколько слышал, SBCL не самый быстрый.
Попробуй проведи тест у себя и напиши сколько времени это занимает. Какой у тебя процессор и версия Lisp?

Ivan8209



$ cat script.scm

(define strlist (make-list 3200000 "ZZ"

(begin

    (display (current-time (newline)

    (apply string-append strlist)

    (display (current-time (newline

$ guile -s script.scm

1141897979

1141897980

$ guile --version

Guile 1.6.7

P4 2,8 GHz
---
...Я работаю антинаучным аферистом...
Оставить комментарий
Имя или ник:
Комментарий: