SENI #009

ARTS7 Oktober 2018 pukul 01.465 min read

SENI #009

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

SENI adalah kegiatan yang diprakarsai oleh 由左耳朵耗子--陈皓: Kerjakan setidaknya satu pertanyaan algoritma leetcode setiap minggu, baca dan komentari setidaknya satu artikel teknis berbahasa Inggris, pelajari setidaknya satu keterampilan teknis, dan bagikan artikel yang berisi opini dan pemikiran. (Artinya, Algoritma, Review, Tip, dan Share disebut sebagai SENI) dan bertahan setidaknya selama satu tahun.

SENI 009

Ini adalah pasal 9

Pertanyaan algoritma algoritma

pertanyaan algoritma leetcode 338. Menghitung Bit: Kesulitan: Sedang


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.

Proses pemecahan masalah:

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

Jika i kebetulan 2 dipangkatkan ke n, maka representasi biner dari i hanya mempunyai satu 1. Jika i tidak tepat 2 dipangkatkan ke n, bagaimana cara menghitungnya? Dapat dipecah menjadi 2^n + m, 2^n < i dan 2^n+1 > i. Misalnya, 13 dapat dipecah menjadi 2^3 + 5. Banyaknya angka 1 yang terdapat pada data biner 13 sama dengan banyaknya angka 1 yang terdapat pada data biner 1 ditambah 5. Terlihat bahwa kita dapat menggunakan data yang diketahui untuk mencari data yang tidak diketahui. Kunci implementasinya disini adalah bagaimana mencari n yang merupakan operasi logaritma dengan basis 2. Implementasinya sebagai berikut, running time adalah 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;
}

Saya melihat implementasi singkatnya, sebagai berikut, waktu berjalannya adalah 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;
}

Mari kita analisis implementasi ini: Kunci dari algoritma ini adalah memahami dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1); Lebih mudah dipahami jika *returnSize ditulis dalam biner. Asumsikan *returnSiz sama dengan 13, Representasi biner dari 13 adalah: 0000 1101, 0000 1101 >> 1, diikuti oleh 0000 0110, bit terakhir dihilangkan, dan bit tinggi diisi dengan 0; Jika angka terakhirnya adalah 0, misalnya 12, maka angka 1 yang terdapat pada 0000 1100 sama dengan angka 1 yang terdapat pada angka yang digeser ke kanan 0000 0110. Jika angka terakhirnya adalah 1, misalnya 13, maka angka 1 yang terdapat pada 0000 1101 lebih banyak 1 daripada jumlah angka 1 yang terdapat pada angka 0000 0110 setelah digeser ke kanan. Banyaknya bilangan biner yang mengandung 1 setelah pergeseran ke kanan telah dihitung sebelumnya.

Apakah sama atau 1 lebih banyak dari setelah pergeseran ke kanan dapat diperoleh dengan bitwise AND (*returnSize & 1), atau *returnSize % 2 juga dapat digunakan.

Mari kita lihat algoritma lainnya:

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

Kunci dari algoritma ini adalah

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

Setelah memahami nearest = (i & (i - 1)) == 0 ? i : nearest;, Anda juga memahami algoritma ini. Ketika i bernilai sesuatu, (i & (i - 1)) == 0 akan benar. Itu hanya akan benar jika i tepat 2^n. Oleh karena itu ide algoritma ini sama dengan implementasi saya, namun lebih pintar dalam mencari n dan layak untuk dipelajari.

Ada juga algoritma berikut yang juga lebih pintar dalam mencari n. Tandanya adalah 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;
}

Mari kita analisis algoritma lain:

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

Ide implementasi algoritma ini juga dibagi menjadi 2^n + m. Jika setara dengan mencari n, jika tidak mencari m. table[i] = 1 + table[i & ~(1 << (bit-2))];, angka 1 di sebelah kiri tanda plus merupakan angka 1 tertinggi yaitu 2^n. i & ~(1 << (bit-2)) dalam tabel[i & ~(1 << (bit-2))]; adalah m, yang setara dengan i - 2^n.

Banyak implementasi orang lain yang telah dianalisis di atas, dan Anda dapat melihat bahwa mereka pada dasarnya adalah teknik untuk mengoperasikan data biner.

Ulasan

Artikel ini berasal dari: https://blog.google/technology/developers/pushing-limits-streaming-technology/ Mendorong batas-batas teknologi streaming Menantang batas-batas teknologi streaming

Media streaming telah mengubah cara kita mengonsumsi musik dan video, sehingga memudahkan Anda mengakses konten favorit secara instan. Ini adalah proses yang secara teknis rumit dan telah berkembang pesat dalam beberapa tahun saja, namun batasan teknis berikutnya untuk streaming akan jauh lebih menuntut daripada video. Streaming telah mengubah cara kita mengonsumsi musik dan video, sehingga memudahkan Anda mendapatkan konten favorit secara instan. Ini adalah proses yang secara teknis rumit dan telah berkembang pesat hanya dalam beberapa tahun, namun batasan teknologi berikutnya dalam streaming akan lebih menuntut daripada video.

Kami sedang mengerjakan Project Stream, sebuah pengujian teknis untuk memecahkan beberapa tantangan terbesar dalam streaming. Untuk pengujian ini, kami akan melampaui batas dengan salah satu aplikasi streaming yang paling menuntut—video game blockbuster. Kami telah mengerjakan Project Stream, yang merupakan uji teknologi yang memecahkan tantangan terbesar media streaming. Untuk pengujian ini, kami akan menerapkan salah satu aplikasi streaming yang paling menuntut di luar sana - video game blockbuster.

Kami telah bermitra dengan salah satu penerbit video game paling inovatif dan sukses, Ubisoft, untuk melakukan streaming Assassin’s Creed Odyssey® yang akan segera dirilis ke browser Chrome Anda di laptop atau desktop. Mulai tanggal 5 Oktober, peserta dalam jumlah terbatas akan dapat memainkan game terbaru dari franchise terlaris ini tanpa biaya selama durasi pengujian Project Stream. Kami bekerja sama dengan salah satu penerbit video game paling inovatif dan sukses, Ubisoft, untuk melakukan streaming rilis mendatang Assassin’s Creed Odyssey® di Chrome untuk laptop atau desktop. Mulai tanggal 5 Oktober, peserta dalam jumlah terbatas akan dapat memainkan game terbaru dari seri terlaris secara gratis selama periode proyek beta. Kami telah bermitra dengan Ubisoft, salah satu penerbit video game paling inovatif dan sukses, untuk menghadirkan Assassin’s Creed Odyssey® yang akan datang ke browser Chrome di laptop atau desktop Anda. Mulai 5 Oktober, sejumlah peserta terbatas akan memainkan franchise terlaris secara gratis selama proyek streaming beta.

Gagasan untuk melakukan streaming konten kaya grafis yang memerlukan interaksi hampir instan antara pengontrol game dan grafik di layar menimbulkan sejumlah tantangan. Saat streaming TV atau film, konsumen merasa nyaman dengan buffering beberapa detik di awal, namun streaming game berkualitas tinggi memerlukan latensi yang diukur dalam milidetik, tanpa degradasi grafis. Gagasan untuk melakukan streaming konten yang kaya grafis, yang memerlukan interaksi hampir seketika antara pengontrol game dan grafis di layar, menghadirkan sejumlah tantangan. Konsumen baik-baik saja dengan buffering beberapa detik saat streaming TV atau film, tetapi streaming game berkualitas tinggi memerlukan latensi yang diukur dalam milidetik tanpa penurunan kualitas gambar.

Teknologi dan kreativitas di balik video game AAA ini sungguh luar biasa—mulai dari detail luar biasa dan pergerakan kulit, pakaian, dan rambut karakter yang sangat nyata, hingga skala besar dunia tempat game tersebut berlangsung, hingga setiap helai rumput terakhir. Setiap piksel didukung oleh serangkaian teknologi rendering real-time, seni, efek visual, animasi, simulasi, fisika, dan dinamika. Kami terinspirasi oleh para pembuat game yang menghabiskan waktu bertahun-tahun menciptakan dunia, petualangan, dan pengalaman menakjubkan ini, dan kami membangun teknologi yang kami harap akan mendukung dan memberdayakan kreativitas tersebut. Teknologi dan kreativitas di balik video game AAA ini sangat fenomenal - mulai dari detail luar biasa dan pergerakan kulit karakter, pakaian, dan rambut yang terlihat nyata, hingga skala dunia tempat game tersebut berlangsung, hingga ke setiap helai rumput. Setiap piksel didukung oleh serangkaian teknologi rendering real-time, seni, efek visual, animasi, simulasi, fisika, dan dinamika. Kami terinspirasi oleh para pengembang game yang telah menghabiskan waktu bertahun-tahun menciptakan dunia, petualangan, dan pengalaman menakjubkan ini, dan kami mengembangkan teknologi yang kami harap akan mendukung dan memberdayakan kreativitas tersebut.Tempat yang tersedia untuk Project Stream terbatas, namun jika Anda tertarik untuk berpartisipasi, Anda dapat mendaftar di situs web kami. Project Stream ditujukan untuk koneksi internet rumah yang mampu mencapai 25 megabit per detik, dan Anda harus berusia 17 tahun ke atas dan tinggal di AS untuk berpartisipasi (persyaratan lainnya dapat ditemukan di pusat bantuan).

Tempat yang tersedia di Project Stream terbatas, namun jika Anda tertarik untuk berpartisipasi, Anda dapat mendaftar di situs web kami. Project Stream berfungsi pada koneksi internet rumah 25 megabit per detik, dan Anda harus berusia 17 tahun ke atas dan tinggal di Amerika Serikat untuk berpartisipasi (persyaratan tambahan dapat ditemukan di Pusat Bantuan).

Kami menantikan masa depan streaming, dan masukan dari mereka yang berpartisipasi dalam Project Stream. Terima kasih telah membantu kami membawa streaming ke level berikutnya. Kami menantikan masa depan streaming dan masukan dari pihak-pihak yang terlibat dalam Project Stream. Terima kasih telah membantu kami membawa streaming ke level berikutnya.

Ubisoft dan Assassin’s Creed Odyssey adalah merek dagang Ubisoft Entertainment di AS dan/atau negara lain.

DIPOSTING DI: PENGEMBANG

TIPS:

Cara mengimplementasikan animasi linier seperti berikut ini 1213

Itu dapat diimplementasikan dengan CAShapeLayer + UIBezierPath. Kesulitannya disini adalah bagaimana menentukan CGPath. Ini sederhana dan dapat disesuaikan secara perlahan sendiri. Untuk animasi yang kompleks, kode dapat dibuat secara otomatis.

Ide umumnya adalah sebagai berikut 1 Biarkan desainer mengekspor grafik yang digambar oleh Sketch dalam format SVG 2 Seret file SVG ke PaintCode, dan perangkat lunak PaintCode akan secara otomatis menghasilkan kode jalur OC. 3 Dengan kode jalur ini, kita dapat menggambar grafik ini 4 Kemudian gunakan CABasicAnimation untuk menambahkan animasi

Baru-baru ini saya membaca Pemahaman Mendalam Sistem Komputer Edisi Ketiga, dan saya baru membaca bab pertama. Bab pertama berbicara banyak tentang bahasa C. Terlihat bahwa penulis buku tersebut sangat perhatian. Setiap poin pengetahuan akan memiliki latihan yang sesuai untuk membantu Anda memahami poin pengetahuan yang sesuai. Namun, kepadatan pengetahuannya sangat tinggi, jadi Anda hanya bisa meluangkan waktu saja.

Sebagai pengembang iOS, mengapa Anda perlu membaca dan memahami sistem komputer secara mendalam? Faktanya, banyak pekerjaan pengembangan iOS yang melibatkan bisnis menggambar UI dan menulis. Metode yang umum digunakan semuanya dikemas oleh Apple, tetapi ketika Anda ingin mengoptimalkan APP Anda secara mendalam, Anda akan menemukan bahwa pengetahuan dasar komputer harus dikuasai, seperti cara mendapatkan informasi kerusakan, cara mempercepat startup APP, dan cara menerapkan sistem logging. Semua ini memerlukan dasar komputer yang kuat untuk melakukannya.

FAQ