Create a fast algorithm for a "weighted" median

Posted by Hameer Abbasi on Programmers See other posts from Programmers or by Hameer Abbasi
Published on 2012-10-31T10:54:43Z Indexed on 2012/10/31 11:13 UTC
Read the original article Hit count: 242

Filed under:

algorithms

Suppose we have a set S with k elements of 2-dimensional vectors, (x, n). What would be the most efficient algorithm to calculate the median of the weighted set?

By "weighted set", I mean that the number x has a weight n. Here is an example (inefficient due to sorting) algorithm, where Sx is the x-part, and Sn is the n-part. Assume that all co-ordinate pairs are already arranged in Sx, with the respective changes also being done in Sn, and the sum of n is sumN:

sum <= 0; i<= 0
while(sum < sumN)
  sum <= sum + Sn(i)
  ++i
if(sum > sumN/2)
  return Sx(i)
else
  return (Sx(i)*Sn(i) + Sx(i+1)*Sn(i+1))/(Sn(i) + Sn(i+1))

EDIT: Would this hold in two or more dimensions, if we were to calculate the median first in one dimension, then in another, with n being the sum along that dimension in the second pass?

Related posts about algorithms

Finding a problem in some task [closed]

as seen on Programmers - Search for 'Programmers'
Recently I competed in nation wide programming contest finals. Not unexpectedly all problems were algorithmic. I lost (40 points out of 600. Winner got ~300). I know why I lost very well - I don't know how to find actual problem in those obfuscated tasks which are life-blood of every competition.… >>> More
Genetic algorithms

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues. I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of… >>> More
understanding evaluation function

as seen on Programmers - Search for 'Programmers'
I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the… >>> More
How to know whether to create a general system or to hack a solution

as seen on Programmers - Search for 'Programmers'
I'm new to coding , learning it since last year actually. One of my worst habits is the following: Often I'm trying to create a solution that is too big , too complex and doesn't achieve what needs to be achieved, when a hacky kludge can make the fit. One last example was the following (see paste… >>> More
How to implement a genetic algorithm with distance, time, and cost

as seen on Programmers - Search for 'Programmers'
I want to make a solution to find the optimum route of school visit. For example, I want to visit 5 schools (A, B, C, D, E) in my city. Then I must find out what school I should visit first, then the second, then the third etc. with distance, time, and cost criteria. The problem is, I am confused… >>> More

Developer IT