轻松的脑力劳动者,更好的算法

Question

这是在社区大学.我失败了,但想知道答案.

问题是这样的:你有一个代表图像的2D结构阵列.每个结构都有一个红色,绿色,蓝色和alpha值.可以有更多信息,但不是解决问题所必需的.

假设图像是4000x4000或1600万个元素.每个角落都需要更新/检查每个元素.

对于您需要的每个元素:

• 如果<50或将设置为205> 205,则将红色字节设置为50
• 使用rand()将绿色字节设置为0到255之间的随机值
• 以"有趣"的方式修改蓝色.

"你不能蛮力,以更聪明的方式思考;你需要一个更好的算法"

我基本上做了一个循环.我是最快的,但他说这是"关于找到一个更好的算法,而不是使用可爱的编译器和指针技巧".

还需要在纯C中.没有OpenMP/Threads或OpenGL着色,OpenCL等......只有带有标准库的ANSI C(甚至禁止使用GNU/POSIX库).

我询问了按位操作,他说"那些在C [??]中非常昂贵,它是关于编写一个快速而可靠的算法,而不是你不断提出的这些可爱的技巧".

那有什么提示吗？

Answer 1

是的,让我们都弄清楚如何写一个算法"以'有趣'的方式修改蓝色.",只要它"快速而坚实".很高兴的社区学院教学如此强大.我从来没有听说过按位操作很贵.比较贵的什么？当你说你是"最快的"时,你的意思是你是第一个提出答案的人,或者你的答案是最有效的实施方式吗？如果你被迫将数据存储为结构的2D数组(而不是树),我不确定你还能做些什么.所以你知道你失败了,但没有被告知正确的答案？现在这就是我所说的edjumacation!

Answer 2

的rand()通话将最有可能称霸程序的运行,所以在试图将智能与智能环结构或花哨的位运算是没有意义的.

因此,最有效的优化可能实际上是将每个值从rand拆分为字节(取决于rand实现),以减少调用.

至于老师真正想要的是什么,这是一个疯狂的猜测:

1. 使用rand设置绿色字节
2. 使用一些奇特的方法来设置红色字节
3. 在您喜欢的方法中的某处包含蓝色字节,因此它获得一个新值作为方便的副作用
4. 最终得到一个神秘而毫无意义的单行(因为他认为程序越少,行必须越快)

Answer 3

解决方案1

更新大数组时最重要的一点是通过使用局部性来利用内存层次结构。这隐藏了内存延迟，从而加速了算法。

首先，您想要一起处理每个像素的颜色，因为它们位于同一结构中。像素的处理完全适合现代 CPU 的寄存器组。根据实际存储，此处可以进行一些位/字节/字调整，但听起来您的讲师并没有强调这一点。

其次，您希望按照像素存储在内存中的顺序更新像素。这意味着在内部循环中循环内部数组维度。这使得编译器和 CPU 能够有效地访问大块中的像素（关键字缓存行和预取）。

解决方案2

一种完全不同的方法是添加一个间接层。

不要直接访问图像数组，而是通过访问器函数路由所有访问。现在，您可以编写访问器函数来实现对图像所需的更改，而无需访问数组，甚至根本不需要循环所有像素！

这就像面向对象语言中的装饰器模式。