是否有一個算法來對屬性排列上的集合進行索引？

考慮：是否有一個算法來對屬性排列上的集合進行索引？

IMatchCriteria { 
    string PropA{get;} 
    string PropB{get;} 
    int? PropC {get;} 
    int? PropD {get;} 
} 

IReportRecord : IMatchCriteria {...} 

IMatchCriteriaSet : IMatchCriteria { 
    int MatchId {get;} 
    double Limit{get;} 
} 

public class Worker{ 

private List<IMatchCriteriaSet> _matchers = GetIt(); 
//Expecting this list to be huge, ***upto 0.1m***. Some of the sample matchers: 
// MatchId=1, Limit=1000, PropA=A, PropC=101, PropD=201 
// MatchId=2, Limit=10, PropA=A 
// MatchId=3, Limit=20,   PropC=101 
// MatchId=4, Limit=500,      PropD=201 

    //Based on sample entries: 
    //Input: reportRecord{ PropA=A, PropC=101 }, Ouput: 1000, 20 
    //Input: reportRecord{ PropA=A1, PropC=102, PropD=201 }, Ouput: 500 
    public IEnumerable<double> GetMatchingLimits(IReportRecord reportRecord) { 
     //Bad, very bad option: 
     foreach(var matcher in _matchers){ 
      var matchFound=true; 
      if(reportRecord.PropA!=null && reportRecord.PropA!=matcher.PropA){     
       continue; 
      } 
      if(reportRecord.PropB!=null && reportRecord.PropA!=matcher.PropB){ 
       continue; 
      } 
      if(reportRecord.PropC!=null && reportRecord.PropC.Value!=matcher.PropC.Value){ 
       continue; 
      } 
      if(reportRecord.PropD!=null && reportRecord.PropD.Value!=matcher.PropD.Value){ 
       continue; 
      } 
      yield return matcher.Limit; 
     } 
    } 

    }

注：期待IMatchCriteriaSet是0.1米記錄。期待GetMatchingLimits被調用1m次。要求是爲實時應用程序執行所有這些操作。

基本上我需要的是一種方法來索引IMatchCriteria列表。但不能使用字典，因爲我的密鑰沒有定義。尋找一些算法來解決這個問題高效。

在.net（不僅僅是c＃）範圍內的任何建議的解決方案將是有用的。

謝謝。

來源

2013-03-03 Manish Basantani

爲每個可索引屬性使用一個字典，映射到一組匹配器。然後，您可以爲記錄中設置的每個屬性（對數複雜度）進行字典查找，並與結果集相交。從最小的結果集開始，縮小它以獲得最佳運行時間。

來源

2013-03-03 01:13:27

我剛剛解決了同樣的問題。缺點是限制了財產匹配者（一個新的財產需要新的詞典和代碼更改）。 – 2013-03-03 01:23:01

實現了一個更大的差距。即使我爲每個屬性創建一個字典，我也無法使用任何地圖來減少集合！因爲，對於每個樣本，我需要考慮兩個集合：1）範圍內的properyValue和匹配器的映射，2）該屬性未指定的地方。在建議的解決方案中，我們將錯過2）如果我們從properyMatcherDict開始並減少集合。 – 2013-03-03 01:58:44

「未指定」可以輕鬆處理爲特殊值（'null'）。至於代碼更改，是的，這是一個問題，但添加屬性也是一個代碼更改。爲了本地化影響，請列出需要枚舉屬性並將它們放在接口聲明附近的方法。如果你有很多這樣的接口，考慮代碼生成（編譯時或通過動態方法運行時）。 – 2013-03-03 08:25:13

是否有一個算法來對屬性排列上的集合進行索引？

回答

相關問題