Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
1 / 1 / 1
Регистрация: 21.11.2022
Сообщений: 15

Обращение к гуру для помощи с распареллеливанием задачи

16.09.2024, 23:23. Показов 667. Ответов 8

Студворк — интернет-сервис помощи студентам
Доброго времени суток, уважаемые знатоки

Задача такая - имеется список из n строк (n - большое число, 100к+), требуется сопоставить каждую строку из текста используя нечетким поиском, если значение метрики нечеткого поиска > определенного числа -> записать результат.

С самой бизнес-логикой задачи разобрался, оптимизировал как мог, но на выборке из 150к строк обработка каждой занимает +-0.1 секунду, что довольно долго. Появилась идея прикрутить многопроцессорность, но из распараллеливании задач я знаю только то, что потоки используют общую память, а процессы нет

Сам код:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    while data:
        element_i = data.pop(0)
 
        results = []
        remove_list = []
        for j in data:
            if (............................):
'''
Тут происходят все сопоставления, не вижу смысла их загружать
Берутся все элементы из element_i и сопоставляются соответственно с каждым элементов из j
'''
# В случае, если нашел для element_i - сохраняет результат + добавляет j в список на удаление
                results.append(j)
                remove_list.append(j)
 
        for z in remove_list:
            data.remove(z)
'''
Дальше он записывает все то, что попало в result в отведенное место, идет переход к while
'''

В общем, никак не могу понять, есть ли вообще способы как-то это распараллелить (в идеале - через многопроцессорность)
Нужно, чтобы процессы выполняли блок с удалением (for z in remove_list ) только тогда, когда все остальные процессы дошли до него + чтобы процессы не переходили к очередной итерации в цикле while до тех пор, пока все процессы не удалят в data то, что нужно


PS
Если у кого-то есть идеи по организации нечеткого поиска - поделитесь, очень поможете
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
16.09.2024, 23:23
Ответы с готовыми решениями:

Обращение к гуру numpy
Здравствуйте уважаемые гуру и знатоки... Я новичок в данной области и у меня возник вопрос: Может быть это простой и глупый...

Решение задачи. Требуется мнение гуру
Здравствуйте! Собираюсь на курсы по Java в Epam, поэтому решил порешать их задачки какие только можно найти в сети. Хочу услышать...

Составить программу для решения задачи с целыми числами при помощи циклов
Что за бред...Как это сделать? Составить программу для решения задачи с целыми числами при помощи циклов. Долгожитель (возраст не...

8
Эксперт Python
 Аватар для Red white socks
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  [ТС]
Изменил как вы и сказали, отказался от удаления

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    
for i in range(len(data)):
        if data[i][5]:
            continue
        else:
            data[i][5] = True
 
        results = []
        for j in range(len(data)):
            if data[j][5]:
                continue
                if (............................):
 
'''
Тут происходят все сопоставления, не вижу смысла их загружать
Берутся все элементы из element_i и сопоставляются соответственно с каждым элементов из j
'''
# В случае, если нашел для element_i - сохраняет результат + добавляет j в список на удаление
                    results.append(j)
                    data[j][5] = True
ииииии... не получил заметного прироста по производительности.... (по хорошему нужно конечно проводить тесты, смотреть за сколько обработает 1к, 10к, 100к и тд, но не хочу на это тратить время)
Первые строки все также обрабатываются за 0.08-0.1 сек.


Но, большое спасибо за ваши мысли, с теперь организация мультипроцессорности кажется более простой задачей.


Следовательно, появился вопрос, при организации многопроцессорной обработки могу ли я как-то избавится от коллизий?
(сейчас код для каждого i ищет дубликаты в цикле по j, если нашел какие-то дубликаты, записывает в нужное место + "удаляет" дубликаты из data, т.е. не может быть ситуации, что для разного i код может обнаружить одинаковый дубликат (т.е. индекс j)) Но в случае с многопроцессорной обработкой такое случиться может (если я правильно понимаю).

Стоит ли пытаться указывать для каждого процесса логику, когда ему можно обрабатывать список, а когда выставлять флаги(если это вообще возможно), или проще после завершения расчетов пройтись по файлу, который вышел и удалить все дубликаты? (файл становится в 5-10 раз меньше + у каждой строки есть свой уникальный id, вроде не так затратно получается)
0
 Аватар для MallSerg
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 (пока не щупал что это, но товарищ посоветовал присмотреться)


Цитата Сообщение от MallSerg Посмотреть сообщение
они вроде не пересекаюцо
Пересекаются.....
А каждая порция - это от 1 до 10 строк
0
Эксперт Python
 Аватар для Red white socks
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
Цитата Сообщение от MallSerg Посмотреть сообщение
TCC & notepad++
это что за зверь?
0
 Аватар для MallSerg
91 / 58 / 14
Регистрация: 16.11.2018
Сообщений: 273
17.09.2024, 13:56
Стоит познакомиться с таким невкусным кактусом как PyCUDA. От него никуда не деться когда поднимается вопрос оптимизации расчетов. =(

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

Добавлено через 4 минуты
Цитата Сообщение от Ципихович Эндрю Посмотреть сообщение
TCC
Не самый оптимальный но очень маленький и быстрый компилятор c/c++ с возможностью собирать и запускать приложения сразу в памяти. Когда не хватает возможностей скриптов самое то =).
А нотепат просто настроен на роль ИДЕ.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
17.09.2024, 13:56
Помогаю со студенческими работами здесь

Разработка программы для численного решения модельной задачи при помощи метода левой прогонки
# include <iostream> # include <locale.h> # include <math.h> using namespace std; #define PI 3.1415926 using namespace std;...

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

Обращение к символам строки при помощи строковых команд
Помогите пожалуйста вот с чем - мне необходимо осуществить ввод\вывод через Си, а обработку строки - через ассемблер. Не мог бы кто...

Обращение матрицы и решение СЛАУ при помощи LU разложения
Обращение матрицы и решение СЛАУ при помощи LU разложения//// РЕАЛИЗАЦИЯ ПРОГРАММЫ В delphi ... вывести нужно Матрицу исходную,LU...

Решить краевую задачу при помощи функции Грина. Построить функцию Грина и выписать решение краевой задачи для уравнения
Решить краевую задачу при помощи функции Грина. Построить функцию Грина и выписать решение краевой задачи для уравнения ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
Первый деплой
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
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru