Bitmap算法

如题：在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。

采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

下面我用golang实现bitmap（简单版本，00置01）：

package main

import (
	"fmt"
	"math"
	"math/rand"
	"unsafe"
)

const (
	size = 100
)

func main() {
	test_sort()
}

func test_sort() {
	arr := make([]int, size) // int占4字节，100个就占用占用400字节，3200位
	for i := 0; i < len(arr); i++ {
		arr[i] = rand.Intn(size)
	}
	print_array(arr)
	newarr := bitmap_sort(arr)
	print_result(newarr)
}

func print_array(arr []int) {
	fmt.Printf("array:")
	for i := 0; i < len(arr); i++ {
		fmt.Printf(" %d", arr[i])
	}
	fmt.Printf("\n")
}

//内存少数据最大值小可以采用方式，位排序
func bitmap_sort(arr []int) (newarr []int) {
	var left uint32
	size := int(unsafe.Sizeof(arr[0]) * 4)
	newarr = make([]int, len(arr))
	for i := 0; i < len(arr); i++ {
		index := arr[i] / size
		left = uint32(arr[i] % size)

		leftvalue := newarr[index] & (int(math.Pow(2.0, float64(left))) - 1)
		newarr[index] = (newarr[index] >> left)
		if (newarr[index] & 1) == 0 {
			newarr[index] += 1
		}
		newarr[index] = (newarr[index] << left) + leftvalue
	}
	return newarr
}

func print_result(arr []int) {
	index := 0
	size := int(unsafe.Sizeof(arr[0]) * 4)
	fmt.Printf("new array:")

	for i := 0; i < len(arr); i++ {
		for j := 0; j < size; j++ {

			bit := arr[i] & 1
			if bit != 0 {
				fmt.Printf(" %d", index)
			}
			arr[i] = arr[i] >> 1
			index++
		}
	}
}

Bitmap算法

原文：http://my.oschina.net/yang1992/blog/523994