熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> .NET編程 >> 正文

用 C# 實現帶鍵值的優先隊列[2]

2013-11-13 12:13:43  來源: .NET編程 

  上述 KeyedPriorityQueue<T K V> 類中T 是要存儲在這個帶鍵值的優先隊列中的數據的類型K 是鍵的數據類型V 是值的數據類型

  Dictionary<K int> keys 字段用於存儲鍵(K)在堆(heap)中的索引

  bool ContainsKey(K key) 方法用於查找指定的鍵是否在該優先隊列中

  Update(T v) 方法用於更新指定項目的值注意如果要使用這個方法的話T 不能是值類型之所以在這個方法的第二行:

  if (typeof(T)IsValueType) throw new InvalidOperationException(T 不能是值類型);

  進行這個判斷而不是在將該類聲明為

  class KeyedPriorityQueue<T K V> where T : class { }

  這是因為如果不需要調用 Update(T v) 方法的話T 還是允許是值類型的

  該類的其他方面除了加入對 keys 字段的處理以外就和標准的優先隊列差不多了

  有了這個 KeyedPriorityQueue<T K V> 類就可以從中派生出 PriorityQueue<T> 類來

class PriorityQueue<T> : KeyedPriorityQueue<T object object>
{
 public PriorityQueue() : base(null) { }
 public PriorityQueue(int capacity) : base(capacity null) { }
 public PriorityQueue(IComparer<T> comparer) : base(comparer null) { }
 public PriorityQueue(int capacity IComparer<T> comparer) : base(capacity comparer null) { }
}

  對於 PriorityQueue<T> 類的實例如果調用 ContainsKey 方法總是返回 false如果調用 Update 方法總是引發 NotSupportedException 異常

  現在讓我們回到上一篇隨筆 Timus Memory management 中需要稍微修改一下我們的內存管理器程序

  首先Block 必須從結構改為類如下所示

sealed class Block
{
 public int Id { get; private set; }
 public int Time { get; set; }
 public Block(int id int time) { Id = id; Time = time; }
}

  然後需要一個實現 IKeyValue<T K V> 接口的類

sealed class IdTime : IKeyValue<Block int int>
{
 public int GetKey(Block x) { return xId; }
 public int GetValue(Block x) { return xTime; }
 public void SetValue(Block x int v) { xTime = v; }
}

  最後就剩下最簡單的工作了將 Main 方法的第二行

  var used = new KeyedPriorityQueue(new TimeComparer());

  修改為

  var used = new KeyedPriorityQueue<Block int int>(new TimeComparer() new IdTime());

  就可以了

  當然這也是有代價的就是運行時間和內存使用都增加了

ID Date Author Problem Language Judgement

  result

Execution

  time

Memory

  used

:: Apr skyivben C# Accepted KB :: Apr skyivben C# Accepted KB


  上表中第二行就是上一篇隨筆中的程序提交的結果第一行就是按照本篇隨筆修改後的程序提交的結果

  實際上雖然 KeyedPriorityQueue 類中的代碼與 PriorityQueue<T> 類中代碼有大量的重復可以用本篇隨筆的方法將 KeyedPriorityQueue 類改為 KeyedPriorityQueue<T K V> 泛型類再從中派生出 PriorityQueue<T> 類來以消除重復的代碼但是這樣必然造成 PriorityQueue<T> 類的運行效率降低所以一般情況下PriorityQueue<T> 類還是使用原來的代碼為好

  當然如果能夠從 PriorityQueue<T> 類派生出 KeyedPriorityQueue<T K V> 類那就比較完美了不知各位大俠是否還有更好的方法?

[]  []  


From:http://tw.wingwit.com/Article/program/net/201311/15448.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.