Optimize Challenge #1 - Find Curves (connected edges)

thomthom

I'll be trying out an experiment to see if we can all learn from each other the various tricks and methods we've all learned independently.
If it turns out to be of value I'll to to make regular challenges like this. (Please suggest new challenges.)

The goal is to see the various ways a problem can be resolved and how it can be done in the most efficient manner and with easily readable code.

Challenge #1
Finding curves
Given a set of entities, find all sets of connected edges, and return an array of each set sorted from start to end.
("Curve" here is a set of edges, not Sketchup::Curve objects. Edges connected to faces should be ignored.)

Results from this should be:

<span class="syntaxdefault"><br /></span><span class="syntaxkeyword">[<br /></span><span class="syntaxdefault">  </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">sorted_edges</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxcomment"># (Curve1)<br /></span><span class="syntaxdefault">  </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">sorted_edges</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxcomment"># (Curve2)<br /></span><span class="syntaxdefault">  </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">sorted_edges</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxcomment"># (Curve3)<br /></span><span class="syntaxdefault">  </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">sorted_edges</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxcomment"># (Curve4)<br /></span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault"> </span>

Use the attached model to benchmark your solution.

Post back:

the time it took to find all curves
the code

(Please make your test code colourize the curves afterwards to visually inspect correct results. No not include the colouring in your benchmark time.)

22099 Edges

thomthom

My current solution:

TT_Find_Curves.run === Find Curves === Method: TT_Find_Curves Found 4253 curves in 7.191s

(I must be doing something terribly wrong, as 7 seconds seems all too slow.)

Revision 1

thomthom

Faster solution, using hashes for quick lookups:

` === Find Curves ===

Sorting: 0.306s (11%)
Filter: 0.05s

Method: TT_Find_Curves
Found 4253 curves in 2.62s`

Revision 2