2011-10-19 28 views
12

Tôi có một Dictionary<string, List<int>> trong mã của tôi mà tôi đang sử dụng theo cách sau đây:Có thể thực hiện đối sánh chuỗi một phần trên khóa chuỗi từ điển không?

Key   Values 
2011-07-15 1, 2, 3 
2011-07-20 4, 5, 6 
2010-02-11 7, 8, 9 

Mã của tôi cần để có thể truy vấn cho tất cả các giá trị phù hợp với một chuỗi đặc biệt trong khóa. Ví dụ: nếu tôi có chuỗi con 2011-07, nó sẽ trả lại giá trị {1, 2, 3, 4, 5, 6}. Chuỗi con của 11 phải trả về tất cả các ID từ 1-9.

Có ai có thể giới thiệu một cách súc tích để đạt được điều này không? Hoặc cung cấp cấu trúc dữ liệu tốt hơn để truy xuất thông tin này?

+0

Tôi nghĩ rằng nhiều câu trả lời dưới đây cho thấy mọi người đang giả định những thứ khác nhau cho "chuỗi con" có nghĩa là gì. Tôi giả sử từ bình luận của bạn về 11 rằng bạn có nghĩa là một chuỗi con thực sự chung mà không nhất thiết là một tiền tố, hậu tố, chỉ là một [năm | tháng | ngày], và không phải là một regex? –

+1

@J Trana - bạn là chính xác, tôi có nghĩa là một chuỗi con thực sự chung chung. – LeopardSkinPillBoxHat

+0

@LeopardSkinPillBoxHat, bạn có thể vui lòng đăng những giải pháp cuối cùng mà bạn đã đi cùng với? – EndlessSpace

Trả lời

8

tôi sẽ làm một phương pháp khuyến nông:

public static class DictionaryExt 
{ 
    public static IEnumerable<T> PartialMatch<T>(this Dictionary<string, T> dictionary, string partialKey) 
    { 
     // This, or use a RegEx or whatever. 
     IEnumerable<string> fullMatchingKeys = 
      dictionary.Keys.Where(currentKey => currentKey.Contains(partialKey)); 

     List<T> returnedValues = new List<T>(); 

     foreach (string currentKey in fullMatchingKeys) 
     { 
      returnedValues.Add(dictionary[currentKey]); 
     } 

     return returnedValues; 
    } 
} 

Các "chi phí" thêm giá trị vào từ điển sẽ không thay đổi, nhưng chi phí thu hồi sẽ cao hơn, nhưng chỉ khi bạn biết bạn đang đi với một phần phù hợp.

Btw, tôi chắc chắn bạn có thể chuyển đổi điều này trong một biểu thức Lambda đơn lẻ, nhưng khái niệm vẫn giữ nguyên.

Chỉnh sửa: Trong ví dụ của bạn, phương pháp này sẽ trả về 2 danh sách giá trị, nhưng bạn có thể thay đổi nó để hợp nhất các danh sách. Dưới đây là phương pháp mở rộng bạn có thể làm:

public static IEnumerable<T> PartialMatch<T>(
    this Dictionary<string, IEnumerable<T>> dictionary, 
    string partialKey) 
{ 
    // This, or use a RegEx or whatever. 
    IEnumerable<string> fullMatchingKeys = 
     dictionary.Keys.Where(currentKey => currentKey.Contains(partialKey)); 

    List<T> returnedValues = new List<T>(); 

    foreach (string currentKey in fullMatchingKeys) 
    { 
     returnedValues.AddRange(dictionary[currentKey]); 
    } 

    return returnedValues; 
} 

Chỉnh sửa 2: Hãy đến với suy nghĩ của nó, bạn cũng có thể làm cho nó chung chung hơn. Với phương pháp mở rộng tiếp theo, nó sẽ làm việc trên bất kỳ từ điển, chừng nào mà bạn cung cấp một comparer đó kiểm tra những gì bạn có ý nghĩa bởi "phù hợp với phần":

public static IEnumerable<TValue> PartialMatch<TKey, TValue>(
    this Dictionary<TKey, IEnumerable<TValue>> dictionary, 
    TKey partialKey, 
    Func<TKey, TKey, bool> comparer) 
{ 
    // This, or use a RegEx or whatever. 
    IEnumerable<TKey> fullMatchingKeys = 
     dictionary.Keys.Where(currentKey => comparer(partialKey, currentKey)); 

    List<TValue> returnedValues = new List<TValue>(); 

    foreach (TKey currentKey in fullMatchingKeys) 
    { 
     returnedValues.AddRange(dictionary[currentKey]); 
    } 

    return returnedValues; 
} 
+0

