Shulou(Shulou.com)05/31 Report--

Today, I would like to share with you the relevant knowledge points about how C# uses symbol tables to achieve search algorithms. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Efficient retrieval of massive information (classical search algorithm) is the infrastructure of the modern information world. We use a symbol table to describe an abstract table, store the information (values) in it, and then search for and get the information according to the specified key. The exact meaning of keys and values depends on different applications. Many keys and a lot of information may be stored in a symbol table, so it is an important task to implement an efficient symbol table.

Symbol tables are sometimes called dictionaries and sometimes indexes.

1. Symbol table

A symbol table is a data structure that stores key-value pairs, supporting two operations: put, which stores a new set of key-value pairs in the table, and get, which gets the corresponding value according to a given key. The main purpose of a symbol table is to associate a key with a value.

There are many ways to construct symbol tables, which can not only insert and find efficiently, but also perform several other convenient operations. To implement a symbol table, you must first define the data structure behind it, and specify the algorithms needed to create and manipulate this data structure to achieve insertion, lookup, and other operations.

API public interface ISymbolTables where Key: IComparable {int CompareCount {get; set;} / stores the key-value pair in the table (delete the key key from the table if the value is not empty) / void Put (Key key, Value value) / get the value corresponding to the key key (return null if the key does not exist) / Value Get (Key key); / / delete the key key / void Delete (Key key) from the table / whether the key key exists in the table / bool Contains (Key key); / whether the table is not empty / bool IsEmpty () The number of key-value pairs in the table / int Size (); / the collection of all keys in the table / IEnumerable Keys () / minimum key / Key Min (); / largest key / Key Max () / Key Floor (Key key) less than or equal to key; / Key Ceilling (Key key) greater than or equal to key / / number of keys less than key (key ranking) / int Rank (Key key); / Key Select (int k) / remove the smallest key / void DeleteMin (); / delete the largest key / void DeleteMax (); / [lo... The number of keys between hi] / int Size (Key lo,Key hi); / [lo. Key / IEnumerable Keys between hi] (Key lo, Key hi);}

Basic implementation:

/ symbol table base class / public class BaseSymbolTables: ISymbolTables where Key: IComparable {public int CompareCount {get; set } / store the key-value pair in the table (delete the key key from the table if the value is not empty) / public virtual void Put (Key key Value value) {} / get the value corresponding to the key key (return null if the key does not exist) / public virtual Value Get (Key key) {return default (Value) } / / delete the key key / public void Delete (Key key) {} / whether the key key exists / from the table Public bool Contains (Key key) {return false } / whether the table is not empty / public bool IsEmpty () {return Size () = = 0 The number of key-value pairs in the table / public virtual int Size () {return 0 The collection of all keys in the table / public virtual IEnumerable Keys () {return new List () } / minimum key / public virtual Key Min () {return default (Key) } / largest key / public virtual Key Max () {return default (Key) } / public virtual Key Floor (Key key) {return default (Key) less than or equal to key } / public virtual Key Ceilling (Key key) {return default (Key) greater than or equal to key } / number of keys less than key (key ranking) / public virtual int Rank (Key key) {return 0 } / key / public virtual Key Select (int k) {return default (Key) } / remove the smallest key / public virtual void DeleteMin () {} / delete the largest key / public virtual void DeleteMax () {} / [lo... Number of keys between hi] / public virtual int Size (Key lo, Key hi) {return 0;} / [lo... Key / public virtual IEnumerable Keys (Key lo, Key hi) {return new List ();}} 2 between hi]. Ordered symbol table

In a typical application, keys are IComparable objects, so you can use a.CompareTo (b) to compare an and b keys. The symbol table keeps the order of the key, and its API can be extended to define more practical operations based on the relative position of the key. For example, the largest and smallest keys.

Ranking (Rank method) and selection (Select method)

The basic operations to check whether a new key is inserted in the right place are ranking (Rank, finding the number of keys less than the specified key) and selection (Select, finding the key ranked k). For all I from 0 to Size ()-1, I = = Rank (Select (I)), and all keys satisfy key = = Select (Rank (key)).

Equivalence of bond

The CompareTo and Equals methods are consistent in the IComparable type, but to avoid any potential ambiguity, we simply use a.CompareTo (b) = = 0 to determine whether an and b are equal.

Cost model

Cost model of lookup: in the implementation of the symbol table, the number of comparisons is used as the cost model. Use the number of visits to the array without a comparison in the inner loop.

The focus of the symbol table implementation is on the data structures and Get (), Put () methods used in it.

3. Sequential lookup in unordered linked lists

A simple choice of data structures used in a symbol table is a linked list, where each node stores a key-value pair.

The implementation of the Get method is to traverse the linked list, and the Equals method is used to compare the keys that need to be found with the keys in each node. Returns the corresponding value if it matches, otherwise returns null. The implementation of the Put method is also traversal, updating the corresponding value if it matches, otherwise creating a new node with the given key-value pair and inserting it at the beginning of the linked list. This method is called sequential lookup.

/ / search / public class SequentialSearchST:BaseSymbolTables 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);}}

