|
1 / 1 / 1
Регистрация: 21.11.2022
Сообщений: 15
|
||||||
Обращение к гуру для помощи с распареллеливанием задачи16.09.2024, 23:23. Показов 693. Ответов 8
Доброго времени суток, уважаемые знатоки
Задача такая - имеется список из n строк (n - большое число, 100к+), требуется сопоставить каждую строку из текста используя нечетким поиском, если значение метрики нечеткого поиска > определенного числа -> записать результат. С самой бизнес-логикой задачи разобрался, оптимизировал как мог, но на выборке из 150к строк обработка каждой занимает +-0.1 секунду, что довольно долго. Появилась идея прикрутить многопроцессорность, но из распараллеливании задач я знаю только то, что потоки используют общую память, а процессы нет ![]() Сам код:
В общем, никак не могу понять, есть ли вообще способы как-то это распараллелить (в идеале - через многопроцессорность) Нужно, чтобы процессы выполняли блок с удалением (for z in remove_list ) только тогда, когда все остальные процессы дошли до него + чтобы процессы не переходили к очередной итерации в цикле while до тех пор, пока все процессы не удалят в data то, что нужно PS Если у кого-то есть идеи по организации нечеткого поиска - поделитесь, очень поможете
0
|
||||||
| 16.09.2024, 23:23 | |
|
Ответы с готовыми решениями:
8
Решение задачи. Требуется мнение гуру
|
|
4523 / 1899 / 336
Регистрация: 18.01.2021
Сообщений: 3,489
|
|
| 17.09.2024, 06:54 | |
|
Для начала вообще уберите затратную операцию удаления из списка (включая мегазатратное data.pop(0)). Можно использовать булевый массив с флагами обработан/не обработан.
Если уж так хочется удалять, то удаляйте из set вместо list. Добавлено через 3 минуты Алгоритм у вас квадратичный, одной секунды все равно не будет, но мин за 10-15 (плюс/минус от мощности машины и сложности вашего if ...) управиться уже можно.
0
|
|
|
1 / 1 / 1
Регистрация: 21.11.2022
Сообщений: 15
|
||||||
| 17.09.2024, 10:27 [ТС] | ||||||
|
Изменил как вы и сказали, отказался от удаления
Первые строки все также обрабатываются за 0.08-0.1 сек. Но, большое спасибо за ваши мысли, с теперь организация мультипроцессорности кажется более простой задачей. Следовательно, появился вопрос, при организации многопроцессорной обработки могу ли я как-то избавится от коллизий? (сейчас код для каждого i ищет дубликаты в цикле по j, если нашел какие-то дубликаты, записывает в нужное место + "удаляет" дубликаты из data, т.е. не может быть ситуации, что для разного i код может обнаружить одинаковый дубликат (т.е. индекс j)) Но в случае с многопроцессорной обработкой такое случиться может (если я правильно понимаю). Стоит ли пытаться указывать для каждого процесса логику, когда ему можно обрабатывать список, а когда выставлять флаги(если это вообще возможно), или проще после завершения расчетов пройтись по файлу, который вышел и удалить все дубликаты? (файл становится в 5-10 раз меньше + у каждой строки есть свой уникальный id, вроде не так затратно получается)
0
|
||||||
|
91 / 58 / 14
Регистрация: 16.11.2018
Сообщений: 274
|
|
| 17.09.2024, 10:46 | |
|
Можешь попробовать развернуть цикл и за один проход брать по 4 - 20 порций данных они вроде не пересекаюцо.
На интерпретаторе питона это не даст такого же эффекта как в компилируемых языках с оптимизаторами но эффект должен быть заметен хоть не очень понятно что это за данные если порция данных большая то пляски вокруг них не дадут заметного эффекта. В таких задачах меня выручает TCC & notepad++ =). Предположу что данный код это попытка реализации аналитики на базой данных только без средств аналитики и базы данных только питон.
0
|
|
|
1 / 1 / 1
Регистрация: 21.11.2022
Сообщений: 15
|
||
| 17.09.2024, 11:00 [ТС] | ||
|
Это попытка развернуть сервис для 1С для нечеткого поиска дубликатов, сейчас я беру данные из обычного json (выгрузка нужной мне базы), но в будущем данные будут браться из БД, для этого планирую использовать Elasticsearch (пока не щупал что это, но товарищ посоветовал присмотреться)
А каждая порция - это от 1 до 10 строк
0
|
||
|
4523 / 1899 / 336
Регистрация: 18.01.2021
Сообщений: 3,489
|
|
| 17.09.2024, 11:48 | |
|
Судя по коду, ваше соответствие обладает свойством транзитивности, т.е. если i~j и j~k, то i~k.
В таком случае список распадается на классы эквивалентности(рефлексивность и симметричность по определению). Классы можно обрабатыывать СНМ (система непересекающихся множеств), по буржуйски DSU (disjoint-set unit). Изначально каждый класс содержит один элемент. Вы делите массив на несколько частей (число настраивается в зависимости от числа ядер и среднего размера одного класса) Далее, в каждой части вы объединяете классы при соответствии их представителей. Обработка каждой части происходит параллельно на отдельном ядре. И т.д. Пока не произойдет сравнений по всем классам. Можно идти рекурсивно сверху вниз, деля изначальное множество на 2 или несколько частей. А можно снизу вверх, поделив сразу до минимального обрабатываемого куска.
1
|
|
|
1 / 1 / 1
Регистрация: 21.11.2022
Сообщений: 15
|
|
| 17.09.2024, 13:05 [ТС] | |
|
Ох ты, про классы эквивалентности (особенно про свойство транзитивности) это вы здорово что написали.
(было в универе когда-то, смутно помню). Про СНМ прочитаю, спасибо Но, я правильно понимаю, что ваш совет относится к той части, когда я уже обработал нечетким поиском свои данные? т.е. условно выделены такие классы (множества) { id1 id2 id3 id4 } { id5 id6 id7 } { id3 id8 id9 } И суть в том, чтобы эффективно объединить множество 1 и множество 3? Добавлено через 22 минуты Хотя стоп, я же привел пример пересекающихся множеств ...
0
|
|
|
1712 / 579 / 76
Регистрация: 10.04.2009
Сообщений: 9,327
|
|
| 17.09.2024, 13:33 | |
|
0
|
|
|
91 / 58 / 14
Регистрация: 16.11.2018
Сообщений: 274
|
||
| 17.09.2024, 13:56 | ||
|
Стоит познакомиться с таким невкусным кактусом как PyCUDA. От него никуда не деться когда поднимается вопрос оптимизации расчетов. =(
Не понятны качественные характеристики работы алгоритма. Возможно многопоточность хромает на обе ноги из за глобальных блокировок интерпретатора. Обычно с работы кода снимают профиль работы каким нибудь профилировщиком и анализируют работу на предмет узких мест и самых затратных операций что сильно помогает в процессе оптимизации. Добавлено через 4 минуты А нотепат просто настроен на роль ИДЕ.
0
|
||
| 17.09.2024, 13:56 | |
|
Помогаю со студенческими работами здесь
9
Разработка программы для численного решения модельной задачи при помощи метода левой прогонки обращение матриц при помощи разбиения на клетки Обращение к символам строки при помощи строковых команд Обращение матрицы и решение СЛАУ при помощи LU разложения Решить краевую задачу при помощи функции Грина. Построить функцию Грина и выписать решение краевой задачи для уравнения Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ВВЕДЕНИЕ
Выполняя задание на управление насосной группой заполнения резервуара,. . .
|
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
|
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога
Финальные проекты на Си и на C++:
hello-sdl3-c. zip
hello-sdl3-cpp. zip
Результат:
|
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога
MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
|
|
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд.
Даже если у вас. . .
|
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает
монорепозиторий в котором находятся все исходники.
При создании нового решения, мы просто добавляем нужные проекты
и имеем. . .
|
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение:
В этой книге («Подход, основанный на вариантах использования») Ивар утверждает,
что архитектура программного обеспечения — это
структуры,. . .
|
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога
Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
|