прикреплённый файл:sort_tape.py к странице LecturesVMSH/2012-02-08

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 «Сортировка магнитных лент». Дан файл («магнитная лента»), содержащий строки, одновременно не умещающиеся в памяти. Требуется отсортировать этот файл построчно (записать отсортированные данные обратно на эту ленту). Для сортировки разрешается открывать небольшое число дополнительных файлов произвольного размера (использовать небольшое число дополнительных «лент»). Вот алгоритм с четырьмя лентами. Назовём отрезком упорядоченную последовательность строк на ленте. При записи отрезка на ленту применяется специальный маркер-разделитель. Сначала разобьем исходную ленту на отрезки и перепишем их на первую вспомогательную ленту. Затем перепишем первые два отрезка на две временные ленты и сольём их в один, добавив на вторую вспомогательную ленту. Повторим процесс, пока все отрезки не кончатся (если остался один, просто допишем его). Поменяем вспомогательные ленты местами. Повторим процесс слияния отрезков до тех пор, пока на ленте-приёмнике не окажется ровно один отрезок. Это и будут отсортированные данные. Перепишем содержимое отрезка на исходную ленту.
   5 '''
   6 
   7 import os, sys, pickle
   8 
   9 NEXT,LAST=True,False
  10 
  11 def joinfile(N1,N2,f):
  12     '''Слить два отсортированных файла с именами N1 и N2 в файл-с-отрезками f'''
  13     f1,f2=file(N1),file(N2)
  14     s1,s2=f1.readline(),f2.readline()
  15     while s1 and s2:
  16         if s1<s2: 
  17             pickle.dump(s1,f)
  18             s1=f1.readline()
  19         else:
  20             pickle.dump(s2,f)
  21             s2=f2.readline()
  22     while s1:
  23         pickle.dump(s1,f)
  24         s1=f1.readline()
  25     while s2:
  26         pickle.dump(s2,f)
  27         s2=f2.readline()
  28 
  29 def slice(name,sname):
  30     '''Превратить файл в файл-с-отрезками.
  31     Вернуть количество отрезков'''
  32     old, N, F = "", 1, file(sname,"w")
  33     for s in file(name):
  34         if s<old:
  35             pickle.dump(NEXT,F)
  36             N+=1
  37         pickle.dump(s,F)
  38         old = s
  39     pickle.dump(NEXT,F)
  40     if N%2 and N>1:     # отрезков должно быть чётное число
  41         pickle.dump(NEXT,F)
  42     pickle.dump(LAST,F)    # последний отрезок
  43     F.close()
  44     return N
  45 
  46 def pour(inflow,Name):
  47     '''Перелить отрезок в файл'''
  48     F=open(Name,"w")
  49     s=pickle.load(inflow)
  50     while type(s) is str:
  51         F.write(s)
  52         s=pickle.load(inflow)
  53     F.close()
  54     return s
  55 
  56 def jointsort(name):
  57     '''Сортировка слиянием с использованием четырёх дополнтельных файлов'''
  58     In, Out, Name1, Name2 = name+".in", name+".out", name+".1", name+".2"
  59     N=slice(name,Out)
  60     while N>1:
  61         os.rename(Out,In)
  62         FIn, FOut, N = file(In,"r"), file(Out,"w"), 0
  63         while pour(FIn,Name1) and pour(FIn,Name2):
  64             joinfile(Name1,Name2,FOut)
  65             N+=1
  66             pickle.dump(NEXT,FOut)
  67         if N%2 and N>1: pickle.dump(NEXT,FOut)
  68         pickle.dump(LAST,FOut)
  69         FOut.close()
  70     F=file(Out,"r")
  71     pour(F,name)
  72     for n in In, Out, Name1, Name2:
  73         os.unlink(n)
  74 
  75 if len(sys.argv)>1: # Задано имя входного файла — сортировщик
  76     jointsort(sys.argv[1])
  77 else:               # Генератор
  78     import random
  79     alp="qazwsxedcrfvtgbyhnujmikolp        "
  80     def linegen():
  81         return "".join((random.choice(alp) for i in xrange(random.randint(10,30)))).capitalize()
  82     out=[ l for j in xrange(random.randint(100,200)) for l in [linegen()] for i in xrange(random.choice((1,1,1,1,1,1,1,2,3,4,5))) ]
  83     random.shuffle(out)
  84     for l in out:
  85         print l