Here we use an array of strings to test the above algorithm, where the key is the value in the array and the value is the inserted index:

String [] strs = new string [] {"S", "E", "A", "R", "C", "H", "E", "X", "A", "M", "P", "L", "E"}

The following is the trajectory of the index use case that is sequentially searched:

Analyzing symbol table algorithms is more difficult than sorting algorithms because different use cases perform different sequences of operations. A common situation is that although the usage patterns of lookups and inserts are unpredictable, their use is certainly not random. So we focus on worst-case performance. We use a hit to indicate a successful lookup and a miss to indicate a failed lookup.

In a linked list-based symbol table with N pairs of key values, N comparisons are required for missed lookups and inserts. A hit search requires N comparisons in the worst case. In particular, inserting N different keys into an empty table requires ~ N ^ 2 / 2 comparisons.

Finding an existing key does not take a linear level of time. One measure is to look up each key in the table and divide the total time by N. In the case where the possibility of each key in the lookup table is the same, the result is the average number of comparisons required for a lookup. Call it a random hit. From the above algorithm, we can get that the average number of comparisons is 2: the first key needs to be compared once, and the second key needs to be compared twice. The average number of comparisons was (1 / 2 / 3 / N) / N = (Numb1) / 2.

This proves that linked list-based implementation and sequential lookup are inefficient.

4. Binary search in ordered arrays

The implementation of the ordered symbol table API uses a data structure of a pair of parallel arrays, one storage key and one storage value. The following code ensures that the keys of type IComparable in the array are ordered, and then uses the index of the array to efficiently implement Get and other operations.

The core of the following algorithm is the Rank method (which uses a binary lookup algorithm), which returns the number of keys in the table that are less than a given key. For the Get method, it returns as long as the given key exists in the table, otherwise it returns null.

The Put method, as long as the given key exists in the table, the Rank method can tell us exactly what it is and update it, and we can also store the key until where it is stored when the key does not exist. When you insert a key-value pair, move the larger key and value back one grid, and insert the given key-value pair into the array, respectively.

Public class BinarySearchST: BaseSymbolTables 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 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; keys -) {keys [j] = Keys [j-1]; vals [j] = vals [j-1];} keys [I] = key; vals [I] = return keys [0];} public override Key Min () {vals [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 Keys () {return keys;}}

The following is the use case movement trajectory of the algorithm:

Analysis of binary search

The recursive implementation of the Rank method uses binary search, which is much faster than sequential search. Binary search takes up to (lgN + 1) comparisons in an ordered array of N keys.

Although the algorithm can guarantee that the time required for lookup is logarithmic, the Put method is still too slow and needs to move the array. For random arrays, the number of times to access the array required to construct a symbol table based on an ordered array is the square of the length of the array.

Inserting a new key-value pair into an ordered array of N requires access to the ~ 2N degree group at worst, so inserting N elements into an empty symbol table requires access to the ~ N ^ 2 degree group at worst.

For a static table (insert is not allowed), it is worthwhile to sort it at initialization time. The following is a summary of the simple implementation of the symbol table:

Arithmetic

Worst-case cost

(after N insertions)

Average cost

(after N random inserts)

Whether to support ordering-related operation search insert search insert order search (unordered linked list) NNN/2N No binary search (ordered array) lgN2NlgNN is all the contents of the article "how to use the symbol table to achieve the search algorithm in C #", thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.