Ускорение алгоритма за счет разбиения оного на потоки

@Lesch · Регистрация: 28.05.2020

Студворк — интернет-сервис помощи студентам

Ребят, есть алгоритм кодирования со строками огромной длины, работает вроде бы быстро,но то что нужно закодировать по размерам ну просто огромное(13,5 миллионов символов) . На то чтобы это закодировать и раскодировать уходит около 150 минут XD. Если я попытаюсь разбить его на потоки( System.Threading) ,скажем так на штук 16,будет ли от этого смысл ? Просто прочитал что хочешь не хочешь процессор все равно по сути последовательно делает операции.Спасибо

@Элд Хасп · 24.04.2023, 17:03

Сообщение от Lesch

есть алгоритм

Какой?

Сообщение от Lesch

со строками огромной длины

Позволяет ли алгоритм блочную обработку?
То есть - результата кодирования строки 2 ни как не зависит от кодирования строки 1 и ни как не влияет на кодирование строки 3?

Сообщение от Lesch

Просто прочитал что хочешь не хочешь процессор все равно по сути последовательно делает операции

Нет. Процессор (современный) выполняет операции в нескольких потоках на нескольких ядрах параллельно относительно друг друга.
Другое дело. что конкретный алгоритм, задача могут быть не подходящими для распараллеливания.
Типичный пример - работа с текстовым файлом на диске. По факту распараллеливание чтения даст даже хуже результат чем чтение в одном потоке.

@Lesch · 24.04.2023, 17:16 **[ТС]**

Сообщение от Элд Хасп

Позволяет ли алгоритм блочную обработку?

Думаю да,кодирование происходит по 600 символов ,вроде это можно назвать блоком.

Добавлено через 2 минуты

Сообщение от Элд Хасп

Какой?

Рида-Соломона

@Элд Хасп · 24.04.2023, 18:06

Сообщение от Lesch

Думаю да,кодирование происходит по 600 символов ,вроде это можно назвать блоком.

Самый простой способ:
- однопоточный Reader Enumerable<byte> считывающий по 600 байт;
- однопоточный Writer пишущий результаты кодирования блока;
- какой-то семафор-очередь с 10-20 потоками, которые по очереди обращаются к Reader, кодируют блоки и по очереди передают их в Writer;

Эффективность будет переделяться тем какая доля времени из общего приходится на кодирование (обычно самые медленные операции это ввод-вывод, а не кодирование). С учётом накладных расходов, если это значение 50% и меньше, то распараллеливание не будет иметь выгод. Безусловная выгода будет для доли >90%.

@Lesch · 24.04.2023, 18:17 **[ТС]**

Сообщение от Элд Хасп

(обычно самые медленные операции это ввод-вывод, а не кодирование).

В моем случае самой прожорливой операцией оказалось кодирование,поэтапно замерял скорость. Общее время кодирования и декодирования 0,084c , ~0,052с занимает кодирование

@Элд Хасп · 24.04.2023, 18:26

Lesch, тогда это будет для вас эффективно.
Что помешало вам это реализовать?

@Lesch · 24.04.2023, 19:26 **[ТС]**

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

Добавлено через 2 минуты
Удивительно что такая по сути простая работа со строками такая прожорливая. Скорее всего я намудрил со всем.

@Элд Хасп · 24.04.2023, 21:11

Сообщение от Lesch

Удивительно что такая по сути простая работа со строками такая прожорливая.

Строки это, наверное, самый прожорливый из простых .Net типов и самый медленный.
Работать нужно с байтовым потоком, а не со стрингами.

Добавлено через 2 минуты
Тем более, что код Рида-Соломона лучше всего ложится на двоичные данные: биты, байты, short, uint, ulong.

@Lesch · 24.04.2023, 21:24 **[ТС]**

Сообщение от Элд Хасп

Тем более, что код Рида-Соломона лучше всего ложится на двоичные данные: биты, байты, short, uint, ulong.

Да все верно,работа вся в байтах ,но эти байты как раз из строк получаются,дело в этом. Строка -> байт -> вычисления -> байт -> строка;

@Элд Хасп · 24.04.2023, 23:03

Сообщение от Lesch

Строка -> байт -> вычисления -> байт -> строка;

??? !!!
С какого перепуга?
Исходная информация разве не в файле?

Добавлено через 2 минуты
Скорее всего у вас всё и теряется на этом двойном-тройном преобразовании: Файл (он всегда двоичный) -> строка -> двоичные байты -> Опять строка -> Файл (опять двоичный). 4-х кратное преобразование!

