[Code] Grepping entities

thomthom · 9 Nov 2012, 09:29

Further test - just to see how select scales with multiple entities:

<span class="syntaxdefault"><br />model&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">Sketchup</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_model<br /><br />num_edges&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_entities</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">grep</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">Sketchup</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Edge</span><span class="syntaxkeyword">).</span><span class="syntaxdefault">size<br /><br />puts&nbsp;</span><span class="syntaxstring">"===&nbsp;Select&nbsp;Entities&nbsp;by&nbsp;Type&nbsp;==="<br /></span><span class="syntaxdefault">puts&nbsp;</span><span class="syntaxstring">">&nbsp;#{model.active_entities.length}&nbsp;entities&nbsp;in&nbsp;the&nbsp;active&nbsp;context."<br /></span><span class="syntaxdefault">puts&nbsp;</span><span class="syntaxstring">">&nbsp;#{num_edges}&nbsp;edges&nbsp;in&nbsp;the&nbsp;active&nbsp;context."<br /><br /></span><span class="syntaxdefault">puts&nbsp;</span><span class="syntaxstring">"\n---&nbsp;#select{}&nbsp;---"<br /></span><span class="syntaxdefault">10.times&nbsp;</span><span class="syntaxkeyword">{<br />&nbsp;&nbsp;</span><span class="syntaxdefault">GC</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">start<br />&nbsp;&nbsp;t</span><span class="syntaxkeyword">=</span><span class="syntaxdefault">Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now<br />&nbsp;&nbsp;edges&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_entities</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">select</span><span class="syntaxkeyword">{&nbsp;|</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">|&nbsp;</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">is_a</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">Sketchup</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Edge</span><span class="syntaxkeyword">)&nbsp;}<br />&nbsp;&nbsp;</span><span class="syntaxdefault">puts&nbsp;Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now</span><span class="syntaxkeyword">-</span><span class="syntaxdefault">t<br /></span><span class="syntaxkeyword">}<br /><br /></span><span class="syntaxdefault">puts&nbsp;</span><span class="syntaxstring">"\n---&nbsp;#grep&nbsp;---"<br /></span><span class="syntaxdefault">10.times&nbsp;</span><span class="syntaxkeyword">{<br />&nbsp;&nbsp;</span><span class="syntaxdefault">GC</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">start<br />&nbsp;&nbsp;t</span><span class="syntaxkeyword">=</span><span class="syntaxdefault">Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now<br />&nbsp;&nbsp;edges&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_entities</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">grep</span><span class="syntaxkeyword">(&nbsp;</span><span class="syntaxdefault">Sketchup</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Edge&nbsp;</span><span class="syntaxkeyword">)<br />&nbsp;&nbsp;</span><span class="syntaxdefault">puts&nbsp;Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now</span><span class="syntaxkeyword">-</span><span class="syntaxdefault">t<br /></span><span class="syntaxkeyword">}<br /><br /></span><span class="syntaxdefault">puts&nbsp;</span><span class="syntaxstring">"\n---&nbsp;for&nbsp;in&nbsp;---"<br /></span><span class="syntaxdefault">10.times&nbsp;</span><span class="syntaxkeyword">{<br />&nbsp;&nbsp;</span><span class="syntaxdefault">GC</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">start<br />&nbsp;&nbsp;t</span><span class="syntaxkeyword">=</span><span class="syntaxdefault">Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now<br />&nbsp;&nbsp;edges&nbsp;</span><span class="syntaxkeyword">=&nbsp;[]<br />&nbsp;&nbsp;for&nbsp;</span><span class="syntaxdefault">e&nbsp;in&nbsp;model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_entities<br />&nbsp;&nbsp;&nbsp;&nbsp;edges&nbsp;</span><span class="syntaxkeyword"><<&nbsp;</span><span class="syntaxdefault">e&nbsp;</span><span class="syntaxkeyword">if&nbsp;</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">is_a</span><span class="syntaxkeyword">?(&nbsp;</span><span class="syntaxdefault">Sketchup</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Edge&nbsp;</span><span class="syntaxkeyword">)<br />&nbsp;&nbsp;</span><span class="syntaxdefault">end<br />&nbsp;&nbsp;puts&nbsp;Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now</span><span class="syntaxkeyword">-</span><span class="syntaxdefault">t<br /></span><span class="syntaxkeyword">}<br /><br /></span><span class="syntaxdefault">puts&nbsp;</span><span class="syntaxstring">"\n---&nbsp;#select{}&nbsp;Edge&nbsp;or&nbsp;Face&nbsp;---"<br /></span><span class="syntaxdefault">10.times&nbsp;</span><span class="syntaxkeyword">{<br />&nbsp;&nbsp;</span><span class="syntaxdefault">GC</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">start<br />&nbsp;&nbsp;t</span><span class="syntaxkeyword">=</span><span class="syntaxdefault">Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now<br />&nbsp;&nbsp;edges&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_entities</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">select</span><span class="syntaxkeyword">{&nbsp;|</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">|&nbsp;</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">is_a</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">Sketchup</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Edge</span><span class="syntaxkeyword">)&nbsp;||&nbsp;</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">is_a</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">Sketchup</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Face</span><span class="syntaxkeyword">)&nbsp;}<br />&nbsp;&nbsp;</span><span class="syntaxdefault">puts&nbsp;Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now</span><span class="syntaxkeyword">-</span><span class="syntaxdefault">t<br /></span><span class="syntaxkeyword">}<br /><br /></span><span class="syntaxdefault">puts&nbsp;</span><span class="syntaxstring">"\n---&nbsp;#select{}&nbsp;Face&nbsp;or&nbsp;Edge&nbsp;---"<br /></span><span class="syntaxdefault">10.times&nbsp;</span><span class="syntaxkeyword">{<br />&nbsp;&nbsp;</span><span class="syntaxdefault">GC</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">start<br />&nbsp;&nbsp;t</span><span class="syntaxkeyword">=</span><span class="syntaxdefault">Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now<br />&nbsp;&nbsp;edges&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_entities</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">select</span><span class="syntaxkeyword">{&nbsp;|</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">|&nbsp;</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">is_a</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">Sketchup</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Face</span><span class="syntaxkeyword">)&nbsp;||&nbsp;</span><span class="syntaxdefault">e</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">is_a</span><span class="syntaxkeyword">?(</span><span class="syntaxdefault">Sketchup</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Edge</span><span class="syntaxkeyword">)&nbsp;}<br />&nbsp;&nbsp;</span><span class="syntaxdefault">puts&nbsp;Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now</span><span class="syntaxkeyword">-</span><span class="syntaxdefault">t<br /></span><span class="syntaxkeyword">}<br />&nbsp;</span><span class="syntaxdefault"></span>

