A fila de prioridade que permite atualização prioridade eficiente?

Question

Atualizar : Aqui está minha implementação do sincronismo Hashed Rodas . Por favor, deixe-me saber se você tem uma idéia para melhorar o desempenho e simultaneidade. (20-Jan-2009)

// Sample usage:
public static void main(String[] args) throws Exception {
    Timer timer = new HashedWheelTimer();
    for (int i = 0; i < 100000; i ++) {
        timer.newTimeout(new TimerTask() {
            public void run(Timeout timeout) throws Exception {
                // Extend another second.
                timeout.extend();
            }
        }, 1000, TimeUnit.MILLISECONDS);
    }
}

Atualizar : noreferrer Eu resolvi esse problema usando hierárquica e Cronometragem Hashed Rodas . (19-Jan-2009)

Eu estou tentando implementar um temporizador de propósito específico em Java que é otimizada para a manipulação de tempo limite. Por exemplo, um usuário pode registrar uma tarefa com uma linha de mortos eo temporizador poderia notificar método de retorno de um usuário quando a linha de mortos é longo. Na maioria dos casos, uma tarefa registrada será feito dentro de um período muito curto de tempo, por isso a maioria das tarefas será cancelado (por exemplo task.cancel ()) ou remarcado para o futuro (por exemplo task.rescheduleToLater (1, TimeUnit.SECOND)) .

Eu quero usar este temporizador para detectar uma conexão de soquete ocioso (por exemplo, fechar a conexão quando nenhuma mensagem é recebida em 10 segundos) eo tempo limite de gravação (por exemplo, gerar uma exceção quando a operação de gravação não está terminado em 30 segundos). Em maioria dos casos, o tempo de espera não irá ocorrer, o cliente irá enviar uma mensagem ea resposta será enviada a menos que haja um problema de rede estranho ..

Eu não posso usar java.util.Timer ou java.util.concurrent.ScheduledThreadPoolExecutor porque eles assumem a maioria das tarefas é suposto ser excedido. Se uma tarefa for cancelada, a tarefa cancelada é armazenado em seu acervo interno até ScheduledThreadPoolExecutor.purge () é chamado, e é uma operação muito cara. (O (n log n) talvez?)

