這個算法主要用于需要針對坐標的高速插入移動和查詢。比如游戲的坐標定位，查找。問題的來源是博問上的一個問題：http://space.cnblogs.com/question/21594/

　　問題描述：已知一個userId對應一個(x，y)坐標 給定minX，maxX，minY，maxY，求出該范圍內所有 userId。 考慮到大量的userId的坐標實時在變化更新，要求插入和 檢索給定范圍內的所有userid的效率要高

算法思路

　　如上圖所示，整個算法由三部分組成，第一部分是 id 到 鏈表節點的哈希表，這個哈希表的設計是為了快速通過id找到id所在的位置。第二部分是一個二維矩陣，這個矩陣的設計是為了快速通過坐標定位到該坐標下的id列表，第三部分是雙向鏈表，采用雙向鏈表的好處是可以快速的增加和刪除節點，雙向鏈表的類屬性中設計增加當前坐標位置的屬性，每個坐標對應一個雙向鏈表。

哈希表在程序中的表現形式

Dictionary<T, LinkedListNode<T>> _Dict
二維矩陣在程序中的表現形式
MatrixLinkedList<T>[,] _Maxtrix

矩陣指向的鏈表在程序中的表現形式

class MatrixLinkedList<MT> : LinkedList<MT>
{
public int X;
public int Y;

internal MatrixLinkedList(int x, int y)
{
X = x;
Y = y;
}
}

　　插入過程

/// <summary>
/// 向矩陣增加一個帶坐標的值
/// </summary>
/// <param name="value">值</param>
/// <param name="x">x坐標</param>
/// <param name="y">y坐標</param>
public void Add(T value, int x, int y)

　　以上是函數原型，插入過程如下：

　　首先通過坐標到二維矩陣中匹配，找到對應的鏈表，然后將該值插入對應的鏈表，并得到改值在鏈表中的節點，再將值和節點插入到哈希表中。

　　刪除過程

　　以上是函數原型，刪除過程如下：通過 value 在哈希表中找到對應的鏈表節點，在鏈表中刪除這個節點。

　　移動過程

/// <summary>
/// 將某個值的坐標移動到指定的坐標
/// </summary>
/// <param name="value">值</param>
/// <param name="x">x坐標</param>
/// <param name="y">y坐標</param>
public void MoveTo(T value, int x, int y)

　　以上是函數原型，移動過程是為了實現某個值的坐標的變化，比如一個 id 對應的坐標從 1,1 變化為 2,2 了，這時需要調用這個函數更新一下數據結構

　　過程如下：通過value 在哈希表中找到對應的鏈表節點，刪除這個節點，然后通過新坐標在矩陣中找到新坐標對應的鏈表，將這個節點加入目標鏈表。接下來再更新哈希表中這個值對應的鏈表節點。

　　范圍查找過程

/// <summary>
/// 范圍查找
/// </summary>
/// <param name="minX">x 的最小值</param>
/// <param name="maxX">x 的最大值</param>
/// <param name="minY">y 的最小值</param>
/// <param name="maxY">y 的最大值</param>
/// <returns>返回在這個范圍內的所有值</returns>
public T[] RangeSearch(int minX, int maxX, int minY, int maxY)

　　以上是函數原型，查找過程如下：根據范圍在這個矩陣中找到所有這個范圍內的鏈表，并將所有這些鏈表對應的值輸出到數組中。

測試數據

　　測試環境：

　　硬件環境:

Intel i5 m430 2.27GHz ，內存4G 筆記本電腦

　　軟件環境:

　　Win7 64bit, .net framework 2.0

　　測試方法：

　　根據索引的容量，即 id 的數量，分別以1萬，10萬，100萬，1000萬為基準進行測試。測試插入的平均時間，移動的平均時間，和范圍查詢的平均時間。

范圍查詢的參數是 100 * 100 的正方形區域內的范圍。

　　從數據來看插入和移動時間容量大小幾乎沒有太大關系，每次插入和移動的時間 0.001ms 左右。每秒鐘可以插入或移動100萬次。范圍查詢的速度和容量有關，因為容量越大，需要拷貝出來的數據就越多。按照原題作者的需求，10萬容量下，范圍查詢的平均時間是0.3ms左右，每秒鐘可以查詢3000次。這個效率已經遠遠超過了原題作者要求每秒鐘更新和查詢一次的要求。

測試數據：時間參數為ms

測試代碼

代碼

Stopwatch sw = new Stopwatch();



//初始化矩陣

//假設是矩陣代表 1024*768分辨率的屏幕

//userid 為 int 

Algorithm.MatrixIndex<int> matrixIndex = new Algorithm.MatrixIndex<int>(1024, 768);
string line = Console.ReadLine();
Random rand = new Random();

int count = int.Parse(line);
sw.Reset();
sw.Start();
//初始化用戶坐標數據,將用戶坐標寫入矩陣索引

for (int userid = 0; userid < count; userid++)
{
int x = rand.Next(0, matrixIndex.Width);
int y = rand.Next(0, matrixIndex.Height);
matrixIndex.Add(userid, x, y);
}

sw.Stop();
Console.WriteLine(string.Format("插入{0}次 用時{1}ms", count, sw.ElapsedMilliseconds));
sw.Reset();

sw.Start();

for (int i = 0; i < 500; i++)

{

matrixIndex.RangeSearch(i, i +100, i, i + 100);

}

sw.Stop();



Console.WriteLine(string.Format("范圍查詢500次 用時{0}ms", sw.ElapsedMilliseconds));







