Pesquisa dinâmica paralela

24

Existe um análogo paralelo natural às árvores de vermelho-preto com propriedades semelhantes ou até mesmo terrivelmente piores para atualizações, sendo razoavelmente eficiente no trabalho?

De um modo mais geral, o que podemos fazer de melhor para pesquisas paralelas com atualizações?

ds.algorithms ds.data-structures dc.parallel-comp concurrency dynamic-algorithms Suresh Venkat
fonte
Quais propriedades em particular você deseja preservar ou tornar-se "não terrivelmente pior"? Quão importante é que a condição de equilíbrio ainda seja a das árvores vermelho-pretas? Os limites esperados, como nas listas de pulos simultâneos, seriam aceitáveis?
Jbapple #
Eu acho que os limites esperados seriam bons. Essa é uma situação em que estamos atingindo a estrutura de dados com frequência, com valores-chave atualizados, para que seja preciso, mesmo operações eficientes de mudança de chave de mudança, as pilhas de fibonacci são boas. Você tem uma boa referência para ignorar listas simultâneas?
Suresh Venkat
O livro de Herlihy & Shavit, The Art of Multiprocessor Programming, ou "Listas vinculadas sem bloqueio e listas de pulos " ou java.util.concurrent ou Practical lock-freedom . Você já pensou em usar uma tabela de hash simultânea como uma tabela de hash de amarelinha ?
Jbapple #
Na verdade não. Infelizmente, sou analfabeto em métodos concorrentes. Obrigado pelos árbitros.
Suresh Venkat

Respostas:

8

Pelo que sei, as estratégias envolvem condições relaxantes de equilíbrio e, em seguida, realizam atualizações de reequilíbrio em rajadas. Aqui está um artigo de Hanke et al., 1997 [PDF] , que acho que se concentra na técnica de agregação e resolução de operações de atualização, para que possam ser executadas simultaneamente.

James King
fonte
5

Acho que você pode encontrar uma resposta interessante no livro de Okasaki, Purely Functional Data Structures . Neste livro, muitas estruturas de dados são mostradas, de modo que todas as atualizações não são caras (geralmente levam apenas um tempo constante ou de logaritmo).

nn

Arthur MILCHIOR
fonte
4
Penso que, sem mais modificações, as árvores de pesquisa puramente funcionais serializam todas as atualizações e, portanto, apresentam um desempenho ruim sob a disputa por gravação.
Jbapple # 3/10