c#中位圖算法及其應(yīng)用的示例分析

這篇文章給大家分享的是有關(guān)c#中位圖算法及其應(yīng)用的示例分析的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

• 位圖算法

    位圖法就是bitmap的縮寫(xiě)，所謂bitmap，是用每一位來(lái)存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來(lái)判斷某個(gè)數(shù)據(jù)存不存在的。

• 應(yīng)用

 1.給40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù)，沒(méi)排過(guò)序。給一個(gè)無(wú)符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中。

  解決方法：申請(qǐng)512M的內(nèi)存一個(gè)bit位代表一個(gè)unsigned int值讀入40億個(gè)數(shù)，設(shè)置相應(yīng)的bit位讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在。

   2.使用位圖法判斷×××數(shù)組是否存在重復(fù)

    解決辦法：判斷集合中存在重復(fù)是常見(jiàn)編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時(shí)我們通常希望少進(jìn)行幾次掃描，這時(shí)雙重循環(huán)法就不可取了。位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個(gè)長(zhǎng)度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到 5就給新數(shù)組的第六個(gè)元素置1，這樣下次再遇到5想置位時(shí)發(fā)現(xiàn)新數(shù)組的第六個(gè)元素已經(jīng)是1了，這說(shuō)明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這種給新數(shù)組初始化時(shí)置零其后置一的做法類(lèi)似于位圖的處理方法故稱(chēng)位圖法。它的運(yùn)算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長(zhǎng)的話效率還能提高一倍。

    3.使用位圖法進(jìn)行×××數(shù)組排序

  解決辦法：

 首先遍歷數(shù)組，得到數(shù)組的最大最小值，然后根據(jù)這個(gè)最大最小值來(lái)縮小bitmap的范圍。這里需要注意對(duì)于int的負(fù)數(shù)，都要轉(zhuǎn)化為unsigned int來(lái)處理，而且取位的時(shí)候，數(shù)字要減去最小值。

應(yīng)用1代碼實(shí)現(xiàn)：

#pragma once
#include<vector>
template<class T>
struct DataType
{
	long long operator()(const T&key)
	{
		return key;
	}
};
template<class T>
struct StringType
{
	long long operator()(const string&key)
	{
		long long size = 0;
		for (int i = 0; i < key.size(); i++)
		{
			size += key[i];
		}
		return size;
	}
};
template<class T,class BMFunc=DataType<T>>
class BitMap
{
public:
	BitMap(size_t size = 1)
	{
		_a.resize(size / 32 + 1);
	}
	~BitMap(){}
	void set(T &x)
	{
		BMFunc bmf;
		size_t index = bmf(x)/ 32;
		size_t num = bmf(x) % 32;
		if (!(_a[index] & (1 << num)))
		{
			_a[index] |= (1 << num);
			_size++;
		}
		
	}
	void Reset(T x)
	{
		BMFunc bmf;
		size_t index = bmf(x) / 32;
		size_t num = bmf(x) % 32;
		if (!(_a[index] & (1 << num)))
		{
			_a[index] &= (~(1 << num));
			_size--;
		}
	}
	bool Test(T x)
	{
		BMFunc bmf;
		size_t index = bmf(x)/ 32;
		size_t num = bmf(x)% 32;
		return _a[index] &(1 << num);
	}
protected:
	vector<size_t> _a; 
	size_t _size;
};

應(yīng)用2代碼實(shí)現(xiàn)：

bool hasDuplicatedItem(int *a, int len)
{
	int length, max, i;
	length = len;
	max = a[0];
	for (i = 1; i < length; i++){
		if (a[i] > max)
			max = a[i];
	}
	int *arr;
	arr = (int*)malloc(sizeof(int)* (max + 1));
	for (i = 0; i < length; i++){
		if (arr[a[i]])
			return true;
		else
			arr[a[i]] = 1;
	}
	return false;
}

應(yīng)用3代碼實(shí)現(xiàn)：

void bitmapSort(int *a, int len)
{
	int length, max, min, i, index;
	length = len;
	min = max = a[0];
	//找出數(shù)組最大值
	for (i = 1; i < length; i++){
		if (a[i] > max){
			max = a[i];
		}
		if (min > a[i]) {
			min = a[i];
		}
	}
	//得到位圖數(shù)組
	int *arr;
	arr = (int*)malloc(sizeof(int)* (max - min + 1));
	for (i = 0; i < length; i++){
		index = a[i] - min;
		arr[index]++;
	}
	//重整a中的元素
	int arr_length;
	arr_length = max - min + 1;
	index = 0;
	for (i = 0; i < arr_length; i++){
		while (arr[i] > 0){
			a[index] = i + min;
			index++;
			arr[i]--;
		}
	}
}

感謝各位的閱讀！關(guān)于“c#中位圖算法及其應(yīng)用的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！