🙆🏼 ℹ️ 🎀 メモリ不足時の整数のソート 🦒 ⌛️ 🧓🏻

英語の原作者-dzeban

はじめに

前回、プログラムで使用可能なメモリを人為的に制限する方法について説明しました。ボーナスとして、 libmemrestrict-メモリ使用量を追跡するためのmallocなどの関数ラッパーを備えたライブラリ、およびptrace-restrict-同じ目的でbrk、sbrkおよびmmap呼び出しをインターセプトするptraceベースのツールを入手しました。

それでは、なぜメモリ制限を整理する必要があるのでしょうか？ OOMが最後にアプリケーションを釘付けにしたのはいつですか？プログラミング中のメモリ消費について常に考えていますか？メモリは安価であり、メモリが不足した場合は、さらに数ギガバイトを追加します。

それにもかかわらず、メモリを際限なく追加することは不可能です。無限のソースがないためではありません。ビッグデータを処理する場合、すべての入力を配列に収容することは不可能です。RAM、ストレージメディア、ネットワーク間でデータを分散する必要があります。このようなデータ処理には、アルゴリズムと技術が必要です。

それで、単純なタスクから始めて、2 MiBのメモリで100万個の整数（4 MiBデータ）をソートする方法を説明します。このタスクは、すべてのデータを収容するのに十分なメモリがない場合に一般化できます。

与えられた

ファイルに格納されている整数のセットをソートするプログラムを作成する必要があります。それを作成するために、最も単純なユーティリティrandintsおよびrangeintsを作成しました

プログラムは、標準出力にテキストとしてソートされた配列を作成する必要があります

彼女は実行時間を測定し、stderrに出力する必要があります。 timeユーティリティを使用してプログラムを実行することはできません。ファイルを読み取る時間と出力する時間をカウントするためです。

ファイルの少なくとも半分のサイズで動作するはずです。これを行うには、libmemrestrictまたはptrace-restrictを使用します。

一部の方法では、これらのユーティリティは役に立ちません。たとえば、mmapでは機能しません。メモリの使用を物理的に制限する必要があります。

元の問題を解決するためにチェックされます（4 MiBを2 MiBに分類します）。また、128 MiBのメモリを搭載した仮想マシンで実行して、500 Mb（1億2,500万の4バイト整数）をソートします。

素朴なアプローチ

数値を直接並べ替えて、メモリ使用量（および時間）を計算してみましょう。ファイルを整数の配列に読み込み、 qsortを呼び出します。

4 MBのデータを含むファイルを試してみましょう。制限なしで、すべてが機能します：

$ ./naive 4M.bin > /dev/null 4000000 bytes sorted in 0.323146 seconds

しかし、それは面白くありません。メモリ2 MiBの制限：

 $ LD_PRELOAD=./libmemrestrict.so ./naive ints > ints.sorted Segmentation fault

制限を4 MiBに上げます-再び失敗します。（libmemrestrictは環境から設定を読み取ります）。

 $ MR_THRESHOLD=5000000 LD_PRELOAD=./libmemrestrict.so ./naive ints > ints.sorted Segmentation fault

明らかに、qsortはより多くのメモリを必要とします。彼がvalgrindのmassifでどれだけ欲しいか見てみましょう：

 $ valgrind --tool=massif ./naive ints $ ms_print massif.out.10676

美しいスケジュールは次のとおりです。

  MB 8.819^ :::::::::::::::::::::::::::# | : # | : # | : # | : # | : # | : # | : # | : # | :::::::@ #:::::::::::::::::::::::: | : @ # | : @ # | : @ # | : @ # | : @ # | @@@@@@: @ # | @ : @ # | @ : @ # | :::@ : @ # | ::: @ : @ # 0 +----------------------------------------------------------------------->Gi 0 1.721

