7 Replies - 1264 Views - Last Post: 24 March 2017 - 08:40 AM

#1 uniqCoder  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 67
  • Joined: 13-March 16

diagonal elements in a matrix - challenge - not a h/w

Posted 16 October 2016 - 11:27 AM

This is a very beginner level question.

Just print the diagonal elements in a given matrix....but it should be the best efficient one.

I was doing it in a very inefficient way until I got an instinct to do it better.

Just post your solutions but don't see the answer before trying.

Spoiler



And admin..the point is that I know the answer...

I have the wisdom that I don't want to steal from anyone.

Is This A Good Question/Topic? 0
  • +

Replies To: diagonal elements in a matrix - challenge - not a h/w

#2 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12189
  • View blog
  • Posts: 45,251
  • Joined: 27-December 08

Re: diagonal elements in a matrix - challenge - not a h/w

Posted 16 October 2016 - 11:36 AM

The solution is really obvious. I don't see the point for discussion here. There aren't other approaches to this, besides the obvious one and the inefficient one.
Was This Post Helpful? 0
  • +
  • -

#3 uniqCoder  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 67
  • Joined: 13-March 16

Re: diagonal elements in a matrix - challenge - not a h/w

Posted 16 October 2016 - 11:40 AM

Ok...I see so many experts here...this was meant to be a.beginner level problem

I havehave to lean more.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5929
  • View blog
  • Posts: 20,272
  • Joined: 05-May 12

Re: diagonal elements in a matrix - challenge - not a h/w

Posted 16 October 2016 - 01:46 PM

Assuming a contiguous two dimensional square matrix in C or C++, there is actually something more efficient. It'll have the same O(n) complexity, but the cost of each iteration involves simple addition rather than the usual multiplication and addition done when doing two dimensional indexing, or the indirection and offsetting that a na´ve compiler may implement.
Was This Post Helpful? 1
  • +
  • -

#5 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5929
  • View blog
  • Posts: 20,272
  • Joined: 05-May 12

Re: diagonal elements in a matrix - challenge - not a h/w

Posted 18 October 2016 - 05:40 AM

LOL! This is going to abuse hashtables, but if you set things up just right, you could have all the elements on the diagonal to all hash to the same key. Since people claim that hashtables have amortized/average O(1) access even if they use chaining, you could claim that you are getting O(1) to list N elements.

Other people will say: "But wait! That's apples and oranges!" Unfortunately, the going wisdom is that hashtables are treated as O(1) even if they use chaining or probing because when they compute the complexity of hashtables they only look at the average case, while looking at the complexity of everything else, they look at the worse case.
Was This Post Helpful? 0
  • +
  • -

#6 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1852
  • View blog
  • Posts: 6,664
  • Joined: 19-February 09

Re: diagonal elements in a matrix - challenge - not a h/w

Posted 20 October 2016 - 08:42 PM

uniqCoder your discovery is to be admired. The efficiency has increased in the use of flops as well as in code input. Don't let the gigantic boots of jaded grandee Dics, who have forgotten or disregard the joie de codage of earlier years, squash your delight. :P

Little Jack Horner
Sat in the corner,
Programming the value of pi;
He put in his num,
And pulled out a sum,
And said 'What a good coder am I!'

Was This Post Helpful? 0
  • +
  • -

#7 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1270
  • View blog
  • Posts: 4,997
  • Joined: 09-June 09

Re: diagonal elements in a matrix - challenge - not a h/w

Posted 08 November 2016 - 06:36 PM

Like skydiver mentioned, you could avoid the 2D array indexing overhead by using a 1D array. This would effectively save N multiplications.

int index = 0;
for(int i=0; i < N; ++i) {
   std::cout<<matrix[index];
   index += N + 1;
}



The memory reads are also non-coalesced accesses since you are on a diagonal. There may be some optimization in that department, but that would involve restructuring the matrix.
Was This Post Helpful? 1
  • +
  • -

#8 IngeniousHax  Icon User is offline

  • |>|20-514<|{3|2

Reputation: 84
  • View blog
  • Posts: 1,385
  • Joined: 28-March 09

Re: diagonal elements in a matrix - challenge - not a h/w

Posted 24 March 2017 - 08:40 AM

You can also use pointer arithmetic to accomplish this. Although a bit more difficult to read...
    for(int i = 0; i < HEIGHT; i++)
    {
        printf("%d\n", *(*(matrix + i) + i));
    }


This post has been edited by IngeniousHax: 24 March 2017 - 08:41 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1