j.goor has asked for the wisdom of the Perl Monks concerning the following question:

Hi there,
I cannot find an answer (afaik) here at the Monestery, SO here it is: I am writing a simple "matrix rotation" routine (90 deg. clockwise). I found code that use a hash of arrays.

My Question: Isn't it better/faster to use an array of arrays?

In case of the hash I need to "sort {$a <=> $b} keys %hash" for the outer loop, because the key is a counter, while an array implicitly uses this construction already. Also I need to "$counter++" with the hash-solution, which does not makes is faster...

Rgd,
John

Replies are listed 'Best First'.
Re: Need help on performance question
by BrowserUk (Patriarch) on Feb 21, 2003 at 07:58 UTC

    Hashes are great when you want to do fast lookups of data by key, but for inherently indexed datasets, they make very little sense at all, as they do not preserve order.

    For matrix operations, an AoA makes much more sense. If pure speed is your criteria and each of your rows have the same number of elements (ditto the columns), then using a single dimension array and using math to convert your 2d indices to 1d indices might prove a little quicker.

    Examine what is said, not who speaks.
    1) When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.
    2) The only way of discovering the limits of the possible is to venture a little way past them into the impossible
    3) Any sufficiently advanced technology is indistinguishable from magic.
    Arthur C. Clerk.
[reply]
Re: Need help on performance question
by robartes (Priest) on Feb 21, 2003 at 07:48 UTC
    Whenever you have a question that starts with "isn't it faster to ...", Benchmark should immediately spring to mind. Just test both solutions (and a third: array of arrays, wich is probably the most common way of representing a matrix), and use whichever is faster. Then optimize that one.

    CU
    Robartes-

[reply]
      Performing a good benchmark is hard. It looks simple, but many times I've seen benchmarks posted on perlmonks which were utterly useless, as they weren't testing what they thought they were testings. Furthermore, the vast majority of the people writing a benchmark run the benchmark on a single data set. Noone seems to have a problem coming up with alternative code fragments to test, but to actually vary the size of the data set is much rarer.

      Also, your advice of "Just test both solutions, use whichever is faster, then optimize that one" is just plain wrong. There's no point in benchmarking unoptimized code, and then decide which solution to toss away. Suppose you have algorithms A and B, benchmark them, and find A to be twice as fast as B. Now you toss away B, and optimize A. Suppose after optimization, A runs three times as fast; that is, 6 times as fast as the unoptimized B. But maybe it was possible to optimize B such that it runs 10 times as fast, making it faster than the optimized A. You wouldn't know, you've already (and too early) decided to go for algorithm A.

      You should benchmark *optimized* code. And you should run it with a large range of data set sizes.

      Abigail

[reply]
        Very good point indeed. Benchmarking first, then optimizing the fastest method is indeed the wrong way of doing this. I stand corrected. Abigail-II++.

        CU
        Robartes-

[reply]
Re: Need help on performance question
by schweini (Friar) on Feb 21, 2003 at 08:27 UTC
    depends on what kind of matrices sp? you're talking about, but if the start getting 'interesting', and you want to do some even more interesting stuff with them, someone once pointed me to the whole bunch of PDL modules.
    their code is, AFAIK, made of lovingly handcoded C, so that should give you a decent performance.
    never really looked into the wonders that PDL's supposed to offer, but it sure is on my (AU long) to-do list.
[reply]
Re: Need help on performance question
by thor (Priest) on Feb 21, 2003 at 13:42 UTC
    Might I ask why? I don't remember anything from linear algebra that required you to rotate a matrix by 90 degrees. Unless you're doing "rotation matricies", which, in 2-D are given as: 
    [[cos $theta, -sin $theta]
 [sin $theta,  cos $theta]]

    [download]
    Then again, you may not be doing linear algebra at all, so I might be off my rocker.

    thor

    Update: had the signs of the sines switched. Fixed.

[reply]
[d/l]

Back to Seekers of Perl Wisdom