メモリリクエストを4 MiBに倍増する複数のデータ配置を確認できます。これが私の配列で、qsort用にさらに4 MiBです。統計：

 -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 21 173,222,581 5,247,504 4,000,568 1,246,936 0 22 173,223,802 5,246,920 4,000,000 1,246,920 0 23 173,226,655 5,247,504 4,000,568 1,246,936 0 24 173,229,202 5,246,920 4,000,000 1,246,920 0 25 173,229,311 9,246,928 8,000,000 1,246,928 0 26 869,058,772 9,246,928 8,000,000 1,246,928 0 86.52% (8,000,000B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->43.26% (4,000,000B) 0x400A26: readfile (in /home/avd/dev/cs/sorting/external/naive) | ->43.26% (4,000,000B) 0x400ACD: main (in /home/avd/dev/cs/sorting/external/naive) | ->43.26% (4,000,000B) 0x35D40383F7: qsort_r (in /usr/lib64/libc-2.18.so) | ->43.26% (4,000,000B) 0x400B3D: main (in /home/avd/dev/cs/sorting/external/naive) | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)

400万バイト、さらに400万バイト-qsort_rを使用しています。さらに、別の1.2 MBがヒープ上にmassifを追加で使用します。

明らかに、この場合、qsortはボリュームの複雑さに関してO（n）のように動作します。 qsortは「インプレース」で動作し、さまざまな最適化手法を使用してO（log n）のボリュームの複雑さを保証するため、これは奇妙です。 glibc qsortの実装に関する詳細情報。

さて、500 MBを128 MiB RAMに分類できますか？

 $ ./naive 500M.bin > /dev/null Segmentation fault

もちろん違います。性能：

 $ ./naive 4M.bin > /dev/null 4000000 bytes sorted in 0.322712 seconds

これは、単純なソートが制限なしで適切に機能し、制限付きではまったく機能せず、qsortがO（n）メモリを必要とすることを意味します。これは奇妙です。たとえば、メモリを5.3 MBに制限すると、動作し、O（n）メモリを必要としません。私はまだこれを扱っています。

ファイルとmmap

mmapは、メモリ制限の条件下で大量のデータをソートするハッカーの方法です。メモリとスワップの間のデータ配布の負担をOSの肩に移します。

次のように機能します。

mmapを通じて、ファイル全体をメモリに送信します
データへのポインタを取得します
このポインタでデータをソートするアルゴリズムを呼び出します

それだけです！使用可能なメモリよりも大きいボリュームでファイルをソートしても、メモリオーバーフローは発生しません。メカニズムを理解するには、OSのメモリ管理について少し理解する必要があります。

各プログラムは、他から分離された独自の仮想アドレス空間を持つプロセスによって表されます。その長さはCPUバスの幅によって制限されます。つまり、32ビットCPUの場合は2 ³² 、つまり4 GiBです。

プロセスに関係するすべてのメモリ割り当ては、仮想メモリで発生します。この仮想メモリは、メモリを操作するためにカーネルの物理サブシステム-MMUにマップされます。通常、「遅延」モードで発生します。つまり、プロセスがメモリを要求すると、カーネルはすぐにメモリを割り当てますが、物理的に即座に配置することはありません。つまり、仮想メモリのページは物理に直接マッピングされません。そのようなページにアクセスすると（たとえば、記録のために）、MMUは「ページフォールト」例外を発生させます。これは、カーネルが仮想ページを物理ページにマッピングすることで処理します。これで表示され、このページのレコードはMMUによって物理メモリの特定のアドレスのレコードとしてブロードキャストされます。

一方、仮想アドレス空間がCPUバスのサイズによってのみ制限されることを覚えている場合、プログラムが使用可能なメモリよりも多くのメモリを使用したいという状況に陥ることがあります。たとえば、256 MiB RAMの32ビットシステムでは、プロセスは1 GiBのメモリを配置して使用できます。この場合、メモリページはスワップに分類されます-RAMの代わりに、ハードディスクなどのドライブに移動します。そのようなページにアクセスすると、カーネルはそれをドライブから読み取り、メモリに送信します（メモリ内の別のページを置き換えます）。

