примера общих ресурсоемких задач

Question

Для тестирования инструмента распараллеливания Я ищу примеры задач или алгоритмов, которые являются:

1. ресурсоемких
2. параллелизуемого
3. имеют относительно небольшого входа и выходом
4. обычно используются в повседневном программировании (т.е. не только учеными и разработчиками алгоритмов)

I мы нашли много примеров, но ни один из них не удовлетворяет цифре 4. Наиболее очевидной является простая факторизация. Проблема с продавцом - это еще одна проблема.

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

Answer 1

Есть два типа трудоемкие задачи:

1. Итерация большое количество данных ... что нарушает пункт 3 (если вы не создавать ваши данные на лету)

2. ли время потребляя вычисление на небольших данных ... нарушающую точку 4.

Что я могу предложить это создать большую зЬй :: вектор основного типа и выполнять простые операции на каждом е (вставить случайное значение/изменить по случайному значению) или отсортировать его

Это будет интенсивным процессом, его легко разделить на несколько потоков, вы можете генерировать свои данные «на лету» (небольшой вход, но по-прежнему огромный объем памяти), и он не является алгоритмическим.

Answer 2

Несколько фильтров обработки изображений занимают много времени и имеют высокую степень параллелизуемости.

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

Типичные размеры изображений - это несколько МБ. Хорошим и полезным приложением является разрешение обратной связи в реальном времени на регулируемые параметры, что требует времени работы под вторым.

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

Линейная алгебра предоставит ряд алгоритмов с поведением N³ для хранения N². Тей сильно используются в коде физического моделирования.