リスト内から中央値が最大となる連続要素をみつける

How to calculate the maximum median in an array – StackOverflow

「連続要素」「中央値」という条件から,まず最大値を探し,そのインデックスを基準にサイズ2, 3程度の走査で良いと思うので,O(n)で解けるのでは.最初に最大値を探すのにO(n),最大になる中央値を探す部分はせいぜい15通りにしかならないので,全体としてO(n).

と思ったけど,これだと失敗するケースもあるか.
どちらにせよ,線形時間で解けそうだが.

from itertools import product
from statistics import median


def find_max_median(lst):
    N, idx = len(lst), max(enumerate(lst))[0]
    if idx == N - 1:
        return max(median(lst[idx-i:idx+1]) for i in range(1, 3))
    else:
        g = (tpl for tpl in product(range(3), range(2 if idx==N-2 else 3)) if 0<sum(tpl)<3)
        return max(median(lst[idx-i:idx+1+j]) for i, j in g)


def find_max_median2(lst):
    def seq_median(x): return max(median(lst[i:i+x]) for i in range(len(lst)-x+1))

    return max(seq_median(2), seq_median(3))


lst = ([100, 1, 99, 2, 1000], [4, 5, 6, 1, 9, 2, 3, 8, 0, 7], [600, 500, 0, 1000])
for l in lst:
    print(find_max_median(l), find_max_median2(l))

lst *= 100
%timeit [find_max_median(l) for l in lst]
%timeit [find_max_median2(l) for l in lst]

lst *= 100
%timeit [find_max_median(l) for l in lst]
%timeit [find_max_median2(l) for l in lst]
501.0 501.0
7 7
500.0 550.0

1000 loops, best of 3: 1.11 ms per loop
100 loops, best of 3: 3.3 ms per loop

10 loops, best of 3: 111 ms per loop
1 loop, best of 3: 334 ms per loop

特に今のケースでは,(確信は無いが)要素数2 or 3で良さそうなので,要素数が2の場合は平均を,要素数が3の場合は,(バブルソートでも3回の入れ替えでしかないので)ソートして真ん中の値を選択するのが最も速いと思う(自分で実装するよりもCythonizeされている組み込み関数を用いる方が良い).

def find_max_median3(lst):
    return max(
        max((lst[i]+lst[i+1])/2 for i in range(len(lst)-1)),
        max(sorted(lst[i:i+3])[1] for i in range(len(lst)-2))
    )


lst = ([100, 1, 99, 2, 1000], [4, 5, 6, 1, 9, 2, 3, 8, 0, 7], [600, 500, 0, 1000])

lst *= 100
%timeit [find_max_median2(l) for l in lst]
%timeit [find_max_median3(l) for l in lst]

lst *= 100
%timeit [find_max_median2(l) for l in lst]
%timeit [find_max_median3(l) for l in lst]
100 loops, best of 3: 3.46 ms per loop
1000 loops, best of 3: 1.65 ms per loop

1 loop, best of 3: 346 ms per loop
10 loops, best of 3: 164 ms per loop
広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください