使用List <T> .Sort和IEnumerable进行算法加速

Question

对于我的项目,我首先从文件加载图像,并将每个像素放入2D pixels[,]数组中.然后,我想检查每个像素,并根据它们的着色方式将它们分成"箱",然后对每个箱进行排序.所以我有一个Bin对象,它封装了一个List<Pixel>,我有List<Bin>一个(相对较小)数量的箱子.

我的问题是,当我尝试从非常大的图像(例如1920x1200 = 230万像素)填充这些垃圾箱时,我使用的算法比我想要的慢,并且我已经将问题追溯到一些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)由于需要枚举像素的2D数组和所选区域,因此根据用户选择的内容,枚举非常慢.我怎样才能加快速度呢？

然后,在用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秒,大约需要2秒钟.对230万随机ints的一个列表进行排序需要不到200毫秒.我可以理解使用原始类型有一定程度的加速,但它真的使用速度慢了10倍IComparable？这里有加速吗？

我为这个长期问题道歉,如果有人对我有任何建议,我会很感激!

Answer 1

您确实需要分析您的代码并查看哪些地方慢。

最明显的是：

• Pixel没有实现通用IComparable<Pixel>，因此 Compare 必须做更多的工作。
• 尝试制作像素值类型。您很可能会看到性能下降，但也可能不会。
• Pixel如果您发现性能低于您认为可接受的范围，请考虑传递 2d 范围（矩形）并直接通过索引而不是迭代器访问对象。迭代器很好，但不是免费的。