@Lesch · 24.04.2023, 23:07 **[ТС]**

Вот вы сейчас сказали про это и меня осенило. Получается я могу загрузить файл(фото,видео, не важно) и закодировать его ? Изначально просто "чинил" текст любой вводимый мной, а потом на уже разные другие масштабные идеи появились

@Элд Хасп · 24.04.2023, 23:10

Сообщение от Lesch

Получается я могу загрузить файл(фото,видео, не важно) и закодировать его ?

Конечно.
Только сами себе усложнили и замедлили задачу стрингами.

@Lesch · 24.04.2023, 23:14 **[ТС]**

Я просто когда это делал,допустим фото, разбивал по пикселям и по цветам и дальше уже по 16(64 цвета (байта)) пикселей кодировал. Если можно обойтись без разбивки на это то это просто супер. Я не додумался xD

@EugenyS · 25.04.2023, 00:23

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

Однако, в случае с большими данными, можно использовать подход MapReduce. Он позволяет параллельно обрабатывать большие объемы данных на кластере из нескольких вычислительных узлов. В этом случае данные разбиваются на меньшие блоки, которые обрабатываются параллельно на узлах кластера. После этого результаты собираются в единую последовательность.

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

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

@Lesch · 25.04.2023, 00:35 **[ТС]**

Вы просто гляньте на эту красоту, первое фото размер байтового массива где я перелопачивал фото по пикселям а потом по цветам (6000000++) а второе где сразу взял массив байт из фото (240000) разница в 25 раз, и никаких больше строк, если это действительно сработает то это будет просто бомба

@Lesch · 25.04.2023, 00:38 **[ТС]**

Добавлено через 39 секунд
EugenyS, Обязательно попробую ,спасибо!

@Элд Хасп · 25.04.2023, 08:32

Сообщение от Lesch

EugenyS, Обязательно....

Это ChatGPT. Смысла в его ответе нет. По крайней мере, для применения на Шарпе в настольном компе.

Добавлено через 2 минуты

Сообщение от Lesch

разница в 25 раз, и никаких больше строк, если это действительно сработает то это будет просто бомба

Должно сработать.
Код Рида-Соломона он же не искажает первичную информацию, а напротив нацелен на её полное восстановление даже если будут случайные искажения при передаче информации.

@Wolfdp · 25.04.2023, 09:36

Не по теме:

Сообщение от Элд Хасп

Это ChatGPT. Смысла в его ответе нет. По крайней мере, для применения на Шарпе в настольном компе.

Я рыдаю...

Сообщение от Lesch

Получается я могу загрузить файл(фото,видео, не важно) и закодировать его ?

Все и вся храниться в виде двоичной логике. Двоичная логика это тоже самое что и десятеричная, просто набор сокращен до 2 значений (долго объяснять причины). Грубо говоря любой файл -- тупо последовательность чисел, которая в дальнейшем программа как-либо итрепритирует.

Исходя из этого, всякие алгоритмы шифрования, архивирования и прочих преобразований абстрактных данных всегда работает с блоками байт (отсюда и вся работа в Stream, при работе с файлами). В общем совет от Элд Хасп самый дельный

Сообщение от Элд Хасп

Самый простой способ:
- однопоточный Reader Enumerable<byte> считывающий по 600 байт;
- однопоточный Writer пишущий результаты кодирования блока;

Изначально стоит реализовать однопоточный вариант, где читаешь-преобразовываешь-пишешь. Причину уже указывали выше: запись/чтения с диска гораздо медленее, чем обработка данных CPU. Проблема лежит в том что ЛЮБАЯ работа с диском ПОСЛЕДОВАТЕЛЬНАЯ, т.е. если вы одновременно сформировали 100 блоков для записи, то они уйдут исключительно очередью.

@NEED-A-JOB · 25.04.2023, 09:43

Сообщение от Lesch

Вы просто гляньте на эту красоту,

на картинки посмотреть? да я получше в фотошопе нарисую.

@Lesch · 25.04.2023, 13:21 **[ТС]**

Сообщение от Неко с ушами

Все и вся храниться в виде двоичной логике. Двоичная логика это тоже самое что и десятеричная, просто набор сокращен до 2 значений (долго объяснять причины). Грубо говоря любой файл -- тупо последовательность чисел, которая в дальнейшем программа как-либо итрепритирует.

