search.py

   1 from itertools import product, chain
   2 import resource
   3
   4 from exc import IncompatibleUnits, MemExceeded
   5
   6 def search(base_numbers, ops, cc, max_round=None, mem_limit=2*1024**2):
   7     # Round 0
   8     bf = [base_numbers]
   9     # check if measurements do not mean anything directly
  10     for m in base_numbers:
  11         cc.checkCandidate(m, verbose=True)
  12
  13     elem_count = 0
  14     final_round = max_round == 0
  15     round_count = 1
  16     try:
  17         while not final_round:
  18             final_round = max_round == round_count
  19
  20             print
  21             print "ROUND %d started"%(round_count,)
  22             print
  23             ro = []
  24             try:
  25                 for op in ops.get(round_count, ops.get('default', None)):
  26                     ar = op.getArity()
  27                     if ar >= 3:
  28                         raise NotImplementedError
  29
  30                     last = bf[-1]
  31                     sofar = list(chain(*bf))
  32
  33                     pr = [last] + [sofar]*(ar-1)
  34                     i1 = product(*pr)
  35                     i2 = ()
  36
  37                     if not op.isCommutative() and ar == 2:
  38                         i2 = product(chain(*(bf[:-1])), last)
  39
  40                     for t in chain(i1, i2):
  41                         if elem_count % 10000 == 0 and not final_round:
  42                             mem_used = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
  43                             if mem_used > mem_limit:
  44                                 print
  45                                 print "MEM EXCEEDED"
  46                                 print "Limit %.1f MB, Used %.1f MB"%(mem_limit / 1024.0, mem_used / 1024.0)
  47                                 print "FINAL ROUND FOLLOWS"
  48                                 raise MemExceeded
  49                         elem_count += 1
  50
  51                         try:
  52                             res = op(t)
  53                             # we do not need to add if we are in the final round
  54                             # we save a lot of memory this way (and may even be able to compute one more round therefore
  55                             if not final_round:
  56                                 ro.append(res)
  57                             # register the result to see improving matches incrementaly
  58                             cc.checkCandidate(res, verbose=True)
  59                         except IncompatibleUnits:
  60                             pass
  61                         except ZeroDivisionError:
  62                             pass
  63
  64             except MemExceeded:
  65                 # set the limit so that we end in the next iteration
  66                 max_round = round_count + 1
  67
  68             bf.append(ro)
  69             print
  70             print "ROUND %d ended, searched %d combinations in total"%(round_count, elem_count)
  71             print
  72
  73             round_count += 1
  74     except KeyboardInterrupt:
  75         pass
  76
  77     print
  78     print
  79     print "END"
  80     print
  81     print "Best matches:"
  82     print
  83     # show what we have found
  84     cc.printBestMatches()