Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / WinForms, .Net Framework Новый топик    Ответить
 Можно ли распаралелить рекурсивную функцию?  [new]
iskatelsql
Member

Откуда:
Сообщений: 785
Вот такая функция, чесно стыренная с просторов интернета, решает задачу перестановок элементов массива

public static List<List<T>> ShowAllCombinations<T>(IList<T> arr, List<List<T>> list = null, List<T> current = null)
        {
            if (list == null) list = new List<List<T>>();
            if (current == null) current = new List<T>();
            if (arr.Count == 0) 
            {
                list.Add(current);
                return list;
            }
            for (int i = 0; i < arr.Count; i++) 
            {
                List<T> lst = new List<T>(arr);
                lst.RemoveAt(i);
                var newlst = new List<T>(current);
                newlst.Add(arr[i]);
                ShowAllCombinations(lst, list, newlst);
            }
            return list;
        }


только на 10 элементах работает секунд 10 на моем компе, при этом процессор загружает только процентов на 12. Говорят что распаралеливание помогает загрузить проц на 100%. Но как его сюда приткнуть?
24 ноя 18, 14:42    [21743667]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
iskatelsql,
Во первых, дай пример с тестом как тут принято.
А имхо в том, что при рекурсии нельзя приткнуть.
Только переписать полностью.
24 ноя 18, 16:12    [21743713]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3463
iskatelsql,

если у твоего процессора 8 ядер: то загрузив 1 ядро вы получите 100 / 8 = 12,5%
попробуйте создать метод более высокого уровня, разбейте массив на 8 частей и проитерируйте их всех в разных потоках рекурсивно
24 ноя 18, 16:27    [21743723]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
Dima T
Member

Откуда:
Сообщений: 14035
Перестановки так просто не параллелятся.

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

В остальном, если ты на 10 не хочешь ограничиться, то учти что общее количество комбинаций N!, т.е. даже распараллеленный обсчет при N = 14 будет в 24024 раз дольше чем при N = 10.
24 ноя 18, 17:40    [21743760]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
LR
Member

Откуда: 8P8C
Сообщений: 2404
iskatelsql,

Параллелить рекурсию с lst.Add/Remove - плохая идея - блокировки убьют всю параллель... Я бы "копал" в эту сторону: как заметил Dima T "общее количество комбинаций N!", т.е., мы можем создать "массив" объектов нужного типа нужного размера, и, в зависимости от индекса объекта в массиве, "вычислять конфигурацию" перестановки в методе этого объекта (как это делать, навскидку не придумал). Ну и уже тогда к этому массиву задействовать AsParallel. Х.з., возможно, это и невозможно (придумать алгоритм вычисления перестановки по индексу), но я бы попытался...
25 ноя 18, 23:53    [21744361]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6285
iskatelsql,

есть теорема, что любая рекурсивная функция имеет нерекурсивное исполнение

код конечно ужасен, руки надо отрубать за такое использование ресурсов
26 ноя 18, 11:01    [21744574]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
Siemargl,
Совершенно верно. Но автор ушел в несознанку и молчит.
26 ноя 18, 11:17    [21744606]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3463
на хабре уже всё есть:
https://habr.com/post/248493/
26 ноя 18, 11:56    [21744687]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4821
Вот реализация.
public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list)

        {

            if (list.Count() == 1)

                return new List<IEnumerable<T>> { list };

 

            return list

                .Select((a, i1) => {

                    var res = Permute(list.Where((b, i2) => i2 != i1)).Select(c =>

                    {

                        var res1 = (new T[] { a }).Union(c);

                        return res1;

                    });

                    return res;

                })

                .SelectMany(c => c);

        }
26 ноя 18, 15:18    [21745077]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3463
Отличный пример и памяти не жрёт совсем, так как это IEnumerable.
Лучше конкатинацию (Concat) использовать, а не объединение (Union)
26 ноя 18, 15:35    [21745097]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145663
Перестановки используют те, кто не может построить алгоритм без полного перебора! Например, я Картинка с другого сайта.
26 ноя 18, 18:55    [21745324]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
ViPRos
Member

Откуда:
Сообщений: 9579
Cat2,

какой алгоритм? весь NP класс - полный перебор.
26 ноя 18, 19:09    [21745333]     Ответить | Цитировать Сообщить модератору
 Re: Можно ли распаралелить рекурсивную функцию?  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145663
ViPRos
Cat2,

какой алгоритм? весь NP класс - полный перебор.


Если цель - сделать полный перебор, то да.
Но в реальных задачах полный перебор применяется тогда, когда надо найти что-то оптимальное или единственное. Как правило хороший алгоритмист, которым я, увы, не являюсь, может найти ограничения, которые позволяют заранее отсекать тупиковые варианты и не делать полного перебора.
26 ноя 18, 19:46    [21745374]     Ответить | Цитировать Сообщить модератору
Все форумы / WinForms, .Net Framework Ответить