sw.Reset();

sw.Start();

for (int userid = 0; userid < count; userid++)

{

int x = rand.Next(0, matrixIndex.Width);

int y = rand.Next(0, matrixIndex.Height);



matrixIndex.MoveTo(userid, x, y);

}

sw.Stop();



Console.WriteLine(string.Format("移動{0}次 用時{1}ms", count, sw.ElapsedMilliseconds));



Console.ReadKey();

矩陣索引類的完整源碼

using System;

using System.Collections.Generic;

using System.Text;



namespace Algorithm

{

/// <summary>

/// 矩陣搜索

/// </summary>

/// <typeparam name="T"></typeparam>

public class MatrixIndex<T>

{

class MatrixLinkedList<MT> : LinkedList<MT>

{

public int X;

public int Y;



internal MatrixLinkedList(int x, int y)

{

X = x;

Y = y;

}

}



object _LockObj = new object();



MatrixLinkedList<T>[,] _Maxtrix = null;



Dictionary<T, LinkedListNode<T>> _Dict = null;



readonly int _Width;

readonly int _Height;



/// <summary>

/// 矩陣寬度

/// </summary>

public int Width

{

get

{

return _Width;

}

}



/// <summary>

/// 矩陣高度

/// </summary>

public int Height

{

get

{

return _Height;

}

}



/// <summary>

/// 構造函數

/// </summary>

/// <param name="width">矩陣的寬度</param>

/// <param name="height">矩陣的高度</param>

public MatrixIndex(int width, int height)

{

_Maxtrix = new MatrixLinkedList<T>[width, height];

_Dict = new Dictionary<T, LinkedListNode<T>>();

_Width = width;

_Height = height;

}



/// <summary>

/// 向矩陣增加一個帶坐標的值

/// </summary>

/// <param name="value">值</param>

/// <param name="x">x坐標</param>

/// <param name="y">y坐標</param>

public void Add(T value, int x, int y)

{

lock (_LockObj)

{

if (_Dict.ContainsKey(value))

{

throw new ArgumentException(string.Format("value={0} exists", value));

}



if (_Maxtrix[x, y] == null)

{

_Maxtrix[x, y] = new MatrixLinkedList<T>(x, y);

}



_Dict.Add(value, _Maxtrix[x, y].AddLast(value));

}

}



/// <summary>

/// 從矩陣刪除值

/// </summary>

/// <param name="value"></param>

public void Remove(T value)

{

lock (_LockObj)

{

LinkedListNode<T> node;



if (_Dict.TryGetValue(value, out node))

{

MatrixLinkedList<T> mLinkedList = node.List as MatrixLinkedList<T>;



mLinkedList.Remove(node);



if (mLinkedList.Count == 0)

{

_Maxtrix[mLinkedList.X, mLinkedList.Y] = null;

}



_Dict.Remove(value);

}

}

}



/// <summary>

/// 獲取值的坐標

/// </summary>

/// <param name="value">值</param>

/// <param name="x">x坐標</param>

/// <param name="y">y坐標</param>

public void GetCoordinate(T value, out int x, out int y)

{

lock (_LockObj)

{

LinkedListNode<T> node;



if (_Dict.TryGetValue(value, out node))

{

MatrixLinkedList<T> mLinkedList = node.List as MatrixLinkedList<T>;

x = mLinkedList.X;

y = mLinkedList.Y;

}

else

{

throw new ArgumentException(string.Format("value={0} doesn't exist", value));

}

}

}



/// <summary>

/// 范圍查找

/// </summary>

/// <param name="minX">x 的最小值</param>

/// <param name="maxX">x 的最大值</param>

/// <param name="minY">y 的最小值</param>

/// <param name="maxY">y 的最大值</param>

/// <returns>返回在這個范圍內的所有值</returns>

public T[] RangeSearch(int minX, int maxX, int minY, int maxY)

{

lock (_LockObj)

{



List<MatrixLinkedList<T>> hitNodes = new List<MatrixIndex<T>.MatrixLinkedList<T>>();



int count = 0;



for (int x = minX + 1; x < maxX; x++)

{

for (int y = minY + 1; y < maxY; y++)

{

if (_Maxtrix[x, y] != null)

{

count += _Maxtrix[x, y].Count;

hitNodes.Add(_Maxtrix[x, y]);

}

}

}



T[] result = new T[count];



int index = 0;

foreach (MatrixLinkedList<T> node in hitNodes)

{

node.CopyTo(result, index);

index += node.Count;

}



return result;

}

}



/// <summary>

/// 將某個值的坐標移動到指定的坐標

/// </summary>

/// <param name="value">值</param>

/// <param name="x">x坐標</param>

/// <param name="y">y坐標</param>

public void MoveTo(T value, int x, int y)

{

lock (_LockObj)

{

LinkedListNode<T> node;



if (_Dict.TryGetValue(value, out node))

{

MatrixLinkedList<T> mLinkedList = node.List as MatrixLinkedList<T>;



mLinkedList.Remove(node);



if (mLinkedList.Count == 0)

{

_Maxtrix[mLinkedList.X, mLinkedList.Y] = null;

}



_Dict.Remove(value);



if (_Maxtrix[x, y] == null)

{

_Maxtrix[x, y] = new MatrixLinkedList<T>(x, y);

}



_Dict[value] = _Maxtrix[x, y].AddLast(value);

}

else

{

throw new ArgumentException(string.Format("value={0} doesn't exist", value));

}

}



}

}

}