ARTES #009

ARTS é uma atividade iniciada por 由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS) e persistem por pelo menos um ano.

ARTES 009

Este é o artigo 9

Pergunta sobre algoritmo de algoritmo

Pergunta 338 do algoritmo leetcode. Contagem de bits: Dificuldade: Moderada

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

Input: 2
Output: [0,1,1]
Example 2:

Input: 5
Output: [0,1,1,2,1,2]
Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Processo de resolução de problemas:

0	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	1	2	1	2	2	3	1	2	2	3	2	3

Se acontecer de i ser 2 elevado à enésima potência, então a representação binária de i terá apenas um 1. Se i não for exatamente 2 elevado à enésima potência, como devemos calculá-lo? Pode ser dividido em 2^n + m, 2^n < i e 2^n+1 > i. Por exemplo, 13 pode ser dividido em 2 ^ 3 + 5. O número de 1s contido nos dados binários de 13 é igual ao número de 1s contidos nos dados binários de 1 mais 5. Pode-se ver que podemos usar os dados conhecidos para encontrar os dados desconhecidos. A chave para a implementação aqui é como encontrar n, que é a operação logarítmica com base 2. A implementação é a seguinte, o tempo de execução é de 20ms:

int* countBits(int num, int* returnSize) {
    int* nums = (int*)malloc(sizeof(int) * (num + 1));
    nums[0]  = 0;
    if (num >0) {
        nums[1]  = 1;
        for (int i = 2; i <=num; i++) {
            double log2Dou = log2((double)i);
            int log2int = log2Dou;
            int  remainder = i - pow(2, log2int);
            nums[i] = nums[remainder] + 1;
        }
    }
    *returnSize = num+1;
    return nums;
}

Vi uma implementação curta, como segue, o tempo de execução é de 16ms

int* countBits(int num, int* returnSize) 
{
    int* dp = (int*)malloc(sizeof(int) * (num + 1));
    for (dp[0] = 0, *returnSize = 1; *returnSize <= num; ++*returnSize)
        dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1);
    return dp;
}

Vamos analisar esta implementação: A chave para este algoritmo é entender dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1); É mais fácil entender se *returnSize estiver escrito em binário. Suponha que *returnSiz seja igual a 13, A representação binária de 13 é: 0000 1101, 0000 1101 >> 1, seguido por 0000 0110, o último bit é removido e o bit superior é preenchido com 0; Se o último dígito for 0, como 12, então o número de 1s contido em 0000 1100 é igual ao número de 1s contido no número deslocado para a direita 0000 0110. Se o último dígito for 1, como 13, então o número de 1s contido em 0000 1101 é 1 a mais que o número de 1s contido no número 0000 0110 após o deslocamento para a direita. O número de números binários contendo 1 após o deslocamento para a direita foi calculado anteriormente.

Se é igual ou 1 a mais do que após o deslocamento para a direita, pode ser obtido por AND bit a bit (*returnSize & 1) ou *returnSize% 2 também pode ser usado.

Vejamos outro algoritmo:

int* countBits(int num, int* returnSize) {
    int *dp, i, nearest;

    dp = (int *)malloc(sizeof(int) * (num + 1));
    *returnSize = num + 1;
    if (dp == NULL)
        return NULL;

    dp[0] = 0;

    if (num >= 1)
        dp[1] = 1;

    i = nearest = 2;

    while (i <= num)
    {
        nearest = (i & (i - 1)) == 0 ? i : nearest;
        dp[i] = 1 + dp[i - nearest];
        i++;
    }

    return dp;
}

A chave para este algoritmo é

    while (i <= num)
    {
        nearest = (i & (i - 1)) == 0 ? i : nearest;
        dp[i] = 1 + dp[i - nearest];
        i++;
    }

Depois de compreender nearest = (i & (i - 1)) == 0 ? i : nearest;, você também entende esse algoritmo. Quando i vale alguma coisa, (i & (i - 1)) == 0 será verdadeiro. Só será verdade quando i for exatamente 2^n. Portanto, a ideia desse algoritmo é a mesma da minha implementação, mas é mais inteligente para encontrar n e vale a pena aprender.

Existe também o seguinte algoritmo, que também é mais inteligente ao encontrar n. O sinal é 2^n:

