Code Golf: Shortest code to find a weighted median

问题:

My try at code golfing.

The problem of finding the minimum value of ∑W_i*|X-X_i| reduces to finding the weighted median of a list of x[i] with weights w[i] (see below for definition). How will you do that with a shortest, simplest and most beautiful program?

Here's how my code looked originally (explanation is in the answer to the question and short version is posted as one of the answers below).

    #define zero(x) ( abs(x) < 1e-10 )  /* because == doesn't work for floats */

    float sum = 0;
    int i;

    for (i = 0; i < n; i++) 
         sum += w[i];
    while (sum > 0) 
         sum -= 2*w[--i];

    right = x[i]             // the rightmost minimum point
    left  = ( zero(sum) && zero(w[i]-w[i-1]) ) ? x[i-1] : right;
    answer = (left + right) / 2;

(Actually, it's been already heavily optimized as you see variables i and sum reused)

Rules

Floats and integers: different languages have different floating point arithmetic standards, so I reformulate the problem to have x[i] and w[i] to be integers and you can return twice the value of the answer (which is always integer) if you prefer. You can return, print or assign the answer to variable.

Definition of weighted median and clarifications:

• Median of sorted array x[i] of length n is either x[n/2] or (x[n/2-1/2]+x[n/2+1/2])/2 depending on whether n is odd or even
• Median of unsorted array is the median of array after sort (true, but our array is sorted)
• Weighted median of x[i] with integer positive weights w[i] is defined as the median of larger array where each occurrence of x[i] has been changed into w[i] occurrences of x[i].

What I hope to see

One of the reasons for asking is that I assume the most suitable language will have trivial array summation and iteration with lambdas. I thought a functional language could be reasonable, but I'm not sure about that - so it's part of the question. My hope is to see something like

    // standard function   add  :=  (a,b) :-> a + b 
    myreduce := w.reduce  
        with:  add  
        until: (value) :-> 2*value >= (w.reduce with:add)
    answer = x [myreduce  from:Begin] + x [myreduce  from:End]

Dunno if there's any language where this is possible and is actually shorter.

Test data

static int n = 10;
for (int j = 0; j < n; j++) {
        w[j] = j + 1;
        x[j] = j;
}

Answer: 6 or 12.

static int n = 9;
int w[n], x[n] ;
for (int j = 0; j < n; j++) {
    w[j] = j + ((j<6) ? 1 : 0);
    x[j] = j + 1;
}

Answer: 6.5 or 13.

回答1:

J

Go ahead and type this directly into the interpreter. The prompt is three spaces, so the indented lines are user input.

   m=:-:@+/@(((2*+/\)I.+/)"1@(,:(\:i.@#))@[{"0 1(,:(\:i.@#))@])

The test data I used in my other answer:

   1 1 1 1 m 1 2 3 4
2.5
   1 1 2 1 m 1 2 3 4
3
   1 2 2 5 m 1 2 3 4
3.5
   1 2 2 6 m 1 2 3 4
4

The test data added to the question:

   (>:,:[)i.10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8  9
   (>:m[)i.10
6
   (([+<&6),:>:)i.9
1 2 3 4 5 6 6 7 8
1 2 3 4 5 6 7 8 9
   (([+<&6)m>:)i.9
6.5

---

   i =: (2 * +/\) I. +/

First index such that total sum is greater than or equal to double the accumulated sum.

   j =: ,: (\: i.@#)

List and its reverse.

   k =: i"1 @ j @ [

First indices such that -see above- of the left argument and its reverse.

   l =: k {"(0 1) j @ ]

Those indices extracted from the right argument and its reverse, respectively.

   m =: -: @ +/ @ l

Half the sum of the resulting list.

回答2:

So, here's how I could squeeze my own solution:, still leaving some whitespaces:

    int s = 0, i = 0;
    for (; i < n; s += w[i++]) ;
    while ( (s -= 2*w[--i] ) > 0) ;
    a  =  x[i]  +  x[ !s && (w[i]==w[i-1]) ? i-1 : i ]; 

回答3:

Haskell code, ungolfed: trying for a reasonable functional solution.

import Data.List (zip4)
import Data.Maybe (listToMaybe)

mid :: (Num a, Ord a) => [a] -> (Int, Bool)
mid w = (i, total == part && maybe False (l ==) r) where
    (i, l, r, part):_ = dropWhile less . zip4 [0..] w v $ map (2*) sums
    _:sums = scanl (+) 0 w; total = last sums; less (_,_,_,x) = x < total
    v = map Just w ++ repeat Nothing

wmedian :: (Num a, Ord a) => [a] -> [a] -> (a, Maybe a)
wmedian w x = (left, if rem then listToMaybe rest else Nothing) where
    (i, rem) = mid w; left:rest = drop i x

> wmedian [1,1,1,1] [1,2,3,4]
(2,Just 3)
> wmedian [1,1,2,1] [1,2,3,4]
(3,Nothing)
> wmedian [1,2,2,5] [1,2,3,4]
(3,Just 4)
> wmedian [1,2,2,6] [1,2,3,4]
(4,Nothing)

> wmedian [1..10] [0..9]
(6,Nothing)
> wmedian ([1..6]++[6..8]) [1..9]
(6,Just 7)

---

My original J solution was a straightforward translation of the above Haskell code.

Here's a Haskell translation of the current J code:

{-# LANGUAGE ParallelListComp #-}
import Data.List (find); import Data.Maybe (fromJust)
w&x=foldr((+).fst.fromJust.find((>=sum w).snd))0[f.g(+)0$map
    (2*)w|f<-[zip x.tail,reverse.zip x]|g<-[scanl,scanr]]/2

Yeah… please don't write code like this.

> [1,1,1,1]&[1,2,3,4]
2.5
> [1,1,2,1]&[1,2,3,4]
3
> [1,2,2,5]&[1,2,3,4]
3.5
> [1,2,2,6]&[1,2,3,4]
4
> [1..10]&[0..9]
6
> ([1..6]++[6..8])&[1..9]
6.5

回答4:

short, and does what you'd expect. Not particularly space-efficient.

def f(l,i):
   x,y=[],sum(i)
   map(x.extend,([m]*n for m,n in zip(l,i)))
   return (x[y/2]+x[(y-1)/2])/2.

here's the constant-space version using itertools. it still has to iterate sum(i)/2 times so it won't beat the index-calculating algorithms.

from itertools import *
def f(l,i):
   y=sum(i)-1
   return sum(islice(
       chain(*([m]*n for m,n in zip(l,i))),
       y/2,
       (y+1)/2+1
   ))/(y%2+1.)

回答5:

Python:

a=sum([[X]*W for X,W in zip(x,w)],[]);l=len(a);a[l/2]+a[(l-1)/2]

回答6:

Something like this? O(n) running time.

for(int i = 0; i < x.length; i++)
{
sum += x[i] * w[i];
sums.push(sum);
}

median = sum/2;

for(int i = 0; i < array.length - 1; i++)
{
    if(median > sums[element] and median < sums[element+1]
         return x[i];
    if(median == sums[element])
         return (x[i] + x[i+1])/2
}

Not sure how you can get two answers for the median, do you mean if sum/2 is exactly equal to a boundary?

EDIT: After looking at your formatted code, my code does essentially the same thing, did you want a MORE efficient method?

EDIT2: The search part can be done using a modified binary search, that would make it slightly faster.

index = sums.length /2;
finalIndex = binarySearch(index);

int binarySearch(i)
{
    if(median > sums[i+1])
    {
        i += i/2
        return binarySearch(i);
    }
    else if(median < sums[i])
    {
        i -= i/2
        return binarySearch(i);
    }
    return i;
}

Will have to do some checking to make sure it doesn't go on infinitely on edge cases.

回答7:

Just a comment about your code : I really hope I will not have to maintain it, unless you also wrote all the unit tests that are required here :-)

It is not related to your question of course, but usually, the "shortest way to code" is also the "hardest way to maintain". For scientific applications, it is probably not a show stopper. But for IT applications, it is.

I think it has to be said. All the best.