2012-09-14 35 views
1

我有N個SortedLists,每個SortedLists都有一個對象集合,它們包含一個int ID,它們被排序。我需要找到所有列表中存在的一組對象。Intersect N SortedLists <T> in c#

我的第一個想法是按大小對列表進行排序,以最小子集開始,然後我可以將每個和.Intersect()其他列表放在一起,但是對於大列表和效率,我想利用它們的事實'排序。我猜是有一些算法是最優的 - 也許數據庫引擎會像散列連接一樣使用。我只是不知道什麼算法是最好的。任何幫助表示讚賞。

回答

2

你可以通過並行列表,使用每個列表中的一個索引循環。從其索引中的一個列表中選擇一個值,然後只要其索引中的值更小,就可以推進其他列表。如果您發現缺少該值的列表,請從該列表中獲取下一個較高的值,然後開始尋找。

當您對所有列表進行高級設置並找到所有列表中的值時,您可以添加一個可添加到結果中的值。推進所有列表並重新開始尋找價值。重複,直到您到達所有列表的末尾。

這似乎做的工作:

public static SortedList<int, T> MultiIntersect<T>(params SortedList<int, T>[] lists) { 
    SortedList<int, T> result = new SortedList<int, T>(); 
    int[] index = new int[lists.Length]; 
    bool cont; 
    do { 
    int list = 0; 
    int value = lists[list].Keys[index[list]]; 
    while (list < lists.Length) { 
     while (index[list] < lists[list].Count && lists[list].Keys[index[list]] < value) index[list]++; 
     if (index[list] == lists[list].Count) { 
     return result; 
     } else if (lists[list].Keys[index[list]] > value) { 
     value = lists[list].Keys[index[list]]; 
     list = 0; 
     } else { 
     list++; 
     } 
    } 
    result.Add(value, lists[0].Values[index[0]]); 
    cont = true; 
    for (var i = 0; i < index.Length; i++) { 
     index[i]++; 
     cont &= index[i] < lists[i].Count; 
    } 
    } while(cont); 
    return result; 
} 
3

相交或多或少散列連接。如果對數據進行排序,您可以進行嵌套循環合併,但我認爲沒有任何庫方法會爲您執行此操作,編寫該方法有點麻煩。

另一個基於散列的方法顯着。爲什麼不對列表進行連接並使用Distinct?這將把它保存在一個哈希表中。

使用distinct /散列邏輯,只有尋求優化,如果它實際上會導致性能問題。嵌套循環方法可能會比較慢,無論如何,如果Distinct(或其他基於散列的)方法足夠快,則不需要花費大量時間編寫它。

例子:

var result = list1.Concat(list2).Concat(list3).Distinct(); 

如果你不知道在編譯時列表的數量,試試這個:

IEnumerable<IEnumerable<T>> lists = // a sequence of lists 
var result = lists.Aggregate(Enumerable.Empty<T>(), (a, b) => a.Concat(b)).Distinct(); 
0

這個怎麼樣的做法?

HashSet<YourType> hashSet = new HashSet<YourType>(list1); 
hashSet.IntersectWith(list2); 
hashSet.IntersectWith(list3); 
... 
hashSet.IntersectWith(listn); 
List<YourType> intersection = hashSet.ToList(); 

恕我直言應該足夠高效。

0

什麼,我認爲是在代碼Guffas建議。對於數組,他們打字速度更快。

void Main() 
{ 
var lists = new [] {new[] {1, 1, 2, 3, 4, 5, 6, 9, 11, 13}, 
        new[] {1, 1, 5, 6, 7, 13}, 
        new[] {1, 1, 6, 8, 9, 13}, 
        }; 

var mergedSet = lists[0]; 
for(var i = 1; i < lists.Length; i++) 
{ 
    mergedSet = Merge(lists[i], mergedSet); 
} 
} 

int[] Merge (int[] sla, int[] slb) 
{ 
int ixa = 0, ixb = 0; 
List<int> result = new List<int>(); 
while(ixa < sla.Length && ixb < slb.Length) 
{ 
    if (sla[ixa] < slb[ixb]) { ixa++; } 
    else if (sla[ixa] > slb[ixb]) { ixb++; } 
    else { result.Add(sla[ixa]); ixa++; ixb++; } 
} 

return result.ToArray(); 
}  

排序上規模的投入和與最小的啓動列表中可能會提供一些額外的性能,但如果最小列表包含在總集的最小和最大值所有列表中的所有項目將仍然運行。

我覺得可讀性可能有利於使用LINQ查詢,建議其他地方的可能較有效的方法。