int* countBits(int num, int* returnSize) { 20
    int* nums=(int *)calloc(num+1,sizeof(int));

    for(int i=1,sign=1;i<=num;i++){
        if(i>1&&i%sign==0){
            sign*=2;
        }
        int n=i%sign;
        nums[i]=nums[n]+1;
    }

    *returnSize=num+1;
    return nums;
}

Vamos analisar outro algoritmo:

int* countBits(int num, int* returnSize) { //28
    int bit = 1;
    *returnSize = num+1;
    int *table = (int *) malloc((*returnSize)*sizeof(int));
    memset(table, 0, (*returnSize)*sizeof(int));
    


    for (int i = 1; i <= num; i++)
    {
        if ((1 << (bit-1)) == i)
        {
            table[i] = 1;
            bit++;
        }

        else
            table[i] = 1 + table[i & ~(1 << (bit-2))];
    }
    return table;
}

A ideia de implementação deste algoritmo também está dividida em 2^n + m. Se é equivalente a procurar n, caso contrário, procurar m. table[i] = 1 + table[i & ~(1 << (bit-2))];, o 1 no lado esquerdo do sinal de mais é o 1 mais alto, que é 2^n. i & ~(1 << (bit-2)) na tabela[i & ~(1 << (bit-2))]; é m, que é equivalente a i - 2^n.

As implementações de muitas outras pessoas foram analisadas acima e você pode ver que são basicamente técnicas para operar dados binários.

Revisão

Este artigo vem de: https://blog.google/technology/developers/pushing-limits-streaming-technology/ Ultrapassando os limites da tecnologia de streaming Desafiando os limites da tecnologia de streaming

O streaming de mídia transformou a forma como consumimos música e vídeo, facilitando o acesso instantâneo ao seu conteúdo favorito. É um processo tecnicamente complexo que percorreu um longo caminho em poucos anos, mas a próxima fronteira técnica para streaming será muito mais exigente do que o vídeo. O streaming mudou a forma como consumimos músicas e vídeos, facilitando a obtenção instantânea do seu conteúdo favorito. É um processo tecnicamente complexo que percorreu um longo caminho em apenas alguns anos, mas a próxima fronteira tecnológica em streaming será ainda mais exigente do que o vídeo.

Estamos trabalhando no Project Stream, um teste técnico para resolver alguns dos maiores desafios do streaming. Para este teste, vamos ultrapassar os limites com um dos aplicativos de streaming mais exigentes: um videogame de grande sucesso. Estamos trabalhando no Project Stream, que é um teste de tecnologia que resolve os maiores desafios do streaming media. Para este teste, vamos ir além com um dos aplicativos de streaming mais exigentes do mercado - um videogame de grande sucesso.

Fizemos uma parceria com uma das editoras de videogame mais inovadoras e bem-sucedidas, a Ubisoft, para transmitir seu Assassin’s Creed Odyssey®, que será lançado em breve, para o navegador Chrome em um laptop ou desktop. A partir de 5 de outubro, um número limitado de participantes poderá jogar o que há de mais recente nesta franquia campeã de vendas, gratuitamente, durante o teste do Project Stream. Estamos trabalhando com uma das editoras de videogame mais inovadoras e bem-sucedidas, a Ubisoft, para transmitir o próximo lançamento de Assassin’s Creed Odyssey® no Chrome para laptop ou desktop. A partir de 5 de outubro, um número limitado de participantes poderá jogar gratuitamente o jogo mais recente da série mais vendida durante o período beta do projeto. Fizemos uma parceria com a Ubisoft, uma das editoras de videogame mais inovadoras e bem-sucedidas, para trazer o próximo Assassin’s Creed Odyssey® para o navegador Chrome em seu laptop ou desktop. A partir de 5 de outubro, um número limitado de participantes jogará gratuitamente a franquia mais vendida durante o stream beta do projeto.

A ideia de transmitir conteúdo graficamente rico que requer interação quase instantânea entre o controlador do jogo e os gráficos na tela apresenta uma série de desafios. Ao fazer streaming de TV ou filmes, os consumidores ficam confortáveis ​​com alguns segundos de buffer no início, mas o streaming de jogos de alta qualidade requer latência medida em milissegundos, sem degradação gráfica. A ideia de transmitir conteúdo graficamente tão rico, exigindo interação quase instantânea entre um controlador de jogo e gráficos na tela, apresenta uma série de desafios. Os consumidores aceitam alguns segundos de buffer ao fazer streaming de TV ou filmes, mas o streaming de jogos de alta qualidade requer latência medida em milissegundos sem queda na qualidade da imagem.

