travessia eficiente de uma lista de alterações

Question

Eu tenho uma lista de mudanças para uma lista - adições e exclusões. A lista poderia ser enorme -. Dizer 10'000 itens

Quero saber o estado da lista após a mudança 9'000.

eu poderia andar a lista desde o início todo o caminho para mudar 9'000. Isso parece um pouco prolixo para mim.

Eu poderia manter uma lista de itens e registro quando eles estão adicionados e quando eles são excluídos, em seguida, caminhar esta lista para ver o que está na lista de uma mudança particular. Se adições e exclusões tinham a mesma probabilidade, gostaria de reduzir pela metade o número de elementos da lista que eu precisaria para percorrer ...

Mas Big O notação diz que reduzir para metade o tamanho do problema não tornar as coisas mais eficiente (se eu entendi corretamente).

Eu poderia armazenar em cache o estado da lista em cada mudança de 100 ou 1000 ... mas, novamente, ó grande diz que dividindo o número de itens por 'n' não faz as coisas mais eficientes.

Então, o que é a maneira eficiente de fazer isso? Existe uma maneira eficiente de fazer isso?

Mais detalhes: Especificamente, eu estou rastreando as alocações de memória / deallocations em um allocater personalizado. Cada alocação / desalocação é um evento na lista. Cada alocação tem uma identificação única. Eu gostaria de saber o que está actualmente afectados depois (por exemplo) 9'000 eventos.

A minha primeira ideia era loja, para cada id, o evento foi alocado e o evento foi desalocada. Então a andar esta lista até a primeira atribuição cujo evento alloc é maior do que 9000. Mas como eu disse, isso só iria reduzir pela metade o número de itens que eu precisaria para percorrer.

Eu gosto do ponto feito por Mike F - caminhada a partir do item 100 mais próxima é tempo constante ...

Answer 1

Se você armazenar em cache o estado da lista cada mudança Xth, então você pode fazer uma costeleta de binário para chegar até dois estados em cache que limitam a mudança que você está procurando, então você anda na maioria dos itens X para chegar ao item em si. Que de O (log N), mais ou menos.

Mas, mais geralmente, reduzindo grande complexidade O é o meio, não o fim. Se a sua lista é geralmente de 10.000 itens, então você deve se preocupar em fazer isso rápido para N = 10.000, quer reduzindo a complexidade, ou apenas fazendo-lo mais rápido.

Editar: Opa, eu só li sua pergunta com mais cuidado. Se você armazenar em cache o estado a cada (por exemplo) 100 itens, você não está procurando assim que você não precisa mesmo de fazer uma costeleta binária - você acabou de saltar diretamente para o estado em cache mais próximo e andar no máximo 100 itens para chegar ao item em si. Então isso é um algoritmo de tempo constante, não?

Answer 2

Que tipo de estrutura que você está trabalhando? Não é uma maneira eficiente para andar uma estrutura de dados genérica, mas existem milhares de métodos de otimização e métodos eficientes de estruturas específicas.

E sim, se você tem um algoritmo que é O (n) a complexidade do tempo, reduzir para metade o número de itens não vai mudá-lo de O (n) a complexidade ... mas isso significa que cada novo item tem apenas metade o efeito que teve originalmente. Big O notação é uma boa maneira de classificar algoritmos, mas ele realmente não entrar em eficiência para além de em grandes números (um bom exemplo é a classificação. Quicksort é pior do que a complexidade mergesort no pior dos casos ... mas você pode implementar quicksort mais eficiente do que mergesort para praticamente qualquer aplicação que não seja aqueles que lidam com a triagem milhões de itens)

Answer 3

'Timestamp' ou marcar cada inserção e exclusão, em seguida, que seria necessário um percurso simples de encontrar alterações (O (n)).