4

コードゴルフをやってみました。

の最小値を見つける∑W_i*|X-X_i|問題は、重み付きのリストの重み付き中央値を見つけることにx[i]なりますw[i]（定義については以下を参照）。最短で、最もシンプルで、最も美しいプログラムでそれをどのように行いますか？

これが私のコードが元々どのように見えたかです（説明は質問への回答にあり、短いバージョンが以下の回答の1つとして投稿されています）。

    #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;

i（実際には、変数が表示されて再利用されているため、すでに大幅に最適化されていますsum）

ルール

浮動小数点数と整数：言語が異なれば浮動小数点演算標準も異なるため、問題を整数に再定式化し、x[i]必要にw[i]応じて回答の2倍の値（常に整数）を返すことができます。回答を返す、印刷する、または変数に割り当てることができます。

加重中央値と説明の定義：

  • x[i]ソートされた長さの配列の中央値は、奇数か偶数かによって異なりnます。x[n/2](x[n/2-1/2]+x[n/2+1/2])/2n
  • ソートされていない配列の中央値は、ソート後の配列の中央値です（trueですが、配列はソートされています）
  • x[i]整数の正の重みを持つの重み付き中央値は、の各出現がの出現に変更されw[i]た、より大きな配列の中央値として定義されます。x[i]w[i]x[i]

私が見たいもの

質問する理由の1つは、最も適切な言語には、単純な配列の合計とラムダによる反復があると想定していることです。関数型言語は妥当だと思いましたが、それについてはよくわかりません。それで、それは質問の一部です。私の望みは次のようなものを見ることです

    // 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。

テストデータ

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

回答：6または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;
}

回答：6.5または13。

4

7 に答える 7

2

Haskellコード、ゴルフなし：合理的な機能ソリューションを試みています。

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、ちょうど3）
> wmedian [1,1,2,1] [1,2,3,4]
（3、なし）
> wmedian [1,2,2,5] [1,2,3,4]
（3、ちょうど4）
> wmedian [1,2,2,6] [1,2,3,4]
（4、なし）

> wmedian [1..10] [0..9]
（6、なし）
> wmedian（[1..6] ++ [6..8]）[1..9]
（6、ちょうど7）

私の元のJソリューションは、上記のHaskellコードを直接翻訳したものでした。

これが現在のJコードのHaskell翻訳です：

{-# 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

ええ…このようなコードを書かないでください。

> [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
于 2009-06-08T22:58:08.950 に答える
2

短く、あなたが期待することを行います。特に省スペースではありません。

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.

これは、itertools を使用した定数空間バージョンです。それでも sum(i)/2 回反復する必要があるため、インデックス計算アルゴリズムに勝ることはありません。

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.)
于 2009-06-19T19:03:10.640 に答える
0

このようなもの？O（n）実行時間。

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
}

中央値に対して2つの答えを得る方法がわかりません。つまり、sum / 2が境界に正確に等しいかどうかということですか？

編集：フォーマットされたコードを見た後、私のコードは本質的に同じことをします、あなたはより効率的な方法が欲しかったですか？

EDIT2：検索部分は、修正された二分探索を使用して実行できます。これにより、検索が少し速くなります。

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;
}

エッジケースで無限に進行しないことを確認するために、いくつかのチェックを行う必要があります。

于 2009-06-08T20:54:34.597 に答える
-5

あなたのコードについてのコメント：ここで必要なすべての単体テストも書かない限り、私はそれを維持する必要がないことを本当に望んでいます:-)

もちろん、それはあなたの質問とは関係ありませんが、通常、「コーディングする最短の方法」は「維持するのが最も難しい方法」でもあります。科学的なアプリケーションの場合、それはおそらくショーストッパーではありません。しかし、ITアプリケーションの場合はそうです。

言わざるを得ないと思います。ではごきげんよう。

于 2009-06-08T20:49:41.423 に答える