2015-11-26 59 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):) –