Como melhor tipo uma parte de um buffer circular?

StackOverflow https://stackoverflow.com/questions/281488

Pergunta

Eu tenho um buffer circular, estaticamente alocada em C, o que eu estou usando como uma fila para um profundidade busca em largura. Eu gostaria ter o topo N elementos na fila ordenada. Seria fácil simplesmente usar um qsort regulares () - exceto que é um buffer circular, e os elementos de topo N pode envolver em torno. Eu poderia, é claro, escrever a minha própria implementação de classificação que usa aritmética modular e sabe como envolver o array, mas eu sempre pensei que escrever funções de ordenação é um bom exercício, mas algo melhor para a esquerda para bibliotecas.

Eu pensei em várias abordagens:

  1. Use um buffer linear separada - primeiro copiar os elementos do buffer circular, em seguida, aplicar qsort, em seguida, copiá-los de volta. Utilizando um meio de amortecimento adicionais mais um O (N) requisito de espaço, o que traz me
    • Classificar o "top" e "bottom" Halve usando qsort, e depois juntá-las usando o buffer adicional
    • O mesmo que 2. mas fazer a fusão final no local (não achei muito em fusão no local, mas as implementações que eu vi não parecem vale reduzida complexidade espaço)

Por outro lado, passar uma hora contemplando como evitar elegantemente escrever meu próprio quicksort, em vez de adicionar esses 25 (ou mais) linhas pode não ser a mais produtiva ou ...

Correção: Cometi um erro estúpido de comutação DFS e BFS (eu prefiro escrever um DFS, mas neste caso particular, eu tenho que usar um BFS), desculpe pela confusão

.

Descrição mais detalhada do problema original:

Estou implementando uma amplitude primeira pesquisa (algo não muito diferente do quinze enigma, apenas mais complicado, com cerca de O (n ^ 2) possíveis expansões em cada estado, em vez de quatro). O algoritmo "bruteforce" é feito, mas é "estúpido" - em cada ponto, ele se expande todos os estados válidos, em uma ordem hard-coded. A fila é implementada como uma memória tampão circular (fila não assinado [MAXLENGTH]), e armazena-o inteiro índices numa tabela de estados. Além de duas funções simples para fila e Dequeue um índice, não tem encapsulamento -. É apenas uma simples, array estaticamente alocado de não assinados

Agora eu quero adicionar algumas heurísticas. A primeira coisa que eu quero é tentar classificar os estados criança expandidas após a expansão ( "expandi-los em uma ordem melhor") - apenas como eu faria se eu estivesse programando um simples best-primeiros DFS. Para isso, eu quero tomar parte da fila (que representa o mais recentes estados ampliados), e classificá-los usando algum tipo de heurística. Eu também poderia expandir os estados em uma ordem diferente (portanto, neste caso, não é realmente importante se eu quebrar as FIFO propriedades da fila).

O meu objectivo não é implementar A * , ou uma busca em profundidade com base algoritmo (eu não posso pagar para expandir todos os estados, mas se eu não fizer isso, eu vou começar a ter problemas com ciclos infinitas no espaço de estado, então eu teria que usar algo como iterativo aprofundamento ).

Foi útil?

Solução

Não estou vendo exatamente a solução que você pediu no c. Você pode considerar uma dessas idéias:

  • Se você tiver acesso à fonte de libc do seu qsort(), você pode copiá-lo e simplesmente substituir todo o acesso à matriz e código de indexação com equivalentes apropriadamente generalizadas. Isto dá-lhe alguma garantia modesto que o tipo subalterno é eficiente e tem alguns bugs. Sem ajuda com o risco de introduzir seus próprios erros, é claro. O grande como o qsort sistema, mas possivelmente com um multiplicador pior.

  • Se a região a ser classificado é pequeno em comparação com o tamanho do buffer, você pode usar o tipo em frente linear, guardando a chamada com um envoltório de teste para-e fazer a cópia-to-linear- rotina tampão-sort-then-cópia de volta apenas se necessário. Apresenta uma operação O(n) extra nos casos que a viagem da guarda (para n o tamanho da região a serem classificados), o que torna a O(n^2/N) < O(n) média.