đây là một cách tiếp cận tốt đẹp. – DarthVader

+0

Với chỉnh sửa thứ hai, miễn là bạn vượt qua một phương pháp so sánh phù hợp, bạn có thể có loại khóa từ điển của int và nói rằng 43 phần khớp với 343756. – Tipx

1

Cách ngắn gọn là sử dụng Bản đồ đa giá trị.

Ví dụ:

Dictionary<string, Dictionary<string, List<int>> 

tại sao không bạn lưu trữ các 2011-07 như một chìa khóa và 15 cho khóa từ điển bên trong và 1,2,3 như các giá trị.

bản đồ ["2011-07"] ["15"] = {1,2,3};

nếu bạn muốn chỉ 2011-07 bạn có thể nhận mọi thứ trong từ điển khác bằng cách truyền tải.

map["2011-07"] // sẽ trở lại u 1,2,3,4,5,6

và nếu bạn muốn đi đến một ngày cụ thể, 2011-07-15, điều này sẽ trở u chỉ 1,2,3

foreach(var element in map["2011-07"]){ 

    var values = element.values; // and you can append them to a list. 

} 

nếu bạn cần năm/tháng/ngày, bạn sẽ cần từ điển đa cấp. hoặc bạn cũng có thể sử dụng Tree.

+0

Bạn có thể cung cấp hoặc chỉ cho một ví dụ không? – LeopardSkinPillBoxHat

+0

Đề xuất của bạn không giúp ích cho ví dụ thứ 2 của tôi - Tôi muốn có thể cung cấp bất kỳ chuỗi con nào - không nhất thiết phải được chia nhỏ gọn vào năm/tháng/ngày. – LeopardSkinPillBoxHat

+0

xem chỉnh sửa. lấy làm tiếc. – DarthVader

2

Nếu từ điển sử dụng băm nội bộ, bạn sẽ không may, vì các chuỗi tương tự tạo ra các băm không giống nhau. Tôi vừa thực hiện giải pháp cho yêu cầu này vào cuối tuần tại C, một bài kiểm tra phỏng vấn/bài tập về nhà. Tôi đã sử dụng một mảng được sắp xếp làm cấu trúc cơ bản - chèn đắt tiền, nhưng tra cứu nhanh (bằng cách sử dụng tìm kiếm nhị phân). Để tìm tất cả các mục có khóa bắt đầu bằng tiền tố, tôi sẽ tìm số thứ nhất, sau đó chỉ cần tiếp theo, tiếp theo ... Đối với chuỗi con chung, tức là tiền tố không chỉ, giải pháp của tôi sẽ không hoạt động. Tại thời điểm này tôi không biết nên đề xuất gì cho tìm kiếm "chuỗi con chung".

2

Bạn có thể có ba từ điển. Năm tháng ngày.

Lưu ý rằng khi bạn thêm các mục vào ba từ điển, bạn KHÔNG sao chép các mục.

Khi bạn kéo các mục ra bằng hai phím, bạn có thể sử dụng phương pháp mở rộng LINQ Intersect() để lấy các mục khớp với cả hai phím (Sử dụng Giao điểm trên hai tập kết quả).

Lưu ý, thực hiện theo cách này sẽ không dẫn đến mã thực thi nhanh nhất.

+1

tôi nghĩ rằng việc sử dụng cây sẽ nhanh hơn thế này. nếu bạn chia sẻ các nút con, vì vậy sau đó bạn không phải làm điều LINQ. – DarthVader

+0

Bạn sẽ không phải đi qua cây nhiều lần để thu thập các nút phù hợp? Điều đó đã tăng lên. –

3

Bạn đang tìm kiếm câu trả lời ngắn gọn. Nếu không có chỉ mục ưa thích ở mức thấp cho văn bản (trong đó tôi không biết về bất kỳ lớp .Net chuyên ngành nào), tôi nghĩ từ điển vẫn là đặt cược tốt nhất của bạn. Truy vấn bằng một cái gì đó như:

myDictionary.Where (kvp => kvp.Key.Contains ("11")). SelectMany (kvp => kvp.Value);

Bạn phải tìm kiếm qua tất cả các khóa cho chuỗi con tổng quát mà không có một số ma thuật khá thú vị (không được cung cấp bởi .Net), vì vậy LINQ không làm bạn đau ở đây nhiều.

Các vấn đề liên quan