Go to Qiita Advent Calendar 2024 Top
LoginSignup
30
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@LouiS0616

Pythonワンライナーでスターリンソート

Last updated at Posted at 2019-07-31

#概要

Pythonワンライナーでこれを実現する。
ただし、コードゴルフや過度な難読化を目的とはしない。

なお、入力はコマンドライン引数として与えられることとする。

#最初の実装

Haskell版を移植したもの。ワンライナーらしい素直な実装である。Wandbox

print(*(lambda func: (lambda arr: func(func, arr)))(lambda func, arr: [] if not arr else arr if len(arr) == 1 else [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else func(func, [arr[0], *arr[2:]]))([*map(int, __import__('sys').argv[1:])]))

これを読み易く整形、適宜コメントを加えると次のようになる。

print(*
    # 再帰可能にする為に高階関数を噛ませる
    (lambda func:
        (lambda arr:
            func(func, arr)
        )
    )
    # ソート実装本体
    (lambda func, arr:
        # arrが空リストなら、空リストを返す
        []                             if not arr          else
        # arrが長さ1であるなら、そのままarrを返す
        arr                            if len(arr) == 1    else
        # 粛清が必要無い場合、最初の要素を通過させる
        [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else
        # 粛清が必要な場合、粛々と粛清する
        func(func, [arr[0], *arr[2:]])
    )
    # コマンドライン引数を数値列に変換
    ([*map(int, __import__('sys').argv[1:])])
)

ワンライナービギナー向けに書き下すと、こんな感じ。

def higher_func(func):
    def inner(arr):
        return func(func, arr)
    
    return inner


def stalin_sort(func, arr):
    if not arr:
        return []
    
    if len(arr) == 1:
        return arr
    
    if arr[0] <= arr[1]:
        return [arr[0], *func(func, arr[1:])]
    
    return func(func, [arr[0], *arr[2:]])

stalin_sort = higher_func(stalin_sort)     # 本来はデコレータを使うべき


import sys

arr = [*map(int, sys.argv[1:])]
print(*stalin_sort(arr))

#想定される抵抗と、その鎮圧
抵抗を予期して対処する為には、検閲が必要である。
次のように検閲関数を適当に用意し、引数censorとして渡す。

# 再帰可能にする為、また事前検閲の為に高階関数を噛ませる
(lambda func, censor:
    (lambda arr:
        func(func, censor(arr))
    )
)
(
    # 第一引数： ソート実装本体
    (lambda func, arr: 
        略
    ),
    # 第二引数： 検閲関数
    (lambda arr: 
        検閲し、必要なら新たなリストを返す
    )
)
# ソート元リスト
(略)

以降、検閲関数の実装を考える。

##対 人海戦術
ソート対象のリストが過度に長大で有る場合、MemoryErrorやRecursionErrorを引き起こす恐れがある。1

ここでは、要素数が1024を超える入力2を与える輩には相応の措置を与えるようにする。

###要素の切り詰め
恐らく最も穏便且つ寛大な方法である。

# 第二引数： 検閲関数
(lambda arr: arr[:1024])

###大粛清
単純な方法であるが、インパクトに欠ける。

# 第二引数： 検閲関数
(lambda arr: [] if 1024 < len(arr) else arr)

###例外送出
raise文は使えないので、generator.throwを利用する。
また例外は決して凡庸なものであってはならない。type関数でBaseExceptionを継承し、特別に生成する。3

# 第二引数： 検閲関数
(lambda arr: 
    (_ for _ in []).throw(
        type('StalinPurge', (BaseException,), {}), 'array is too long'
    ) if 1024 < len(arr) else arr
)

###強制遮断
例外はキャッチされてしまう恐れがある。
それを避ける為には、プロセス自体を落としてやるのが有用である。4

# 第二引数： 検閲関数
(lambda arr: 
    (print("You're purged."), __import__('sys').exit(1)) if 1024 < len(arr) else arr
)

##対 不正入力
数字列の入力を望んでいるが、不敬の輩は不純物を交え妨害してくるだろう。
これに備えて、入力部分及び検閲関数を次のように修正する。

# 再帰可能にする為、また事前検閲の為に高階関数を噛ませる
(lambda func, censor:
    (lambda arr:
        func(func, censor(arr))
    )
)
(
    # 第一引数： ソート実装本体
    (lambda func, arr: 
        略
    ),
    # 第二引数： 検閲関数
    (lambda raw_arr:
        # 数値列化してからの検閲
        (lambda arr:
            略
        )
        # 関数呼び出しは左結合なので、括弧で優先してやる必要がある
        (
            # 生入力に対する検閲
            (lambda raw_arr: 
                検閲の結果を踏まえ、リストを数値列化して返す
            )
            (raw_arr)
        )
    )
)
# 
(__import__('sys').argv[1:])

###不純物の排除
不純要素だけを排斥する、やはり寛大な方法である。5

# 生入力に対する検閲
(lambda raw_arr: 
    [int(e) for e in raw_arr if e.isdecimal()]
)

###連帯責任
先の大粛清・例外送出・強制遮断のいずれかを用いてソート自体を拒絶する。
その場合次のように条件を指定してやれば良い。

# 生入力に対する検閲
(lambda raw_arr: 
    粛清処理 if not all(map(str.isdecimal, raw_arr)) else [*map(int, raw_arr)]
)

#成果物

せっかくなので、一番書くのが面倒だった例外処理を採用する。

print(*
    # 再帰可能にする為に高階関数を噛ませる
    (lambda func, censor:
        (lambda arr:
            func(func, censor(arr))
        )
    )
    (
        # 第一引数： ソート実装本体
        (lambda func, arr:
            # arrが空リストなら、空リストを返す
            []                             if not arr          else
            # arrが長さ1であるなら、そのままarrを返す
            arr                            if len(arr) == 1    else
            # 粛清が必要無い場合、最初の要素を通過させる
            [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else
            # 粛清が必要な場合、粛々と粛清する
            func(func, [arr[0], *arr[2:]])
        ),
        # 第二引数： 検閲関数
        (lambda raw_arr:
            (lambda arr:
                (_ for _ in []).throw(
                    type('StalinPurge', (BaseException,), {}), 'array is too long'
                ) if len(arr) > 1024 else arr
            )
            (
                (lambda raw_arr: 
                    (_ for _ in []).throw(
                        type('StalinPurge', (BaseException,), {}), 'spy is found.'
                    ) if not all(map(str.isdecimal, raw_arr)) else [*map(int, raw_arr)]
                )
                (raw_arr)
            )
        )
    )
    # コマンドライン引数を変換せずに渡す
    (__import__('sys').argv[1:])
)

一行に詰めるとこんな感じ。600文字以内で書けた。Wandbox

print(*(lambda func, censor: (lambda arr: func(func, censor(arr))))((lambda func, arr: [] if not arr else arr if len(arr) == 1 else [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else func(func, [arr[0], *arr[2:]])), (lambda raw_arr: (lambda arr: (_ for _ in []).throw(type('StalinPurge', (BaseException,), {}), 'array is too long') if len(arr) > 1024 else arr)((lambda raw_arr: (_ for _ in []).throw(type('StalinPurge', (BaseException,), {}), 'spy is found.') if not all(map(str.isdecimal, raw_arr)) else [*map(int, raw_arr)])(raw_arr))))(__import__('sys').argv[1:]))

お手元のPythonでも、 python -c "上記コード" 数値1 数値2 数値n で試せる。

標準入力を使いたいなら、
__import__('sys').argv[1:]を__import__('sys').stdin.read().split()に差し替えれば良い。

#追記

本家にプルリクを出してみた。
変更した仕様は次のとおり：

  • 関数stalin_sortを用意し、コマンドライン引数の読み取りを廃した。
  • 数値列以外の引数を拒むようにした。

今後進展があったらさらに追記する。通ると良いなぁ。
通った。まじか。とても嬉しい。

image.png

#先駆者たち

Python

黒魔術

#参考

  1. 特に何も考えずに100万長のリストを与えてみたら、PCが粛清された。
    これはスターリンの意向に沿わないので、適当な方法で排除しなければならない。 ↩

  2. 歴史に疎いので、スターリンらしい上限値が思い付かない。詳しい人、教えて下さい。 ↩

  3. 本来ならBaseExceptionは継承してはならない。スターリン特例である。 ↩

  4. SystemExitが捕捉できるとか、そういうことは言っちゃいけない。 ↩

  5. str.isdecimalは想像するより多くの『数字』を看過する。アラビア数字以外認めないのであれば all(c in set('0123456789') for c in e) あたりが適当か。 ↩

30
11
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
30
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?