OpenEuphoria

Re: Optimizing basic operations

• Posted by gimlet Aug 05, 2013
• 5640 views

Basically you are doing too much work. The only requirements we really need are:

1. That we know the minimum record for the top 100, the others do not concern us.

2. A data structure which will efficiently provide us with that (eg: a heap). See Wikipedia 'Heap (data structure)' only reverse the conditon so that root is the minimum and items are greater than or equal to their parent node.

create heap H 
for i = 1 to 100 
	insert R.i into H 
end  
 
for i = 101 to N do 
	if R.i > H.min then 
                drop H.min '(root) 
		insert R.i into H 
	end if 
end for 
 
sort H (it's already half-sorted). 

This is a good solution as it uses constant space and an (optimal) single read of the data.