прикреплённый файл:2013-04-19.halffile.py к странице LecturesVMSH/Python/2013-04-19

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Поиск методом половинного деления строки, начинающейся с заданной подстроки
   5 в сортированном строковом файле
   6 '''
   7 
   8 def search(word, filename):
   9     '''Поиск методом половинного деления в сортированном файле filename
  10     строк, начинающихся с word'''
  11     # TODO файлы с малым числом строк
  12     F=open(filename)
  13     F.seek(0,2)         # конец файла
  14     size=F.tell()
  15     pos,offset,direction=size/2,size/2,1
  16     while offset:
  17         F.seek(pos)
  18         F.readline()        # предположительно неполная строка
  19         s1,s2=F.readline(),F.readline()
  20         if s1 >= word or not s1:
  21             # искомые (или вообще все) строки начинаются раньше
  22             direction=-1
  23         elif s2.startswith(word):
  24             # s2 — первая из искомых строк
  25             while s2.startswith(word):
  26                 sys.stdout.write(s2)
  27                 s2=F.readline()
  28             break
  29         elif not s2 or s2>word:
  30             # конец файла или следующая строка уже больше
  31             break
  32         else:
  33             # s1 и s2 меньше word
  34             direction=1
  35         offset/=2
  36         pos+=offset*direction
  37 
  38 def dumbsearch(word, filename):
  39     '''Поиск методом последовательноого сравнения в файле filename
  40     строк, начинающихся с word'''
  41     F=open(filename)
  42     for s in F:
  43         if s.startswith(word):
  44             sys.stdout.write(s)
  45 
  46 import sys
  47 if len(sys.argv)>3:     # лишний параметр, ищем по-простому
  48     dumbsearch(sys.argv[1],sys.argv[2])
  49 else:
  50     search(sys.argv[1],sys.argv[2])