Конкурс "Вопрос-Решение". "Найти символьные вхождения в строке".

05.04.13

Разработка - Математика и алгоритмы

+3 –
  • Скрин
В конкурсе "Вопрос-Решение" была задана задача": "Найти символьные вхождения в строке". Вот моё решение.

Файлы

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование Скачано Купить файл
ПоискВхождений_00.epf
.epf 9,57Kb
14 2 500 руб. Купить

Подписка PRO — скачивайте любые файлы со скидкой до 85% из Базы знаний

Оформите подписку на компанию для решения рабочих задач

Оформить подписку и скачать решение со скидкой

Вы можете заказать платную доработку или адаптацию этой разработки под вашу конфигурацию на «Бирже заказов».

  • 0% комиссии — оплата напрямую исполнителю;
  • Исполнители любого масштаба — от отдельных специалистов до команд под проект;
  • Прямой обмен контактами между заказчиком и исполнителем;
  • Безопасная сделка — при необходимости;
  • Рейтинги, кейсы и прозрачная система откликов.

Условия конкурса. 

 

решение данной задачи относительно несложное. вот что получилось.

с Уважением Шёпот теней, в миру Александр Шишкин.

буду рад критики, поддержке конкурса, советам ...

 

... вот ... 

Вступайте в нашу телеграмм-группу Инфостарт

+3 –

См. также

Улучшенный алгоритм Левенштейна для 1С: интеллектуальное сравнение строк

Математика и алгоритмы Программист 1С 8.3 Абонемент ($m)

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

1 стартмани

07.11.2025    5406    14    InFlach    17    

27
Поиск дублей по полям ключей шапки, табличных частей

Математика и алгоритмы Запросы Программист 1С:Предприятие 8 Бесплатно (free)

Рассмотрим быстрый алгоритм поиска дублей с использованием hash функции по набору полей шапки и табличных частей.

08.07.2024    5620    ivanov660    9    

24
Метод Дугласа-Пойкера

Математика и алгоритмы Программист 1С:Предприятие 8 1C:Бухгалтерия Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    13625    stopa85    12    

43
Алгоритм симплекс-метода

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    21594    user1959478    57    

40
Математический тренажер созданный для тестирования Вашего ребенка на предмет: умножения, деления, сложения и вычитания.

Математика и алгоритмы Разное 1С:Предприятие 8 1C:Бухгалтерия Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    12851    maksa2005    8    

27
Регулярки на 1С

Математика и алгоритмы Инструментарий разработчика Программист 1С:Предприятие 8 Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    22460    11    SpaceOfMyHead    20    

65
Мини-обзор разных решений задач

Математика и алгоритмы Программист 1С:Предприятие 8 1C:Бухгалтерия Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    14577    RustIG    9    

30
Тестирование средств 1С для решения СЛАУ

Механизмы платформы 1С Математика и алгоритмы Программист 1С:Предприятие 8 Россия Бесплатно (free)

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

23.11.2022    13609    gzharkoj    15    

