|
1 / 1 / 1
Регистрация: 21.11.2022
Сообщений: 15
|
||||||
Обращение к гуру для помощи с распареллеливанием задачи16.09.2024, 23:23. Показов 667. Ответов 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
Сообщений: 273
|
|
| 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
|
|
|
1711 / 578 / 76
Регистрация: 10.04.2009
Сообщений: 9,306
|
|
| 17.09.2024, 13:33 | |
|
0
|
|
|
91 / 58 / 14
Регистрация: 16.11.2018
Сообщений: 273
|
||
| 17.09.2024, 13:56 | ||
|
Стоит познакомиться с таким невкусным кактусом как PyCUDA. От него никуда не деться когда поднимается вопрос оптимизации расчетов. =(
Не понятны качественные характеристики работы алгоритма. Возможно многопоточность хромает на обе ноги из за глобальных блокировок интерпретатора. Обычно с работы кода снимают профиль работы каким нибудь профилировщиком и анализируют работу на предмет узких мест и самых затратных операций что сильно помогает в процессе оптимизации. Добавлено через 4 минуты А нотепат просто настроен на роль ИДЕ.
0
|
||
| 17.09.2024, 13:56 | |
|
Помогаю со студенческими работами здесь
9
Разработка программы для численного решения модельной задачи при помощи метода левой прогонки обращение матриц при помощи разбиения на клетки Обращение к символам строки при помощи строковых команд Обращение матрицы и решение СЛАУ при помощи LU разложения Решить краевую задачу при помощи функции Грина. Построить функцию Грина и выписать решение краевой задачи для уравнения Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Первый деплой
lagorue 16.01.2026
Не спеша развернул своё 1ое приложение в kubernetes.
А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения
развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .
|
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ *
Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам
Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .
|
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым.
Но восстановить их можно так.
Для этого понадобится консольная утилита. . .
|
Изучаю kubernetes
lagorue 13.01.2026
А пригодятся-ли мне знания kubernetes в России?
|
|
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
|
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11
— это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
|
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11
Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
|
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
|