二進制搜索自定義數據類型的列表，以匹配只是一個場

我有一個列表：二進制搜索自定義數據類型的列表，以匹配只是一個場

List<Student> allStudents = new List<Student>();

包含94,000 Student對象，其中學生被定義爲：

public class Student 
{ 
    public Int32 ID { get; set; } 
    public String Surname { get; set; } 
    public String Other_Names { get; set; } 
    public String DOB { get; set; } 
    // remaining fields omitted 
}

和分類按姓氏。

從另一個源抓取一個Student對象後，我想要對列表allStudents進行二進制搜索以僅基於Surname屬性查找匹配項。例如，如果在列表allStudents現有的記錄是：

Student(8139241, "Flintstone", "Fred", "12/1/1967")

，我搜索的項：

Student(7294311, "Flintstone", "Wilma", "14/6/1969")

二進制搜索應該是成功的。

List.BinarySearch（T，IComparer）過載似乎是一種可能性，但它是一種可行的解決方案嗎？還是有更好的策略？我將處理大量記錄和搜索，因此O（n）搜索功能將不可行。

在此先感謝！

更新：我決定從Wintellect PowerCollections庫中的MultiDictionary中替換我的List。此MultiDictionary可以接受重複密鑰。

來源

2011-06-27 InvalidBrainException

List.BinarySearch是一個很好的解決方案，其工作方式與您所期望的相似。這是一個鏈接，顯示您需要的IComparer的solution similar。不過，他們的示例不使用通用IComparer。

public class CompareCustomDataType : IComparer<Student> { 

    public int Compare(Student x, Student y) 
    { 
    if (x == y) return 0; 
    if (x == null) return -1; 
    if (y == null) return 1; 

    return String.Compare(x.Surname, y.Surname); 
    } 
... 
}

來源

2011-06-27 03:07:12

它具有以下限制

如果列表中包含具有相同值的多個元素，該方法只返回事件之一，它可能會返回事件中的任何一個，不一定是第一個。
列表必須已經根據比較器實現進行排序;否則，結果不正確。

我會建議你使用LINQ找到您的列表匹配的數據。

var data = students.where(o => o.SurName='xxxxx');

>您還可以使用查找或使用謂詞列表對象的FindAll方法。

來源

2011-06-27 03:12:59

謝謝大家對您的輸入。 @Amit有使用Linq的優勢嗎？我知道Find和FindAll是線性搜索; Linq查詢更好地攤銷？ – InvalidBrainException

我不是linq的專家; Linq使用線性搜索。 Linq是一種結構化編程技術，它使代碼更具可讀性和可理解性。如果您看到該語句非常明顯，那麼代碼行試圖查找列表中與Surname字段匹配的所有項目。 –

有了這麼多的條目，你可能會更好使用Dictionary<string, Student>查找，這將被攤銷O（1）。雖然可能會有多個學生具有相同的姓氏，所以它可能會是類似Dictionary<string, List<Student>>

也作爲阿米特指出，使用二進制搜索時，有重複的項目可能會很棘手，因爲你不知道哪個索引你會得到一系列的重複。您必須搜索返回索引的左側和右側，查看是否存在其他匹配的姓氏。

來源

2011-06-27 04:53:21 BrandonAGr

感謝您的建議。字典的想法似乎非常有吸引力，由於O（1）攤銷，但我曾經使用過的最接近的東西是Perl哈希值，所以我試圖讓我的頭靠近它。確切的說，我需要我的列表和數據表：大學畢業生找到匹配（姓氏，Other_Names，...，...）。唯一的兩個領域是Surname和Other_Names，顯然他們是唯一匹配的領域。 – InvalidBrainException

但因爲字典只能有每對一個關鍵，我需要匹配兩個字符串（姓和Other_Names），我需要思考如何構建字典，以便它可以對列表匹配。哎，細節... – InvalidBrainException

也許我可以定義一個類名（姓氏，Other_Names），然後做一個解釋（<姓名，學>）。但是如果有幾個同名的人（例如加利福尼亞的約翰史密斯和愛達荷的約翰史密斯），鑰匙就不再是唯一的，這是不好的。然後可能定義Name類爲Name（Surname，Other_Names，UniqueID）將起作用。嗯........ – InvalidBrainException

定義IComparable<T>界面爲你Student類。然後，您的列表中的所有排序和比較方法，包括BinarySearch()都會自動使用這一個。

來源

2011-06-27 07:41:59 Dummy01

二進制搜索自定義數據類型的列表，以匹配只是一個場

回答

相關問題