カーネルは、メモリとドライブ間のデータの分散にうまく対応しているため、タスクでこのプロパティを使用しようとするのは自然なことです。ファイルに対してmmapを呼び出すと、カーネルは、すぐには割り当てられない仮想アドレスの範囲を予約します。それらにアクセスしようとすると、カーネルはそれを入力ファイルからメモリにロードします。物理メモリが不足すると、カーネルはスワップ内のページを削除します。したがって、ディスク上のファイル、メモリ、およびスワップ間でデータのバランスを取ります。

制限は仮想アドレス空間（32ビットシステムの場合は4 GiB、64ビットの場合は256 TiB）とスワップだけです。しかし、今日のストレージデバイスは安価です。

mmapはファイル全体を仮想メモリにロードするという事実により、仮想メモリ自体を制限するため、libmemrestrictまたはptrace-restrictを使用できません。ボリュームが100Mのデータをボリュームが10Mの仮想メモリにソートしようとすると、mmapからエラーが発生します。

 $ qemu-x86_64 -R 10M ./mmaped 100M.bin mmap stack: Cannot allocate memory

不思議ではありません-ファイルは仮想メモリにロードされ、カーネルはそれを物理メモリとスワップに分配します。そのため、少なくとも100Mの仮想メモリと、qemu用のスペースが必要です。

したがって、この方法では、128 MiBのメモリを持つ仮想マシンを使用します。 mmapを使用したソートプログラムを次に示します。そしてそれは動作します！

 $ free -m total used free shared buffers cached Mem: 119 42 76 0 4 16 -/+ buffers/cache: 21 97 Swap: 382 0 382 $ ll -h 500M.bin -rw-r--r-- 1 root root 477M Feb 3 05:39 500M.bin $ ./mmaped 500M.bin > /dev/null 500000000 bytes sorted in 32.250000 seconds

上からの情報：

 PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 3167 root 20 0 480m 90m 90m R 84.6 76.4 1:18.65 mmaped

500 MBの仮想メモリを使用しますが、実際に使用可能なメモリは90 MiBです。 MiBは2 ²⁰であり、MBは10 ⁶ = 100万です。 500 MB = 500,000,000バイト、500,000,000 >> 20 = 476 MiB。

500 MBのソート中にvmstatの詳細を見ると、カーネルがスワップ、ディスクキャッシュ、バッファ、空きメモリの間でどのようにバランスを取っているかがわかります。

 procs -----------memory---------- ---swap-- -----io---- -system-- ----cpu---- rb swpd free buff cache si so bi bo in cs us sy id wa 0 0 0 77776 2120 15104 1 27 710 971 24 34 3 1 95 1 1 1 0 2060 488 90068 1 27 785 1057 25 37 3 1 95 1 1 0 928 3400 60 89744 1 27 799 1092 25 38 3 1 94 1 0 2 1908 1928 212 92040 1 27 852 1174 26 40 4 1 94 1 0 2 3436 2360 280 93056 1 27 911 1282 28 42 4 1 94 2 0 0 5272 3688 196 94688 1 27 1066 1471 31 48 4 1 93 2 0 0 5272 3720 204 94700 1 27 1064 1469 31 48 4 1 93 2

最初に、約70 MiBの空きメモリ、空のスワップがあり、メモリのビットがI / Oバッファとキャッシュに割り当てられました。その後、mmap後、このメモリはすべてキャッシュに保存されました。空きメモリがなくなると、カーネルはスワップの使用を開始しましたが、スワップはI / O負荷の増加とともに増加します。そして、ほぼすべてのメモリがディスクキャッシュに割り当てられるという結論に達しました。これは、アプリケーションにメモリが必要な場合、ディスクキャッシュのあるページが最初になるため、通常のことです。

そのため、mmapによる並べ替えは、メモリの操作に関する基本的なアイデアを必要とするクールなハックであり、少量のメモリで大量のデータを処理するための簡単なソリューションを提供します。

外部マージソート

mmapは使用できないとしましょう。32ビットシステムで5 GiBのファイルをソートしたいとします。

