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

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

16.09.2024, 23:23. Показов 693. Ответов 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
Сообщений: 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 (пока не щупал что это, но товарищ посоветовал присмотреться)


Цитата Сообщение от 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
1712 / 579 / 76
Регистрация: 10.04.2009
Сообщений: 9,327
17.09.2024, 13:33
Цитата Сообщение от MallSerg Посмотреть сообщение
TCC & notepad++
это что за зверь?
0
 Аватар для MallSerg
91 / 58 / 14
Регистрация: 16.11.2018
Сообщений: 274
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
Ответ Создать тему
Новые блоги и статьи
[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-код на мобильном. Вращайте камеру одним пальцем,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru