2015-11-26 60 views
9

這裏是一個非常方便的擴展,它適用於任何事物的arrayc#泛型,涵蓋數組和列表?

public static T AnyOne<T>(this T[] ra) where T:class 
{ 
    int k = ra.Length; 
    int r = Random.Range(0,k); 
    return ra[r]; 
} 

遺憾的是它不爲任何東西一個List<>工作。下面是對任何List<>

public static T AnyOne<T>(this List<T> listy) where T:class 
{ 
    int k = listy.Count; 
    int r = Random.Range(0,k); 
    return listy[r]; 
} 

工作其實相同的擴展名,有沒有辦法來概括仿製藥在一氣呵成涵蓋array S和List<> S'或者它知道是不可能的?


它發生在我身上,答案甚至可以進一步包括Collection s?或者確實有一位以下的專家已經實現了?


PS,我很抱歉沒有明確提到這是在Unity3D環境中。 「Random.Range」是一個統一到骨骼的功能,並且任何遊戲工程師都會將「AnyOne」調用視爲100%的遊戲引擎。這是您爲任何遊戲項目輸入的第一個擴展名,並且您不斷在遊戲代碼中使用它(「任何爆炸!」,「任何硬幣音效!」等等等等!)。

顯然,它當然可以用於任何c#milieu。

+0

什麼是Random.Range()?它是否在'(start,end)'之間產生一個值,包括結束或排除? –

+0

嗨yannick,謝謝你關注這個問題。 Random.Range真的不重要,只是考慮它的僞代碼。非常明顯,對於整數,它是0到k獨佔(arraywise),或它不會工作:) ...它只是來自最受歡迎的遊戲開發環境Unity3D的一個函數 – Fattie

回答

5

實際上對於你的情況T[]List<T>之間最合適的通用接口是IReadOnlyList<T>

public static T AnyOne<T>(this IReadOnlyList<T> list) where T:class 
{ 
    int k = list.Count; 
    int r = Random.Range(0,k); 
    return list[r]; 
} 

作爲另一個答覆中提到,IList<T>也可以,但是良好的實踐要求你從呼叫者要求該方法所需的最小功能,在此情況下爲Count屬性和只讀索引器。

IEnumerable<T>也適用,但它允許調用者傳遞一個非集合迭代器,其中CountElementAt擴展方法可能是非常低效的 - 像Enumerable.Range(0, 1000000),數據庫查詢等


注意事項Unity3D工程師:如果你看看IReadOnlyList Interface documentation‌的最底部,它從.Net 4.5開始可用。在.Net的早期版本中,您必須求助於IList<T>(自2.0起可用)。 Unity在.NET版本上的表現遠遠落後。 2016年Unity只使用.Net 2.0.5。因此對於Unity3D,您必須使用IList<T>

+0

似乎**非常敏感** - 這個問題似乎已成爲頂級專家之間的微妙爭論! :)我甚至不知道數組是什麼:-) – Fattie

+0

數組就是一切:)'IEnumerable','ICollection','IList','IEnumerable ','ICollection ','IList ',' 'IReadOnlyCollection ','IReadOnlyList ' –

+0

如果我沒有弄錯,這似乎是所有專家的**共識首選答案**?我對嗎? (你們都是**這樣的專家**這對我來說並不是那麼容易**真正遵循這裏的論點的細節**) – Fattie

3

T[]List<T>都共享相同的接口:IEnumerable<T>

IEnumerable<T>但是,沒有長度或計數成員,但有一個擴展方法Count()。也沒有序列的索引器,所以你必須使用ElementAt(int)擴展方法。

沿東西線:

public static T AnyOne<T>(this IEnumerable<T> source) 
{ 
    int endExclusive = source.Count(); 
    int randomIndex = Random.Range(0, endExclusive); 
    return source.ElementAt(randomIndex); 
} 
+0

Upvote用於很好的解釋,並且不使用無意義的變量名像OP一樣。 – ataravati

+0

嗨ataravati,看到像你這樣完全不識字的人,總是讓我難過:)「ra」顯然意味着「陣列」,這可能是編程中最有名的笑話或有趣的名字。 – Fattie

+0

@JoeBlow,我知道。 「k」也表示計數,「r」表示隨機。 – ataravati

7

T[]List<T>實際上都實現IList<T>,它提供枚舉,一個Count屬性和一個索引。

public static T AnyOne<T>(this IList<T> ra) 
{ 
    int k = ra.Count; 
    int r = Random.Range(0,k); 
    return ra[r]; 
} 

剛一說明:爲Unity3D環境而言,這是完全正確的答案。關於這個答案的進一步改進,IReadOnlyList<T>,它在Unity3D中不可用。 (關於IEnumerable<T>的(巧妙)擴展,甚至覆蓋對象的情況下,沒有countingness /可轉位,當然在遊戲引擎的情況,這將是一個不同的概念(如AnyOneEvenInefficientlyAnyOneEvenFromUnsafeGroups)。)

+1

是的,讓我想知道爲什麼。執行「IList 」的數組違反了Liskov替換原則。 –

+0

@YannickMotton好點! – Christos

+0

是的,雖然'T []'爲'IsReadOnly'返回true。然而,讀/寫接口應該是分開的,因爲我確信財產很少很少被防範。 –

0

你可以改變你定義了一下:

public static T AnyOne<T>(this IEnumerable<T> ra) 
{ 
    if(ra==null) 
     throw new ArgumentNullException("ra"); 

    int k = ra.Count(); 
    int r = Random.Range(0,k); 
    return ra.ElementAt(r-1); 
} 

現在,定義爲所有實現IEnumerable<T>接口類型的擴展方法。

+0

'IEnumerable ','IList '沒有任何索引,但是... –

+0

我覺得'ElementAt'完全不會這樣嗎? – Christos

+0

當時我寫我的評論,你已經從OP複製索引器;-) –

4

有趣的是,有些人選擇IEnumerable<T>,而其他一些人堅持IReadOnlyList<T>

現在說實話。 IEnumerable<T>是有用的,非常有用。在大多數情況下,你只是想把這個方法放在某個庫中,然後把你的效用函數放到你認爲是一個集合的地方,然後用它來完成。但是,使用IEnumerable<T>正確是有點棘手,因爲在這裏我要指出...

IEnumerable的

讓我們的第二個假設op是使用LINQ,並希望從中獲取隨機元素一個序列。基本上,他從@Yannick代碼結束,在實用的輔助函數庫結束:

public static T AnyOne<T>(this IEnumerable<T> source) 
{ 
    int endExclusive = source.Count(); // #1 
    int randomIndex = Random.Range(0, endExclusive); 
    return source.ElementAt(randomIndex); // #2 
} 

現在,這主要做的是兩兩件事:

  1. 計數元素的數量在來源中。如果源是簡單的IEnumerable<T>這意味着要經歷列表中的所有元素,如果它是f.ex.一個List<T>,它將使用Count屬性。
  2. 重置枚舉,轉到元素randomIndex,抓住並返回它。

這裏有兩件事可能會出錯。首先,你的IEnumerable可能是一個緩慢的順序存儲,而做Count會以一種意想不到的方式破壞應用程序的性能。例如,從設備流式傳輸可能會讓您陷入麻煩。也就是說,你可能會認爲,當這是該系列的特徵所固有的時候 - 而且我個人認爲這種說法會持續下去。

其次 - 這也許更重要 - 不能保證你枚舉將在每次迭代中返回相同的序列(因此也不能保證你的代碼不會崩潰)。例如,考慮這個無辜的看着一段代碼,可能用於測試目的是有用的:

IEnumerable<int> GenerateRandomDataset() 
{ 
    Random rnd = new Random(); 
    int count = rnd.Next(10, 100); // randomize number of elements 
    for (int i=0; i<count; ++i) 
    { 
     yield return new rnd.Next(0, 1000000); // randomize result 
    } 
} 

第一次迭代(呼叫Count()),你可能會產生99個結果。你選擇元素98.接下來你調用ElementAt,第二次迭代產生12個結果,你的應用程序崩潰。不酷。

修復了IEnumerable實現

