Параллелизируйте код во вложенных циклах

Entity-components-system запрашивает конкретную конструкцию.

ECS следует принципу композиции по наследованию

blockquote>

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

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

Давайте реализуем пример.

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

blockquote>
  1. Entity.cs

Объект обычно состоит из идентификатора и списка компонентов, которые к нему прикреплены.

blockquote>
class Entity
{
    public Entity(Guid entityId)
    {
        EntityId = entityId;
        Components = new List();
    }

    public Guid EntityId { get; }
    public List Components { get; }
}
  1. Component.cs

Начиная с интерфейса маркера.

interface IComponent { }

enum Appearance : byte
{
    Human,
    Monster,
    SparksFlyingAround,
    FlyingArrow
}

class VisibleComponent : IComponent
{
    public Appearance Appearance { get; set; }
}

class PhysicalComponent : IComponent
{
    public double X { get; set; }
    public double Y { get; set; }
}
  1. System.cs

Добавление коллекции для SystemEntities.

interface ISystem
{
    ISet SystemEntities { get; }
    Type[] ComponentTypes { get; }

    void Run();
}

class DrawingSystem : ISystem
{
    public DrawingSystem(params Type[] componentTypes)
    {
        ComponentTypes = componentTypes;
        SystemEntities = new HashSet();
    }

    public ISet SystemEntities { get; }

    public Type[] ComponentTypes { get; }

    public void Run()
    {
        foreach (var entity in SystemEntities)
        {
            Draw(entity);
        }
    }

    private void Draw(Guid entity) { /*Do Magic*/ }
}
  1. ComponentPool.cs

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

interface IComponentPool
{
    void RemoveEntity(Guid entityId);
    bool ContainsEntity(Guid entityId);
}

interface IComponentPool : IComponentPool
{
    void AddEntity(Guid entityId, T component);
}

class ComponentPool : IComponentPool
{
    private Dictionary component = new Dictionary();

    public void AddEntity(Guid entityId, T component)
    {
        this.component.Add(entityId, component);
    }

    public void RemoveEntity(Guid entityId)
    {
        component.Remove(entityId);
    }

    public bool ContainsEntity(Guid entityId)
    {
        return component.ContainsKey(entityId);
    }
}

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

class PoolDecorator : IComponentPool
{
    private readonly IComponentPool wrappedPool;
    private readonly EntityManager entityManager;
    private readonly ISystem system;

    public PoolDecorator(IComponentPool componentPool, EntityManager entityManager, ISystem system)
    {
        this.wrappedPool = componentPool;
        this.entityManager = entityManager;
        this.system = system;
    }

    public void AddEntity(Guid entityId, T component)
    {
        wrappedPool.AddEntity(entityId, component);

        if (system.ComponentTypes
            .Select(t => entityManager.GetComponentPool(t))
            .All(p => p.ContainsEntity(entityId)))
        {
            system.SystemEntities.Add(entityId);
        }
    }

    public void RemoveEntity(Guid entityId)
    {
        wrappedPool.RemoveEntity(entityId);
        system.SystemEntities.Remove(entityId);
    }

    public bool ContainsEntity(Guid entityId)
    {
        return wrappedPool.ContainsEntity(entityId);
    }
}

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

  1. EntityManager.cs

Оркестратор (он же посредник, контроллер, ...)

class EntityManager
{
    List systems;
    Dictionary componentPools;

    public EntityManager()
    {
        systems = new List();
        componentPools = new Dictionary();
        ActiveEntities = new HashSet();
    }

    public ISet ActiveEntities { get; }

    public Guid CreateEntity()
    {
        Guid entityId;
        do entityId = Guid.NewGuid();
        while (!ActiveEntities.Add(entityId));

        return entityId;
    }

    public void DestroyEntity(Guid entityId)
    {
        componentPools.Values.Select(kp => (IComponentPool)kp).ToList().ForEach(c => c.RemoveEntity(entityId));
        systems.ForEach(c => c.SystemEntities.Remove(entityId));
        ActiveEntities.Remove(entityId);
    }

    public void AddSystems(params ISystem[] system)
    {
        systems.AddRange(systems);
    }

    public IComponentPool GetComponentPool(Type componentType)
    {
        return (IComponentPool)componentPools[componentType];
    }

    public IComponentPool GetComponentPool() where TComponent : IComponent
    {
        return (IComponentPool)componentPools[typeof(TComponent)];
    }

    public void AddComponentPool(IComponentPool componentPool) where TComponent : IComponent
    {
        componentPools.Add(typeof(TComponent), componentPool);
    }

    public void AddComponentToEntity(Guid entityId, TComponent component) where TComponent : IComponent
    {
        var pool = GetComponentPool();
        pool.AddEntity(entityId, component);
    }

