Beachhouse13 Ответов: 1

Нужна помощь с оптимизацией потоков

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

Код основан на подходе ветвей и границ для поиска оптимального решения проблемы. Каждый ответ получает оценку, которая является свойством Result. Чем меньше балл, тем лучше. Ответы с наибольшим количеством баллов выбираются для повторения при выработке новых ответов, каждый со своей собственной оценкой, которые возвращаются в список. После выполнения определенных критериев ответ считается окончательным и больше не обрабатывается. После того, как ответ является окончательным, он сравнивается с текущим лучшим ответом (если есть) и становится лучшим ответом, если у него лучший результат. Способ работы алгоритма оценки делает невозможным получение ответа с более низкой оценкой, поэтому, как только будет найден лучший ответ, любые ответы в списке с более высокой оценкой не могут дать лучший ответ и могут быть удалены из списка.

Dim MainList as new List(of B)
Populate(MainList ) ' Populates MainList 
Dim Best as B = Nothing

Do
  Dim Current as B = MainList(0)
  MainList.RemoveAt(0)
  Dim SubList as list(of B)=PerformWork(Current) ' Function that preforms the work
  if Sublist.Count > 0 then
    If Sublist(0).IsFinal then ' Note that only 1 item will be returned if IsFinal is true
      If Best Is Nothing OrElse Best.Result > SubList(0).Result then
        Best=Sublist(0)
        Remove(Best.Result) ' Removes all items in MainList that have a Result > Best.Result
      End if
    Else
      Insert(SubList) ' Sub that inserts all the items in SubList into MainList
    End if
  end if
Loop While MainList.Count > 0


Моя цель состоит в том, чтобы распараллелить этот процесс, взяв первое n число объектов и запустив поток для каждого, который вернет список объектов. Когда каждый поток возвращается, возвращенный список объектов будет вставлен в список, а текущий первый объект будет передан новому потоку.

Каждый пример, который я видел, будет просто перебирать весь список и создавать новый поток для каждого объекта. Поскольку я хочу сосредоточиться только на лучших объектах, и это будет меняться по мере выполнения программы, я не думаю, что это лучший подход. Я мог бы просто перебрать первые 4 пункта и продолжать в том же духе, но я планирую использовать несколько компьютеров, и каждый из них должен будет иметь программное обеспечение, настроенное специально для него. Есть ли какой-нибудь способ заставить фреймворк определить наилучшее количество потоков?

Что я уже пробовал:

Пока ничего мудрого в коде нет, просто просмотрел много статей, которые не очень помогают.

1 Ответов

Рейтинг:
2

Richard Deeming

Я не думаю, что сортировка имеет какой-либо смысл. Если вы обрабатываете список параллельно, элементы могут быть обработаны в любом порядке.

То List(Of T) класс-не лучший выбор. Это не потокобезопасно, и удаление элементов из начала списка-дорогостоящая операция. Я бы предложил использовать ConcurrentQueue(Of T)[^] вместо этого класс.

Вам понадобится метод расширения, чтобы получить" потребляющий " перечислитель, который удаляет элементы из очереди по мере их обработки:

Module CollectionExtensions
    <Extension()> 
    Public Iterator Function GetConsumingEnumerator(Of T)(ByVal source As IProducerConsumerCollection(Of T)) As IEnumerable(Of T)
        Dim item As T
        While source.TryTake(item)
            Yield item
        End While
    End Function
End Module

Затем вы можете использовать Методами asparallel[^] метод расширения для параллельного использования списка:
Dim best As B = Nothing
Dim initialList As New List(Of B)
Populate(initialList)

Dim mainList As New ConcurrentQueue(Of B)(initialList)
While Not mainList.IsEmpty
    Dim newItems As IEnumerable(Of List(Of B)) = mainList _
        .GetConsumingEnumerator() _
        .AsParallel() _
        .Where(Function (current) best Is Nothing OrElse current.Result <= best.Result) _
        .Select(Function (current) PerformWork(current)) _
        .Where(Function (newList) newList.Count > 0)
        
    For Each newList As List(Of B) In newItems
        If newList(0).IsFinal Then
            If best Is Nothing OrElse best.Result > newList(0).Result Then
                best = newList(0)
            End If
        Else
            For Each item As B In newList
                mainList.Enqueue(item)
            Next
        End If
    Next
End While

NB: У вас есть ошибка в вашем текущем коде: 
If Best IsNot Nothing OrElse Best.Result > SubList(0).Result then
Если Best является Nothing, вы получите NullReferenceException на этой строке.

Beachhouse13

Ричард, Спасибо за ответ, но это не сработает для меня. Я должен извиниться, так как мой первоначальный пост не был настолько ясен в моих намерениях. Я добавил больше описания, чтобы помочь с этим. По сути, я не хочу работать над каждым пунктом в списке, поэтому сортировка важна. При этом я не могу использовать ConcrurrentQueue не будет работать, так как я не могу вставлять в него элементы. Я понимаю, что класс List работает медленно, и это следующий в моем списке, чтобы сделать его более эффективным, но пока это лучшее, что я могу сделать. Я планирую иметь возможность использовать этот список, так как я получаю доступ к нему только в основном потоке, а не в любом из рабочих потоков.

Кроме того, Спасибо, что указали на ошибку в коде. Это было исправлено.

Richard Deeming

Если вы не знаете, над какими элементами вы хотите работать, пока не оценили элемент #0, то вы не можете работать над ними параллельно.

Beachhouse13

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