ARTES #009

ARTS7 de octubre de 2018 a las 01:466 min read

ARTES #009

简体中文 العربية English Español Bahasa Indonesia Português

ARTES es una actividad iniciada por 由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Sugerencia y Compartir se denominan ARTS) y persisten durante al menos un año.

##ARTES 009

este es el articulo 9

Pregunta sobre el algoritmo del algoritmo

Pregunta 338 del algoritmo leetcode. Contando bits: Dificultad: 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.

Proceso de resolución 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

Si resulta que i es 2 elevado a la enésima potencia, entonces la representación binaria de i tiene solo un 1. Si i no es exactamente 2 elevado a la enésima potencia, ¿cómo deberíamos calcularlo? Se puede dividir en 2^n + m, 2^n < i y 2^n+1 > i. Por ejemplo, 13 se puede dividir en 2^3 + 5. El número de unos contenidos en los datos binarios de 13 es igual al número de unos contenidos en los datos binarios de 1 más 5. Se puede ver que podemos usar los datos conocidos para encontrar los datos desconocidos. La clave de la implementación aquí es cómo encontrar n, que es la operación logarítmica con base 2. La implementación es la siguiente y el tiempo de ejecución es de 20 ms:

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 una implementación breve, como sigue, el tiempo de ejecución es 16 ms

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;
}

Analicemos esta implementación: La clave de este algoritmo es comprender dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1); Es más fácil de entender si *returnSize está escrito en binario. Supongamos que *returnSiz es igual a 13, La representación binaria de 13 es: 0000 1101, 0000 1101 >> 1, seguido de 0000 0110, el último bit se elimina y el bit alto se llena con 0; Si el último dígito es 0, como 12, entonces el número de unos contenidos en 0000 1100 es el mismo que el número de unos contenidos en el número desplazado a la derecha 0000 0110. Si el último dígito es 1, como 13, entonces el número de unos contenidos en 0000 1101 es 1 más que el número de unos contenidos en el número 0000 0110 después del desplazamiento a la derecha. El número de números binarios que contienen 1 después del desplazamiento a la derecha se ha calculado previamente.

Si es igual o 1 más que después del desplazamiento a la derecha se puede obtener mediante AND bit a bit (*returnSize & 1), o también se puede usar *returnSize % 2.

Veamos otro 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;
}

La clave de este algoritmo es

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

Después de comprender nearest = (i & (i - 1)) == 0 ? i : nearest;, también comprenderá este algoritmo. Cuando i vale algo, (i & (i - 1)) == 0 será verdadero. Sólo será cierto cuando i sea exactamente 2^n. Por lo tanto, la idea de este algoritmo es la misma que mi implementación, pero es más inteligente para encontrar n y vale la pena aprenderlo.

También existe el siguiente algoritmo, que también es más inteligente a la hora de encontrar n. El signo es 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;
}

Analicemos otro 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;
}

La idea de implementación de este algoritmo también se divide en 2 ^ n + m. Si es equivalente a buscar n, en caso contrario buscar m. table[i] = 1 + table[i & ~(1 << (bit-2))];, el 1 en el lado izquierdo del signo más es el 1 más alto, que es 2^n. i & ~(1 << (bit-2)) en la tabla[i & ~(1 << (bit-2))]; es m, que equivale a i - 2^n.

Se han analizado anteriormente las implementaciones de muchas otras personas y se puede ver que son básicamente técnicas para operar datos binarios.

Revisión

Este artículo proviene de: https://blog.google/technology/developers/pushing-limits-streaming-technology/ Superando los límites de la tecnología de streaming Desafiando los límites de la tecnología de streaming

La transmisión de medios ha transformado la forma en que consumimos música y videos, facilitando el acceso instantáneo a su contenido favorito. Es un proceso técnicamente complejo que ha avanzado mucho en unos pocos años, pero la próxima frontera técnica del streaming será mucho más exigente que el vídeo. El streaming ha cambiado la forma en que consumimos música y vídeos, facilitando la obtención de tu contenido favorito al instante. Es un proceso técnicamente complejo que ha avanzado mucho en tan solo unos años, pero la próxima frontera tecnológica del streaming será incluso más exigente que el vídeo.

Hemos estado trabajando en Project Stream, una prueba técnica para resolver algunos de los mayores desafíos del streaming. Para esta prueba, vamos a superar los límites con una de las aplicaciones de streaming más exigentes: un videojuego de gran éxito. Hemos estado trabajando en Project Stream, que es una prueba de tecnología que resuelve los mayores desafíos de la transmisión de medios. Para esta prueba, vamos a ir más allá con una de las aplicaciones de streaming más exigentes que existen: un videojuego de gran éxito.

Nos hemos asociado con uno de los editores de videojuegos más innovadores y exitosos, Ubisoft, para transmitir su próximo lanzamiento Assassin’s Creed Odyssey® a su navegador Chrome en una computadora portátil o de escritorio. A partir del 5 de octubre, un número limitado de participantes podrán jugar lo último de esta franquicia más vendida sin costo alguno durante la prueba de Project Stream. Estamos trabajando con uno de los editores de videojuegos más innovadores y exitosos, Ubisoft, para transmitir su próximo lanzamiento de Assassin’s Creed Odyssey® en Chrome para computadora portátil o de escritorio. A partir del 5 de octubre, un número limitado de participantes podrá jugar gratis al último juego de la serie más vendida durante el período beta del proyecto. Nos hemos asociado con Ubisoft, uno de los editores de videojuegos más innovadores y exitosos, para llevar el próximo Assassin’s Creed Odyssey® al navegador Chrome de su computadora portátil o de escritorio. A partir del 5 de octubre, un número limitado de participantes jugará la franquicia más vendida de forma gratuita durante la versión beta del proyecto.

