Coleção de objetos que podem decidir dividir-se ao meio

5

Eu me deparei com um problema como este mais de uma vez e gostaria de saber a (s) abordagem (s) recomendada (s) para lidar com isso. Como alternativa, gostaria de saber se tem um nome.

Para a concretude, vamos supor que temos um objeto Colony, em que um dos membros é uma lista de objetos Organism. Objetos de organismos possuem um método Update. Sob certas condições, o comportamento desejado ao chamar Update é para o organismo "dividir-se ao meio" - isto é, produzir dois novos Organismos a serem inseridos na coleção, e então ter-se removido da coleção e destruído.

Para tornar as coisas interessantes, digamos que a coleção é ordenada e queremos que os novos Organismos sejam inseridos no mesmo ponto que o antigo Organismo anteriormente ocupado.

Além disso, digamos que queremos percorrer a coleção de Organismos chamando Update em cada um deles, e queremos fazer isso de tal forma que a Atualização não seja chamada em Organismos recém-criados.

Como variante, talvez o Organismo queira se manter vivo, mas inserir seus descendentes na coleção próxima a ele.

Posso pensar em algumas maneiras de fazer isso com várias compensações:

  1. Atualize para retornar uma lista de Organismos, seja ele mesmo ou uma lista de novos. Em seguida, faça o loop chamando Update para construir uma nova coleção a partir deles e substitua a coleção antiga por ela no final.
  2. Passa Atualiza alguns (callbacks / ponteiros / o que for) permitindo que ele insira itens na coleção de forma que o (iterador / índice de loop / o que quer que seja) seja movido para além deles.
  3. Faça com que o Update comunique seu desejo de inserir novos objetos no loop de chamada e que o código de chamada cuide da inserção real.

Existem outras maneiras razoáveis de fazer isso? Existem vantagens / desvantagens não óbvias para eles? Eles têm nomes? Existem maneiras fáceis de fazê-las automaticamente?

    
por Daniel McLaury 18.03.2017 / 00:42
fonte

3 respostas

1

Aviso de isenção

Esta solução não é orientada a objetos, mas talvez ainda seja interessante.

TL; DR

Indo com a sua primeira ideia (se a atualização retornar uma lista de Organismos), em Haskell você pode

  1. defina um tipo Organism ,
  2. define uma função de atualização update :: Organism -> [Organism] ,
  3. faça um loop sobre uma lista organism :: [Organism] com organisms >>= update .

Resposta detalhada

No Haskell você pode modelar a função update como uma função que produz uma lista de organismos:

data Organism = ...

update :: Organism -> [Organism]

Então a função update pode produzir dois novos organismos e esquecer o antigo, ou repetir o antigo organismo seguido por seus filhos:

-- Parent disappears
update x = [child1 x, child2 x]
  where
    child1 x = ...
    child2 x = ...

-- Parent followed by children
update x = [x, child1 x, child2 x]
  where
    child1 x = ...
    child2 x = ...

Agora, sua iteração se resume a mapear a função update sobre a lista inicial de organismos (que fornece uma lista de listas de organismos) e depois achatar o resultado usando concat , assim

organisms = [..., ..., ]
newOrganisms = concat (map update organisms)

A combinação concat - map pode ser expressa por outra função chamada bind e escrita >>= em Haskell (no Scala, ela é chamada flatMap ), então você também pode escrever:

organisms >>= update

Isso itera na lista, aplica update a cada elemento e nivela o resultado.

Nota

Se você precisar de alguma informação sobre como experimentar esta solução em um interpretador Haskell, posso fornecer mais detalhes.

    
por 18.03.2017 / 09:12
fonte
3

Como a principal operação aqui é inserir objetos no meio de uma lista onde você já tem um ponteiro para o organismo correto, um lista ligada seria uma das formas mais eficientes de implementar isso.

Suponha que você tenha uma estrutura de dados assim:

class Organism(object):
    def __init__(self):
        # you don't have to have reference to 
        # the Node in the Organism, but having it makes
        # things slightly easier if Organism can only
        # belong to a single LinkedList. If you don't have 
        # a reference to the Node, you'd want to have
        # a mapping/dictionary in the LinkedList object
        # to lookup the Node representing an Organism
        # in that Linked List
        self.node = None

class Node(object):
    def __init__(self, obj):
        self.left = None
        self.right = None
        self.obj = obj
        self.obj.node = self

Para inserir um objeto na lista vinculada que você faz:

class Node(object):
    ...
    def insert_left(self, obj):
        node = Node(obj)
        node.left = self.left
        node.right = self
        self.left.right = node
        self.left = node

Para remover um objeto da lista vinculada, faça o seguinte:

class Node(object):
    ...
    def remove(self):
        self.left.right = self.right
        self.right.left = self.left
        self.left = None
        self.right = None

Para dividir um organismo, você faz:

class Organism(object):
    ...
    def mitosis(self):
        c1 = Organism()
        c2 = Organism()
        node = self.node
        node.insert_left(c1)
        node.insert_left(c2)
        node.remove()

Para que o Organismo original sobreviva ao nascimento depois de seus filhos:

class Organism(object):
    ...
    def birth(self):
        c = Organism()
        self.node.insert_left(c)

Para iterar a lista encadeada, basta percorrer os nós corretos:

class LinkedList(object):
    def __iter__(self):
        node = self.list.head
        while node is not None:
            yield node.obj
            node = node.right

class Colony(object):
    def __init__(self):
        self.list = LinkedList()

    def update(self):
        for node in self.list:
            node.update()

Como você insert_left () quando o Organism split () ou birth (), qualquer Organisms recém-criado não será atualizado na iteração atual.

Se você quiser que um Organismo seja capaz de decidir se os novos filhos devem ou não ser iterados ou se você quer a flexibilidade de saber se os novos filhos são insert_left () ou insert_right () e se o Organismo recém-criado ainda precisa para ser ignorado, você pode usar Continuation Passing Style durante a iteração e retornar explicitamente o próximo Organismo para fazer uma iteração.

    
por 18.03.2017 / 05:08
fonte
1

A opção 3 será a mais fácil, mais flexível e mais eficiente. Na maioria das vezes, um objeto apenas atualiza seu estado interno e "passa" ao ser dividido.

Update does not get called on newly-created Organisms.

Isso não parece servir a um propósito. Você deseja que um objeto monitore o número de vezes que ele foi atualizado de qualquer maneira (idade) e seria melhor ter um novo objeto inicializando-se na primeira atualização, em vez de tê-lo inicializado pelo pai.

Você pode usar um loop for e inserir novos objetos à frente do valor do iterador. Desta forma, todos os novos objetos serão os primeiros a serem atingidos para atualização.

Uma maneira prática seria que um objeto de divisão retornasse um objeto filho. O conhecimento do processo de divisão e como atualizar a parte restante do objeto pode permanecer no próprio objeto. Se a atualização retornar null, não haverá nada a fazer (próximo). Se um filho é retornado, o código do loop pode decidir inseri-lo antes do pai ou em uma coleção diferente.

Supondo que o processo de atualização depende dos vizinhos, você precisaria que objetos tivessem referências a esses vizinhos no momento da atualização. Links no próprio objeto podem servir a esse propósito, mas você também pode ter referências a vizinhos injetados como argumentos do método Update. Isso pouparia muitas referências particulares.

Como alternativa, peça para os objetos rastrearem sua posição em um avião e alimentá-los com vizinhos próximos em cada atualização. Programe algum comportamento. Você pode visualizar isso em um bitmap. Deve ser divertido.

    
por 18.03.2017 / 10:35
fonte