On Wed, Dec 31, 2008 at 4:32 AM, Andrei Alexandrescu <[email protected]> wrote: > Don wrote: >> >> Andrei Alexandrescu wrote: >>> >>> Don wrote: >>>> >>>> Christopher Wright wrote: >>>>> >>>>> Don wrote: >>>>>> >>>>>> The creation of temporaries during expressions is something I'm >>>>>> currently working on solving. The case you mentioned is addressed by a >>>>>> proposal I made long ago: >>>>> >>>>> The easiest way is to add an intermediate struct. This takes a fair bit >>>>> of manual effort, though, and prevents you from using auto. >>>> >>>> That particular case is the easiest possible one. The case x = y - x, >>>> for example, is much more difficult to recognize. >>>> >>>>> >>>>> Essentially, you need a struct MyClassAddition that just records >>>>> operands. Then give it an implicit cast to MyClass that does the work. >>>>> This >>>>> is an ugly solution because you need to duplicate the operator overloads >>>>> on >>>>> MyClassXXX as well as MyClass. >>>>> >>>>> I believe I got this solution from an article by Andrei. It should work >>>>> pretty well for classes that define few overloads. >>>> >>>> I'm talking about a language solution. I want to solve this for the >>>> general case. >>> >>> Don't forget that the case you are solving is not general enough because >>> you are focusing on eliminating temporaries, which is only part of the >>> story. I suggest you make place in your thoughts for loop fusion. >> >> Yes. That's the classic problem for matrices, but I'm still trying to work >> out if it is really a general problem. I was hoping to see some new use >> cases, but none so far. > > I think the matrices case is important enough to make it its own class of > problems. For example, bitmap processing is another instance of matrix > usefulness, just one that doesn't usually jump to mind when thinking of > matrices.
Graph algorithms can often be thought of as matrices too. I recall some shortest path algorithms where you write edge weight between node i & j in the i,j entry. Then you do a multiply on the matrices, but instead of using the regular vector inner product for each <row, column>, you use max(). I forget which algo it is. I'm thinking Floyd-Warshall. Also there was some algorithm I recall that can be done with a boolean matrix. Probably some kind of connected components algo? --bb