La idea de transmitir contenido tan rico en gráficos que requiere una interacción casi instantánea entre el controlador del juego y los gráficos en la pantalla plantea una serie de desafíos. Al transmitir TV o películas, los consumidores se sienten cómodos con unos segundos de almacenamiento en búfer al inicio, pero la transmisión de juegos de alta calidad requiere una latencia medida en milisegundos, sin degradación gráfica. La idea de transmitir contenido tan rico en gráficos, que requiere una interacción casi instantánea entre un controlador de juego y los gráficos en pantalla, presenta una serie de desafíos. Los consumidores están de acuerdo con unos segundos de almacenamiento en búfer cuando transmiten televisión o películas, pero la transmisión de juegos de alta calidad requiere una latencia medida en milisegundos sin una caída en la calidad de la imagen.

La tecnología y la creatividad detrás de estos videojuegos AAA son extraordinarias: desde detalles increíbles y movimientos realistas de la piel, la ropa y el cabello de los personajes, hasta la escala masiva del mundo en el que se desarrolla el juego, hasta hasta la última brizna de hierba. Cada píxel funciona con una variedad de tecnologías de renderizado en tiempo real, arte, efectos visuales, animación, simulación, física y dinámica. Nos inspiramos en los creadores de juegos que pasan años creando estos increíbles mundos, aventuras y experiencias, y estamos creando tecnología que esperamos respalde y potencie esa creatividad. La tecnología y la creatividad detrás de estos videojuegos AAA son fenomenales: desde los increíbles detalles y el movimiento realista de las pieles, la ropa y el cabello de los personajes, hasta la enorme escala de los mundos en los que se desarrollan los juegos, hasta cada brizna de hierba. Cada píxel funciona con una variedad de tecnologías de renderizado en tiempo real, arte, efectos visuales, animación, simulación, física y dinámica. Nos inspiramos en los desarrolladores de juegos que han pasado años creando estos increíbles mundos, aventuras y experiencias, y estamos desarrollando tecnología que esperamos respalde y potencie esa creatividad.Hay espacios limitados disponibles para Project Stream, pero si está interesado en participar, puede presentar su solicitud en nuestro sitio web. Project Stream está dirigido a conexiones a Internet domésticas con capacidad de 25 megabits por segundo, y debe tener 17 años o más y vivir en los EE. UU. para participar (puede encontrar otros requisitos en el centro de ayuda).

El espacio disponible en Project Stream es limitado, pero si estás interesado en participar puedes postularte en nuestro sitio web. Project Stream funciona con una conexión a Internet residencial de 25 megabits por segundo y debe tener 17 años o más y residir en los Estados Unidos para participar (puede encontrar requisitos adicionales en el Centro de ayuda).

Esperamos con ansias lo que depara el futuro del streaming y los comentarios de quienes participan en Project Stream. Gracias por ayudarnos a llevar el streaming al siguiente nivel. Esperamos con ansias el futuro del streaming y los comentarios de quienes participan en Project Stream. Gracias por ayudarnos a llevar la transmisión al siguiente nivel.

Ubisoft y Assassin’s Creed Odyssey son marcas comerciales de Ubisoft Entertainment en EE. UU. y/u otros países.

PUBLICADO EN: DESARROLLADORES

CONSEJOS:

Cómo implementar una animación lineal como la siguiente 1213

Se puede implementar con CAShapeLayer + UIBezierPath. La dificultad aquí es cómo determinar el CGPath. Es simple y usted mismo puede ajustarlo lentamente. Para animaciones complejas, el código se puede generar automáticamente.

La idea general es la siguiente. 1 Deje que el diseñador exporte los gráficos dibujados por Sketch en formato SVG 2 Arrastre el archivo SVG a PaintCode y el software PaintCode generará automáticamente el código de ruta OC. 3 Con este código de ruta, podemos dibujar este gráfico. 4 Luego use CABasicAnimation para agregar animación

Recientemente estuve leyendo Comprensión profunda de los sistemas informáticos, tercera edición, y acabo de leer el primer capítulo. El primer capítulo habla mucho sobre el lenguaje C. Se puede ver que el autor del libro está muy atento. Cada punto de conocimiento tendrá ejercicios correspondientes para ayudarlo a comprender el punto de conocimiento correspondiente. Sin embargo, la densidad de conocimiento es realmente alta, por lo que sólo puedes tomarte tu tiempo.

Como desarrollador de iOS, ¿por qué necesita leer y comprender el sistema informático en profundidad? De hecho, gran parte del trabajo de desarrollo de iOS implica dibujar la interfaz de usuario y escribir negocios. Apple empaqueta todos los métodos de uso común, pero cuando desee optimizar profundamente su APLICACIÓN, encontrará que debe dominar conocimientos informáticos básicos, como cómo obtener información sobre fallas, cómo acelerar el inicio de la APLICACIÓN y cómo implementar un sistema de registro. Todo esto requiere una base informática sólida.

FAQ