Slow edges implementation

[chanlenn]

Hi. I'm pretty new to this Eigen library and I implemented edges, but it uses nested loops and takes around 30 seconds to complete. I compared it to the igl implementation and that takes less than a second. I heard in tutorial that you won't be marking us on runtime, except if it's too slow.

Is this slow implementation okay or am I in the wrong track? Are there any tips or hints on how to implement this faster? Are matrix operations the way to do it?

[otmanon]

Yeah i'd like an answer to this too. Specifically my code can take like 45 secs running in debug but less than 5 in release

[chanlenn]

After researching Eigen and IGL more, I was able to make a fast implementation. I think the question still needs to be answered for other people though.

[alecjacobson]

Aim for the correct asymptotic runtime performance. Determining what the correct asymptotic runtime performance is is implicitly part of the assignment.

[cuppajoeman]

I was also thinking about this. If we naively just check if an edge we want to add is already in the matrix by iterating until we do (or don't) find it, I think the runtime would be O(n^2) (which doesn't seem good, n being the number of edges). Are we suppose to use a hash table or something like that to lower the cost of checking if an edge is already in the matrix?

[rikingurditta]

There are tradeoffs between time and space too though. My current implementation could be made asymptotically faster if I required it to use asymptotically greater space. Should I prioritize time over space?

[cuppajoeman]

There is a property about the edges so that you don't have to use different data structures and it runs quickly. (If you find it, I don't think you have to check for the edge through the matrix anymore)