document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. # -*- coding: utf-8 -*-
  2.  
  3. # Authors: João S. O. Bueno, Humberto C. Innareli
  4. # License: Creative Commons Attribution Required 3.0
  5.  
  6.  
  7. """Problema porposto por Shandler Lyrio --
  8. Idéia de Solução Humebrto Celeste Innareli
  9. Implementação: João Sebastião de Oliveira Bueno
  10.  
  11.  
  12. Problema:
  13. Dadas faixas de CEPS atendidas por diferentes distribuidores, uma busca
  14. para encontrar quais distribuidores podem atender quais CEPs
  15. çeva cerca de 1 min. para rodar com a seleção feita toda dentro do SQL,
  16. para cerca de 1500 faixas de CEP e 85000 CEPs
  17.  
  18. Solução encontrada:
  19. Ordenar os CEPs em memoria, propiciando uma busca O(log(N)) nos mesmos, e, para cada
  20. faixa de CEPs atendida, selecionar a fatia de CEPs atendida pela faixa:
  21. O(M log(N))
  22. (Em vez de para cada CEP procurar em todas as faixas para verificar se
  23. ele se enquadra dentro de seus limites -- log(N^2))
  24. """
  25.  
  26.  
  27.  
  28. import bisect
  29.  
  30. class Range(object):
  31.     total = 0
  32.     ranges = {}
  33.     def __init__(self, start, stop, value = None):
  34.         self.start = start
  35.         self.stop = stop
  36.         self.id = Range.total
  37.         self.ranges[self.id] = value
  38.         Range.total += 1
  39.    
  40.  
  41.  
  42. class Distributors(object):
  43.     def __init__(self):
  44.         self.ranges = []
  45.     def check(self, zips):
  46.         """Zips must be a sorted list of Zips"""
  47.         results = {}
  48.         for range_ in self.ranges:
  49.             first = bisect.bisect_left(zips, range_.start)
  50.             last = bisect.bisect(zips, range_.stop)
  51.             for index in xrange(first, last):
  52.                 if not zips[index] in results:
  53.                     results[zips[index]] = [range_.id]
  54.                 else:
  55.                     results[zips[index]].append(range_.id)
  56.         ungrouped = set(zips)
  57.         ungrouped.difference_update(results.keys())
  58.         return results, ungrouped
  59.     def __setitem__(self, (start, stop), value=None):
  60.         self.ranges.append(Range(start, stop, value))
  61.    
  62.     def __getitem__(self, index):
  63.         """Don\'t use this but for testing purposes -- rather call "check" with a list with all the zip codes"""
  64.         r,u = self.check([index])
  65.         if r:
  66.             return [Range.ranges[range_index] for range_index in  r[index]]
  67.         return []
  68.  
  69.  
  70. if __name__ == "__main__":
  71.     import unittest
  72.     import random
  73.     import timeit
  74.  
  75.     class TestDistributor(unittest.TestCase):
  76.  
  77.         def setUp(self):
  78.             self.dist = Distributors()
  79.             self.dist[100,120] = 1                            
  80.             self.dist[105, 115] = 2                            
  81.             self.dist[110, 110] = 3
  82.            
  83.         def testEmpty(self):
  84.             self.assertEqual(self.dist[99], [])
  85.            
  86.         def testUpperEmpty(self):
  87.             self.assertEqual(self.dist[121], [])
  88.            
  89.         def testBelonging(self):
  90.             self.assertEqual(self.dist[101],[1])
  91.            
  92.         def testLowerBoundary(self):
  93.             self.assertEqual(self.dist[100],[1])
  94.            
  95.         def testUpperBoundary(self):
  96.             self.assertEqual(self.dist[120],[1])
  97.            
  98.         def testIntersection(self):
  99.             self.assertEqual(self.dist[105],[1, 2])
  100.            
  101.         def testUnitRange(self):
  102.             self.assertEqual(self.dist[110],[1,2,3])
  103.    
  104.    
  105.     RANGES = 2000
  106.     ZIPS = 100000
  107.     class DistributorPerformance(object):
  108.  
  109.         def setUp(self):
  110.             self.dist = Distributors()
  111.             for i in xrange(RANGES):
  112.                 indx1 = random.randrange(10000000, 99999999)
  113.                 #indx2 = random.randrange(indx1, 99999999)
  114.                 indx2 = random.randrange(indx1, min(indx1 + 2000000, 99999999))
  115.                 self.dist[indx1, indx2] = i
  116.        
  117.         def zip_setup(self, numbers):
  118.             print "Building %s zip codes" % numbers
  119.             zips = []
  120.             for i in xrange(numbers):
  121.                 zips.append(random.randrange(10000000, 99999999))
  122.             zips.sort()
  123.             self.zips = zips
  124.             print "Done"            
  125.        
  126.         def testTiming(self):
  127.             r, u = self.dist.check(self.zips)
  128.             print "Total de CEPS encontrados, e CEPs sem faixa: ", len(r), len(u)
  129.  
  130.     print "Criando %s faixas de CEP" % RANGES
  131.     perf_test = DistributorPerformance()
  132.     t1 = timeit.timeit(perf_test.setUp, number=1)
  133.     print "Tempo de criação: %.2fs\\n" % t1
  134.    
  135.     print "Criando %s codigos de CEP, ordenados" % ZIPS
  136.     t2 = timeit.timeit(lambda: perf_test.zip_setup(ZIPS), number=1)
  137.     print "Tempo de criação: %.2fs\\n" % t2
  138.    
  139.     print "Executando %s buscas em %s registros de faixas" %(ZIPS, RANGES)
  140.     t3 = timeit.timeit(perf_test.testTiming, number=1)
  141.     print "Tempo de busca: %.2fs \\n" % t3
  142.     print "Tempo total: %.2fs" % (t1 + t2 + t3)
  143.     unittest.main()
');