gifts2017

Опять двойка!

Опубликовал Сергей (ildarovich) в раздел Программирование - Практика программирования

Продолжение тем, связанных с использованием степеней двойки «Порождающий запрос» [http://infostart.ru/public/90367/] «Транзитивное замыкание запросом» [http://infostart.ru/public/158512/] На этот раз речь пойдет об операциях со строками.

Данная статья касается особенностей выполнения операций над строками в языке программирования платформы «1С: Предприятие» и проблемы медленной конкатенации строк, возникающей, если эти особенности не учитываются. Приводятся две новые полезные функции, позволяющие обходить указанную проблему.

Для примера рассмотрим следующую простую задачу: дана строка, из которой требуется исключить ненужные (повторяющиеся) пробелы. Эту операцию можно назвать «отжим пробелов».
Первое, что приходит в голову, для решения этой задачи, это использовать стэйт-машину в виде функции на подобие следующей

Функция ПростойОтжим(Текст, Ответ = "", Было = "") Экспорт

    Для
ё = 1 По СтрДлина(Текст) Цикл Стало = Сред(Текст, ё, 1); Ответ = Ответ + ?(Было + Стало = "  ", "", Стало); Было = Стало КонецЦикла;

    Возврат
Ответ

КонецФункции

На первый взгляд кажется, что никакого подвоха в этом коде нет. Однако на самом деле на длинных строках такая функция работает невероятно долго. Дело в том, что в цикле здесь используется простая по виду конструкция, которая дописывает справа к получаемой строке один значащий (не пробельный) символ. По замерам времени выполнения можно заключить, что в 1С такая конструкция работает примерно так: выделяется область памяти на один символ длиннее, чем строка, накапливающая результат, затем ВСЕ содержимое этой строки копируется в новую область, а добавляемый символ записывается справа. Следовательно, при удлинении всего на один символ строки длины в тысячу символов в оперативной памяти придется перенести целый килобайт данных (или два, если речь идет о юникоде)! А эта операция выполняется в цикле, повторяющемся для каждого символа новой строки! Последовательная посимвольная конкатенация в процессе накопления строки иллюстрируется следующей схемой:

Схема конкатенации

В качестве доказательства существования проблемы приводится график зависимости времени конкатенации от длины строки, накапливающей результат.

График зависимости

График получен в результате работы следующей процедуры:

Процедура ТестВремениКонкатенации()

   
Текст = "";

    Для
ё = 1 По 32 Цикл

       
Старт = ТочноеТекущееВремя();

        Для
ж = 1 По 16384 Цикл Текст = Текст + "а" КонецЦикла;

       
Сообщить("" + 16384 * ё + ":" + (ТочноеТекущееВремя() - Старт))

    КонецЦикла

КонецПроцедуры

Анализируя график, можно сделать еще один интересный практический вывод: обработка строк, длиннее, чем примерно 262144 символа производится платформой существенно дольше, чем обработка более коротких строк. Возможно, такие строки размещаются непосредственно на диске (есть и другие предположения).
Тем не менее, существует простое решение, позволяющее обойти при решении рассматриваемой задачи указанную проблему медленной конкатенации строк. Это решение имеет определенную аналогию с ранее предложенными приемами построения запросов и представлено следующей функцией «отжима пробелов»:

Функция ДвойнойОтжим(Знач Текст) Экспорт

    Для
ё = 1 По Log(СтрДлина(Текст)) / Log(2) + 1 Цикл Текст = СтрЗаменить(Текст, "  ", " ")

    КонецЦикла;

    Возврат
Текст

КонецФункции

В этой функции каждая итерация цикла уменьшает длину цепочки пробелов в два раза. Поэтому даже если строка состоит из одних пробелов, на ее «отжим» понадобится не больше чем  ] log2(N) [ итераций цикла, где N – исходная длина строки. Работа функции иллюстрируется следующей схемой:

Схема работы функции

На длинных строках такая функция работает приемлемое время, что показывает отчет, приложенный к статье. Строку из миллиона символов функция обрабатывает примерно за 200 миллисекунд. Скачавшие отчет смогут замерить (если хватит терпения) и время выполнения более очевидной функции «простого отжима» в зависимости от длины текста и процентного содержания пробелов в нем.
Кроме того, возможно, в коде отчета окажется интересным прием генерации «случайного» тестового текста с использованием «таблицы хаоса» из статьи "Порождающий запрос" [http://infostart.ru/public/90367/].
Нужно сказать, что предлагаемая функция «двойного отжима» более известна в виде функции «условного отжима»:

Функция УсловныйОтжим(Знач Текст) Экспорт

    Пока
Найти(Текст, "  ") Цикл Текст = СтрЗаменить(Текст, "  ", " ")

    КонецЦикла;

    Возврат
Текст

КонецФункции

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

Размышляя над отмеченной проблемой, можно прийти к выводу, что в 1С также трудно решаются любые задачи, в которых требуется синтезировать длинные строки. Например, первоначально было затруднительно получить длинную строку со случайным расположением пробелов для проверки предлагаемых функций, так как при этом также на первый взгляд требовалось использовать посимвольное наращивание строки.
Тем не менее, выход есть. Для решения таких задач предлагается первоначально работать с такими длинными строками как с массивом символов, а затем преобразовывать массив символов в результирующую строку с помощью второй предлагаемой в статье функции

Функция Строчка(Массив, От, До)

    Возврат ?(
От = До, Массив[От], Строчка(Массив, От, Цел((От + До) / 2)) + Строчка(Массив, Цел((От + До) / 2) + 1, До))

КонецФункции

Эта простая рекурсивная функция работает существенно быстрее последовательной посимвольной конкатенации из-за того, что требуется перемещать меньшие объемы данных при меньшем общем количестве необходимых конкатенаций. Работа функции построена на рекурсивном объединение строк из половинок обрабатываемого массива. Этот принцип отражает следующая схема:

Схема работы рекурсивной функции 

Например, массив из миллиона символов преобразуется в строку примерно за 20 секунд. ВНИМАНИЕ! Эта запись функции предполагает, что параметр «От» всегда меньше или равен параметру «До». 
Однако здесь следует сказать, что для преобразования массива символов в строку существует несколько более быстрый способ. Он основан на использовании функции «ЗначениеВСтрокуВнутр»

Функция ВСтроку(Массив) Экспорт

    Возврат
Сред(СтрЗаменить(ЗначениеВСтрокуВнутр(Массив), """}," + Символы.ПС + "{""S"",""", ""), 53 + СтрДлина(Формат(Массив.Количество(), "ЧГ=")), Массив.Количество())

КонецФункции

В этом варианте записи функции считается, что все элементы массива – это строки длиной в один символ. Ограничение длины легко преодолевается при чуть более сложной записи, а вот если в массиве могут оказаться данные разных типов, то, возможно, выгоднее будет применять рекурсивную функцию.
Для быстрого преобразования исходной строки в массив для ее обработки в таком виде можно использовать прием из статьи «Порождающий запрос»[http://infostart.ru/public/90367/]. Там этот прием использовался в задачах подсчета частоты символов и подсчета частоты слов в тексте.
В результате комбинация всех этих приемов позволяет решить, например, задачу быстрой транлитерации большого текста, представление текста первыми буквами всех его слов и тому подобные задачи, не решаемые комбинациями стандартных операций над строками.

В заключение хочется выразить надежду, что

  1. обозначенная проблема медленной конкатенации строк и показанная зависимость времени обработки от длины строк будет учитываться в практике программирования для платформы «1С: Предприятие»;
  2. приведенные функции окажутся востребованными, так как сокращают время выполнения часто используемых операций над строками;
  3. по аналогии с приведенными функциями и на их основе будут построены другие полезные функции обработки строк;
  4. анализ приведенных функций позволит лучше понять преимущества методов из статей «Порождающий запрос» [http://infostart.ru/public/90367/], «Транзитивное замыкание запросом»[http://infostart.ru/public/158512/], поскольку предлагаемые приемы и контрприемы имеют общую математическую основу.

Скачать файлы

Наименование Файл Версия Размер
Отчет ДвойнойОтжим 10
.erf 8,58Kb
25.11.12
10
.erf 8,58Kb Скачать

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Алексей Роза (DoctorRoza) 26.11.12 09:51
Скажите, а как часто у Вас появляется необходимость в использовании соединения строк, букв? В моей, скромной практике такое случается редко да и то когда нужно в, например, отчете соединить, типа - "Итого: " + Строка(Сумма). Но за работу плюс! :)
2. Александр Орефков (orefkov) 26.11.12 10:42
Резкие тормоза после 262144 - не связаны с записью на диск.
Скорее всего, это связано с менеджером выделения памяти, сделанном в 1С.
Видимо блоки размером до 0x40000 (а это и есть 262144) выделяются 1Ской из заранее выделенного пула, а за блоками большей длины аллокатор каждый раз обращается к ОС. Хотя это навскидку, детально код из "stl82.dll :: operator new" я не исследовал.
RailMen; tormozit; Serj1C; +3 Ответить 2
3. игорь ром (djd.sf) 26.11.12 10:45
интересно было бы посмотреть сравнение с ФорматированнаяСтрока из 8.3.
4. Александр Орефков (orefkov) 26.11.12 10:47
Ну и кроме того, во многих языках тупая работа со сложением строк неэффективна, и рекомендуется для этих целей использовать либо спец-объекты (StringBuilder в C# например), либо затачивать алгоритм.
5. Сергей (ildarovich) 26.11.12 10:50
(2) Да, такое объяснение больше похоже на правду. Для себя не вижу большой необходимости докапываться до первопричин в этом вопросе. Важнее зафиксировать обстоятельства возникновения эффекта и учесть его в разработке.
6. Александр Орефков (orefkov) 26.11.12 10:52
+(2)
Либо еще возможный вариант увеличения тормозов - до данного размера память в строке выделяется с запасом (т.е. например под строку в 17 символа память выделяется сразу для 32 символов, и пока строка не увеличится до 32 символов - перевыделения памяти и копирования символов не происходит, а потом сразу выделяется для 64 символов), а после этой магической константы память выделяется тютелька в тютельку каждый раз.
7. игорь ром (djd.sf) 26.11.12 10:52
в шарпе строки(String) иммутабельны, насколько мне известно, поэтому и неэффективно, для этого и существует класс StringBuilder . Что в 1С делать непонятно. (ВК писать нет никакого смысла). Вот ФорматированнаяСтрока появилась в 8.3.
8. Сергей (ildarovich) 26.11.12 10:58
(1) Довольно часто. Однако понятно, что эффект проявляется только на длинных строках, работать с которыми приходится реже. Я не такой фанат, чтобы вместо "а" + "б" + "р" + "а" + "к" + "а" + "д" + "а" + "б" + "р" + "а" писать ((("а" + "б") + "р")+ (("а" + "к") + "а")) + ((("д" + "а") + "б") + ("р" + "а")), хотя из статьи следует, что эта запись быстрее.
Очень часто приходится удалять лишние пробелы в наименованиях. Для меня открытием было то, что метод "условного отжима", который я использовал лишь для краткости записи, ОКАЗАЛСЯ ТАК ЭФФЕКТИВЕН.
9. Ярослав Радкевич (WKBAPKA) 26.11.12 17:43

Функция ПростойОтжим(Текст, Ответ = "", Было = "") Экспорт

Для ё = 1 По СтрДлина(Текст) Цикл Стало = Сред(Текст, ё, 1); Ответ = Ответ + ?(Было + Стало = " ", "", Стало); Было = Стало КонецЦикла;

Возврат Ответ

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


уже в этом тексте можно немного оптимизировать код, например, СтрДлина() вызвать до цикла и один раз :)

а вызвать функцию СтрЗаменить() не быстрее было бы, например

РезТекст = СтрЗаменить(Текст," ","");
10. Сергей (ildarovich) 26.11.12 18:14
(9) Не согласен:
- Выражение "По" в заголовке цикла "Для" считается ОДИН РАЗ (только что еще раз проверил);
- Менять пробел на пустышку так нельзя, так как ОДИН пробел между словами по условиям задачи должен остаться.
Al-X; bulpi; +2 Ответить 1
11. Алексей (devel0per) 27.11.12 01:08
Для работы с крупноразмерными текстами
меня еще моя бабушка учила юзать XSLT:
Процедура Тест1()
СтрXML = "<?xml version=""1.0"" encoding=""UTF-8""?>
|
|<text>
|	Примерчик,   с
|  большим     количеством                 лишненьких,
|	   случайненьких                           пробельчиков  
|	от     которых          мы хотим         
|                  отчесаться.
|
|</text>";

Преобразование = Новый ПреобразованиеXSL;
СтрокаXSLT = "<?xml version=""1.0""?>
|<xsl:stylesheet version=""1.0""           
|     xmlns:xsl=""http://www.w3.org/1999/XSL/Transform"">
|
|  <xsl:output method=""xml""   
|       omit-xml-declaration=""yes""/>
|
|<xsl:template match=""/text"">
|До: 
|<xsl:value-of select='.'/>
|Опосля: <xsl:value-of select='normalize-space()'/>
|</xsl:template>
|
|</xsl:stylesheet>";

Преобразование.ЗагрузитьИзСтроки(СтрокаXSLT);
СтрРез = Преобразование.ПреобразоватьИзСтроки(СтрXML);
Сообщить(СтрРез);

КонецПроцедуры

&НаКлиенте
Процедура Команда1(Команда)
	Тест1();
КонецПроцедуры
...Показать Скрыть
12. Сергей (ildarovich) 27.11.12 14:07
(11)
Если бабушка вам говорит, что без варежек играть в снежки удобнее - значит, это не ваша бабушка.
- А если серьезно, то спасибо за расширение кругозора. Вот только протестировать Ваш метод пока не смог. Переписал его вот в таком виде:
Функция ОтжимXSLT(Текст) Экспорт
	
	СтрXML = "<?xml version=""1.0"" encoding=""UTF-8""?>
	|
	|<text>
	|" + Текст + ".
	|
	|</text>";
	
	Преобразование = Новый ПреобразованиеXSL; 
	
	СтрокаXSLT = "<?xmlversion=""1.0""?>
	|<xsl:stylesheet version=""1.0""           
	|     xmlns:xsl=""http://www.w3.org/1999/XSL/Transform"">
	|
	|  <xsl:output method=""xml""   
	|       omit-xml-declaration=""yes""/>
	|
	|<xsl:template match=""/text"">
	|До: 
	|<xsl:value-of select='.'/>
	|Опосля: <xsl:value-of select='normalize-space()'/> </xsl:template>
	|
	|</xsl:stylesheet>";

	Преобразование.ЗагрузитьИзСтроки(СтрокаXSLT);
	
	Возврат Преобразование.ПреобразоватьИзСтроки(СтрXML)
	
КонецФункции
...Показать Скрыть
При вызове получаю ошибку:
{ВнешнийОтчет.ДвойнойОтжим.МодульОбъекта(89)}: Ошибка при вызове метода контекста (ЗагрузитьИзСтроки)
Преобразование.ЗагрузитьИзСтроки(СтрокаXSLT);
по причине:
Ошибка разбора XML: - [1,13]
Фатальная ошибка:
ParsePI: PI xmlversion space expected
13. Алексей (devel0per) 27.11.12 22:43
(12)
Караул грабят! Хулиганы на рынке форуме у прохожих пробелы отжимают!
Код
СтрокаXSLT = "<?xmlversion=""1.0""?>
Показать полностью

Я ясно помню!
Код
"xml<ВОТ ЗДЕСЬ/>version" 
Показать полностью
у меня стоял пробел. На каком ходу копи-пасты вы его съели?
Прикрепленные файлы:
14. Сергей (ildarovich) 28.11.12 00:29
(13) Извиняюсь за невнимательность - один пробел действительно "зажал"!
Провел эксперимент. Он показал, что метод с использованием "ПреобразованиеXSL" примерно на 30% медленнее предлагаемого на 1048576 символах теста при 50% заполнении пробелами. При сокращении количества пробелов до 0 проигрыш достигает четырех раз. С помощью прилагаемого отчета это можно проверить самостоятельно.
Прикрепленные файлы:
ДвойнойОтжим_.erf
15. Алексей (devel0per) 28.11.12 09:42
(14)
Это был шок! Я просто не мог поверить своим глазам!
Не смотря на то, что мне удалось добиться некоторой прибавки в быстродействии для функции XSLTОтжим,
главным образом, за счет вынесения переменной "Преобразование" в модуль объекта и путём замены output method с xml на text, ваш метод все равно работает быстрее.
Вот значения системных свойств XSLT:
Version: 1.0
Vendor: libxslt
Vendor URL: http://xmlsoft.org/XSLT/
Из этих значений можно предположить, что ваш метод работает быстрее, чем функция из библиотеки libxslt, которая написана на голом Си и входит в состав проекта GNOME.

ildarovich, спасибо за науку!
16. Алексей (devel0per) 28.11.12 15:14
(14)
Не давала мне покоя неудача с XSLT. Пришлось снять и выкинуть варежки.
Добавил функцию COMRegExp. Эксперименты показали, что метод с использованием
регулярных выражений быстрее двойного отжима приблизительно в 4-ре раза.
Обработка прилагается.
Прикрепленные файлы:
ДвойнойОтжим_.zip
ildarovich; +1 Ответить 1
17. bulpi bulpi (bulpi) 28.11.12 15:22
(10) ildarovich,
"Выражение "По" в заголовке цикла "Для" считается ОДИН РАЗ "

Таки да! Я в шоке. Век живи, век учись.
18. Сергей (ildarovich) 28.11.12 18:44
(16) RegExp - это конечно, первое, что приходит в голову, когда речь идет о подобных задачах. Сомневаться в его преимуществах здесь не приходится. Однако, это уже не 1С. Тем не менее спасибо за пример!
19. Erdos Temirzhanov (erdos) 28.11.12 23:31
а я думал xlst это не нужная штуковина в 1с
20. Ilya (i_volodin) 04.12.12 15:25
Можно, ли мне внеси маленькую лепту... к "обработкам строк"? Думаю, что обычный отжим Вы сильно тормознули. (Написал было код, да он как оказалось(как обычно) - не работает,) :) - исправлю - напиишу :)
21. Ilya (i_volodin) 04.12.12 16:46
Вот - вроде бы работающий код. Конечно он не обгонит Ваши новшества, но смыл такой, что бы убрать долгую функцию Сред()
Функция ПростойОтжим_2(Знач Текст) Экспорт
	НайденныйПробел = 1;
	Ответ = "";
	//Для П = 1 По СтрДлина(Текст) Цикл
	Пока НайденныйПробел<>0 Цикл
		НайденныйПробел = Найти(Текст, " "); 
		Ответ = Ответ + СокрЛ(Лев(Текст,НайденныйПробел));
		Текст = СокрЛ(Прав(Текст,СтрДлина(Текст)-НайденныйПробел));
	КонецЦикла;
	Возврат Ответ;
КонецФункции
...Показать Скрыть
ildarovich; +1 Ответить 1
22. Сергей (ildarovich) 04.12.12 17:26
(21) Илья! Ваш вариант мне понравился по двум причинам. Первое - в задаче об "отжиме" пробелов используется СокрЛ - функция "по теме". Второе - он действительно быстрее и из-за Сред(), но, главное (и об этом статья) - использует меньше конкатенаций. Настолько меньше, насколько больше одной буквы средняя длина слова. Если бы было нужно, я бы текст делил, применяя для половинок СокрЛП. В целом считаю Ваш вариант полезным идеями.
Однако для меня поиск решений данной задачи закрыт. Как делается оптимизация в коде 1С вообще - находится близкая по смыслу функция, которая делает "почти то, что нужно", но за один прием. Тут это и сделано по-максимуму. Статью я написал, потому, что меня поразило: насколько не эффективен путь стэйт-машины, которым идут все, кто обрабатывал строки на других языках. И я также думал: будет время, перепишу условный отжим на стэйт-машину и будет быстрее. И сильно ошибался. Когда формировал строку из мегабайта символов - 1С так подвисал, что я чуть было не начал платформу переустанавливать.
Ну и еще удивился очень близкой аналогии с приемом построения запроса. В той задаче никто не рискнул (а мог бы) предлагать другое решение, чтобы сравнить быстродействие, а здесь это легче.
23. Сергей (ildarovich) 16.05.13 13:22
В обсуждении к статье Составные типы — бесплатный сыр мышеловки производительности ее автор предложил для синтеза длинных строк использовать объект ЗаписьXML в виде функции (в моей интерпретации) наподобие
Функция ДлиннаяСтрокаЧерезЗаписьXML(Длина, Чего = "") Экспорт
	Запись = Новый ЗаписьXML;
	Запись.УстановитьСтроку(); 
	Чего = Лев(Чего + " ", 1);
	Для ё = 0 По Длина - 1 Цикл Запись.ЗаписатьБезОбработки(Чего) КонецЦикла;
	Возврат Запись.Закрыть()
КонецФункции
...Показать Скрыть
Она работает еще быстрее (примерно на 12%), чем функция через представление массива, приведенная в статье.
24. Алексей Опарихин (Al-X) 20.06.13 12:44
Мда !! Люблю я статьи про исследования 1С. За статью - спасибо ! Но я как-то слабо (точнее никак) представляю, когда может понадобиться обрабатывать строки большей длинны ? Может у меня не так много опыта еще....
25. Ilya (i_volodin) 20.06.13 14:52
(24) Al-X, Ну генерация текста запроса - самый очевидный ответ.
26. Святослав Ушаков (sacred) 28.10.13 13:14
(24) Al-X, А я как-то раз занимался "конвертированием" правил обмена из Конвертации данных в программный код. Строка там получалась зело длинная. Тогда я выкрутился созданием нескольких вложенных циклов, вместо одного линейного. Парадокс. Во внутреннем складывал 20-30 кусочков и полученная строчка уходила на обработку во внешний цикл. Внешний тоже складывал 10-20 уже укрупнённых строк. Ну и самый внешний складывал самые крупные куски. Такая методика сильно ускорила построение текста по сравнению с одним простым циклом.
Однако, сейчас я бы это делал через ЗаписьТекста/ТекстовыйДокумент.
27. Сергей (ildarovich) 28.10.13 13:56
(26) Самый быстрый из проверенных способов - через объект ЗаписьXML. Ссылка в комментарии (23).
28. serno (Sergey.Noskov) 17.07.14 15:13
(24) Al-X, формирование текстов писем, тестов логов, обмен через текстовые файлы
29. serno (Sergey.Noskov) 17.07.14 15:15
(27) ildarovich, ЗаписьТекста или ТекстовыйДокумент пробовали? Интересно узнать сравнительные замеры. Решал задачу связанную со сложением строк в базе ЦУП, использовал тогда ТекстовыйДокумент.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа