Leo-20180707.md

Leo Lei | 雷雨

July 07, 2018

1.Leetcode

Counting Bits

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: For num = 5 you should return [0,1,1,2,1,2].

Analysis

It's easy to come up a brute force solution: count bits for each number between 0 and n, both inclusive. Counting bits for a number could also be solved brutally. An improvement would be using Brian Kernighan's Algorithm to count bits.

However, the problem could be a dynamic programming problem if we find the relation between the sequential numbers(a.k.a. a transformation function). One such function is

res[i] = res[i - (1 << power)] + 1, e.g. res[3] = res[3-2] + 1

(0)<sub>10</sub> = (0)<sub>2</sub>

(1)<sub>10</sub> = (1)<sub>2</sub>

(2)<sub>10</sub> = (10)<sub>2</sub>

(3)<sub>10</sub> = (11)<sub>2</sub>

......

Implementation

# brute force + Brian Kernighan's Algorithm
class Solution(object):
    def count_ones(self, n):
        ones = 0
        while n:
            ones += 1
            n &= n - 1
        return ones

    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        return [self.count_ones(n) for n in range(num+1)]

# Dynamic programming
class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        if num < 2:
            return [i for i in range(num+1)]

        res = [0 for i in range(num+1)]
        res[1] = 1
        power = 1
        for i in range(2, num+1):
            res[i] = res[i - (1 << power)] + 1
            if (i+1) == 1 << (power+1):
                power += 1

        return res

2. Article and comment

How I won Lyft Perception Challenge by Asad Zia

I also attended the challenge but didn't do very well (top 40% I guess). I've learned so much from Asad Zia, the winner, by reading his write up.

1. Binary Dilation
2. Optimize Inference graph
3. Profile GPU
4. Parallel pre/post process

The 1st technique is to improve precision/recall, and the rest are to speed up the training and inference.

3. New skill

Deluge BitTorrent Client for Ubuntu 16.04

• use deluge to download large datasets, e.g. the multi-gigabytes data breach dumps
• Deluge Console Documentation

4. Share an article

Semantic Segmentation Basics

Segmentation is essential for image analysis tasks. Semantic segmentation describes the process of associating each pixel of an image with a class label, (such as flower, person, road, sky, ocean, or car).