Pythonでの再帰関数を使用したクイックソートがエラーメッセージ無しで停止した場合の対処法を教えていただきたいです

Question

前提・実現したいこと

Pythonの勉強のため再帰関数を使用したクイックソートを行いたいです。
実行環境は下記の通りです。
OS : Windows10(64bit), Ubuntu系のディストリビューション
Python : 3.10.0, 3.7.3

教えていただきたいこと

プログラムの停止する原因と対処法
エラーメッセージが出力されない原因
この問題が分かる方がいらっしゃれば、ご教示をお願いいたします。

発生している問題・エラーメッセージ

Pythonを用いてクイックソートのプログラムを作成し、ソートする要素の数を多くしたところ、エラーメッセージを表示しないでプログラムが終了しました。

エラーメッセージはありません

該当のソースコード

import random
import time
import sys
import threading

#再起する回数の上限を設定
sys.setrecursionlimit(2100000000)
#スタックの容量を設定
threading.stack_size(255*1024*1024)

#並び替えをするリスト内の要素数を設定するための変数
N = 0
#生成する乱数の大きさの範囲を設定するための変数
random_range = 9999999

#乱数リストを生成する関数
def make_ramdom_list():
    global random_list
    random_list = []
    for i in range(N):
        random_list = random_list + [random.randrange(random_range)]

#クイックソートのメインプログラム
def quick_sort(sort_ramdom_list, first, last):
    if first < last:
        pivot = sort_ramdom_list[int((first + last) / 2)]
        i = first
        j = last

        while sort_ramdom_list[i]  < pivot:
            i += 1
        while sort_ramdom_list[j]  > pivot:
            j -= 1
        if i <= j:
            swap_number = sort_ramdom_list[j]
            sort_ramdom_list[j] = sort_ramdom_list[i]
            sort_ramdom_list[i] = swap_number
            i += 1
            j -= 1
        
        quick_sort(sort_ramdom_list, first, j)
        quick_sort(sort_ramdom_list, i, last)

#ソートする要素の数を設定
N = 200000
print("N:" + str(N))
make_ramdom_list()
start = time.time()
quick_sort(random_list, 0, N - 1)
#ソートされたリストを表示する(要素が多いと表示する量が多くなりますのでコメントアウトします。)
#print(random_list)
print("time:" + str(time.time() - start))

試したこと

再帰する回数の上限を設定
スタックの容量を設定

補足情報（FW/ツールのバージョンなど）

当方の実行環境ではリストの要素の数が数万程度であれば実行可能なのですが、20万程度になるとエラーメッセージが無くプログラムが停止します。

プログラム実行時に使用するメモリーの量を確認したところ、最大で13メガバイト程度でした。

同様の結果を出力するマージソートのプログラムを実行したところ問題なく実行されました。

参考にしたサイトでは再帰関数がタイムアウトする可能があるとの記述があったのですが、技術不足の為に理解することができませんでした。

Comments

[TakaiY]

ソースコードの quick_sort 関数内のwhileループあたりのインデントがおかしくありませんか？
これだと、ソートできないと思うのですが。

[python__student]

返答ありがとうございます。
インデントがおかしいというのは「i += 1」の部分でしょうか？
現状、このプログラムで45行目の「N=200000」を「N=10000」程度の値を代入すると、
ソートする要素の数が代入値になり実行することができました。

[TakaiY]

すみません。こちらがちょっと勘違いしていたようです。

[python__student]

わかりました。
不明な点があれば、ご質問ください。

Answer 1

一般論で言いますと、再起関数というのはスタックを消費するためにあまり深くは実行できません。
なので、対処法、というなら、再帰を使わない処理に書き変える、ということになろうかと思います

Comments

[python__student]

返答ありがとうございます。
現在、プログラムの学習のために再帰を用いてプログラムを行っています。
ですので、方針としては再帰的なプログラムで実行したいと考えています。
それらを踏まえて、スタックの使用可能容量と使用容量を調べると、設定したスタックの容量に届かない程度しか使用していませんでした。
よろしければ、この問題を一緒に解決していただけないでしょうか。