「外部マージソート」と呼ばれるよく知られた方法があります。十分なメモリがない場合は、ハードディスクなどの外部ドライブを使用する必要があります。データはメモリに収まらないため、1つずつ処理する必要があります。

外部マージソートは次のように機能します。

利用可能なメモリの量でデータを断片に分割します
各ピースはメモリでソートされ、外部メディアに書き込まれます
これで、filesize / buffersizeのサイズの断片ができました
サイズbuffersize /＃チャンクの一部を読み取り、それらをバッファに結合し、結果をファイルに出力します

私は単純な最適化されていない実装を行いました：

 $ LD_PRELOAD=./libmemrestrict.so ./external-merge 4M.bin 1048576 > /dev/null 4194304 bytes sorted in 0.383171 seconds

2 MiBのメモリでソートされ、1 MiBのバッファを使用します。

500 MBをソートします。まず、データの交換を手動で制御するため、スワップを無効にします。

 $ swapoff /dev/vda5

キャッシュをゼロにします。

 $ echo 3 > /proc/sys/vm/drop_caches

使用可能なメモリを確認します。

 $ free -m total used free shared buffers cached Mem: 119 28 90 0 0 6 -/+ buffers/cache: 21 97 Swap: 0 0 0

50 MBのバッファを使用します-ファイルサイズの10倍のサイズです。

 $ ./external-merge 500M.bin 50000000 > /dev/null 500000000 bytes sorted in 120.115180 seconds

何も、2分！どうしてですか？もちろん、I / O操作が原因です。 3つのことがプロセスを妨げます。データ分離フェーズでは、小さなバッファーを使用してファイルを順次読み取ります。マージフェーズでは、情報を含むファイルを開いたり閉じたりします。また、結論もあります。マージフェーズでは、50 MBのデータをstdoutに出力します。これは、/ dev / nullにリダイレクトされますが、負荷を与えます。これを無効にすると、パフォーマンスが25％向上します。

 $ ./external-merge-no-output 500M.bin 50000000 > /dev/null 500000000 bytes sorted in 87.140000 seconds

メモリの使用は私には問題ありません。 massifを介してプログラムを実行すると、消費のピークはバッファーのサイズと小さなヒープであることがわかります。

 -------------------------------------------------------------------------------- Command: ./external-merge 500M.bin 50000000 Massif arguments: (none) ms_print arguments: massif.out.17423 -------------------------------------------------------------------------------- MB 47.75^ ::::: |#::::::@:::::::::::@:::::::::@:::@::::@::::@::::::::@::::@::::@:::@ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ |# : : @ : : : : @ : : @ @ @ @ : @ @ @ @ 0 +----------------------------------------------------------------------->Gi 0 332.5 Number of snapshots: 98 Detailed snapshots: [4 (peak), 10, 20, 29, 32, 35, 38, 45, 48, 54, 64, 74, 84, 94] -------------------------------------------------------------------------------- n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B) -------------------------------------------------------------------------------- 0 0 0 0 0 0 1 119,690 584 568 16 0 2 123,141 50,004,496 50,000,568 3,928 0 3 4,814,014 50,005,080 50,001,136 3,944 0 4 4,817,234 50,005,080 50,001,136 3,944 0 99.99% (50,001,136B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->99.99% (50,000,000B) 0x400FA2: external_merge_sort (in /root/external-merge) | ->99.99% (50,000,000B) 0x40128E: main (in /root/external-merge) | ->00.00% (1,136B) in 1+ places, all below ms_print's threshold (01.00%)

メモリを50 MBに制限し、さらにファイルパスを含む一時行にさらに500 KBを制限できます。

 $ LD_PRELOAD=./libmemrestrict.so MR_THRESHOLD=51000000 ./external-merge 500M.bin 50000000 > /dev/null 500000000 bytes sorted in 87.900000 seconds

一般に、メモリでは-わかりました、速度では-わかりません。 mmapはこの操作を32秒で実行できました。方法を改善しましょう。

gprofを使用してプログラムのプロファイルを作成しましょう。バイナリを作成する

 $ gcc -pg -g -Wall -Wextra external-merge.c -o external-merge-gprof

また、gprof記事の便利なスクリプトを使用して、プログラムを何度も呼び出して統計を蓄積します。結果は次のとおりです。

 % cumulative self self total time seconds seconds calls Ts/call Ts/call name 81.98 432.87 432.87 compar 18.17 528.82 95.95 print_arr 0.00 528.82 0.00 1100 0.00 0.00 form_filename 0.00 528.82 0.00 100 0.00 0.00 merge 0.00 528.82 0.00 100 0.00 0.00 save_buf 0.00 528.82 0.00 10 0.00 0.00 external_merge_sort 0.00 528.82 0.00 10 0.00 0.00 split

ほとんどの時間はソートと出力に費やされました。ただし、gprofはシステムコールとI / Oにかかった時間を表示しないことを忘れないでください。

ここで何を改善できますか？

外部ソートにマルチスレッドとI / Oトリックを追加する
別のソートアルゴリズムを使用する

ユニバーサル外部マージソートは、少量のメモリでビッグデータをソートするためのシンプルなアイデアですが、改善なしでゆっくりと動作します。

並べ替えをカスタマイズする

もちろん、マルチスレッドを使用して分離してマージすることもできますが、これは悪い考えです。データは1つのバッファーに含まれているため、分離フェーズで使用することは意味がありません。カーネルがデータを読み取る方法に影響を与えることができます。これには2つの機能があります。

readahead（Linuxのみ）。
POSIX_FADV_SEQUENTIALを指定したposix_fadvise。

メモリ管理サブシステムに、データの読み取り方法を伝えます。この場合、読み取りはシーケンシャルであるため、ページキャッシュ内のファイルの内容を確認すると便利です。

マージフェーズでは、ファイルを常に開いたり閉じたりすることはできませんが、ファイルごとに専用のストリームを作成します。各ストリームはファイルを開いたままにし、そのバッファを埋めます。いっぱいになると、ソートされて出力されます。また、先読みは各スレッドで機能します。

以下は、外部マージソートの高度なマルチスレッドバージョンです。さて、私が言ったように、マルチスレッドは良い考えではありません。シングルコアプロセスに違いはありません。

 $ ./mt-ext-merge 500M.bin 50000000 > /dev/null 500000000 bytes sorted in 117.380000 seconds

これはデータ出力です。そして出力なし：

 $ ./mt-ext-merge-no-output 500M.bin 50000000 > /dev/null 500000000 bytes sorted in 91.040000 seconds

それでは、4コアマシン（Intel Core i7-3612QM CPU @ 2.10GHz）で試してみましょう。

 $ ./naive 500M.bin > /dev/null 500000000 bytes sorted in 23.040499 seconds $ ./mmaped 500M.bin > /dev/null 500000000 bytes sorted in 23.542076 seconds $ ./external-merge 500M.bin 50000000 > /dev/null 500000000 bytes sorted in 39.228695 seconds $ ./mt-external-merge 500M.bin 50000000 > /dev/null 500000000 bytes sorted in 41.062793 seconds $ ./external-merge-no-output 500M.bin 50000000 > /dev/null 500000000 bytes sorted in 28.893745 seconds $ ./mt-external-merge-no-output 500M.bin 50000000 > /dev/null 500000000 bytes sorted in 28.368976 seconds       : $ ./external-merge-no-output 500M.bin 5000000 > /dev/null 500000000 bytes sorted in 27.107728 seconds $ ./mt-external-merge-no-output 500M.bin 5000000 > /dev/null 500000000 bytes sorted in 28.558468 seconds

external-mergeとmt-external-mergeの間に違いはありません。これはなぜですか？はい、マルチスレッドは入力および出力の制限の問題を解決しないためです。次の場合に適しています。

スレッドの独立した実行
入力リソースと出力リソースは並行して動作できます-たとえば、RAID

スレッドは相互に依存しています。メインスレッドは、バッファがソートされるのを待ってから、ファイルから次の読み取りを開始する必要があります。また、スプリットへの読み取りはバッファのソートよりも高速であるため、ほとんどの場合、スレッドはメインスレッドが終了するまで待機します。