Results:
` === Select Entities by Type ===

497078 entities in the active context.
474629 edges in the active context.

--- #select{} ---
0.27
0.27
0.26
0.26
0.26
0.26
0.27
0.27
0.26
0.26

--- #grep ---
0.15
0.15
0.15
0.15
0.15
0.15
0.16
0.15
0.16
0.15

--- for in ---
0.29
0.28
0.29
0.28
0.28
0.28
0.28
0.28
0.29
0.29

--- #select{} Edge or Face ---
0.28
0.28
0.28
0.27
0.29
0.28
0.29
0.28
0.281
0.28

--- #select{} Face or Edge ---
0.37
0.37
0.38
0.38
0.38
0.38
0.37
0.37
0.37
0.37`

thomthom · 9 Nov 2012, 09:31

Notice when I select Edges and Faces it matters what I test for first. The whole collection of entities is nearly all edges. If I test for them first it's just about as fast as just selecting edges - because of short-circuiting.

But if I test for faces first - which there isn't any of then there's a penalty.

So test for the most likely cause first!

Dan Rathbun · 9 Nov 2012, 11:44

@thomthom said:

@tig said:

It would need to be something like:
fs=Sketchup.active_model.entities.grep(Sketchup::Face).select{|f|f.material}
to get an array of all faces that have a material assigned to them etc.

But then you do a double iteration. I'd think it's be best to do this as:

fs=Sketchup.active_model.entities.select{|f|f.is_a?(Sketchup::Face) && f.material}

That's just one iteration.

How about this ?

fs=Sketchup.active_model.entities.grep(Sketchup::Face){|f| f.material ? f : nil }.compact

compact removes the nil elements afterward.

thomthom · 9 Nov 2012, 12:14

Again - a second iteration. Of the result, but none the less - an extra iteration.

What's interesting here is what the performance is.

thomthom · 9 Nov 2012, 15:34

I've looked st a couple of methods in Vertex Tools - where I refactored them to use grep in combo with hashes and I'm getting huge improvements!

dkendig · 9 Nov 2012, 16:02

Glad I got frustrated on Wednesday and started throwing stuff at the wall to see what stuck! Nice benchmarks Thomthom, hope my find can help some folks out!

dkendig · 9 Nov 2012, 16:42

Dan, did you try benchmarking your pattern? It might not have much of a performance hit if you have the extra filtering criteria in the grep block:

@unknownuser said:

Don’t forget the extra processing — a map operation — comes “free” if you provide grep with a block

http://www.globalnerdy.com/2008/08/21/enumerating-enumerable-enumerablegrep/

Dan Rathbun · 9 Nov 2012, 18:14

@dkendig said:

Dan, did you try benchmarking your pattern?