A tecnologia e a criatividade por trás desses videogames AAA são extraordinárias – desde detalhes incríveis e movimentos realistas da pele, roupas e cabelos dos personagens até a enorme escala do mundo em que o jogo se desenrola, até a última folha de grama. Cada pixel é alimentado por uma variedade de tecnologia de renderização em tempo real, arte, efeitos visuais, animação, simulação, física e dinâmica. Somos inspirados pelos criadores de jogos que passaram anos criando esses mundos, aventuras e experiências incríveis, e estamos construindo tecnologia que esperamos que apoie e fortaleça essa criatividade. A tecnologia e a criatividade por trás desses videogames AAA são fenomenais - desde os detalhes incríveis e movimentos realistas das peles, roupas e cabelos dos personagens, até a escala dos mundos em que os jogos se desenrolam, até cada folha de grama. Cada pixel é alimentado por uma variedade de tecnologias de renderização em tempo real, arte, efeitos visuais, animação, simulação, física e dinâmica. Somos inspirados pelos desenvolvedores de jogos que passaram anos criando esses mundos, aventuras e experiências incríveis, e estamos desenvolvendo tecnologia que esperamos que apoie e fortaleça essa criatividade.As vagas disponíveis para o Project Stream são limitadas, mas se você estiver interessado em participar, pode se inscrever em nosso site. O Project Stream é voltado para conexões domésticas de Internet com capacidade de 25 megabits por segundo, e você deve ter 17 anos ou mais e morar nos EUA para participar (outros requisitos podem ser encontrados na central de ajuda).

As vagas disponíveis no Project Stream são limitadas, mas se você estiver interessado em participar pode se inscrever em nosso site. O Project Stream funciona em uma conexão doméstica de Internet de 25 megabits por segundo, e você deve ter 17 anos ou mais e residir nos Estados Unidos para participar (requisitos adicionais podem ser encontrados na Central de Ajuda).

Estamos ansiosos para saber o que o futuro do streaming reserva e o feedback dos participantes do Project Stream. Obrigado por nos ajudar a levar o streaming para o próximo nível. Estamos ansiosos pelo futuro do streaming e pelo feedback dos envolvidos no Project Stream. Obrigado por nos ajudar a levar o streaming para o próximo nível.

<iframe width=“560” height=“315” src=“https://www.youtube.com/embed/sE53eSbzxoU” frameborder=“1” permitir=“autoplay; mídia criptografada” permitir tela cheia></iframe>

Ubisoft e Assassin’s Creed Odyssey são marcas registradas da Ubisoft Entertainment nos EUA e/ou em outros países.

POSTADO EM: DESENVOLVEDORES

DICAS:

Como implementar animação linear como a seguir

Pode ser implementado com CAShapeLayer + UIBezierPath. A dificuldade aqui é como determinar o CGPath. É simples e pode ser ajustado lentamente por você mesmo. Para animações complexas, o código pode ser gerado automaticamente.

A ideia geral é a seguinte 1 Deixe o designer exportar os gráficos desenhados pelo Sketch no formato SVG 2 Arraste o arquivo SVG para PaintCode e o software PaintCode gerará automaticamente o path code OC. 3 Com este path code, podemos desenhar este gráfico 4 Em seguida, use CABasicAnimation para adicionar animação

Compartilhar:

Recentemente eu estava lendo Compreensão aprofundada de sistemas de computador, terceira edição, e acabei de ler o primeiro capítulo. O primeiro capítulo fala muito sobre a linguagem C. Percebe-se que o autor do livro está muito atento. Cada ponto de conhecimento terá exercícios correspondentes para ajudá-lo a compreender o ponto de conhecimento correspondente. Porém, a densidade de conhecimento é muito alta, então você só pode levar o seu tempo.

Como desenvolvedor iOS, por que você precisa ler e compreender profundamente o sistema do computador? Na verdade, muito trabalho de desenvolvimento para iOS envolve desenhar UI e escrever negócios. Os métodos comumente usados ​​são todos empacotados pela Apple, mas quando você deseja otimizar profundamente seu APP, você descobrirá que deve dominar conhecimentos básicos de informática, como obter informações sobre falhas, como acelerar a inicialização do APP e como implementar um sistema de registro. Tudo isso requer uma base sólida de computador.