c# - 使用 List.Sort 和 IEnumerable 的算法加速

Question

对于我的项目，我首先从文件中加载图像，然后将每个像素放入 2D pixels[,] 中大批。然后，我想检查每个像素并根据它们的颜色将它们分成“箱子”，然后对每个箱子进行排序。所以我有一个 Bin对象，它封装了一个 List<Pixel> ，我有一个 List<Bin>包含(相对较少)数量的垃圾箱。

我的问题是，当我尝试从非常大的图像(例如 1920x1200 = 230 万像素)填充这些 bin 时，我使用的算法比我想要的要慢，我已经找到了问题所在某些特定于 C# 语言的功能，这些功能似乎比我预期的要花费更长的时间。我想要一些关于如何更好地使用 C# 来消除这些瓶颈的建议。

加载图像后，我调用一个名为“fillBinsFromSource”的函数，它获取一个可枚举的像素列表，找到它们属于哪个 bin，并将它们放在那里:

public void fillBinsFromSource(IEnumerable<Pixel> source)
    {
        Stopwatch s = new Stopwatch();
        foreach (Pixel p in source)
        {
            s.Start();
            // algorithm removed for brevity
            // involves a binary search of all Bins and a List.Add call
            s.Stop();
        }           
    }

对于大图像，预计我的算法会花费一些时间，但是当我在函数调用之外放置一个秒表时，事实证明它花费的时间大约是 s 上累积时间的两倍。 ，这意味着使用 foreach 进行枚举占用了此函数一半的时间(1920x1200 图像的 1.6 秒中大约有 800 毫秒)。

我需要传递可枚举列表的原因是因为有时用户只会添加图片的一小部分区域，而不是整张图片。耗时的调用向下传递几个迭代器，首先从图像列表，然后从列表中的每个图像，像这样(简化):

class ImageList : IEnumerable<Pixel>
{
    private List<Image> imageList;
    public IEnumerator<Pixel> GetEnumerator()
    {
        foreach (Image i in imageList)
            foreach (Pixel p in i)
                yield return p;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    } 

class Image : IEnumerable<Pixel>
{
    private Pixel[,] pixels; // all pixels in the image        
    private List<Pixel> selectedPixels;// all pixels in the user's selection

    public IEnumerator<Pixel> GetEnumerator()
    {
        if (selectedPixels == null)
            for (int i = 0; i < image.Width; i++)
                for (int j = 0; j < image.Height; j++)
                    yield return pixels[i, j];
        else
            for (int i = 0; i < selectedPixels.Count; i++)
                yield return selectedPixels[i];
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

最后我称之为

ImageList list; // pretend it contains only 1 image, and it's large
fillBinsFromSource(list);

问题 1) 由于需要枚举二维像素阵列和选定区域，具体取决于用户的选择，枚举速度非常慢。我怎样才能加快速度？

然后，在用 Pixel 填充所有这些容器之后对象，我对它们进行排序。我调用List<Pixel>.Sort()并依靠IComparable ，像这样:

ImageList list; // pretend it contains only 1 image, and it's large
fillBinsFromSource(list);
foreach(Bin b in allBins)
    b.Sort(); // calls List<Pixel>.Sort()


class Pixel : IComparable
{
    // store both HSV and RGB
    float h, s, v;
    byte r, g, b;

    // we sort by HSV's value property
    public int CompareTo(object obj)
    {
        // this is much faster than calling CompareTo on a float
        Pixel rhs = obj as Pixel;
        if (v < rhs.v)
            return -1;
        else if (v > rhs.v)
            return 1;
        return 0;
    }

问题2)假设allBins有 7 个元素；排序 7 个单独的列表，总共有 230 万 Pixel s 在他们身上大约需要 2 秒。对 230 万个随机列表进行排序 int s 不到 200 毫秒。我可以理解使用原始类型有一定程度的加速，但使用 IComparable 真的慢 10 倍以上吗？ ？这里有任何加速吗？

对于这么长的问题，我深表歉意，如果有人对我有任何建议，我将不胜感激!

Answer 1

您确实需要分析您的代码，看看哪里慢了。

最明显的:

• Pixel不实现通用 IComparable<Pixel>结果，Compare 不得不做更多的工作。
• 尝试制作像素值类型。您很可能会看到性能下降，但也可能不会。
• 考虑传递二维范围(矩形)并访问 Pixel如果您发现性能低于您认为可以接受的水平，则直接通过索引而不是迭代器访问对象。迭代器很好，但不是免费的。