Hello guys, I finished writing a Bucket Sorting package, that supports the following operations: build bucket, update bucket, empty bucket, top_bucket and search bucket. I am using these codes for ray tracing. It is supposed to be 5 times faster than using a binary heap, but unfortunately my run time is duplicated. I am not a computer scientist, and I am sure that there are better ways to write these functions, but just in case anyone need to use them, bellow I’ll leave the codes.
build_bucket: Builds the empty buckets between dmin and dmax, using an interval dmax/dmin.
update_bucket: allows you to append to the bucket a two column matrix, and sorts it in the buckets using the second column to order.
empty_bucket: tests if the buckets are empty (gives a true or false).
top_bucket: returns the first element of the entire bucket array.
search_bucket: tests if a value is contained in the bucket (based on the first column, but can be modified).
Hopefully somebody will find it useful.
function build_bucket(dmin, dmax) where T
numBuckets=Int(round(dmax/dmin))
zbuck=[[] for i in 1:numBuckets]
#Store the maximum value for each bin
maxBinVal = collect(range(dmin, dmax,numBuckets+1))
#Remove the extra bin where the max value is minimum(tt)
popfirst!(maxBinVal)
return zbuck,maxBinVal,numBuckets
end
function update_bucket(fs,zbuck,maxBinVal,numBuckets)
#Loop through all the values in the FS
for i in 1:length(fs[:,1])
if fs[i,2]>=maxBinVal[numBuckets]
push!(zbuck[numBuckets],fs[i,:])
else
ind = searchsortedfirst(maxBinVal, fs[i,2])
push!(zbuck[ind],fs[i,:])
end
end
return zbuck
end
function empty_bucket(zbuck)
a=isempty.(zbuck)
b=a==[true for i in 1:length(a)]
return b
end
function top_bucket(zbuck,numBuckets,mode)
u=[]
for i in 1:numBuckets
if !isempty(zbuck[i]) && mode==1
u=popfirst!(zbuck[i])
break
elseif !isempty(zbuck[i]) && mode==2
u=first(zbuck[i])
break
end
end
return u'
end
function search_bucket(zbuck,node,numBuckets)
a=[]
b=[]
point=[]
for i in 1:numBuckets
for j in 1:length(zbuck[i])
a=node==(zbuck[i][j][1])
if a==true
b=zbuck[i][j][2]
point=(i,j,2)
break
else
end
end
if a==true
break
else
end
end
return a,b,point
end
fs=[5 74.0;2 128;8 87;10 0.0; 7 127]
#fs=[1 0.0]
@time (zbuck,maxBinVal,numBuckets)=build_bucket(10.0,100.0)
puf=@time update_bucket(fs,zbuck,maxBinVal,numBuckets)
(a,b,point)=@time search_bucket(zbuck,7,numBuckets)
tt=@time top_bucket(zbuck,numBuckets,1)
@time empty_bucket(zbuck)