C#泛型,涵盖数组和列表?

24

这里有一个非常实用的扩展,它适用于任何类型的数组

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];
}

事实上,是否有一种方法可以将泛型概括为同时涵盖 arrayList<>?还是不可能做到?
答案是否甚至可以包括Collection
PS,我很抱歉没有明确提到这是在Unity3D环境中。例如,“Random.Range”只是Unity调用(执行显而易见的操作),而“AnyOne”则是游戏编程中完全典型的扩展或调用。
显然,这个问题当然适用于任何C#环境。
6个回答

20
事实上,对于您的情况,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)、数据库查询等。

2020年,对于Unity3D程序员来说,.Net的现代版本当然已经可以在Unity中使用了!

enter image description here


1
@JoeBlow 是的...不仅仅是针对Unity3D....这是因为IList<T>没有实现IReadOnlyList<T>。可能是因为你可以有一个只能写而不能读的列表。这就是为什么我添加的答案包括了两种情况。对于自定义列表,你可能会遇到同样的麻烦;不幸的是,比起IReadOnlyListIList有更多的实现。 - atlaste
@IvanStoev 嗯...事实上,Linq的设计核心是假定枚举器只被使用一次或者是确定性的。但是现实很残酷,接口并不能保证这些。在这种情况下,这意味着“错误”。换句话说:如果你需要两者,IEnumerable<T>是错误的。然而,问题是实现者是否在实现阶段考虑了这些隐含的约束条件。我认为这不现实;个人认为这是Linq中一个严重的设计缺陷,我见过很多真实的bug就是因为这个原因发生的。 - atlaste
@IvanStoev 所以,一切条件相等的情况下,我认为我们可以合理地假设AnyOne是一个实用函数,这意味着适当的设计将归结为“可重用性”。考虑到这一点,对于这种情况,IEnumerable<T>听起来是一个相当合理的设计要求,即使我们同意它在某些方面有缺陷。如果实现细节然后需要Count和索引器,则仅意味着我们必须强制执行它。这可能听起来出乎意料,但实际上已经有很多Linq函数这样做了(例如OrderBy)。 - atlaste
2
@JoeBlow 如果你看一下IReadOnlyList<T>接口文档的最底部,你会看到类似于**.NET Framework** 自4.5版本起可用 :( 所以在早期版本中,你必须使用IList<T> (自2.0版本起可用) - Ivan Stoev
1
欢迎,乔。很高兴能参与这场有趣的讨论。 - Ivan Stoev
显示剩余4条评论

13

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的正确且唯一的解决方案,因为在早期现代的.NET框架在Unity中不可用。


1
是啊,我也在想为什么会这样。实现 IList<T> 的数组违反了 Liskov 替换原则。 - Yannick Motton
2
@Joe,在这里使用IReadOnlyList实际上是更好的选择,因为它不允许写操作(比如Add),而提问者的代码并不需要这样的操作。 - Richard Szalay
1
“当你还需要计数和索引器时,就不能使用IReadOnlyCollection了。” 当然,你需要选择具有这些概念的抽象级别——因此也许IReadOnlyList是最好的选择? - Fattie
1
撇开无意义的讨论,@RichardSzalay 你能否将索引器访问更改为 ra[r]?目前情况是,如果 Random 产生了一个 0,这段代码将会引发 IndexOutOfRangeException - Yannick Motton
1
兄弟们,我大胆决定在这里放置代币赏金。原因有两个:(1)R.S.首先通过IList揭开了这个长期困扰人们的难题,而IReadOnlyList的(杰出)改进也是由于这个答案而来。此外,(2)对于十亿的游戏程序员在谷歌搜索时(这是使用C#编写组件时最流行的扩展想法),这确实是“答案”,所以这是一件好事。我感谢每一个人。 - Fattie
显示剩余11条评论

6
有趣的是,一些人选择使用 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>,这意味着要遍历列表中的所有元素;如果源是一个类似于 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>实现的问题在于您必须两次遍历数据。 我们可以通过一次遍历数据来解决这个问题。
“技巧”其实很简单:如果我们已经看到了一个元素,我们肯定希望考虑返回它。 考虑到所有元素,有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> 接口。

由于我们知道 IReadOnlyList<T> 的属性为真,因此我们现在可以安全地使用索引和 Count,而不会冒着崩溃应用程序的风险。

但是,虽然 IReadOnlyList<T> 看起来很吸引人,但由于某种原因,IList<T> 似乎没有实现它...这基本上意味着在实践中,IReadOnlyList<T> 有点冒险。在这方面,我相信有很多 IList<T> 实现,而不是 IReadOnlyList<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;
    }
}

注意:对于更复杂的情况,请查看策略模式。

随机数

@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));

这样一来,每次调用 AnyOne 函数时,随机数生成器都会接收到另一个种子,并且即使在紧密的循环中也能正常工作。
总结:
因此,需要逐个迭代 IEnumerable,不要重复迭代。否则,用户可能会得到意外的结果。
如果您拥有比简单枚举更好的功能,则无需遍历所有元素。最好立即获取正确的结果。
非常仔细地考虑您正在检查的接口。虽然 IReadOnlyList 明显是最佳选择,但它没有从 IList 继承,这意味着在实践中效果会较差。
最终结果是完美运行。

Ivan做得不错,谢谢。(顺便说一下,那个维基页面真的糟糕!) - Fattie
2
@IvanStoev 哈哈 :) 说实话,我觉得给这些琐碎的算法命名很傻,我通常都是边做边想出来的... - atlaste
我觉得这个答案非常出色地解释了如何使用IEnumerable,如果确实想要“覆盖”所有的IEnumerable。太棒了。 - Fattie
@atlaste 一个需要考虑的问题是,在调用中新建 Random 对象可能会在紧密循环中产生相同的结果,因为 Random 的默认构造函数以当前机器 tick 作为种子,相同 tick 会得到相同的随机序列。使用 StaticRandom 可能是个不错的主意:请查看 http://www.yoda.arachsys.com/csharp/miscutil/usage/staticrandom.html。 - Yannick Motton
@atlaste 我的观点是,在经常调用的实用方法中新建一个Random实例在随机性方面并不是一个好主意。我确实同意,完全锁定的 Random 实例不是必需的,只要该实例不被多个线程重用即可。然而,以你呈现的方式,我认为你会将其从用于Random实例的工厂方法中运行,这会使其具有与完全锁定的 Random 实现大致相同的性能。至少在 StaticRandom 实现中,您可以将其设置为ThreadStatic并避免所有锁定。 - Yannick Motton
显示剩余6条评论

3

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

然而,IEnumerable<T>没有Length或Count成员,但有一个扩展方法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);
}

点赞好的解释,也不要像楼主一样使用无意义的变量名。 - ataravati
嗨ataravati,看到像你这样完全文盲的人总是让我感到悲伤 :) “ra”显然意味着“数组”,这可能是编程中最著名的笑话或有趣的名称之一。 - Fattie
@JoeBlow,我知道。“k”也表示计数,“r”表示随机。 - ataravati
Yan,你似乎通过IEnumerable揭示了问题的核心,但是你现在是否认同共识,即在实际代码中使用'IReadOnlyList<T>是最好的方法?抱歉,我很难理解这里的微妙之处。 - Fattie

2
答案是使用原始代码!
这应该是StackOverflow上唯一一个问题,其中问题本身展示了比任何提供的答案都更好的代码。所有建议的答案都鼓励使用接口,这将意味着显着的性能损失。不要在生产代码中使用那些解决方案!
考虑到问题标记为unity3d,很明显代码将成为游戏的一部分。在游戏中,你最不想看到的就是由于垃圾收集而引起的间歇性卡顿。通常,在Unity中,你希望枚举器具有极高的性能表现。这就带我来到了答案本身:
不要使用枚举的接口
除非你真的需要。List和T[]类型具有高度优化的值类型枚举器。一旦将类型转换为接口,就会恢复到未经优化的引用类型版本。每次调用未经优化的GetEnumerator()版本都会产生垃圾,累加到稍后发生的卡顿(相信我),当垃圾收集器收集这些分配的对象时。
  • 优化过的 List<T>.GetEnumerator() 版本 在这里
  • 未经优化的 IEnumerable<T>.GetEnumerator() 版本 在这里

详情请见 我的 其他回答


答案是使用原始代码。这个“答案”是回答哪个问题的?显然不是OP,他希望将该代码泛化为除数组以外的容器类型。其次,通用答案使用了2个简单的虚拟属性——Countthis(索引器),因此不会“导致显著的性能损失”。最后,在这个问题中根本没有涉及枚举,因此“答案本身”,虽然在一般情况下是正确的,但却回答了这里没有提出的问题。 - Ivan Stoev
@IvanStoev,虽然你提到的观点在“这个QA”方面很重要,但是我认为这个基本信息非常有价值:一旦你将类型转换为接口,你就会回到非优化的引用类型版本 - Fattie

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> 接口的类型定义了扩展方法。


我认为 ElementAt 正好做到了这一点,不是吗? - Christos
在我写评论的时候,你已经从 OP 复制了索引器;-) - Yannick Motton

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接