Eu vejo que C ++ não é uma opção para você. :: suspiro :: Vou deixar isso aqui no caso de alguém mais pode usá-lo.

  • Se C ++ é uma opção que você poderia (subclasse o tampão se necessário, e) sobrecarregar o operador [] para tornar o padrão de algoritmos de ordenação trabalho. Mais uma vez, deve funcionar como o tipo padrão, com uma penalidade multiplicador.

Outras dicas

Eu acho que você precisa dar um passo atrás grande do problema e tentar resolvê-lo como um todo - as chances são boas de que o buffer circular semi-ordenados não é a melhor maneira de armazenar seus dados. Se for, então você já está comprometido e você terá que escrever o buffer para classificar os elementos - mesmo que isso signifique realizar uma espécie ocasional com uma biblioteca externa, ou fazê-lo quando são inseridos elementos que eu não sei. Mas no final do dia ele vai ser feio porque um FIFO e ordenados tampão são fundamentalmente diferentes.

resposta anterior, que assume a sua biblioteca tipo tem um API robusto e característica cheia (tal como solicitado na sua pergunta, isto não requer que você escreva seu próprio tipo mod ou qualquer coisa - isso depende da biblioteca de suporte arbitrária localizada de dados, geralmente através de uma função de retorno Se o seu tipo não suporta listas ligadas, não pode lidar com isso.):

O tampão circular já resolveu este problema utilizando% aritmética (mod). QSort, etc não se preocupam com as posições na memória -. Eles só precisam de um esquema para lidar com os dados de uma forma linear

Eles trabalham bem para listas ligadas (que não são lineares na memória) como fazem para 'real' linear matrizes não circulares.

Então, se você tiver uma matriz circular com 100 entradas, e você acha que precisa para classificar no top 10, e os dez acontecer para quebrar ao meio, na parte superior, em seguida, você alimenta o tipo o seguinte dois bits de informação:

  • A função para localizar um item da matriz é (x 100%)
  • Os itens a serem classificadas estão em locais 95 a 105

A função irá converter os endereços dos usos de ordenação em um índice usado na matriz real, e o fato de que a matriz envolve está escondido, embora possa parecer estranho para classificar um array passado seus limites, uma matriz circular, por definição, não tem limites. As alças% operador que para você, e você pode muito bem estar se referindo à parte da matriz como 1295 a 1305 para tudo o que importa.

pontos de bónus para ter uma matriz com 2 ^ n elementos.

Os pontos de consideração:

Parece-me que você está usando uma biblioteca de classificação que é incapaz de classificar qualquer coisa diferente de uma matriz linear - por isso não pode classificar listas, ou matrizes ligada com outra coisa senão simples ordenação. Você realmente só tem três opções:

  • Você pode re-escrever a biblioteca a ser mais flexível (ou seja, quando você chamá-lo de você dar-lhe um conjunto de ponteiros de função para operações de comparação, e as operações de acesso de dados)
  • Você pode re-escrever sua matriz por isso de alguma forma se adapta à sua existente bibliotecas
  • Você pode escrever os tipos personalizados para sua solução particular.

Agora, pela minha parte eu re-escrever o código de ordenação de modo que era mais flexível (ou duplicá-lo e editar a nova cópia para que você tenha os tipos que são rápidos para arrays lineares, e os tipos que são flexíveis para não- matrizes lineares)

Mas a realidade é que agora sua biblioteca tipo é tão simples que você não pode mesmo dizer-lhe como acessar dados que é não linear armazenado.

Se é assim tão simples, não deve haver nenhuma hesitação para adaptar a própria biblioteca para suas necessidades específicas, ou adaptar o seu tampão para a biblioteca.

Tentando um kludge feio, como de alguma forma transformar o seu tampão em uma matriz linear, classificando-o, em seguida, colocá-lo de volta no é apenas isso - um kludge feio que você vai ter que entender e manter depois. Você vai 'quebrar' em seu FIFO e mexer com as entranhas.