アルゴリズムを改善する他の方法が必要です。

特別なソートアルゴリズム

QuickSort以外のものを使用してみましょう。整数をソートしていることがわかっているため、これを使用する必要があります。特定のデータ型に使用される特別なアルゴリズムがあり、2つのグループに分けることができます。

比較を使用しないでください
アレイ全体をメモリにロードする必要はありません

O（n log（n））-QuickSortなどのアルゴリズムを比較するための下限よりも優れています。しかし、メモリの制限がある場合、それらのすべてが適しているわけではありません。だから私はカウントソートを使用することに決めました

カウントソート

スプレッドが小さい多くのデータがある場合は、カウントソートを使用できます。考え方は単純です。データをメモリに保存するのではなく、カウンタの配列を保存します。データを順番に読み取り、対応するカウンターを増やします。アルゴリズムの複雑さは、時間とボリュームで線形であり、データの範囲に比例します。

単純な実装は、0〜Nの配列で機能します。整数は配列のインデックスに対応します。これが私のバージョンです。これはチューニングなしでうまく機能します。 2番目の引数は、要素内のバッファのサイズです。プログラムはファイルから4バイトを読み取らないため、バッファリングは作業を大幅に高速化します。

 $ ./counting-array 500M-range.bin 1000000 > /dev/null Range is 1000000 500000000 bytes sorted in 3.240000 seconds

ウグムス。半ギガバイトのデータは、128 MiBメモリと1つのCPUで3秒半でソートされます。 qsortまたはmmapと比較してください：

 $ ./mmaped 500M-range.bin > /dev/null 500000000 bytes sorted in 76.150000 seconds

23倍高速！

ただし、制限（整数（またはそれらに相当するもの）のみ）とそれらの小さな連続した間隔を忘れないでください。ハッシュとバイナリ検索で一貫性のない間隔でオプションを作成しようとしましたが、そのパフォーマンスは非常に劣っています。

そして、数値の一意性を仮定すると、カウンターは2つの状態にしかなれない-あるかどうかに関係なく、単一ビットにすることができます。その後、配列が縮小します。はい、配列は必要ありません。ビットの形式で数値を格納できます。つまり、配列の代わりにベクトルがあります。数値Nがあった場合、ファイルを読み取ってN番目のビットを設定します。その後、ベクトルを調べて、ビットがコックされている数値を出力します。

あなたはまだ限界を超えることができるので、そのような決定には慎重なアプローチが必要です。たとえば、整数の範囲（2 ³² ）からすべての数値をソートするには、各数値に1ビットが必要です。これは4294967296ビット= 536870912バイト= 512 MiBです。また、128 MiBしかありませんが、これでは十分ではありません。しかし、場合によっては、利益が膨大になることがあります-Jon BentleyによるProgramming Pearlsのこのテーマに関するストーリーです。

データを知ることは非常に役立ちます。

まとめ

記事に費やした5か月間、私は多くのことをしました-多数のプログラム、いくつかの良いアイデア、多くの悪いもの。そして、さらに多くのことができ、修正することができます。

メモリ不足でデータを並べ替えるという単純な問題により、通常考えられない奇妙な点がすべて明らかになりました。

一般的なアルゴリズムはすべての問題に適しているわけではありません
デバッグとプロファイリングは非常に便利で視覚的なものです
すべての作業をコアにシフトしないと、I / Oが問題の領域になります
マルチスレッドは速度の万能薬ではありません
データと環境を知る

ソートプレート：

テスト	素朴なQuickSort	mmapとクイックソート	外部マージソート	マルチスレッド外部マージソート	カウントソート
2 MiBに4 MiB	セグフォルト	N / a	0.38秒	0.41秒	0.01
128 MiBで500 MB	セグフォルト	32.25秒	87.14秒	91.04	3.24

データを理解し、それらと連携する簡単なアルゴリズムを開発してください！

メモリ不足時の整数のソート