прикреплённый файл:sort_file.py к странице LecturesVMSH/2012-01-25

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Дан очень длинный файл. Отсортировать его построчно. Условие:
   5  запрещено хранить все данные из файла целиком в памяти, зато разрешено хранить
   6 промежуточные файлы и переписывать исходный файл.
   7 '''
   8 
   9 import os, sys
  10 
  11 def joinfile(f1,f2,f):
  12     '''Слить два отсортированных файла f1 и f2 в файл f'''
  13     s1,s2=f1.readline(),f2.readline()
  14     while s1 and s2:
  15         if s1 and s1<s2: 
  16             f.write(s1)
  17             s1=f1.readline()
  18             continue
  19         if s2 and s2<s1:
  20             f.write(s2)
  21             s2=f2.readline()
  22             continue
  23     while s1:
  24         f.write(s1)
  25         s1=f1.readline()
  26     while s2:
  27         f.write(s2)
  28         s2=f2.readline()
  29 
  30 def newfile(L,N,mode):
  31     '''Открыть новый файл с именем, вычисляемым из L и N'''
  32     return open("{0}_{1}".format(L,N),mode)
  33 
  34 def addempty(L,N):
  35     '''Добавить N+1й пустой файл'''
  36     out=newfile(L,N+1,"w")
  37     out.close()
  38     return N+1
  39 
  40 def slice(name,prefix):
  41     '''Разбить файл f в упорядоченные файлы с именами prefixN,
  42     вернуть N — количество файлов'''
  43     old, N, = "", 0
  44     F=newfile(prefix,N,"w")
  45     for s in file(name):
  46         if s<old:
  47             F.close()
  48             N+=1
  49             F=newfile(prefix,N,"w")
  50         F.write(s)
  51         old = s
  52     F.close()
  53     return N
  54 
  55 def junksort(name):
  56     '''Вариант с огромным количеством файлов (до N)'''
  57 
  58     # Разбиваем на отрезки
  59     N=slice(name,0)
  60     # отрезков должно быть чётное число
  61     if N%2 == 0: N=addempty(0,N)
  62     # Сливаем отрезки попарно, пока их > 1
  63     L=0
  64     while N>0:
  65         for i in xrange(0,N,2):
  66             F1=newfile(L,i,"r")
  67             F2=newfile(L,i+1,"r")
  68             F=newfile(L+1,i/2,"w")
  69             joinfile(F1,F2,F)
  70             F1.close(); os.unlink(F1.name)
  71             F2.close(); os.unlink(F2.name)
  72             F.close()
  73         N/=2
  74         if N>0 and N%2 == 0: N=addempty(L+1,N)
  75         L+=1
  76     return F.name
  77 
  78 outname=junksort(sys.argv[1])
  79 os.rename(outname,(sys.argv[1]))