search.py

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