-Adam

Talvez um prioridade da fila poderia ser adaptado para resolver o problema. '

Você poderia rodar a fila circular até que o subconjunto em questão não envolve. Em seguida, basta passar esse subconjunto para qsort como normal. Isso pode ser caro se você precisa para classificar com freqüência ou se o tamanho do elemento da matriz é muito grande. Mas se os seus elementos da matriz são apenas ponteiros para outros objetos, em seguida, girando a fila pode ser rápido o suficiente. E, de fato, se eles são apenas ponteiros então a sua primeira abordagem pode também ser rápido o suficiente: fazer uma cópia linear separada de um subconjunto, classificando-o, e escrever os resultados de volta .

Você sabe sobre as regras relativas otimização? Você pode google-los (você vai encontrar algumas versões, mas todos dizem praticamente a mesma coisa, não).

Parece que você está otimizando sem testes. Isso é uma enorme falta de nenhum. Por outro lado, você está usando reta C, então provavelmente você está em uma plataforma restrita que requer algum nível de atenção a velocidade, por isso espero que você precisa ignorar as duas primeiras regras, porque eu suponho que você não tem escolha:

Regras de otimização:

  1. não otimizar.

  2. Se você sabe o que está fazendo, ver regra # 1

Você pode ir para as regras mais avançadas:

Regras de otimização (cont):

  1. Se você tem uma especificação que requer um certo nível de desempenho, escrever o código unoptimized e escrever um teste para ver se ele atende a essa especificação. Se ele atende-lo, você está feito. NUNCA escrever código levando em consideração o desempenho até que você tenha chegado a este ponto.

  2. Se você concluir a etapa 3 e seu código não atende as especificações, recode-lo deixando o seu código original "mais óbvia" em lá como comentários e reteste. Se ele não atender aos requisitos, jogá-lo fora e usar o código unoptimized.

  3. Se os seus melhoramentos realizados os testes passam, assegurar que os testes permanecem na base de código e são re-run, e que seus restos código originais lá como comentários.

Nota:., Que deve ser 3. 4. 5. Algo é asneira - eu não estou mesmo usando quaisquer tags de marcação

Ok, então finalmente - eu não estou dizendo isso porque eu li isso em algum lugar. Passei dias tentando desembaraçar alguns messes horrível que outras pessoas codificados porque foi "otimizado" - e a parte realmente engraçada é que 9 vezes fora de 10, o compilador poderia ter otimizado-lo melhor do que eles fizeram <. / p>

Eu percebo que há momentos em que você vai necessidade de otimizar, tudo o que eu estou dizendo é write-lo unoptimized, testar e recode-lo. Realmente não irá demorar muito mais tempo -. Pode até fazer a escrever o código otimizado mais fácil

A única razão pela qual eu estou postando isso é porque quase todas as linhas que você escreveu preocupações desempenho, e eu estou preocupado que a próxima pessoa a ver o seu código vai ser algum pobre coitado como eu.

Como sobre somthing como este exemplo aqui. Este exemplo easely ordena uma parte ou o que quiser sem ter que redefinir um monte de memória extra. Leva inly dois ponteiros de um bit de status e um contador para o loop for. 

#define _PRINT_PROGRESS
#define N 10
BYTE buff[N]={4,5,2,1,3,5,8,6,4,3};
BYTE *a = buff;
BYTE *b = buff;
BYTE changed = 0;
int main(void)
{
    BYTE n=0;
    do
    {
        b++;
        changed = 0;
        for(n=0;n<(N-1);n++)
        {
            if(*a > *b)
            {
                *a ^= *b;
                *b ^= *a;
                *a ^= *b;
                changed = 1;
            }
            a++;
            b++;
        }
        a = buff;
        b = buff;
#ifdef _PRINT_PROGRESS
        for(n=0;n<N;n++)
            printf("%d",buff[n]);
        printf("\n");
    }
#endif
    while(changed);
    system( "pause" );
}
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top