Easy brain stumper, a better algorithm [closed]

Question

This was at a community college. I failed it, but want to know the answer.

The problem is this: you have an 2D array of structs that represents an image. Each struct has a red, green, blue, and alpha value. There can be more info, but not required to solve the problem.

Say the image is 4000x4000 or 16 Million elements. Every element needs to be updated/checked on every turn.

For each element you need to:

• Set the red byte to 50 if < 50 or set to 205 > 205
• Set the green byte to a random value between 0 and 255 using rand()
• Modify blue in an "interesting" way.

"You can't brute force this, think in a smarter way; you need a better algorithm"

I basically did a loop. I was the fastest but he said it was "about finding a better algorithm, not using using cute compiler and pointer tricks".

Also needs to be in pure C. No OpenMP/Threads or OpenGL shading, OpenCL, etc... just ANSI C with standard libraries (even GNU/POSIX libraries were forbidden).

I asked about bitwise operations and he said that "those are very expensive in C [??] and it's about writing a fast and solid algorithm, not these cute tricks you keep coming up with".

So any hints?

Answer 1

Yes, let's all figure out how to write an alogirithm to "Modify blue in an 'interesting' way.", as long as it's "fast and solid". Glad community colleges are teaching so strong. I've never heard that bitwise operations are expensive. Expensive compared to what? When you say that you were "the fastest", do you mean that you were the first to come up with an answer, or that your answer was the most efficient implementation? If you're forced to store the data as a 2D array of structs (as opposed to a tree), I'm not sure what else you can expect to do. So you know that you failed it, but were not told the correct answer? Now that's what I call edjumacation!

Answer 2

The rand() calls will most likely dominate the runtime of the program, so there is no point in trying to be smart with a smart loop structure or fancy bitwise operations.

So it is likely that the most effective optimization would actualy be spliting each value from rand into bytes (depends on rand implementation), to do less calls.

---

As for what the teacher actually wanted, here is a wild guess:

1. Use rand to set the green byte
2. Use some fancy method to set the red byte
3. Include the blue byte somewhere in your fancy method, so it gets a new value as a convenient side effect
4. End up with a cryptic and pointless one-liner (because he thinks the less lines a program has the faster is must run)

Answer 3

Solution 1

The single most important point in updating a big array is exploiting the memory hierarchy by using locality. This hides memory latency and thus accelerates you algorithm.

First, you want to process the colors of each pixel together as they lie in the same struct. The processing of a pixel fits entirely in the register set of modern CPUs. Depending on the actual storage some bit/byte/word tweaking is possible here but it sounds like your instructor doesn't place emphasis on this point.

Second, you want to update the pixels in the order they are stored in memory. This means looping over the inner array dimension in the inner loop. This enables the compiler and the CPU to access the pixels efficiently in big chunks (keywords cache-lines and prefetching).

Solution 2

A completely different approach is adding a layer of indirection.

Instead of accessing the image array directly, route all accesses through accessor functions. Now you can write accessor functions that implement the required changes to the image without needing to access the array or even loop over all pixels at all!

This is like the Decorator pattern in an object-oriented language.

Answer 4

This looks like an interview question. It's silly! If you have to visit each pixel, then you have to use loops! After all, this is their purpose. The best thing you can do is doing a single loop instead of two and edit more pixels on every iteration