要求

有10,000,000个100以内的整数，求某个数字出现的次数。

题解

数字出现的范围已经决定了只有100个整数，所以创建一个100个元素的数组就够用了。我总觉得这道题有坑，循环一千万次可能会比较耗时，所以选择用numpy来计算。

def np_int_counter(arr):
    data = {}
    for i in range(0, 100):
        data[i] = np.where(arr == i, 1, 0).sum()
    return data

但真的循环就慢么?真的迭代器就很爽么？分别写了几个函数来测试一下。

1. counter_sort_array 创建100个元素的数组，直接循环计数，0.85秒
2. counter_sort_dict 创建一个字典，直接循环计数，0.96秒
3. counter_sort_array_v2 依旧用100个元素的数组，直接循环计数，只是每次循环的时候用pop(0)，1.26秒
4. 用迭代器重新跑 counter_sort_array 和 counter_sort_dict，分别是9.29秒和9.46秒
5. 最后用np的数组试试，真重啊！分别是1.86、5.74，3.59秒。

结论

1. 在有限的元素集合里面，数组在查找上还是有无与伦比的优势，比字典快，因为少了Hash函数那一层。
2. 迭代器和序列，实际上就是内存与CPU的博弈。你选择迭代器，可以用到很少的空间，但是每次迭代都会计算一次，次数多了就比较耗时。而序列在这个案例里面，就是用空间来换时间的例子。不过Ruby就是一个例外，很多时候Ruby调优的策略就是就是尽量减少内存的占用。多测测总是好的。

import numpy as np
import time
import sys
import random

def time_it(func):
    def clock(*args):
        t0 = time.time()
        result = func(*args)
        elapsed = time.time() - t0
        output = '%s Total time: %0.8f sec' % (func.__name__, elapsed)
        print(output)
        return result
    return clock

@time_it
def np_int_counter(arr):
    data = {}
    for i in range(0, 100):
        data[i] = np.where(arr == i, 1, 0).sum()
    return data

@time_it
def counter_sort_array(arr):
    counter = [0] * 100
    for i in arr:
        counter[i] += 1
    return counter

@time_it
def counter_sort_array_v2(arr):
    counter = [0] * 100
    try:
        while True:
            counter[arr.pop()] += 1
    except IndexError:
        pass
    
    return counter

@time_it
def counter_sort_dict(arr):
    counter = {i: 0 for i in range(0, 100)}
    for i in arr:
        counter[i] += 1
    return counter


arr = [random.randrange(0, 100) for _ in range(10000000)]

print(sys.getsizeof(arr))
counter_sort_array(arr)
counter_sort_dict(arr)
counter_sort_array_v2(arr)

arr = (random.randrange(0, 100) for _ in range(10000000))

print(sys.getsizeof(arr))
counter_sort_array(arr)

arr = (random.randrange(0, 100) for _ in range(10000000))
counter_sort_dict(arr)

arr = np.random.randint(0, 100, size=10000000)
counter_sort_array(arr)
counter_sort_dict(arr)
np_int_counter(arr)

故事完了么？没有。我又用Ruby和Go去实验了一次。唔，Ruby用数组是0.55秒，用Hash是0.84秒。用Go是0.01秒… 天下武功，唯快不破！

require "benchmark"

arr = (0..10000000).map { rand(100) }

array_count = Benchmark.measure do
  count = [0] * 100
  arr.each { |i| count[i] += 1 }
  count
end

hash_count = Benchmark.measure do
  count = (0..100).map { |i| [i, 0] }.to_h
  arr.each { |i| count[i] += 1 }
  count
end

puts array_count
puts hash_count

package main
 
import "fmt"
import "math/rand"
import "time"

func main(){
    const n = 10000000
    var arr [n]int
    var counter [100]int

    for i := 0; i < n; i++ {
      arr[i] = rand.Intn(100)
    }

    for i := 0; i < 100; i++ {
      counter[i] = 0
    }

    t1 := time.Now()

    for i := 0; i < n; i++ {
      counter[arr[i]] += 1
    }

    elapsed := time.Since(t1)
    fmt.Println("elapsed: ", elapsed)

    fmt.Println(counter)
}