    public void RemoveComponentFromEntity(Guid entityId) where TComponent : IComponent
    {
        var pool = GetComponentPool();
        pool.RemoveEntity(entityId);
    }
}
  1. Program.cs
  2. [1128 ]

    Где все это объединяется.

    class Program
    {
        static void Main(string[] args)
        {
            #region Composition Root
    
            var entityManager = new EntityManager();
    
            var drawingComponentTypes = 
                new Type[] {
                    typeof(VisibleComponent),
                    typeof(PhysicalComponent) };
    
            var drawingSystem = new DrawingSystem(drawingComponentTypes);
    
            var visibleComponent =
                new PoolDecorator(
                    new ComponentPool(), entityManager, drawingSystem);
    
            var physicalComponent =
                new PoolDecorator(
                    new ComponentPool(), entityManager, drawingSystem);
    
            entityManager.AddSystems(drawingSystem);
            entityManager.AddComponentPool(visibleComponent);
            entityManager.AddComponentPool(physicalComponent);
    
            #endregion
    
            var entity = new Entity(entityManager.CreateEntity());
    
            entityManager.AddComponentToEntity(
                entity.EntityId,
                new PhysicalComponent() { X = 0, Y = 0 });
    
            Console.WriteLine($"Added physical component, number of drawn entities: {drawingSystem.SystemEntities.Count}.");
    
            entityManager.AddComponentToEntity(
                entity.EntityId,
                new VisibleComponent() { Appearance = Appearance.Monster });
    
            Console.WriteLine($"Added visible component, number of drawn entities: {drawingSystem.SystemEntities.Count}.");
    
            entityManager.RemoveComponentFromEntity(entity.EntityId);
    
            Console.WriteLine($"Removed visible component, number of drawn entities: {drawingSystem.SystemEntities.Count}.");
    
            Console.ReadLine();
        }
    }
    

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

    blockquote>

    Как упоминалось в ссылочной вики, это на самом деле не рекомендуется.

    Обычной практикой является использование уникального идентификатора для каждого объекта. Это не является обязательным требованием, но оно имеет несколько преимуществ:

    • На объект можно ссылаться, используя идентификатор вместо указателя. Это более надежно, поскольку позволяет уничтожить объект, не оставляя висящих указателей.
    • Это помогает для внешнего сохранения состояния. Когда состояние загружается снова, нет необходимости восстанавливать указатели.
    • Данные могут быть перемешаны в памяти по мере необходимости.
    • Идентификаторы объекта могут использоваться при связи по сети, чтобы однозначно идентифицировать объект.
    blockquote>

5
задан Juliet 5 January 2009 в 04:00
поделиться

4 ответа

Как уже говорилось существует конкуренция обновления, при попытке иметь различные входные строки процесса различных потоков, так как каждый поток может увеличить количество каждой буквы. У Вас может быть каждый поток, производят его собственную Карту, и затем 'сложите все Карты', но что заключительный шаг может быть дорогим (и не является столь же подходящим к использованию потоков из-за совместно используемых данных). Я думаю, что большие исходные данные, вероятно, выполнят более быстрое использование алгоритма как тот ниже, где каждый поток обрабатывает различную букву к количеству (для всех строк во входе). В результате каждый поток имеет свой собственный независимый счетчик, таким образом, никакая конкуренция обновления и никакой заключительный шаг для объединения результатов. Однако нам нужна предварительная обработка для обнаружения 'набора уникальных букв', и этот шаг действительно имеет ту же состязательную проблему. (На практике Вы, вероятно, знаете вселенную символов впереди, например, alphabetics, и затем может просто создавать 26 потоков, чтобы обработать a-z и обойти эту проблему.) В любом случае, по-видимому, вопрос главным образом об исследовании, 'как написать асинхронный код F# для деления работы через потоки, таким образом, код ниже демонстрирует это.

#light

let input = [| "aaaaa"; "bbb"; "ccccccc"; "abbbc" |]

// first discover all unique letters used
let Letters str = 
    str |> Seq.fold (fun set c -> Set.add c set) Set.empty 
let allLetters = 
    input |> Array.map (fun str -> 
        async { return Letters str })
    |> Async.Parallel 
    |> Async.Run     
    |> Set.union_all // note, this step is single-threaded, 
        // if input has many strings, can improve this

// Now count each letter on a separate thread
let CountLetter letter =
    let mutable count = 0
    for str in input do
        for c in str do
            if letter = c then
                count <- count + 1
    letter, count
let result = 
    allLetters |> Seq.map (fun c ->
        async { return CountLetter c })
    |> Async.Parallel 
    |> Async.Run

// print results
for letter,count in result do
    printfn "%c : %d" letter count

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

2
ответ дан 14 December 2019 в 13:50
поделиться

Параллель не является тем же, столь асинхронным, как Don Syme объясняет.

Так IMO Вы были бы более обеспеченным использованием PLINQ для параллелизации.

1
ответ дан 14 December 2019 в 13:50
поделиться

Я не говорю F# вообще хорошо, но я могу обратиться к этому. Думайте об использовании, отобразите/уменьшите:

позвольте n = карта (Σ) быть количеством символов σ в алфавите Σ.

Этап карты:

Породите процессы n, где присвоение процесса i-th состоит в том, чтобы соответствовать количеству случаев символа σi в целом входном векторе.

Уменьшите этап:

Соберите общее количество для каждого из процессов n в порядке. Тот вектор является Вашими результатами.

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

0
ответ дан 14 December 2019 в 13:50
поделиться

Вы можете написать это так:

let wordFrequency =
  Seq.concat >> Seq.filter System.Char.IsLetter >> Seq.countBy id >> Map.ofSeq

и распараллелить его только двумя дополнительными символами, чтобы использовать модуль PSeq из FSharp.PowerPack.Parallel.Seq DLL вместо обычного модуля Seq :

let wordFrequency =
  Seq.concat >> PSeq.filter System.Char.IsLetter >> PSeq.countBy id >> Map.ofSeq

Например, время, затрачиваемое на вычисление частот из Библии Короля Иакова на 5,5 Мб, уменьшается с 4,75 с до 0,66 с. Это 7,2-кратное ускорение на этой 8-ядерной машине.

3
ответ дан 14 December 2019 в 13:50
поделиться
Другие вопросы по тегам:

Похожие вопросы: