6

对于我的项目，我首先从文件中加载图像，并将每个像素放入二维pixels[,]数组中。然后，我想检查每个像素并根据它们的颜色将它们分成“箱”，然后对每个箱进行排序。所以我有一个Bin对象，它封装了 a 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();
        }           
    }

对于大图像，预计我的算法会花费一些时间，但是当我在函数调用之外放置一个 Stopwatch 时，结果发现它需要的时间大约是 accrued on 的两倍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 万个Pixels 大约需要 2 秒。对一个包含 230 万个随机ints 的列表进行排序需要不到 200 毫秒。我可以理解使用原始类型有一定程度的加速，但是使用起来真的慢了 10 倍以上IComparable吗？这里有什么加速吗？

我为这个冗长的问题道歉，如果有人对我有任何建议，我将不胜感激！

4

3 回答 3

3

你真的需要分析你的代码，看看什么是慢的。

最明显的：

  • Pixel没有实现泛型IComparable<Pixel>，因此比较不得不做更多的工作。
  • 尝试制作像素值类型。您很可能会看到性能下降，但可能不会。
  • Pixel如果您发现性能低于您认为可以接受的水平，请考虑传递二维范围（矩形）并直接通过索引而不是迭代器访问对象。迭代器很好，但不是免费的。
于 2012-11-30T22:57:23.887 回答
2

如果您想要原始金属性能，那么各种间接方式，例如访问者模式或虚拟继承，都是毒药。虚拟调用、分配、不可预知的分支对算法有很大的损害，这种算法有一个小而紧的内部循环，99.99% 的时间都花在了这个循环上。

为什么？因为 CPU 喜欢并行执行许多（数十条）指令。只有当它可以在指令流中窥视时，它才能做到这一点。上述事情阻止了这一点。

你真的需要把最里面的循环弄对。不要在那里分配，不要调用虚函数（或接口方法或委托）。

可能，您最里面的循环应该使用硬编码内核处理给定图像的矩形。不是按像素实现处理功能，而是按矩形实现。

相反，您如何提供图像流并不重要。随心所欲地使用 LINQ。这是一种低容量操作，因为每张图像有数百万像素。

于 2012-11-30T23:48:53.337 回答
1

您可以使用访问者模式，而不是使用迭代器，甚至构建一个数组/像素列表。表示任意选择的图像、图像列表和其他对象都可以使用单个方法接受访问者类，VisitPixel并为对象表示的每个像素调用该方法。然后，访问者类将负责在访问所有像素时对它们进行分箱。

这可能消除将所有像素提取到单独数组中的需要。它还可能消除创建迭代器以支持简单for循环。

Alexei Levenkov 关于你的第二个问题有一些好的观点。使用Sort 带有IComparer<T>. _

于 2012-11-30T23:23:05.103 回答