27
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. ildarovich 8056 08.04.13 12:56 Сейчас в теме
Под конструктивной критикой можно понимать лучшее решение. В этом смысле моя критика будет неконструктивной.
1. Пример текста к задаче был бы гораздо интереснее и привлек бы больше внимания, если бы являлся кодом программы на языке 1С. Поиск повторов в тексте программ – для многих здесь более актуальная задача, чем анализ стихотворного текста.
2. Относительно небольшое решение должно публиковаться в тексте статьи, а текст обработки прилагаться для проверки. Комментировать решения, методы и алгоритмы удобнее, имея их перед глазами.
3. В обработке по сути, два отдельных метода: предварительная обработка строки (фильтрация и замена символов) и собственно, поиск повторов.
4. Фильтрация и замена символов сделана «с многочисленными огрехами»:
4.1. Сам по себе принцип «наращивания» результирующей строки приведет к тому, что на реальных данных производительность метода быстро деградирует (см. статью «Опять двойка!»). То есть здесь ГОРАЗДО быстрее будет работать цикл из функций «СтрЗаменить».
4.2. В такой простой задаче используется три разных механизма фильтрации и замены: структура для замены (???), поиск в строке алфавита для фильтрации и приведение к нужному регистру. Все преобразования можно выполнить через одно соответствие.
4.3. Структуру для замены использовать неправильно – она для этого не предназначена (хотя и работает, но логарифмической линейкой тоже гвозди забивали) – см. комментарии к статье «Эфективная обработка данных за счет использования коллекции соответствие».
4.4. Зачем заменять на пустышку мягкие и твердые знаки? – Их лучше исключить из алфавита.
4.5. Какой смысл в плавающих отступах?
5. Никаких алгоритмических находок нет. Это решение задачи «в лоб». Время решения пропорционально длине строки в кубе! Тогда как применение суффиксного массива и алгоритма Касаи дает линейное время (не вполне уверен именно в линейности, но точно меньше квадрата). Но даже просто кодирование поиска повторов также не может быть образцом:
5.1. Лишние присваивания исходной строки.
5.2. Лишние вычисления длины строки (в ограничении цикла Для функции вычисляются единственный раз, поэтому нет нужды вычислять длины заранее).
5.3. Вместо ограничения диапазона внутреннего цикла делается проверка длины вырезки, а ведь длина строки долго (пропорционально длине строки) вычисляется.
5.4. Для уже отстатистированной подстроки опять считается число вхождений! (зачем закомментирована проверка?).
5.5. Если подстрока уже не найдена более одного раза, зачем искать еще раз искать более длинные подстроки? Результат будет тем же.
В общем, задача актуальная и интересная, а решение еще улучшать и улучшать.
agrustny; Шёпот теней; +2 – Ответить
2. Шёпот теней 1786 08.04.13 13:25 Сейчас в теме
(1) ... вот бы ещё и посмотреть ...
+ – Ответить
4. ildarovich 8056 08.04.13 14:00 Сейчас в теме
(2)
... вот бы ещё и посмотреть ...
- уточните, пожалуйста, что имели ввиду.
+ – Ответить
5. Шёпот теней 1786 08.04.13 14:07 Сейчас в теме
(4) посмотреть - готовое решние со всеми вашими замечаниями! ... впрочем, я не провоцирую - я согласен с вами ...

... вот ...
+ – Ответить
7. ildarovich 8056 08.04.13 15:16 Сейчас в теме
(5) Провести рефакторинг Вашего решения - тут нет проблем, это не долго (но не интересно), а вот реализовать правильный алгоритм - пока не решил - стоит ли этим заниматься. Вообще не уверен, что на 1С следует решать сложные задачи обработки строк не как учебные. Это не та сфера применения, где платформа 1С эффективна. Для таких случаев разработчики заложили в платформу технологию внешних компонент и нужно использовать их.
+ – Ответить
8. Шёпот теней 1786 08.04.13 15:31 Сейчас в теме
(7) ...нууу, так не интересно ... подобно можно ответить на любой вопрос ...

как МЫ знаем - нет универсальных языков програмирования ... каждый под что-то заточен ...

мы не говорим про эффективность программной среды, мы говорим о выполнении задачи языком 1С ...

в остальном же это дело вкуса, желания, возможности, умения, навыков и пр. ...

... вот ...

п.с. все люди делятся на две категории:
1. одни ищут слова, чтобы отказаться от дела
2. вторые ищут дела, чтобы выполнить свои слова

...
+ – Ответить
9. AlexO 136 08.04.13 16:15 Сейчас в теме
(8)
1. одни ищут слова, чтобы отказаться от дела
2. вторые ищут дела, чтобы выполнить свои слова

Ильдарович ищет знаков, чтобы найти "заточенность" 1С :)
+ – Ответить
10. Шёпот теней 1786 08.04.13 16:26 Сейчас в теме
(9) ... лаТно ужжж Вам ... ))) ...

Сергей Ильдарович - не поленился: скачал, заглянул, увидел, структурировал - высказался !!! за, что ему спАсибо ...

