Programming Pearlsノート(1)
2991 ワード
COLUMU 1: CRACKING THE OYSTER
△原版の英語は、読むのは確かに骨が折れる...でも、堅持しなければならない...私は大まかな内容を書いて、他の中国語版を参考にします.
問題の説明:
入力:n=107より小さい正の整数(positive integers)で、重複せず、他に関連する情報はありません.
出力:大きい順から小さい順に並べます
制約条件(constraints):1 Mb(megabyte)のメインメモリ容量、十分なハードディスクストレージ.実行時間は最大数分、最適10 s、(a run time of ten seconds need not be decreased)
プログラミング:ここでは2つのソリューションについて説明します.
1)集計ソート(Merge Sort)は、大量の中間ファイル(work files)を生成する
2)各整数を32ビットの整数と見なす、1 MBで約250000個の整数を記憶した後、ファイルに対して、40回input filesの内容を読み取り、クイックソート(Quicksort:A Quicksort would be quite efficient for the main-memory sorts)を利用する.これで中間ファイルはありませんが、input filesを何度も読み書きします.
実装シナリオ:
特定の問題を開始するには,いずれも整数であるため,このような格納方式でデータを格納することを考える.
たとえば{1,2,3,5,8,13}はこのような文字列で格納できます.
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
すなわち、整数nについては、n番目のビットに1と書く.
ソートの実装:ダミーコードは次のとおりです.
(ps:私個人にとって:107のような大きな配列をどうやって開くか知りたいです.それともこんなに長い文字列ですか.これはポイントではありません...私の個人的な知識にも限りがあります)
このようなやり方は,上記の2つのスキームに比べて実現され,input fileを1回読み込んで中間ファイルを生成せず,効率の高いソートが実現された.
最後の項目
原則(Principles)
正しい問題(the right broblems)
問題を正しく定義できれば、仕事は半分になります.問題を解決する前に、よく考えてください.私たちの学生にとって問題です.明らかに上の解法は、特定のソートに対してのみ有効である:1.正の整数2.繰り返しません3.関連情報がありません.
Bitmapのデータ構造
これもデータ構造を効率的に組織する方法であり、その3つの条件を満たさなければ、いくつかの変更を行うことができ、表の項目は複雑になります.
Multiple-Pass Algorithms
A time-Space Tradeoff and One That Isn't. 時間空間の転換は,偏ってはならない.
A simple Designプログラムの設計はできるだけ簡単にしなければならない.簡単なプログラムは複雑なプログラムよりも丈夫で、高校です.
個人レベルが限られているので、内容の理解はここまでです.分からないことが多いので、後で補充しましょう.の
△原版の英語は、読むのは確かに骨が折れる...でも、堅持しなければならない...私は大まかな内容を書いて、他の中国語版を参考にします.
問題の説明:
入力:n=107より小さい正の整数(positive integers)で、重複せず、他に関連する情報はありません.
出力:大きい順から小さい順に並べます
制約条件(constraints):1 Mb(megabyte)のメインメモリ容量、十分なハードディスクストレージ.実行時間は最大数分、最適10 s、(a run time of ten seconds need not be decreased)
プログラミング:ここでは2つのソリューションについて説明します.
1)集計ソート(Merge Sort)は、大量の中間ファイル(work files)を生成する
2)各整数を32ビットの整数と見なす、1 MBで約250000個の整数を記憶した後、ファイルに対して、40回input filesの内容を読み取り、クイックソート(Quicksort:A Quicksort would be quite efficient for the main-memory sorts)を利用する.これで中間ファイルはありませんが、input filesを何度も読み書きします.
実装シナリオ:
特定の問題を開始するには,いずれも整数であるため,このような格納方式でデータを格納することを考える.
たとえば{1,2,3,5,8,13}はこのような文字列で格納できます.
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
すなわち、整数nについては、n番目のビットに1と書く.
ソートの実装:ダミーコードは次のとおりです.
1 //phase 1: initialize set to empty
2 for i = [0,n)
3 bit[i] = 0
4 //phase 2: insert present elements into the set
5 for each i in the input file
6 bit[i] = 1
7 //phase 3: write sorted output
8 for i = [0,n)
9 if bit[i] == 1
10 write i on the output file(ps:私個人にとって:107のような大きな配列をどうやって開くか知りたいです.それともこんなに長い文字列ですか.これはポイントではありません...私の個人的な知識にも限りがあります)
このようなやり方は,上記の2つのスキームに比べて実現され,input fileを1回読み込んで中間ファイルを生成せず,効率の高いソートが実現された.
最後の項目
原則(Principles)
正しい問題(the right broblems)
問題を正しく定義できれば、仕事は半分になります.問題を解決する前に、よく考えてください.私たちの学生にとって問題です.明らかに上の解法は、特定のソートに対してのみ有効である:1.正の整数2.繰り返しません3.関連情報がありません.
Bitmapのデータ構造
これもデータ構造を効率的に組織する方法であり、その3つの条件を満たさなければ、いくつかの変更を行うことができ、表の項目は複雑になります.
Multiple-Pass Algorithms
A time-Space Tradeoff and One That Isn't. 時間空間の転換は,偏ってはならない.
A simple Designプログラムの設計はできるだけ簡単にしなければならない.簡単なプログラムは複雑なプログラムよりも丈夫で、高校です.
個人レベルが限られているので、内容の理解はここまでです.分からないことが多いので、後で補充しましょう.の