C#使用符號(hào)表實(shí)現(xiàn)查找算法
高效檢索海量信息(經(jīng)典查找算法)是現(xiàn)代信息世界的基礎(chǔ)設(shè)施。我們使用符號(hào)表描述一張抽象的表格,將信息(值)存儲(chǔ)在其中,然后按照指定的鍵來(lái)搜索并獲取這些信息。鍵和值的具體意義取決于不同的應(yīng)用。符號(hào)表中可能會(huì)保存很多鍵和很多信息,因此實(shí)現(xiàn)一張高效的符號(hào)表是很重要的任務(wù)。
符號(hào)表有時(shí)被稱為字典,有時(shí)被稱為索引。
1.符號(hào)表
符號(hào)表是一種存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu),支持兩種操作:插入(put),即將一組新的鍵值對(duì)存入表中;查找(get),即根據(jù)給定的鍵得到相應(yīng)的值。符號(hào)表最主要的目的就是將一個(gè)健和一個(gè)值聯(lián)系起來(lái)。
構(gòu)造符號(hào)表的方法有很多,它們不光能夠高效地插入和查找,還可以進(jìn)行其他幾種方便的操作。要實(shí)現(xiàn)符號(hào)表,首先要定義其背后的數(shù)據(jù)結(jié)構(gòu),并指明創(chuàng)建并操作這種數(shù)據(jù)結(jié)構(gòu)以實(shí)現(xiàn)插入,查找等操作所需的算法。
API
public interface ISymbolTables<Key,Value> where Key : IComparable { int CompareCount { get; set; } /// <summary> /// 將鍵值對(duì)存入表中(若值未空則將鍵key從表中刪除) /// </summary> /// <param name="key"></param> /// <param name="value"></param> void Put(Key key, Value value); /// <summary> /// 獲取鍵 key 對(duì)應(yīng)的值(若鍵不存在則返回 null) /// </summary> /// <param name="key"></param> /// <returns></returns> Value Get(Key key); /// <summary> /// 從表中刪去鍵 key /// </summary> /// <param name="key"></param> void Delete(Key key); /// <summary> /// 鍵 key 是否在表中存在 /// </summary> /// <param name="key"></param> /// <returns></returns> bool Contains(Key key); /// <summary> /// 表是否未空 /// </summary> /// <returns></returns> bool IsEmpty(); /// <summary> /// 表中的鍵值對(duì)數(shù)量 /// </summary> /// <returns></returns> int Size(); /// <summary> /// 表中所有鍵的集合 /// </summary> /// <returns></returns> IEnumerable<Key> Keys(); /// <summary> /// 最小的鍵 /// </summary> /// <returns></returns> Key Min(); /// <summary> /// 最大的鍵 /// </summary> /// <returns></returns> Key Max(); /// <summary> /// 小于等于 key 的鍵 /// </summary> /// <param name="key"></param> /// <returns></returns> Key Floor(Key key); /// <summary> /// 大于等于 key 的鍵 /// </summary> /// <param name="key"></param> /// <returns></returns> Key Ceilling(Key key); /// <summary> ///小于 key 的鍵的數(shù)量(key 的排名) /// </summary> /// <param name="key"></param> /// <returns></returns> int Rank(Key key); /// <summary> /// 排名為 k 的鍵 /// </summary> /// <param name="k"></param> /// <returns></returns> Key Select(int k); /// <summary> /// 刪除最小的鍵 /// </summary> void DeleteMin(); /// <summary> /// 刪除最大的鍵 /// </summary> void DeleteMax(); /// <summary> /// [lo ... hi]之間的鍵的數(shù)量 /// </summary> /// <param name="lo"></param> /// <param name="hi"></param> /// <returns></returns> int Size(Key lo,Key hi); /// <summary> /// [lo ... hi]之間的鍵 /// </summary> /// <param name="lo"></param> /// <param name="hi"></param> /// <returns></returns> IEnumerable<Key> Keys(Key lo, Key hi); }
基本實(shí)現(xiàn):
/// <summary> /// 符號(hào)表基類 /// </summary> /// <typeparam name="Key"></typeparam> /// <typeparam name="Value"></typeparam> public class BaseSymbolTables<Key, Value>: ISymbolTables<Key, Value> where Key : IComparable { public int CompareCount { get; set; } /// <summary> /// 將鍵值對(duì)存入表中(若值未空則將鍵key從表中刪除) /// </summary> /// <param name="key"></param> /// <param name="value"></param> public virtual void Put(Key key, Value value) { } /// <summary> /// 獲取鍵 key 對(duì)應(yīng)的值(若鍵不存在則返回 null) /// </summary> /// <param name="key"></param> /// <returns></returns> public virtual Value Get(Key key) { return default(Value); } /// <summary> /// 從表中刪去鍵 key /// </summary> /// <param name="key"></param> public void Delete(Key key) { } /// <summary> /// 鍵 key 是否在表中存在 /// </summary> /// <param name="key"></param> /// <returns></returns> public bool Contains(Key key) { return false; } /// <summary> /// 表是否未空 /// </summary> /// <returns></returns> public bool IsEmpty() { return Size()==0; } /// <summary> /// 表中的鍵值對(duì)數(shù)量 /// </summary> /// <returns></returns> public virtual int Size() { return 0; } /// <summary> /// 表中所有鍵的集合 /// </summary> /// <returns></returns> public virtual IEnumerable<Key> Keys() { return new List<Key>(); } /// <summary> /// 最小的鍵 /// </summary> /// <returns></returns> public virtual Key Min() { return default(Key); } /// <summary> /// 最大的鍵 /// </summary> /// <returns></returns> public virtual Key Max() { return default(Key); } /// <summary> /// 小于等于 key 的鍵 /// </summary> /// <param name="key"></param> /// <returns></returns> public virtual Key Floor(Key key) { return default(Key); } /// <summary> /// 大于等于 key 的鍵 /// </summary> /// <param name="key"></param> /// <returns></returns> public virtual Key Ceilling(Key key) { return default(Key); } /// <summary> ///小于 key 的鍵的數(shù)量(key 的排名) /// </summary> /// <param name="key"></param> /// <returns></returns> public virtual int Rank(Key key) { return 0; } /// <summary> /// 排名為 k 的鍵 /// </summary> /// <param name="k"></param> /// <returns></returns> public virtual Key Select(int k) { return default(Key); } /// <summary> /// 刪除最小的鍵 /// </summary> public virtual void DeleteMin() { } /// <summary> /// 刪除最大的鍵 /// </summary> public virtual void DeleteMax() { } /// <summary> /// [lo ... hi]之間的鍵的數(shù)量 /// </summary> /// <param name="lo"></param> /// <param name="hi"></param> /// <returns></returns> public virtual int Size(Key lo, Key hi) { return 0; } /// <summary> /// [lo ... hi]之間的鍵 /// </summary> /// <param name="lo"></param> /// <param name="hi"></param> /// <returns></returns> public virtual IEnumerable<Key> Keys(Key lo, Key hi) { return new List<Key>(); } }
2.有序符號(hào)表
典型的應(yīng)用程序中,鍵都是IComparable 對(duì)象,因此可以使用 a.CompareTo( b ) 來(lái)比較 a 和 b 兩個(gè)鍵。符號(hào)表保持鍵的有序性,可以擴(kuò)展它的API,根據(jù)鍵的相對(duì)位置定義更多實(shí)用操作。例如,最大和最小的鍵。
排名(Rank 方法)和選擇 (Select 方法)
檢查一個(gè)新的鍵是否插入合適位置的基本操作是排名(Rank,找出小于指定鍵的鍵的數(shù)量)和選擇(Select,找出排名為 k 的鍵)。對(duì)于 0 到 Size()-1 的所有 i 都有 i == Rank( Select(i) ),且所有的鍵都滿足 key == Select( Rank( key ) ) 。
鍵的等價(jià)性
IComparable 類型中 CompareTo 和 Equals 方法是一致的,但為了避免任何潛在的二義性,這里只是用a.CompareTo( b ) == 0 來(lái)判斷 a 和 b 是否相等。
成本模型
查找的成本模型:在符號(hào)表的實(shí)現(xiàn)中,將比較的次數(shù)作為成本模型。在內(nèi)循環(huán)不進(jìn)行比較的情況下,使用數(shù)組的訪問(wèn)次數(shù)。
符號(hào)表實(shí)現(xiàn)的重點(diǎn)在于其中使用的數(shù)據(jù)結(jié)構(gòu)和 Get() , Put() 方法。
3.無(wú)序鏈表中的順序查找
符號(hào)表中使用的數(shù)據(jù)結(jié)構(gòu)的一個(gè)簡(jiǎn)單選擇是鏈表,每個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)鍵值對(duì)。
Get 方法的實(shí)現(xiàn)即為遍歷鏈表,用Equals 方法比較需要查找的鍵和每個(gè)結(jié)點(diǎn)中鍵。如果匹配就返回相應(yīng)的值,否則返回 null。Put 方法的實(shí)現(xiàn)也是遍歷,如果匹配就更新相應(yīng)的值,否則就用給定的鍵值對(duì)創(chuàng)建一個(gè)新的結(jié)點(diǎn)并將其插入鏈表的開(kāi)頭。這種方法稱為順序查找。
/// <summary> /// 順序查找 /// </summary> /// <typeparam name="Key"></typeparam> /// <typeparam name="Value"></typeparam> public class SequentialSearchST<Key,Value>:BaseSymbolTables<Key, Value> where Key : IComparable { private Node First; private class Node { public Key key; public Value value; public Node next; public Node(Key _key,Value _value,Node _next) { key = _key; value = _value; next = _next; } } public override Value Get(Key key) { for (Node x = First; x != null; x = x.next) { if (key.Equals(x.key)) return x.value; } return default(Value); } public override void Put(Key key, Value value) { for (Node x = First; x != null; x = x.next) { CompareCount++; if (key.Equals(x.key)) { x.value = value; return; } } First = new Node(key,value,First); } }
這里我們使用一個(gè)字符串?dāng)?shù)組來(lái)測(cè)試上面的算法,鍵是數(shù)組中的值,值是插入的索引:
string[] strs = new string[] { "S", "E", "A", "R", "C", "H", "E", "X", "A", "M", "P", "L", "E" };
下面是順序查找的索引用例的軌跡:
分析符號(hào)表算法比排序算法更困難,因?yàn)椴煌挠美M(jìn)行的操作序列各不相同。常見(jiàn)的情形是雖然查找和插入的使用模式是不可預(yù)測(cè)的,但它們的使用肯定不是隨機(jī)的。因此我們主要研究最壞情況下的性能。我們使用命中表示一次成功的查找,未命中表示一次失敗的查找。
在含有 N 對(duì)鍵值的基于鏈表的符號(hào)表中,未命中的查找和插入操作都需要 N 次比較。命中的查找在最壞情況下需要 N 次比較。特別地,向一個(gè)空表中插入 N 個(gè)不同的鍵需要 ~ N^2 /2 次比較。
查找一個(gè)已經(jīng)存在的鍵并不需要線性級(jí)別的時(shí)間。一種度量方法是查找表中的每個(gè)鍵,并將總時(shí)間除以 N 。在查找表中每個(gè)鍵的可能性都相同的情況下,這個(gè)結(jié)果就是一次查找平均所需的比較次數(shù)。稱它為隨機(jī)命中。由上面的算法可以得到平均比較次數(shù)為 ~N/2: 查找第一個(gè)鍵需要比較一次,查找第二個(gè)鍵需要比較兩次 ...... 平均比較次數(shù)為(1+2+3.....+N)/ N = (N+1)/2。
這證明基于鏈表的實(shí)現(xiàn)以及順序查找是低效的。
4.有序數(shù)組中的二分查找
有序符號(hào)表API的實(shí)現(xiàn)使用的數(shù)據(jù)結(jié)構(gòu)是一對(duì)平行的數(shù)組,一個(gè)存儲(chǔ)鍵一個(gè)存儲(chǔ)值。下面的代碼保證數(shù)組中IComparable 類型的鍵有序,然后使用數(shù)組的索引來(lái)高效地實(shí)現(xiàn) Get 和其他操作。
下面算法的核心是 Rank 方法(它使用二分查找的算法),它返回表中小于給定鍵的鍵的數(shù)量。對(duì)于 Get 方法,只要給定的鍵存在于表中就返回,否則返回空。
Put 方法,只要給定的鍵存在于表中,Rank 方法就能夠精確告訴我們它的為并去更新,以及當(dāng)鍵不存在時(shí)我們也能直到將鍵存儲(chǔ)到什么位置。插入鍵值對(duì)時(shí),將更大的鍵和值向后移一格,并將給定的鍵值對(duì)分別插入到數(shù)組。
public class BinarySearchST<Key,Value> : BaseSymbolTables<Key, Value> where Key : IComparable { private Key[] keys; private Value[] vals; private int N; public BinarySearchST(int capacity) { keys = new Key[capacity]; vals = new Value[capacity]; } public override int Size() { return N; } public override Value Get(Key key) { if (IsEmpty()) return default(Value); int i = Rank(key); if (i < N && keys[i].CompareTo(key) == 0) return vals[i]; else return default(Value); } public override int Rank(Key key) { int lo = 0, hi = N - 1; while (lo <= hi) { int mid = lo + (hi-lo) / 2; CompareCount++; int cmp = key.CompareTo(keys[mid]); if (cmp < 0) hi = mid - 1; else if (cmp > 0) lo = mid + 1; else return mid; } return lo; } public override void Put(Key key, Value value) { int i = Rank(key); if (i < N && keys[i].CompareTo(key) == 0) { vals[i] = value; return; } for (int j = N; j > i; j--) { keys[j] = keys[j-1]; vals[j] = vals[j-1]; } keys[i] = key; vals[i] = value; N++; } public override Key Min() { return keys[0]; } public override Key Max() { return keys[N-1]; } public override Key Select(int k) { return keys[k]; } public override Key Ceilling(Key key) { int i = Rank(key); return keys[i]; } public override IEnumerable<Key> Keys() { return keys; } }
下面是該算法的用例移動(dòng)軌跡:
對(duì)二分查找的分析
Rank 方法的遞歸實(shí)現(xiàn)使用了二分查找,二分查找比順序查找快很多。在 N 個(gè)鍵的有序數(shù)組中進(jìn)行二分查找最多需要 (lgN + 1)次比較。
盡管該算法能夠保證查找所需的時(shí)間是對(duì)數(shù)級(jí)別的,但 Put 方法還是太慢,需要移動(dòng)數(shù)組。對(duì)于隨機(jī)數(shù)組,構(gòu)造一個(gè)基于有序數(shù)組的符號(hào)表所需訪問(wèn)數(shù)組的次數(shù)是數(shù)組長(zhǎng)度的平方級(jí)別。
向大小為 N 的有序數(shù)組中插入一個(gè)新的鍵值對(duì)在最壞情況下需要訪問(wèn) ~2N 次數(shù)組,因此向一個(gè)空符號(hào)表中插入 N 個(gè)元素在最壞情況下需要訪問(wèn) ~N^2 次數(shù)組。
對(duì)于一個(gè)靜態(tài)表(不允許插入)來(lái)說(shuō),將其在初始化時(shí)就排序是值得的。下面是符號(hào)表簡(jiǎn)單實(shí)現(xiàn)的總結(jié):
算法 | 最壞情況下的成本 (N 次插入后) | 平均情況下的成本 (N 次隨機(jī)插入后) | 是否支持有序性相關(guān)的操作 | ||
查找 | 插入 | 查找 | 插入 | ||
順序查找(無(wú)序鏈表) | N | N | N/2 | N | 否 |
二分查找(有序數(shù)組) | lgN | 2N | lgN | N | 是 |
到此這篇關(guān)于C#使用符號(hào)表實(shí)現(xiàn)查找算法的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
一步步教你如何創(chuàng)建第一個(gè)C#項(xiàng)目
這篇文章主要給大家介紹了關(guān)于如何創(chuàng)建第一個(gè)C#項(xiàng)目的相關(guān)資料,文中通過(guò)圖文介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2022-12-12C#實(shí)現(xiàn)Array添加擴(kuò)展實(shí)例
這篇文章主要介紹了C#實(shí)現(xiàn)Array添加擴(kuò)展,對(duì)C#初學(xué)者有不錯(cuò)的參考價(jià)值,需要的朋友可以參考下2014-08-08C#網(wǎng)頁(yè)跳轉(zhuǎn)方法總結(jié)
這篇文章主要介紹了C#網(wǎng)頁(yè)跳轉(zhuǎn)方法總結(jié)的相關(guān)資料,需要的朋友可以參考下2015-12-12C#遞歸應(yīng)用之實(shí)現(xiàn)JS文件的自動(dòng)引用
這篇文章主要為大家詳細(xì)介紹了C#如何利用遞歸實(shí)現(xiàn)JS文件的自動(dòng)引用的功能,文中的示例代碼講解詳細(xì),具有一定的參考價(jià)值,需要的可以參考一下2023-03-03基于C#實(shí)現(xiàn)一個(gè)最簡(jiǎn)單的HTTP服務(wù)器實(shí)例
這篇文章主要介紹了基于C#實(shí)現(xiàn)一個(gè)最簡(jiǎn)單的HTTP服務(wù)器的方法,詳細(xì)分析了http服務(wù)器的實(shí)現(xiàn)原理與相關(guān)技巧,以及對(duì)應(yīng)的注意事項(xiàng),需要的朋友可以參考下2014-12-12