п.с.0. ну, не любит он язык 1С ...
п.с.1. зато любит язык запросов !!!

... вот ...
+ – Ответить
11. agrustny 19 29.04.14 14:59 Сейчас в теме
(10) Профессор Эльдорадович в отношении данной публикации сделал все правильно. Я так считаю.
+ – Ответить
12. Шёпот теней 1786 05.05.14 09:38 Сейчас в теме
(11) agrustny, правильно? не правильно? :

правильно это когда 3+3+3 = 9 а иное - не правильно !!! а вот когда 3*3=9 это тоже правильно ... остальное это споры о "вкусах" ...

... вот моЁ мнение ...
+ – Ответить
13. agrustny 19 05.05.14 16:30 Сейчас в теме
(11) ... вот моЁ мнение ...
+ – Ответить
14. ildarovich 8056 30.07.14 12:27 Сейчас в теме
(8) все же не давала мне покоя эта задача и я постарался ее решить. Решение приведено в статье КопиПастаМер. Правда, в самой статье акцент сделан на практическое применение - поиск повторяющихся фрагментов кода в типовых конфигурациях.

Получились очень интересные результаты (повторов кода в типовых - до фига и больше).

Решение описано штрих-пунктирно, но, если заинтересуетесь, могу дать пояснения. В целом, оказалось, что применив алгоритм Мандера-Майерса и Касаи, можно НА ЧИСТОМ 1С за 15 минут найти ВСЕ повторяющиеся фрагменты в строке из 3,5 миллиона символов.

До этого то же самое сделал на языке запросов, но получилось слишком громоздко и есть одно тонкое место - пока не стал доводить до ума, хотя осталось чуть-чуть.
+ – Ответить
15. Шёпот теней 1786 30.07.14 13:30 Сейчас в теме
(14) ildarovich,
Спасибо! вернее ОЧЕНЬ тебе БЛАГОДАРЕН за все твои решения и великие умения !!!

"В целом, оказалось, что применив алгоритм Мандера-Майерса и Касаи, можно НА ЧИСТОМ 1С за 15 минут найти ВСЕ повторяющиеся фрагменты в строке из 3,5 миллиона символов. "
- вот ведь !!!

если же смотреть на "Повторяемость кода в 1С" - то надо задать и другой вопрос - "А?!, где он не повторяется?" ... сложность написания программы коллективом сложнее чем представляется с т.з. "просто кода" т.к. не "код" определяет работу программы.

...вот...
+ – Ответить
16. ZLENKO 398 29.04.15 16:09 Сейчас в теме
(15) "Спасибо! вернее ОЧЕНЬ тебе БЛАГОДАРЕН за все твои решения и великие умения !!!"

Уже скоро год (судя по дате последнего поста в форуме) как Шёпот теней покинул ИС ?
+ – Ответить
17. AlexO 136 30.04.15 09:22 Сейчас в теме
(16) ZLENKO, да, увы, путный народ разбегается, "среда обитания" вынуждает...
+ – Ответить
18. Шёпот теней 1786 30.04.15 14:32 Сейчас в теме
(16), (17) ... уффф ...

"равнение на среднего приводит к обнулению" это то самое исключение которое не подтверждает правило "перехода количества в качество" ...

... вот ...
ZLENKO; +1 – Ответить
6. AlexO 136 08.04.13 14:07 Сейчас в теме
(4) ildarovich,
"мы не ищем легких путей.."
и простых вопросов :)
+ – Ответить
3. AlexO 136 08.04.13 13:29 Сейчас в теме
(1) ildarovich,
Поиск повторов в тексте программ

это как изволите анализировать? :)
Точнее, как собираетесь анализировать эти самые повторы?
Про невозможность в принципе "увидеть" код типовых - не говорю уже.
И никакая 8.3 тут не поможет, пока 1С не сделает компиляцию отдельно от платформы.
+ – Ответить
Для отправки сообщения требуется регистрация/авторизация