選択した言語でコード例を提供してください。
更新：外部ストレージに制約は設定されていません。
例：整数はネットワークを介して送受信されます。中間結果のためにローカルディスクに十分なスペースがあります。
31849 次
10 に答える
18
問題を利用可能なメモリに収まるほど小さい部分に分割し、マージソートを使用してそれらを結合します。
于 2008-09-25T15:57:14.457 に答える
11
于 2008-10-23T07:38:20.207 に答える
4
100万個の32ビット整数=4MBのメモリ。
外部ストレージを使用するアルゴリズムを使用してそれらをソートする必要があります。たとえば、マージソート。
于 2008-09-25T15:55:35.100 に答える
4
より多くの情報を提供する必要があります。どのような追加のストレージが利用可能ですか？結果をどこに保存しますか？
それ以外の場合、最も一般的な答えは次のとおりです。1.データの最初の半分をメモリ（2MB）にロードし、任意の方法で並べ替えて、ファイルに出力します。2.データの後半をメモリ（2MB）にロードし、任意の方法で並べ替え、メモリに保持します。3.マージアルゴリズムを使用して、2つの並べ替えられた半分をマージし、完全な並べ替えられたデータセットをファイルに出力します。
于 2008-09-25T15:57:52.847 に答える
3
外部ソートに関するこのウィキペディアの記事には、役立つ情報がいくつかあります。
于 2008-09-25T16:38:14.327 に答える
1
#!/usr/bin/env python
import random
from sort import Pickle, Polyphase
nrecords = 1000000
available_memory = 2000000 # number of bytes
#NOTE: it doesn't count memory required by Python interpreter
record_size = 24 # (20 + 4) number of bytes per element in a Python list
heap_size = available_memory / record_size
p = Polyphase(compare=lambda x,y: cmp(y, x), # descending order
file_maker=Pickle,
verbose=True,
heap_size=heap_size,
max_files=4 * (nrecords / heap_size + 1))
# put records
maxel = 1000000000
for _ in xrange(nrecords):
p.put(random.randrange(maxel))
# get sorted records
last = maxel
for n, el in enumerate(p.get_all()):
if el > last: # elements must be in descending order
print "not sorted %d: %d %d" % (n, el ,last)
break
last = el
assert nrecords == (n + 1) # check all records read
于 2008-09-25T18:33:12.380 に答える
0
- ええと、それらをすべてファイルに保存します。
- ファイルをメモリ マップします (RAM は 2M しかないと言っていましたが、アドレス空間がファイルをメモリ マップするのに十分な大きさであると仮定しましょう)。
- ファイル バッキング ストアを使用して、実際のメモリであるかのように並べ替えます。
于 2009-02-12T08:09:50.283 に答える
0
これが有効で楽しい解決策です。
数字の半分をメモリにロードします。それらを適切な場所にヒープソートし、出力をファイルに書き込みます。残りの半分についても繰り返します。外部ソート (基本的にはファイル I/O を考慮したマージソート) を使用して、2 つのファイルをマージします。
余談: 遅い外部ストレージに直面して、ヒープのソートを高速化します。
すべての整数がメモリに格納される前に、ヒープの構築を開始します。
ヒープソートがまだ要素を抽出している間に、整数を出力ファイルに戻し始めます
于 2013-01-16T05:43:37.217 に答える
-2
上記の人々が言及しているように、32ビット4MBのintを入力します。
C ++でint、short、char型を使用して、できるだけ多くの「数値」をできるだけ少ないスペースに収めます。あらゆる場所に何かを詰め込むためにいくつかのタイプのキャストを行うことで、巧妙になる可能性があります（ただし、奇妙な汚いコードがあります）。
ここは私の席の端から外れています。
2 ^ 8（0〜255）未満のものはすべて、char（1バイトのデータ型）として格納されます。
2 ^ 16（256〜65535）未満で2 ^ 8を超えるものはすべて、short（2バイトのデータ型）として格納されます。
残りの値はintに入れられます。（4バイトのデータ型）
charセクションの開始位置と終了位置、shortセクションの開始位置と終了位置、およびintセクションの開始位置と終了位置を指定する必要があります。
于 2008-09-25T16:28:46.127 に答える
-3
例はありませんが、バケットソートは比較的複雑さが低く、実装が簡単です。
于 2008-09-25T20:28:13.900 に答える