Clever Geek Handbook

Pythonで2メガバイトのメモリで100万個の32ビット整数をソートする

Guido van Rossumの記事の私の翻訳：



Pythonでは、100万個の32ビットintを2メガバイトのメモリにソートできるかどうかを冗談で尋ねられました。 考えながら、バッファメモリを使用したI / Oメカニズムを使用するようになりました。



一般的に、これは単なる漫画の質問です-バイナリ表現を前提として、データのみが4メガバイトを占有します！ 確かに、あなたはトリックのために行くことができます-100万の32ビットintを含むファイルを取ります。 最小量のメモリを使用してそれらをソートする方法は？ 何らかの種類のマージソートを行う必要があります。このソートでは、小さなデータがソートされて一時ファイルに書き込まれ、その後、一時ファイルがマージされて最終結果が得られます。



ここに私の解決策があります：



Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  1. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  2. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  3. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  5. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  6. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  7. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  8. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  9. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  10. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  11. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  12. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  14. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  15. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  16. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  17. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  18. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  19. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  20. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  21. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  22. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  23. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  25. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  26. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  27. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  28. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  29. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  30. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  31. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)



  32. Copy Source | Copy HTML #!/usr/bin/env python3.0 import sys, array, tempfile, heapq assert array . array ( 'i' ).itemsize == 4 def intsfromfile (f): while True: a = array . array ( 'i' ) a.fromstring(f.read( 4000 )) if not a: break for x in a: yield x iters = [] while True: a = array . array ( 'i' ) a.fromstring( sys .stdin.buffer.read( 40000 )) if not a: break f = tempfile .TemporaryFile() array . array ( 'i' , sorted (a)).tofile(f) f.seek( 0 ) iters.append( intsfromfile (f)) a = array . array ( 'i' ) for x in heapq .merge(*iters): a.append(x) if len (a) >= 1000 : a.tofile( sys .stdout.buffer) del a[:] if a: a.tofile( sys .stdout.buffer)





3年前のLinuxベースのスタッフでは、100万個のランダムな32ビット整数を含む入力ファイルからデータを読み取るのに5.4秒かかりました。 メモリから直接データを読み取る場合、ソートに2秒かかることを考えると、これはそれほど悪くありません。



Copy Source | Copy HTML



  1. ＃！/ usr / bin / env python3.0
  2. インポート sys、配列
  3. a = 配列 。 配列 （ 'i' 、 sys .stdin.buffer.read（））
  4. a = リスト （a）
  5. a.sort（）
  6. a = 配列 。 配列 （ 'i' 、a）
  7. a.tofile（ sys .stdout.buffer）


ソートに戻りましょう。 最初の3行は明らかです。



Copy Source | Copy HTML



  1. ＃！/ usr / bin / env python3.0
  2. sys、配列、tempfile、heapqをインポートします
  3. 配列を アサートします。 配列 （ 'i' ）.itemsize == 4


最初の行は、Python 3.0を使用していることを示しています。 2行目は必要なモジュールをインポートします。 3行目では、64ビットシステムで割り込みが発生します。intは32ビットではありません-移植可能なコードを書く仕事はありませんでした。



次に、ファイルからintを読み取る関数を宣言しました。



Copy Source | Copy HTML



  1. def intsfromfile （f）：
  2. Trueの場合：
  3. a = 配列 。 配列 （ 'i' ）
  4. a.fromstring（f.read（ 4000 ））
  5. そうでない場合 ：
  6. 破る
  7. aのxに対して：
  8. 収量 x


これは、アルゴリズムの最適化が行われる場所です。一度に最大1000のintを読み取り、それらを1つずつ発行します。 最初は、バッファリングを使用しませんでした-この関数は、ファイルから4バイトを読み取り、整数に変換して返しました。 しかし、それは4倍遅くなりました！ ファイルに十分なデータがない場合はfromfile()



メソッドがエラーを返すのでa.fromfile(f, 1000)



使用できないことに注意してください。また、ファイル内の任意の数のintにコード自体を適合させたいと考えました。



次は入力ループです。 入力ファイルから10'000 intの断片を周期的に読み取り、メモリ内でソートして一時ファイルに書き込みます。 次に、上記のintsfromfile（）関数を使用して、最終段階で必要になるイテレーターのリストに一時ファイルのイテレーターを追加します。



Copy Source | Copy HTML



  1. iters = []
  2. Trueの場合：
  3. a = 配列 。 配列 （ 'i' ）
  4. a.fromstring（ sys .stdin.buffer.read（ 40000 ））
  5. そうでない場合 ：
  6. 破る
  7. f = tempfile .TemporaryFile（）
  8. 配列 配列 （ 'i' 、 ソート済み （a））。tofile（f）
  9. f.seek（ 0 ）
  10. iters.append（intsfromfile（f））


したがって、入力された100万intに対して、それぞれ10,000個の値を持つ100個の一時ファイルが作成されます。



最後に、これらすべてのファイル（各ファイルは既にソートされています）をマージします。 heapqモジュールには、この問題を解決するための素晴らしい関数が含まれています： heapq.merge(iter1, iter2, ... )



、各入力パラメーター自体が目的の順序で値を渡すシーケンスで入力パラメーターをスキップするイテレーターを返します（このように）ケース）。



Copy Source | Copy HTML



  1. a = 配列 。 配列 （ 'i' ）
  2. heapq .mergeのxの場合（* iters）：
  3. a.append（x）
  4. len （a）> = 1000の場合 ：
  5. a.tofile（ sys .stdout.buffer）
  6. デル [：]
  7. 場合 ：
  8. a.tofile（ sys .stdout.buffer）


これは、バッファリングされた入力/出力が必要なもう1つのケースです。個々の値をファイルに書き込むと、使用可能になり次第、アルゴリズムの速度が半分になります。 入力と出力でバッファリングを使用して、実行速度を10倍に上げることができました！


More articles:


All Articles