Em montes tradicionais ou filas de prioridade que aprendi em minhas aulas de CS, atualizando a prioridade de um elemento era uma operação cara (O (log N), em muitos casos, porque ele só pode ser alcançado através da remoção do elemento e re-inserção -lo com um novo valor de prioridade. Alguns montes como Fibonacci pilha tem o (1) tempo de decreaseKey () e min () operação, mas o que eu preciso, pelo menos, é increaseKey rápido () e min () (ou decreaseKey () e max ()).

Você conhece alguma estrutura de dados que é altamente otimizado para este caso de uso particular? Uma estratégia que eu estou pensando é apenas armazenar todas as tarefas em uma tabela hash e repetindo todas as tarefas a cada segundo ou assim, mas não é tão bonito.

Answer 1

Que tal tentar separar a entrega do caso normal onde as coisas concluir rapidamente a partir dos casos de erro?

Use tanto uma tabela hash e uma fila de prioridade. Quando uma tarefa é iniciado ele é colocado na tabela hash e se termina rapidamente ele é removido em O (1) tempo.

Cada um segundo você digitalizar a tabela hash e quaisquer tarefas que têm sido um longo período de tempo, digamos, 75 segundos, se mudou para a fila de prioridade. A fila de prioridade deve ser sempre pequeno e fácil de manusear. Isso pressupõe que um segundo é muito menos do que os tempos de tempo limite que está à procura.

Se a digitalização tabela hash é muito lento, você poderia usar duas tabelas de hash, essencialmente, uma para segundos pares e um para segundos ímpares. Quando uma tarefa é iniciada é colocado na tabela hash atual. Cada segundo mover todas as tarefas da tabela de hash não-corrente na fila de prioridade e trocar as tabelas de hash para que a tabela de hash atual está agora vazia ea tabela não circulante contém as tarefas iniciados entre um e dois segundos atrás.

Há opções são muito mais complicado do que apenas usando uma fila de prioridade, mas são muito facilmente implementada deve ser estável.

Answer 2

Para o melhor de meu conhecimento (eu escrevi um artigo sobre uma nova fila de prioridade, que também analisou os resultados do passado), nenhuma implementação fila de prioridade recebe os limites de aterros de Fibonacci, bem como de tempo constante aumento-chave.

Há um pequeno problema com a obtenção de que, literalmente. Se você pode obter aumento-chave em O (1), então você pode obter de exclusão em O (1) - apenas aumentar a chave para + infinito (você pode lidar com a fila de estar cheio de lotes de + infinitys usando alguns truques de amortização padrão ). Mas se encontrar-min é também O (1), que os meios de eliminação-min = encontrar-min + exclusão torna-se O (1). Isso é impossível em uma fila de prioridade baseado em comparações, porque a ordenação ligada implica (insert tudo, em seguida, remover um por um) que

n * + n * inserção de exclusão-min> n log n.

O ponto aqui é que se você quiser uma prioridade-fila para suporte aumento-chave em O (1), então você deve aceitar uma das seguintes penalidades:

• Não ser comparação baseada. Na verdade, esta é uma boa maneira bonita de obter em torno de coisas, por exemplo, VEB árvores .
• Aceite O (N log N) para pastilhas e também O (N log N) para faz-pilha (dado n valores iniciais). Isso é péssimo.
• Aceite O (log n) para encontrar-min. Isto é inteiramente aceitável se você nunca realmente do encontrar-min (sem um acompanhante de exclusão).

Mas, novamente, para o melhor de meu conhecimento, ninguém fez a última opção. Eu sempre vi isso como uma oportunidade para novos resultados em uma área bastante básico de estruturas de dados.

Answer 3

Use sincronismo Hashed Roda - Google 'hash hierárquica cronometrando Wheels' para mais informações. É uma generalização das respostas feitas por pessoas aqui. Eu preferiria uma roda sincronismo hash com um tamanho grande roda para rodas de tempo hierárquicos.

Answer 4

Uma combinação de hashes e estruturas O (log n) deve fazer o que você pede.

Estou tentado a tergiversar com a maneira que você está analisando o problema. Em seu comentário acima, você diz

Como a atualização irá ocorrer muito, muito frequentemente. Digamos que está enviando mensagens M por conexão, em seguida, o tempo total se torna O (MNlogN), que é muito grande. - trustin Lee (6 horas atrás)

que é absolutamente correto, tanto quanto ele vai. Mas a maioria das pessoas que eu conheço iria concentrar-se no custo por mensagem , na teoria de que como você tem aplicativo mais e mais trabalho a fazer, obviamente que vai exigir mais recursos.

Então, se a sua aplicação tem um bilhão de soquetes abertos simultaneamente (que é realmente provável?) O custo de inserção é de apenas cerca de 60 comparações por mensagem.

Eu aposto que o dinheiro que este é otimização prematura:. Você não tem realmente medidos os gargalos em seu sistema com uma ferramenta de análise de desempenho como CodeAnalyst ou VTune

De qualquer forma, há provavelmente um número infinito de maneiras de fazer o que você pedir, uma vez que você acabou de decidir que nenhuma estrutura única vai fazer o que quiser, e você quer alguma combinação dos pontos fortes e fracos dos diferentes algoritmos.

Uma possibilidade é a de dividir o domínio N tomada em algum número de baldes de tamanho B, e, em seguida, cada uma das tomadas de hash para um dos (N / B) baldes. Em que balde é uma pilha (ou qualquer outro) com O (log B) tempo de actualização. Se um limite superior na N não é fixo com antecedência, mas pode variar, então você pode criar mais baldes de forma dinâmica, o que acrescenta um pouco de complicação, mas é certamente factível.

No pior dos casos, o watchdog timer tem que procurar filas para expirações (N / B), mas presumo o watchdog timer não é obrigado a matar soquetes ociosos em qualquer ordem particular! Ou seja, se 10 soquetes foi ocioso na última fatia de tempo, ele não tem que procurar esse domínio para o que time-out em primeiro lugar, lidar com isso, então encontrar o que excedido segunda, etc. Ele só tem a digitalizar o (N / B) um conjunto de baldes e enumerar todos os tempos de espera.

Se você não está satisfeito com uma matriz linear de baldes, você pode usar uma fila de prioridade de filas, mas você quer evitar atualizar essa fila em cada mensagem, ou então você está de volta onde você começou. Em vez disso, definir algum tempo que é menos do que o limite de tempo real. (Say, 3/4 ou 7/8 de que) e você só colocar a fila de baixo nível para a fila de alto nível se é muito tempo excede a.

E, correndo o risco de afirmar o óbvio, você não quer que suas filas introduzidos no decorrido tempo. As chaves devem ser start tempo. Para cada registro nas filas, tempo decorrido teria que ser atualizado constantemente, mas a hora de início de cada registro não muda.

Answer 5

Há uma maneira muito simples de fazer todas as inserções e remove em O (1), aproveitando-se do fato de que 1) a prioridade é baseada no tempo e 2) você provavelmente tem um número pequeno, fixo de durações de tempo limite.