No, but it can be added to TT's code above if your interested. (As TT said compact() needs to re-iterate the array to remove the nil elements. I tried using next but the block still returns a nil.)

And BTW.. I checked the C source for compact() which uses dup() to create a new array, and then calls compact!(), ie %(#008080)[rb_compact_bang()] on the C-side, so to save time, this pattern might as well use the "bang" edition of the method, and save the time to create a new array.

I'm deep into a Javascript mod for the forums, presently, and not doing much in Ruby.

thomthom · 15 Nov 2012, 18:07

Can you post your result data as well?

thomthom · 15 Nov 2012, 18:08

And what was the comparison code?

dkendig · 15 Nov 2012, 19:34

drawing_ele_test time: 0.00999999046325684, resulted in 1103 elements found
types_test time: 0.00999999046325684, resulted in 1103 elements found
magic_test time: 0.0420000553131104, resulted in 1103 elements found
loop_test time: 0.0190000534057617, resulted in 1103 elements found

that's my results from the huge one-liner that I copy and pasted for a scene with 13108 total entities. 10,000 edges, 1,000 component instances, 1,000 groups, 1,000 faces. The goal was to find anything that could have a material applied to it, so I wanted to filter out edges.

So actually it appears my test was flawed. I'm adding entities to a hash, and looping through the desired types in the "types_test" results. In the "drawing_ele_test" I am just doing a comparison to see if the type matches one of the types I am looking for. They both end up taking the same exact amount of time, so there's probably a cleaner way to write this, but under the hood both of those tests are essentially doing the same thing.

dkendig · 15 Nov 2012, 19:38

Just ran a benchmark in a scene with 10,000 edges, one component instance, one face, and one group. It appears that grepping specific classes you are interested in, is faster than doing a more general grep and then comparing within the block.

sample code soon to follow

dkendig · 15 Nov 2012, 19:39

actually, here's the benchmark code I ran


class Magic;def initialize(&block)
	@block=block;end
	def ===(other)
		@block.call(other)
	end
end

def GetVrayImportantArrayFromGrepDrawingelement(entities)
	return entities.grep(Sketchup;;Drawingelement){|ent| false == (ent.class == Sketchup;;Edge) ? ent ; nil}.compact
end

def GetVrayImportantArrayOfTypesFromGrep(entities,typeHash)
	for curType in typeHash.keys()
		typeHash[curType] = entities.grep(curType )
	end
end

def GetVrayImportantArrayFromGrepMagic(entities)
	return entities.grep(Magic.new {|ent| ent if(ent.class == Sketchup;;ComponentInstance or ent.class == Sketchup;;Group or ent.class == Sketchup;;Face)})
end

def GetVrayImportantArrayFromLoop(entities)
	vrayImportant = Array.new()
	for ent in entities.to_a
		if ent.class == Sketchup;;Face or ent.class == Sketchup;;ComponentInstance or ent.class == Sketchup;;Group
			vrayImportant.push(ent)
		end
	end
	return vrayImportant
end

def RunBenchmarkOnEntities(entities)
	testHash = Hash.new()
	testHash[Sketchup;;Face] = []
	testHash[Sketchup;;ComponentInstance] = []
	testHash[Sketchup;;Group] = []
	
	grep_drawing_ele_result = grep_magic_result = compare_loop_result = nil
	
	grep_drawing_ele_start_time = Time.now.to_f
	grep_drawing_ele_result = GetVrayImportantArrayFromGrepDrawingelement(entities)
	grep_drawing_ele_end_time = Time.now.to_f
	
	grep_types_start_time = Time.now.to_f
	grep_types_result = GetVrayImportantArrayOfTypesFromGrep(entities,testHash)
	grep_types_end_time = Time.now.to_f
	
	grep_magic_start_time = Time.now.to_f
	grep_magic_result = GetVrayImportantArrayFromGrepMagic(entities)
	grep_magic_end_time = Time.now.to_f 
	
	compare_loop_start_time = Time.now.to_f
	compare_loop_result = GetVrayImportantArrayFromLoop(entities)
	compare_loop_end_time = Time.now.to_f
	
	puts "drawing_ele_test time; #{grep_drawing_ele_end_time - grep_drawing_ele_start_time}, resulted in #{grep_drawing_ele_result.size} elements found"
	
	puts "types_test time; #{grep_types_end_time - grep_types_start_time}, resulted in #{testHash.values.flatten.size} elements found"
	
	puts "magic_test time; #{grep_magic_end_time - grep_magic_start_time}, resulted in #{compare_loop_result.size} elements found"
	
	puts "loop_test time; #{compare_loop_end_time - compare_loop_start_time}, resulted in #{compare_loop_result.size} elements found"
	
	return nil
end

RunBenchmarkOnEntities(Sketchup.active_model.entities)