Skip to content

Instantly share code, notes, and snippets.

@philtomson
Created December 18, 2014 20:57
Show Gist options
  • Save philtomson/754910da281e8625e401 to your computer and use it in GitHub Desktop.
Save philtomson/754910da281e8625e401 to your computer and use it in GitHub Desktop.
Histogram Earth Mover Distance in Julia
function emd!(A,B)
@assert(size(A) == size(B))
cost = 0
last_bin = length(A)
for bin = 1:last_bin
delta = A[bin]-B[bin]
if(delta < 0) #more in B than in A
num_to_move = abs(delta)
next_bin = bin+1
#search to the right for place to move 'package'
while(num_to_move > 0 )
if(B[next_bin] < A[next_bin])
B[bin]-=1
B[next_bin]+=1
cost+=(next_bin-bin)
num_to_move-=1
else
#try the next bin
next_bin+=1
end
end
elseif(delta > 0) #more in A than in B
num_to_move = delta
next_bin = bin+1
while(num_to_move > 0 )
if(B[next_bin] > A[next_bin])
B[bin]+=1
B[next_bin]-=1
cost+=(next_bin-bin)
num_to_move-=1
else
#try the next bin
next_bin+=1
end
end
else
end
end
cost
end
@afternone
Copy link

What is the time complexity?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment