網站首頁 編程語言 正文
高效檢索海量信息（經典查找算法）是現代信息世界的基礎設施。我們使用符號表描述一張抽象的表格，將信息（值）存儲在其中，然后按照指定的鍵來搜索并獲取這些信息。鍵和值的具體意義取決于不同的應用。符號表中可能會保存很多鍵和很多信息，因此實現一張高效的符號表是很重要的任務。
符號表有時被稱為字典，有時被稱為索引。
1.符號表
符號表是一種存儲鍵值對的數據結構，支持兩種操作：插入（put），即將一組新的鍵值對存入表中；查找（get），即根據給定的鍵得到相應的值。符號表最主要的目的就是將一個健和一個值聯系起來。
構造符號表的方法有很多，它們不光能夠高效地插入和查找，還可以進行其他幾種方便的操作。要實現符號表，首先要定義其背后的數據結構，并指明創建并操作這種數據結構以實現插入，查找等操作所需的算法。
API
public interface ISymbolTables<Key,Value> where Key : IComparable
{
int CompareCount { get; set; }
/// <summary>
/// 將鍵值對存入表中（若值未空則將鍵key從表中刪除）
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
void Put(Key key, Value value);
/// <summary>
/// 獲取鍵 key 對應的值（若鍵不存在則返回 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>
/// 表中的鍵值對數量
/// </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 的鍵的數量（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]之間的鍵的數量
/// </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);
}基本實現：
/// <summary>
/// 符號表基類
/// </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>
/// 將鍵值對存入表中（若值未空則將鍵key從表中刪除）
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
public virtual void Put(Key key, Value value)
{
}
/// <summary>
/// 獲取鍵 key 對應的值（若鍵不存在則返回 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>
/// 表中的鍵值對數量
/// </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 的鍵的數量（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]之間的鍵的數量
/// </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.有序符號表
典型的應用程序中，鍵都是IComparable 對象，因此可以使用 a.CompareTo( b ) 來比較 a 和 b 兩個鍵。符號表保持鍵的有序性，可以擴展它的API，根據鍵的相對位置定義更多實用操作。例如，最大和最小的鍵。
排名（Rank 方法）和選擇 （Select 方法）
檢查一個新的鍵是否插入合適位置的基本操作是排名（Rank，找出小于指定鍵的鍵的數量）和選擇（Select，找出排名為 k 的鍵）。對于 0 到 Size（）-1 的所有 i 都有 i == Rank( Select(i) )，且所有的鍵都滿足 key == Select( Rank( key ) ) 。
鍵的等價性
IComparable 類型中 CompareTo 和 Equals 方法是一致的，但為了避免任何潛在的二義性，這里只是用a.CompareTo( b ) == 0 來判斷 a 和 b 是否相等。
成本模型
查找的成本模型：在符號表的實現中，將比較的次數作為成本模型。在內循環不進行比較的情況下，使用數組的訪問次數。
符號表實現的重點在于其中使用的數據結構和 Get() , Put() 方法。
3.無序鏈表中的順序查找
符號表中使用的數據結構的一個簡單選擇是鏈表，每個結點存儲一個鍵值對。
Get 方法的實現即為遍歷鏈表，用Equals 方法比較需要查找的鍵和每個結點中鍵。如果匹配就返回相應的值，否則返回 null。Put 方法的實現也是遍歷，如果匹配就更新相應的值，否則就用給定的鍵值對創建一個新的結點并將其插入鏈表的開頭。這種方法稱為順序查找。
/// <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);
}
}這里我們使用一個字符串數組來測試上面的算法，鍵是數組中的值，值是插入的索引：
string[] strs = new string[] { "S", "E", "A", "R", "C", "H", "E", "X", "A", "M", "P", "L", "E" };下面是順序查找的索引用例的軌跡：
分析符號表算法比排序算法更困難，因為不同的用例所進行的操作序列各不相同。常見的情形是雖然查找和插入的使用模式是不可預測的，但它們的使用肯定不是隨機的。因此我們主要研究最壞情況下的性能。我們使用命中表示一次成功的查找，未命中表示一次失敗的查找。
在含有 N 對鍵值的基于鏈表的符號表中，未命中的查找和插入操作都需要 N 次比較。命中的查找在最壞情況下需要 N 次比較。特別地，向一個空表中插入 N 個不同的鍵需要 ~ N^2 /2 次比較。
查找一個已經存在的鍵并不需要線性級別的時間。一種度量方法是查找表中的每個鍵，并將總時間除以 N 。在查找表中每個鍵的可能性都相同的情況下，這個結果就是一次查找平均所需的比較次數。稱它為隨機命中。由上面的算法可以得到平均比較次數為 ~N/2: 查找第一個鍵需要比較一次，查找第二個鍵需要比較兩次 ...... 平均比較次數為（1+2+3.....+N）/ N = (N+1)/2。
這證明基于鏈表的實現以及順序查找是低效的。
4.有序數組中的二分查找
有序符號表API的實現使用的數據結構是一對平行的數組，一個存儲鍵一個存儲值。下面的代碼保證數組中IComparable 類型的鍵有序，然后使用數組的索引來高效地實現 Get 和其他操作。
下面算法的核心是 Rank 方法(它使用二分查找的算法)，它返回表中小于給定鍵的鍵的數量。對于 Get 方法，只要給定的鍵存在于表中就返回，否則返回空。
Put 方法，只要給定的鍵存在于表中，Rank 方法就能夠精確告訴我們它的為并去更新，以及當鍵不存在時我們也能直到將鍵存儲到什么位置。插入鍵值對時，將更大的鍵和值向后移一格，并將給定的鍵值對分別插入到數組。
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;
}
}下面是該算法的用例移動軌跡：
對二分查找的分析
Rank 方法的遞歸實現使用了二分查找，二分查找比順序查找快很多。在 N 個鍵的有序數組中進行二分查找最多需要 （lgN + 1）次比較。
盡管該算法能夠保證查找所需的時間是對數級別的，但 Put 方法還是太慢，需要移動數組。對于隨機數組，構造一個基于有序數組的符號表所需訪問數組的次數是數組長度的平方級別。
向大小為 N 的有序數組中插入一個新的鍵值對在最壞情況下需要訪問 ~2N 次數組，因此向一個空符號表中插入 N 個元素在最壞情況下需要訪問 ~N^2 次數組。
對于一個靜態表（不允許插入）來說，將其在初始化時就排序是值得的。下面是符號表簡單實現的總結：
| 算法 |
最壞情況下的成本 （N 次插入后） |
平均情況下的成本 （N 次隨機插入后） |
是否支持有序性相關的操作 | ||
| 查找 | 插入 | 查找 | 插入 | ||
| 順序查找（無序鏈表） | N | N | N/2 | N | 否 |
| 二分查找（有序數組） | lgN | 2N | lgN | N | 是 |
原文鏈接：https://www.cnblogs.com/afei-24/p/13514164.html
相關推薦
- 2022-12-24 Docker中redis安裝及測試教程_docker
- 2022-11-30 深入了解Golang?interface{}的底層原理實現_Golang
- 2022-11-14 CSS樣式中選擇器+盒子模型+定位+浮動
- 2022-12-24 React?組件的狀態下移和內容提升的操作方法_React
- 2022-03-26 C語言宏定義#define的使用_C 語言
- 2022-09-13 C#使用Objects?Comparer進行對象比較_C#教程
- 2022-04-06 Android關于Button背景或樣式失效問題解決方法_Android
- 2022-11-29 詳解Go語言設計模式之單例模式_Golang
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速