Да это и так понятно, на транзисторах же основан процессор оттуда и двоичная система 1 и 0. Дело в том что я до этого разбивал фото на пиксели и потом уже пиксели на цвета (а это миллионы байт информации на выходе) , просто оказывается что можно брать массив байт сразу с фото, и главное он короче сильно хоть и не понятно что он в себе несет и почему такой короткий.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Lesch 3 / 2 / 1 Регистрация: 28.05.2020 Сообщений: 172

	Ускорение алгоритма за счет разбиения оного на потоки 24.04.2023, 16:31. Показов 2209. Ответов 28 Метки нет (Все метки) Ребят, есть алгоритм кодирования со строками огромной длины, работает вроде бы быстро,но то что нужно закодировать по размерам ну просто огромное(13,5 миллионов символов) . На то чтобы это закодировать и раскодировать уходит около 150 минут XD. Если я попытаюсь разбить его на потоки( System.Threading) ,скажем так на штук 16,будет ли от этого смысл ? Просто прочитал что хочешь не хочешь процессор все равно по сути последовательно делает операции.Спасибо 0

@Элд Хасп Модератор 16116 / 11237 / 2887 Регистрация: 21.04.2018 Сообщений: 33,038 Записей в блоге: 2
	24.04.2023, 18:26
	Lesch, тогда это будет для вас эффективно. Что помешало вам это реализовать? 1

@Lesch 3 / 2 / 1 Регистрация: 28.05.2020 Сообщений: 172
	24.04.2023, 19:26 [ТС]
	Да я сперва ошибки исправлял,доделывал алгоритм, увидел что скорость низкая, еще раз перелопатил переделал и особо ничего не изменилось и только после этого решил распределить по потокам. Спасибо вам,буду пробовать Добавлено через 2 минуты Удивительно что такая по сути простая работа со строками такая прожорливая. Скорее всего я намудрил со всем. 0

@Lesch 3 / 2 / 1 Регистрация: 28.05.2020 Сообщений: 172
	24.04.2023, 23:07 [ТС]
	Вот вы сейчас сказали про это и меня осенило. Получается я могу загрузить файл(фото,видео, не важно) и закодировать его ? Изначально просто "чинил" текст любой вводимый мной, а потом на уже разные другие масштабные идеи появились 0

@Lesch 3 / 2 / 1 Регистрация: 28.05.2020 Сообщений: 172
	24.04.2023, 23:14 [ТС]
	Я просто когда это делал,допустим фото, разбивал по пикселям и по цветам и дальше уже по 16(64 цвета (байта)) пикселей кодировал. Если можно обойтись без разбивки на это то это просто супер. Я не додумался xD 0

@EugenyS 29 / 19 / 10 Регистрация: 24.04.2023 Сообщений: 62
	25.04.2023, 00:23
	Действительно, если ваш алгоритм работает последовательно, то его выполнение на нескольких потоках не ускорит его работы. Если ваш код уже многопоточный, то разбиение на большее число потоков может увеличить количество конкуренции за ресурсы и замедлить общее время выполнения. Однако, в случае с большими данными, можно использовать подход MapReduce. Он позволяет параллельно обрабатывать большие объемы данных на кластере из нескольких вычислительных узлов. В этом случае данные разбиваются на меньшие блоки, которые обрабатываются параллельно на узлах кластера. После этого результаты собираются в единую последовательность. Если вы не работаете с кластером, вы можете использовать библиотеки для распараллеливания операций на нескольких ядрах вашего процессора, например, библиотеку OpenMP для C++. Она позволяет распараллеливать циклы, что может ускорить выполнение программы на многопроцессорных системах. Но прежде чем использовать любую из этих технологий, стоит проверить, можете ли вы оптимизировать ваш алгоритм, чтобы сократить время выполнения на одном потоке. 0

@Lesch 3 / 2 / 1 Регистрация: 28.05.2020 Сообщений: 172
	25.04.2023, 00:35 [ТС]
	Вы просто гляньте на эту красоту, первое фото размер байтового массива где я перелопачивал фото по пикселям а потом по цветам (6000000++) а второе где сразу взял массив байт из фото (240000) разница в 25 раз, и никаких больше строк, если это действительно сработает то это будет просто бомба Изображения 0

@Lesch 3 / 2 / 1 Регистрация: 28.05.2020 Сообщений: 172
	25.04.2023, 00:38 [ТС]
	Добавлено через 39 секунд EugenyS, Обязательно попробую ,спасибо! 0