正如我們所看到的,IEnumerable<T>執行的問題是,你必須要經過數據的2倍。我們可以通過一次性查看數據來解決這個問題。

這裏的'技巧'其實很簡單:如果我們看到1個元素,我們肯定想要考慮返回它。考慮到所有元素,這是我們要返回的元素的50%/ 50%的機率。如果我們看到第三個因素,那麼我們會有33%/ 33%/ 33%的機會返回。等等。

因此,更好的實現可能是這樣:

public static T AnyOne<T>(this IEnumerable<T> source) 
{ 
    Random rnd = new Random(); 
    double count = 1; 
    T result = default(T); 
    foreach (var element in source) 
    { 
     if (rnd.NextDouble() <= (1.0/count)) 
     { 
      result = element; 
     } 
     ++count; 
    } 
    return result; 
} 

在一個側面說明:如果我們使用LINQ,我們希望操作使用IEnumerable<T>一次(也是唯一一次!)。現在你知道爲什麼了。

使其與列表和數組

雖然這是一個巧妙的技巧,我們的表現,現在會比較慢,如果我們在一個List<T>,這沒有任何意義的工作,因爲我們知道有很多工作由於索引和Count可用於我們的財產更好的實施可用。

我們正在尋找的是的公分母這個更好的解決方案,它被用於儘可能多的收藏,我們可以找到。我們最終得到的是接口,它實現了我們需要的一切。

因爲我們知道IReadOnlyList<T>是真實的特性,我們現在可以安全地使用Count和索引,而不運行崩潰的應用程序的風險。

但是,雖然IReadOnlyList<T>似乎有吸引力,IList<T>由於某種原因似乎並沒有實現它......這基本上意味着IReadOnlyList<T>是一個實踐中的賭博。在這方面,我很肯定有比IReadOnlyList<T>實現有更多的IList<T>實現。因此,似乎最好只支持這兩種接口。

這使我們的解決方案在這裏:

public static T AnyOne<T>(this IEnumerable<T> source) 
{ 
    var rnd = new Random(); 
    var list = source as IReadOnlyList<T>; 
    if (list != null) 
    { 
     int index = rnd.Next(0, list.Count); 
     return list[index]; 
    } 

    var list2 = source as IList<T>; 
    if (list2 != null) 
    { 
     int index = rnd.Next(0, list2.Count); 
     return list2[index]; 
    } 
    else 
    { 
     double count = 1; 
     T result = default(T); 
     foreach (var element in source) 
     { 
      if (rnd.NextDouble() <= (1.0/count)) 
      { 
       result = element; 
      } 
      ++count; 
     } 
     return result; 
    } 
} 

PS:對於更復雜的場景中的,檢查出的策略模式。

隨機

@Yannick Motton做,你必須要小心Random此話,因爲如果你這樣調用了很多次的方法也不會是真正隨機的。Random是用RTC初始化的,所以如果你多次創建一個新實例,它不會改變種子。

對此的一種簡單的方法如下:

private static int seed = 12873; // some number or a timestamp. 

// ... 

// initialize random number generator: 
Random rnd = new Random(Interlocked.Increment(ref seed)); 

這樣,每次你打電話的人時,隨機數發生器將接受另一個種子,它會在緊密的循環甚至工作。

總結:

所以,總結一下吧:

  • IEnumerable<T>的應該重複一次,只有一次。否則可能會給用戶帶來意想不到的結果。
  • 如果您可以訪問比簡單枚舉更好的功能,則不需要遍歷所有元素。最好立即抓住正確的結果。
  • 考慮你正在仔細檢查的接口。雖然IReadOnlyList<T>絕對是最好的候選人,但它不會從IList<T>繼承,這意味着它在實踐中效率會降低。

最終結果就是Just Works。

+0

糟糕,錯字......我通常在記事本上寫下這些答案:-)它應該是'count'。 – atlaste

+0

嗯,非常出人意料地,我從來沒有見過「跑步機會」算法 - 謝謝! – Fattie

+0

@JoeBlow它被稱爲[水庫採樣](https://en.wikipedia.org/wiki/Reservoir_sampling):) –