No momento, estou trabalhando em um projeto de dispositivo incorporado em que estou com problemas de desempenho. A criação de perfil localizou uma operação O (N) que gostaria de eliminar.

Eu basicamente tenho duas matrizesint A[N] eshort B[N]. Entradas emA são únicos e ordenados por restrições externas. A operação mais comum é verificar se um determinado valora aparece emA[]. Menos freqüentemente, mas ainda comum é uma mudança em um elemento deA[]. O novo valor não está relacionado ao valor anterior.

Como a operação mais comum é o achado, é aí queB[] vem dentro É uma matriz ordenada de índices emA[], de tal modo queA[B[i]] < A[B[j]] se e apenas sei<j. Isso significa que eu posso encontrar valores emA usando uma pesquisa binária.

Claro, quando eu atualizoA[k], Eu tenho que encontrark emB e mova-o para uma nova posição, para manter a ordem de pesquisa. Desde que conheço os velhos e novos valores deA[k]é apenas ummemmove() de um subconjunto deB[] entre a velha e nova posição dek. Esta é a operação O (N) que preciso corrigir; desde os velhos e novos valores deA[k] são essencialmente aleatórios estou me movendo em média sobreN / 2 Elementos N / 3.

Eu olhei parastd::make_heap usando[](int i, int j) { return A[i] < A[j]; } como o predicado. Nesse caso, posso facilmente fazerB[0] apontar para o menor elemento deAe atualizandoB agora é uma operação de rebalanceamento O (log N) barata. No entanto, geralmente não preciso do menor valor de A, preciso descobrir se algum valor está presente. E agora é uma pesquisa O (N log N) emB. (Metade dos meus N elementos estão no log de profundidade de heap N, um quarto em (log N) -1, etc), o que não é nenhuma melhoria em relação a uma pesquisa O (N) burra diretamente emA.

Considerando questd::set tem O (log N) insert e find, eu diria que deve ser possível obter o mesmo desempenho aqui para update e find. Mas como eu faço isso? Preciso de outro pedido paraB? Um tipo diferente?

B é atualmente umshort [N] PorqueA eB juntos são aproximadamente do tamanho do meu cache de CPU, e minha memória principal é muito mais lenta. Ir de 6 * N para 8 * N bytes não seria legal, mas ainda assim aceitável se meu achado e atualização forem para O (log N) ambos.