1. Crie uma fila FIFO regular para realizar todas as tarefas que tempo limite em 10 segundos. Porque todas as tarefas têm durações de tempo limite idênticos, você pode simplesmente inserir até o fim e remover desde o início para manter a fila ordenada.
2. Criar outra fila FIFO para tarefas com 30 segundos de tempo de espera. Criar mais filas para outras durações de tempo limite.
3. Para cancelar, remover o item da fila. Este é O (1) se a fila é implementado como uma lista ligada.
4. A reprogramação pode ser feito como cancelar-inserção, como ambas as operações são O (1). Note-se que as tarefas podem ser reprogramadas para diferentes filas.
5. Finalmente, para combinar todas as filas FIFO em uma única fila prioritário geral, têm a cabeça de cada FIFO fila de participar em uma pilha regular. A cabeça deste montão será a tarefa com o mais rápido tempo limite expirar fora de todas as tarefas.

Se você tem m número de diferentes durações de tempo de espera, a complexidade de cada operação da estrutura global é O (log m). A inserção é O (log M), devido à necessidade de olhar para cima, que a fila para inserir a. Remove-min é O (log M) para restaurar a pilha. O cancelamento é O (1), mas pior caso O (log m) se você está cancelando a cabeça de uma fila. Uma vez que m é um número pequeno, fixo, O (log M) é, essencialmente, O (1). Ele não escala com o número de tarefas.

Answer 6

O seu cenário específico sugere um buffer circular para mim. Se o máx. tempo limite é 30 segundos e queremos colher soquetes pelo menos a cada décimo de segundo, em seguida, usar um buffer de 300 listas duplamente ligadas, uma para cada décimo de segundo nesse período. Para 'IncreaseTime' em uma entrada, removê-lo da lista que está dentro e adicioná-lo ao um para o seu novo período de décimo-segundo (ambas as operações em tempo constante). Quando um período extremidades, colher qualquer coisa que sobraram na lista atual (talvez, alimentando-o com um fio ceifador) e avançar o ponteiro-lista atual.

Answer 7

Você tem um hard-limite para o número de itens na fila -. Há um limite para sockets TCP

Portanto, o problema é limitado. Eu suspeito que qualquer estrutura de dados inteligente será mais lento do que usar tipos built-in.

Answer 8

Existe uma boa razão para não usar java.lang.PriorityQueue? não remove () lidar com suas cancelar operações no log (N) tempo? Em seguida, implementar sua própria espera com base no tempo até que o item na frente da fila.

Answer 9

Eu acho que o armazenamento de todas as tarefas em uma lista e iteração através deles seria melhor.

Você deve ser (vai) executar o servidor em alguma máquina muito robusto para chegar aos limites onde este custo será importante?