Задача на многопоточность?

Question

[ReanGD]

Посоветуйте интересную для реализации задачу на многопоточность, которую можно опробировать на 1 компьютере. Не обязательно практическую, желательно не слишком объемную, что бы укладывалась в разумное время — недели 2-3.

Хочется поднять свой скилл в данной тематике.

Answer 1

[gricom]

Напишите свою реализацию пула потоков, которые постоянно выбирают из общей очереди задания (объект, реализующий какой-нибудь интерфейс с методом execute) и генератор таких задач. НаУчитесь писать блокирующие очереди и реализуете паттерн producer-consumer. Потом генератор сделайте многопоточным. Потом попробуйте очередь сделать распределенной (по нескольким машинам, например сделайте пару виртуалок), чтоб вы могли распределять нагрузку по узлам кластера из своих виртуалок.
А дальше уже природа вам подскажет, что еще туда прилепить))

Comments

[ReanGD]

Я неплохо представляю, что входит понятие многопоточности и имею кое-какие теоретические знания. Проблема в том, что я не могу придумать какие задачи запихать в пул потоков, кроме банального — сложить N чисел. Хочется чего-то интересного, того, что будет хотеться писать, а фантазию что-то отшибло напрочь (

[gricom]

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

[ReanGD]

Вот, уже интереснее, написать допустим сжатие файлов по Хаффману — получим как минимум блокировку при записи результатов в один «архив» и при получении следующего файла для архивирования, которые нужно будет разрулить. Спасибо

Answer 2

[vsespb]

Если есть желание заодно повозиться с HTTP — напишите многпоточное скачивание файлов по http (http «Range»).

Comments

[ReanGD]

Да, сети вообще и HTTP в частности, никогда не помешают, спасибо за вариант.

Answer 3

[Dzuba]

Первое, что приходит на ум из простого: многопоточное перемножение матриц. Размера этак 100x100 или даже 1000x1000. Задача легко параллелится и не требует спецзнаний.

Comments

[ReanGD]

А в чем тут фишка? Насколько я помню правила перемножения матриц, исходную матрицу можно разделить на N равных частей по числу процессоров и дать каждую часть потоку, каждый поток будет перемножать не пересекаясь с остальными. Т.е. там не нужен ни пул потоков как таковой, ни примитивы синхронизации.

[Dzuba]

Вы же просили простую задачу. Задача почти такая же, как выше — с графами: исходные данные readonly, запись результатов может вестись независимо.
Для использования синхронизации в задаче с матрицами перемножайте не 2 матрицы, а более.
Насчет разделения матрицы на части, следует уточнить, что такое часть. Если подразумевалась прямоугольная область, то нет — нельзя в общем случае. Умножается вся строка одной матрицы на весь столбец другой.

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

Еще можно попробовать написать любое клиент-серверное приложение, в котором совместная работа пользователей осуществляется над одним и тем же набором данных. Например: общий «блокнот» для нескольких пользователей с оперативным отображением внесенных изменений другими пользователями. Вполне реализуемо на 1 машине.

[ReanGD]

Я про простоту не упоминал, только про временные затраты на решение.
Да, вероятно вы правы, задача с графами будет не особо сложна с точки зрения многопоточности, сложности будут скорее в алгоритмическом плане (по крайней мере для меня). С матрицами все равно не нахожу каких-то проблем с синхронизацией данных, хоть две матрицы там умножаются, хоть 10.
Над остальными предложенными задачами — подумаю завтра на свежую голову, они кажутся довольно интересными, по крайней мере на первый взгляд. Спасибо.

[Dzuba]

Ну как же… Поскольку умножение матриц A[0], ..., A[N] — операция последовательная, а сама операция их умножения имеет лишь 2 операнда (то есть A[0] *… * A[N] = (((A[0] * A[1]) * A[2]) * ....), то после каждого умножения двух матриц из всего набора вы вынуждены будете синхронизировать потоки, ожидая заполнения всей промежуточной матрицы.
Насчет простоты, действительно, вы правы, этого нет в тексте вопроса. Меня смутили предыдущие примеры. Каюсь.

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

Answer 4

[OCTAGRAM]

Разгадыватель японских кроссвордов — большое поле для оптимизаций.

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