[y_waiwai]

まあ、スタックサイズを設定で増やして実行できるようにするってのも一つの手ですが、根本的な解決じゃないですね
なにを持って解決とするか、ですが。

[python__student]

解決とするのは、20万程度の大きい要素の数でも実行できるクイックソートのプログラムの製作です。
そのための条件としては再起関数の使用です。
また、同様に再起関数を使用するマージソートという方法でプログラムを製作し実行したところ、正常に動作しました。そのプログラムではクイックソートのプログラムと同じように大きなリストを使う他に、マージという操作を行うためのリストもあります。
先述の状況からスタックの使用量に問題があるのかもわからい状況です。

Answer 2

プログラムの停止する原因と対処法
エラーメッセージが出力されない原因

こちらの Windows 10 環境では quick_sort() の呼び出し深さが 2672 ぐらいで終わります。
pivot 値より小さい値と大きい値に振り分けが終わらないうちに再帰呼び出しになるため深く呼び出す状況となり、たぶんスタックオーバーフローになっていると思います。
ご提示の quick_sort ベースで quick sort にすると次のようになると思います。

def quick_sort(sort_ramdom_list, first, last):
    if first < last:
        pivot = sort_ramdom_list[(first + last) // 2]
        i = first
        j = last
        while True:
            while sort_ramdom_list[i]  < pivot:
                i += 1
            while sort_ramdom_list[j]  > pivot:
                j -= 1
            if i >= j:
                break
            sort_ramdom_list[i], sort_ramdom_list[j] = sort_ramdom_list[j], sort_ramdom_list[i]
            i += 1
            j -= 1

        quick_sort(sort_ramdom_list, first, j)
        quick_sort(sort_ramdom_list, j + 1, last)

できれば計算量が O(n^2) になることがないよう

def median(a, b, c):
    ret = a
    if a >= b >= c or a <= b <= c: ret = b
    if b >= c >= a or b <= c <= a: ret = c
    return ret

def quick_sort(sort_ramdom_list, first, last):
    ...
        #pivot = sort_ramdom_list[int((first + last) / 2)]
        val = sort_ramdom_list[(first + last) // 2]
        pivot = median(sort_ramdom_list[first], val, sort_ramdom_list[last])

としておきたいですね。
そして list の生成は高速化しましょう。

#def make_ramdom_list():
#    global random_list
#    random_list = []
#    for i in range(N):
#        random_list = random_list + [random.randrange(random_range)]
def make_ramdom_list(start, end, num):
    return [random.randrange(start, end) for _ in range(num)]

#make_ramdom_list()
random_list = make_ramdom_list(0, random_range, N)

Comments

[python__student]

lehshellさん
回答ありがとうございます。
問題原因の解説がわかりやすかったです。また、添付していただいたソースコードは高速で驚きました。
添付していただいたプログラムのようなコードを書けるようPythonについて勉強します。

Answer 3

make_random_list を高速化し、quick_sort を正しく実装してみました。

import random
import time

N = 200000
random_range = 9999999

def make_ramdom_list():
	global random_list
	random_list = [0] * N
	for i in range(N):
		random_list[i] = random.randrange(random_range)

def quick_sort(a, first, last):
	if first < last:
		pivot = a[last]
		i = first
		for j in range(first, last):
			if a[j] <= pivot:
				a[i], a[j] = a[j], a[i]
				i += 1
		a[i], a[last] = a[last], a[i]
		quick_sort(a, first, i-1)
		quick_sort(a, i+1, last)

print("N:" + str(N))
make_ramdom_list()
print(random_list[:8])
start = time.time()
quick_sort(random_list, 0, N - 1)
print("time:" + str(time.time() - start))
print(random_list[:8])

ソート前後のデータを先頭 8個だけ表示しています。

Comments

[python__student]

kazuma-sさん
コードの添付ありがとうございます。
ランダムリストの作成やクイックソートが高速化され驚きました。
すべてを再帰的に行おうとして、低速かつ使用スレッド容量が膨大になっていることを改めて理解しました。
こちらで、プログラムを勉強して改善してみます。

Answer 4

問題

1. スタックオーバーフローで落ちている(推測)
2. クイックソートではない
3. スタックの設定が出来ていない

1. スタックオーバーフローで落ちている(推測)

何も表示されないのはおそらくWindowsだからだと思いますが、スタックオーバーフローで落ちています。
Windowsでコマンドプロンプトから実行している場合、実行終了時に

echo %ERRORLEVEL%

とすれば0以外のプロセス終了コードを確認することが出来ます。-1073741571(C00000FD)であればスタックオーバーフローです。

Unix系のOSであればセグメンテーション違反で検出され、大抵のシェルでは処理後にエラー表示があると思います。

2. クイックソートではない

既にご指摘があるとおり、クイックソートではありません。本来のクイックソートはリスト中の全値を走査し、pivot以下のグループ(A)とpivotより大きいグループ(B)に分け、(A)→pivot→(B)となる順に並べた後、(A)内と(B)内をそれぞれ同様に処理していく方法です。

現状のコードはpivotはあるものの1回しかスワップをせずに重複する範囲をさらに再帰呼び出ししているため、バブルソートより効率の悪いソートになっています。

またスワップ1回につき2度再帰呼び出しをするコードなのでスタックを大量に消費しています。ただのクイックソートであればここまで極端にスタックを消費することはありません。ただし正しいクイックソートでも、並び順によっては再帰呼び出しのバブルソートと同じくらいスタックを消費するので、入力が限定されないケースを再帰呼び出しでは実装しません。

まずクイックソートを学びなおしてください。

3. スタックの設定が出来ていない

import threading
threading.stack_size(255*1024*1024)

では自分で起動するスレッドのスタック設定は出来ても、メインスレッドの設定は出来ません。
メインスレッドの設定をしたければ以下のようにしてください。

from resource import *
setrlimit(RLIMIT_STACK, (255 * 1024 * 1024, -1))

回答

プログラムの停止する原因と対処法

原因

スタックの無駄遣いによるスタックオーバーフロー(推測)

対処法

まずは正しくクイックソートを実装してください。
余力があれば再帰呼び出しをやめてください。

エラーメッセージが出力されない原因

スタックオーバーフローだからです(推測)。再帰呼び出しの上限を自分で書き換えて、足りないスタックで動かしたためpython実行環境が落ちています。

Comments

[python__student]

dameoさん
プログラム停止の調査方法やクイックソートでない理由、スタックのメインスレッドの設定方法など、詳細に記述していただきありがとうございます。
大変わかりやすく、他の回答者さんの方の説明と合わせて、かなり理解できたと思います。
Windows10やraspbianでプログラムを実行してみたところ両者ともにエラーの出力がなかったため原因がわかりませんでしが、セグメンテーション違反を示す情報が得て正確な状況を理解できました。
クイックソートについてとプログラムが異常動作した場合のセグメンテーション違反などのOSの動作についてあたらめて学んできます。

Answer 5

手元の環境で、ある操作を行ってから問題のスクリプトを実行してみました。

$ lsb_release -ir
Distributor ID: Ubuntu
Release:        21.04

# デフォルトのスタックサイズは 8 Mib
$ ulimit -a | grep stack
stack size                  (kbytes, -s) 8192

# スタックサイズを 512 KiB に変更
$ ulimit -s 512

# 実行
$ python quick.py
N:200000
Segmentation fault (core dumped) # 短時間で発生

# gdb による解析
$ gdb /usr/bin/python core
            :

Core was generated by `python quick.py'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0  0x0000000000515e42 in _PyEval_EvalFrameDefault ()

スクリプト内ではスタックサイズを 255 MiB に設定していますが、少なくとも Linux OS ではシステム側の設定(最近のデフォルトサイズは 8 MiB)が優先されます。

#スタックの容量を設定
threading.stack_size(255*1024*1024)

プログラムの停止する原因と対処法

Linux OS と同様に Windows OS でもスタックサイズの上限が設定されているのではないかと思います。その値を変更することができるのかどうかは私には分かりませんけれども。

また、末尾再帰に関しては Tail Call Optimization Decorator がありますが、古い話なので効果の程は不明です。

エラーメッセージが出力されない原因

分かりません。

Comments

[python__student]

melianさん
回答ありがとうございます。
提供していただいた情報のOSでのデフォルトの設定は盲点でした。
こちらで、設定を変更する方法を調べ検討します。

Answer 6

コメントをしたので、回答もしておきます。

アルゴリズムがクイックソートでない

ftlobw さんの指摘の通り、この処理はクイックソートにはなっていません。

• リストの真ん中をピボットにする。
• 右(小さい)から順に見ていって、最初のピボットより小さい値が出てくるところをiとする。
• 左(大きい)から順に見ていって、最初のピボットより大きい値が出てくるところをiとする。
• iとjの場所にある値を入れ替える。
• 小さい方からjまでで同じ処理をする
• 大きい方からiもでで同じ処理をする。

となっています。これはクイックソートのアルゴリズムではありません。

クイックソートは

• リストの真ん中をピボットにする。
• ピボットより左にある、ピボットより大きい値を全て右に移す。
• ピボットより右にある、ピボットより小さい値を全て左に移す。
• ピボットより左をソートしたもの + ピボットの値 + ピボットより右をソートしたもの が結果

ざっとという処理になるはずです。

再帰処理で多数のデータをソートするのは現実的ではありません。

クイックソートは再帰で表現するとすっきり書けますので、再帰処理の理解にはよい例だと思いますが、そのロジックで多数のデータをソートするのは現実的ではありません。

大きなデータをクイックソートでソートしたいのであれば、再帰を使わない憑肩で実装すべきです。

Comments

[python__student]

回答ありがとうございます。
再起処理を使用した処理の現実性については理解しました。
しかし、クイックソートの条件について、製作したプログラムの、どの動作が条件を満たさないのかがわかりませんでした。
当方の認識としては、指摘していただいた動作を再起処理により繰り返すことによって、条件を満たしていると考えています。
お手数ですが、補足する解説をお願いできますでしょうか。

[TakaiY]

アルゴリズムについては、回答に書いたとおり、提示されたソースのアルゴリズムとクイックソートのアルゴリズムが異なります。

クイックソートは、言葉で書けば、ピボット値を決めて、それより大きなものと小さなものに分けて、それぞれをソートしていくという方式です。提示のコードがそのような処理をしているようには見えません。

[python__student]

TakaiYさん
解説ありがとうございます。
なんとなくですが、理解できたと思います
ひとまず、新しくプログラムを作成する方法で検討しようと思います。

Answer 7

質問者さんのコメントを受けての追記

(コメントに書いてもらったプログラムはインデントが崩れていて読めないので、すみませんが試していません)
試しにWikipediaの記事にあったクイックソートを実行した場合の途中経過は以下の通りです。
(pivotの選択は、質問者さんの実装と同じにしてあります)

0～9の範囲で pivot: 3 を選択しているところまでは一緒ですが、
その後のpartition処理でpivot未満の数字が一気に左に寄っているのが分かると思います。

before: [1, 7, 5, 4, 3, 8, 9, 2, 6, 0]
first: 0, last: 9, pivot: 3
after: [1, 0, 2, 3, 4, 8, 9, 5, 6, 7]
<以下省略>

何をもってクイックソートと言うのかは、コンピュータサイエンスを専攻したわけではないので自信をもって回答はできないのですが、
Wikipediaの記事に書いてある「ピボットの選択：適当な値（ピボット（英語版）という）を境界値として選択する」を基準にすれば質問者さんの元々の実装は、
再帰を使っているか? → Yes
クイックソートか? → No
だと思います。

from typing import Any, Callable, MutableSequence

# 分割関数
# 配列の指定範囲をピボットに従って分割する
#
# @param seq   - 分割する配列
# @param keyFn - 配列要素のキー値を計算する関数
# @param first - 分割範囲の最初のインデックス
# @param last  - 分割範囲の最後のインデックス
# @returns 分割点のインデックス
def partition(seq: MutableSequence[Any], keyFn: Callable[[Any], Any], first: int, last: int):
    pivot = seq[int((first + last) / 2)]
    print(f'first: {first}, last: {last}, pivot: {pivot}')
    while True:
        while keyFn(seq[first]) < pivot:
            first += 1
        while pivot < keyFn(seq[last]):
            last -= 1
        if first >= last:
            return last + 1
        seq[first], seq[last] = seq[last], seq[first]
        first += 1
        last -= 1

# クイックソート
#
# @param seq   - ソートする配列
# @param keyFn - 配列要素のキー値を計算する関数
def quicksort(seq: MutableSequence[Any], keyFn: Callable[[Any], Any]):
    def quicksortImpl(seq: MutableSequence, keyFn: Callable[[Any], int], first: int, last: int):
        global cnt
        while first < last:
            cnt += 1
            print('before:', seq)
            p = partition(seq, keyFn, first, last)
            print('after:', seq, end='\n\n')
            if (p - first) < (last - p):
                quicksortImpl(seq, keyFn, first, p - 1)
                first = p
            else:
                quicksortImpl(seq, keyFn, p, last)
                last = p - 1
    quicksortImpl(seq, keyFn, 0, len(seq) - 1)


cnt = 0
lst = [1, 7, 5, 4, 3, 8, 9, 2, 6, 0] * 1
quicksort(lst, lambda x: x)

print('=' * 30)
print(cnt, len(lst))
print(lst)

以下は以前の回答です。

pivotを決めた後、quick_sort()を再帰呼び出しするまでの処理が怪しいです。

試しにソートするデータのサイズを変更してquick_sort()の呼び出し回数を確認したところ、
サイズ50で2000回、サイズ100で7.5万回、150で231万回 でした。
このペースだと再帰呼び出しの回数やスタック容量を多少増やしても、
データサイズが大きくなるとスグに破綻すると思います。

添付プログラムのように、最初に [1, 7, 5, 4, 3, 8, 9, 2, 6, 0] というデータを与えて
quick_sort()内でリストの並べ替え状況を確認するコードを埋め込んでみると以下のような結果になります。

これは、ピボットを境界値としてリストをピボット未満(左)とそれ以外(右)に値を分割していくクイックソートではなくて、値を1つづつ入れ替えていくような挙動になっているのではないかと思います。
Wikipediaの記事などを見て、実装を見直してみてはどうでしょうか。

before: [1, 7, 5, 4, 3, 8, 9, 2, 6, 0]
first: 0, last: 9, pivot: 3
after: [1, 0, 5, 4, 3, 8, 9, 2, 6, 7]

before: [1, 0, 5, 4, 3, 8, 9, 2, 6, 7]
first: 0, last: 8, pivot: 3
after: [1, 0, 2, 4, 3, 8, 9, 5, 6, 7]

before: [1, 0, 2, 4, 3, 8, 9, 5, 6, 7]
first: 0, last: 6, pivot: 4
after: [1, 0, 2, 3, 4, 8, 9, 5, 6, 7]

before: [1, 0, 2, 3, 4, 8, 9, 5, 6, 7]
first: 0, last: 3, pivot: 0
after: [0, 1, 2, 3, 4, 8, 9, 5, 6, 7]

<以下省略>

#クイックソートのメインプログラム
def quick_sort(sort_ramdom_list, first, last):
    global cnt
    if first < last:
        cnt += 1
        print('before:', sort_ramdom_list)

        pivot = sort_ramdom_list[int((first + last) / 2)]
        i = first
        j = last

        while sort_ramdom_list[i]  < pivot:
            i += 1
        while sort_ramdom_list[j]  > pivot:
            j -= 1
        if i <= j:
            swap_number = sort_ramdom_list[j]
            sort_ramdom_list[j] = sort_ramdom_list[i]
            sort_ramdom_list[i] = swap_number
            i += 1
            j -= 1

        print(f'first: {first}, last: {last}, pivot: {pivot}')
        print('after:', sort_ramdom_list, end='\n\n')

        quick_sort(sort_ramdom_list, first, j)
        quick_sort(sort_ramdom_list, i, last)

cnt = 0
lst = [1, 7, 5, 4, 3, 8, 9, 2, 6, 0] * 1
quick_sort(lst, 0, len(lst) - 1)

print('=' * 30)
print(cnt, len(lst))
print(lst)

Comments

[python__student]

返答とプログラムの添付、ありがとうございます。
「クイックソートではなく」とのことですが、指定していただいたリンクを確認したところ、クイックソートの動作をしているように見えました。
当方が知識不足のため、具体的にどういった動作がクイックソートの動作でなかったのか、お教えしていただけないでしょうか。

当方がクイックソートであると判断した理由としては、下記の添付していただいたプログラムを加筆したプログラムと結果の抜粋したものを見ていただくと、「cnt」が3と4の時に正常に「first」と「last」の範囲をソートしています。
他にも、「cnt」が5と6の時の「local cnt」の値が減っていることから再帰的に処理していると思います。

言葉足らずで申し訳ありません。

```Python
#クイックソートのメインプログラム
def quick_sort(sort_ramdom_list, first, last, local_cnt):
global cnt
if first < last:
cnt += 1
local_cnt += 1
print('before:', sort_ramdom_list)

pivot = sort_ramdom_list[int((first + last) / 2)]
i = first
j = last

while sort_ramdom_list[i] < pivot:
i += 1
while sort_ramdom_list[j] > pivot:
j -= 1
if i <= j:
swap_number = sort_ramdom_list[j]
sort_ramdom_list[j] = sort_ramdom_list[i]
sort_ramdom_list[i] = swap_number
i += 1
j -= 1

print('after:', sort_ramdom_list)
print(f'cnt: {cnt}, local cnt: {local_cnt}')
print(f'first: {first}, last: {last}, i: {i}, j: {j}, pivot point: {int((first + last) / 2)}', end='\n\n')

print("call_section_1")
quick_sort(sort_ramdom_list, first, j, local_cnt)
print("call_section_2")
quick_sort(sort_ramdom_list, i, last, local_cnt)

cnt = local_cnt = 0
lst = [1, 7, 5, 4, 3, 8, 9, 2, 6, 0] * 1
quick_sort(lst, 0, len(lst) - 1, local_cnt)

print('=' * 30)
print(cnt, len(lst))
print(lst)
```

```出力結果の一部抜粋
call_section_1
before: [1, 0, 2, 4, 3, 8, 9, 5, 6, 7]
after: [1, 0, 2, 3, 4, 8, 9, 5, 6, 7]
cnt: 3, local cnt: 3
first: 0, last: 6, i: 4, j: 3, pivot point: 3

call_section_1
before: [1, 0, 2, 3, 4, 8, 9, 5, 6, 7]
after: [0, 1, 2, 3, 4, 8, 9, 5, 6, 7]
cnt: 4, local cnt: 4
first: 0, last: 3, i: 1, j: 0, pivot point: 1

call_section_1
call_section_2
before: [0, 1, 2, 3, 4, 8, 9, 5, 6, 7]
after: [0, 1, 2, 3, 4, 8, 9, 5, 6, 7]
cnt: 5, local cnt: 5
first: 1, last: 3, i: 3, j: 1, pivot point: 2

call_section_1
call_section_2
call_section_2
before: [0, 1, 2, 3, 4, 8, 9, 5, 6, 7]
after: [0, 1, 2, 3, 4, 8, 9, 5, 6, 7]
cnt: 6, local cnt: 4
first: 4, last: 6, i: 6, j: 4, pivot point: 5
```

[python__student]

ftlobwさん
追加のコメントありがとうございます。
プログラムがクイックソートでない理由について、少しかもしれないですが理解できたと思います。
新しく添付していただいたプログラムを参考にして、プログラムを製作することを検討してみます。