def time_solve(grid):
     start = time.clock()
     values = solve(grid)
     t = time.clock()-start
     ## Display puzzles that take long enough
     if showif is not None and t > showif:
         display(grid_values(grid))
         if values: display(values)
         print '(%.2f seconds)\n' % t
     return (t, solved(values))

    def _recompute_path(self, map, start, end):
        pf = PathFinder(map.successors, map.move_cost, map.move_cost)
        t = time.clock()
        pathlines = list(pf.compute_path(start, end))

        dt = time.clock() - t
        if pathlines == []:
            print "No path found" 
            return pathlines
        else:
            print "Found path (length %d)" % len(pathlines)
            return pathlines

	def __init__(self, session, data, val=None):
		Screen.__init__(self, session, data)

		self.setTitle(_("EMC Cover Selecter"))

		self["actions"] = HelpableActionMap(self, "EMCimdb",
		{
			"EMCEXIT":	self.exit,
			#"green":	self.keySave,
			#"cancel":	self.keyClose,
			"EMCOK":	self.ok,
		}, -1)

		(title, o_path) = data.pop()
		self.m_title = title
		self["m_info"] = Label(("%s") % self.m_title)
		self.o_path = o_path
		self.menulist = []
		self["menulist"] = imdblist([])
		self["poster"] = Pixmap()
		self["info"] = Label(_("Searching for %s") % self.m_title)
		self["menulist"].onSelectionChanged.append(self.showInfo)
		self.check = "false"
		self.path = "/tmp/tmp.jpg"
		self.cover_count = 0
		self.einzel_start_time = time.clock()
		self.einzel_elapsed = time.clock()
		self.einzel_end_time = time.clock()

		self.picload = ePicLoad()
		#self.picload_conn = self.picload.PictureData.connect(self.showCoverCallback)

		self["info"].setText((_("found") + " %s " + _("covers")) % (self.cover_count))
		if val is not None:
			if val == "0":
				self.searchCover(self.m_title)
			elif val == "2":
				self.searchcsfd(self.m_title)
			elif val == "3":
				self.searchcsfd(self.m_title)
				self.searchtvdb(self.m_title)
				self.searchCover(self.m_title)
		else:
			if config.EMC.imdb.singlesearch.value == "0":
				self.searchCover(self.m_title)
			elif config.EMC.imdb.singlesearch.value == "1":
				self.searchtvdb(self.m_title)
			elif config.EMC.imdb.singlesearch.value == "2":
				self.searchcsfd(self.m_title)
			elif config.EMC.imdb.singlesearch.value == "3":
				self.searchcsfd(self.m_title)
				self.searchtvdb(self.m_title)
				self.searchCover(self.m_title)

def get_performance_sort():
    """Get performance"""
    scores = {}
    trial = 1
    while trial <= 16:
        numbers = [random.randint(1,9) for i in range(2**trial)]
        now = time.clock()
        numbers.sort()
        done = time.clock()
        scores[trial] = (done-now)
        trial = trial + 1
    for i in scores:
        print("%d\t%f" %(2**i,scores[i]))

def get_performance_sum():
    """Calculating """
    scores = {}
    trial = 1
    while trial <= 16:
        numbers = [random.randint(1,9) for i in range(2**trial)]
        now = time.clock()
        sum = 0
        for d in numbers:
            sum = sum + d
        done = time.clock()
        scores[trial] = (done-now)
        trial = trial + 1
    for i in scores:
        print("%d\t%f" %(2**i,scores[i]))

	def showCovers(self, data, title):
		print "EMB iMDB: Cover Select - %s" % title
		#print data
		bild = re.findall('<img src="http://ia.media-imdb.com/images/(.*?)".*?<a href="/title/(.*?)/".*?">(.*?)</a>.*?\((.*?)\)', data, re.S)
		if bild:
			for each in bild:
				#print self.cover_count
				self.cover_count = self.cover_count + 1
				imdb_title = each[2]
				imdb_url = each[0]
				imdb_url = re.findall('(.*?)\.', imdb_url)
				extra_imdb_convert = "._V1_SX320.jpg"
				imdb_url = "http://ia.media-imdb.com/images/%s%s" % (imdb_url[0], extra_imdb_convert)

				self.menulist.append(showCoverlist(imdb_title, imdb_url, self.o_path, "imdb: "))
		else:
			self["info"].setText(_("Nothing found for %s") % title)
			print "EMC iMDB: keine infos gefunden - %s" % title

		self["menulist"].l.setList(self.menulist)
		self["menulist"].l.setItemHeight(28)
		self.search_check += 1

		#if not config.EMC.imdb.singlesearch.value == "3":
		self.check = "true"
		self.showInfo()
		self.einzel_end_time = time.clock()
		self.einzel_elapsed = (self.einzel_end_time - self.einzel_start_time)
		self["info"].setText(_("found %s covers in %.1f sec") % (self.cover_count, self.einzel_elapsed))

	def search_done(self):
		#if self.search_check == "2":
		self.check = "true"
		self.showInfo()
		self.einzel_end_time = time.clock()
		self.einzel_elapsed = (self.einzel_end_time - self.einzel_start_time)
		self["info"].setText(_("found %s covers in %.1f sec") % (self.cover_count, self.einzel_elapsed))

 def __init__(self, message='Download', printf = _print):
     import time
     from collections import deque
     self.start = time.clock()
     self.message = message
     self.rates = deque(maxlen=10)
     self.printf = printf

    def progress(self, i, n):

        import time
        now = time.clock()

        if not self.last:
            self.last = now

        if now - self.last > self.freq:
            diff = now - self.start
            self.last = now

            i_rate = float(i)/diff
            self.rates.append(i_rate)
            
            if len(self.rates) > self.rates.maxlen/2:
                rate = sum(self.rates) / len(self.rates)
                rate_type = 'a'
            else:
                rate = i_rate
                rate_type = 'i'

            self.printf("{}: Compressed: {} Mb. Downloaded, Uncompressed: {:6.2f}  Mb, {:5.2f} Mb / s ({})".format(
                 self.message,int(int(n)/(1024*1024)),
                 round(float(i)/(1024.*1024.),2), 
                 round(float(rate)/(1024*1024),2), rate_type))

	def search_done(self):
		self["menulist"].l.setList(self.menulist)
		self["menulist"].l.setItemHeight(image())
		self.check = "true"
		self.showInfo()
		self.einzel_end_time = time.clock()
		self.einzel_elapsed = (self.einzel_end_time - self.einzel_start_time)
		self["info"].setText((_("found") + " %s " + _("covers in") + " %.1f " + _("sec")) % (self.cover_count, self.einzel_elapsed))

 def stop(self):
     """Stop the measurement process.
     
     Arguments:
     - `self`:
     """
     self.stop_time = time.time()
     self.stop_clock = time.clock()
     pass

 def start(self):
     """Start the meaurement process.
     
     Arguments:
     - `self`:
     """
     self.start_time = time.time()
     self.start_clock = time.clock()
     pass

	def showCovers_csfd(self, data, title):
		bild = re.findall('<img src=\"(//img.csfd.cz/files/images/film/posters/.*?)\".*?<h3 class="subject"><a href="(.*?)" class="film c.">(.*?)</a>.*?</li>', data, re.DOTALL | re.IGNORECASE)
		if bild:
			for each in bild:
				print "EMC csfd: Cover Select - %s" % title
				self.cover_count = self.cover_count + 1
				csfd_title = each[2]
				csfd_detail_url = "http://www.csfd.cz" + each[1]
				print "csfd_detail_url: %s" % csfd_detail_url
				csfd_url = "http:" + each[0]
				print "csfd_url: %s" % csfd_url
				self.menulist.append(showCoverlist(csfd_title, csfd_url, self.o_path, 'csfd: '))
				self.searchcsfd_detail(csfd_detail_url, csfd_title)
		else:
			title_s = re.findall('<title>(.*?)\|', data, re.S)
			if title_s:
				csfd_title = title_s[0]
				print "EMC iMDB csfd: Movie found - %s" % csfd_title
			else:
				csfd_title = title
			bild = re.findall('<img src="(//img.csfd.cz/files/images/film/posters/.*?)" alt="poster"', data, re.DOTALL | re.IGNORECASE)
			if bild:
				print "EMC iMDB csfd: Cover Select - %s" % title
				self.cover_count = self.cover_count + 1
				csfd_url = "http:" + bild[0].replace('\\','').strip()
				print "csfd_url: %s" % csfd_url
				self.menulist.append(showCoverlist(csfd_title, csfd_url, self.o_path, "csfd: "))
				bild = re.findall('<h3>Plak.*?ty</h3>(.*?)</table>', data, re.S)
				if bild:
					bild1 = re.findall('style=\"background-image\: url\(\'(.*?)\'\)\;', bild[0], re.DOTALL | re.IGNORECASE)
					if bild1:
						for each in bild1:
							print "EMC iMDB - csfd: Cover Select - %s" % title
							self.cover_count = self.cover_count + 1
							csfd_url = "http:" + each.replace('\\','').strip()
							print "csfd_url: %s" % csfd_url
							self.menulist.append(showCoverlist(csfd_title, csfd_url, self.o_path, "csfd: "))
					else:
						print "EMC iMDB csfd 3 : no else covers - %s" % title
				else:
					print "EMC iMDB csfd 2 : no else covers - %s" % title
			else:
				print "EMC iMDB csfd 1 : keine infos gefunden - %s" % title

		self["menulist"].l.setList(self.menulist)
		self["menulist"].l.setItemHeight(28)
		self.search_check += 1
		if not config.EMC.imdb.singlesearch.value == "3":		
			self.check = "true"
			self.showInfo()
			self.einzel_end_time = time.clock()
			self.einzel_elapsed = self.einzel_end_time - self.einzel_start_time
			self["info"].setText(("found %s covers in %.1f sec") % (self.cover_count, self.einzel_elapsed))

	def display_download(self, movie_title, search_title, path):
		self.counter += 1
		self.counter_download = self.counter_download + 1
		self.end_time = time.clock()
		elapsed = (self.end_time - self.start_time) * 10
		self.count = _("%s: %s von %s") % (self.showSearchSiteName, self.counter, self.count_movies)
		self["info"].setText(self.count)
		self["m_info"].setText(movie_title)
		self["download"].setText(_("Download: %s") % str(self.counter_download))
		self.menulist.append(imdb_show(movie_title, path, str(elapsed), "", search_title))
		self["menulist"].l.setList(self.menulist)
		self["menulist"].l.setItemHeight(28)
		if self.count_movies == self.counter:
			self.check = "true"
			self.init_ende()

	def imdb(self):
		if self.running == "true":
			print "EMC iMDB: Search already Running."

		elif self.running == "false":
			print "EMC iMDB: Search started..."
			self["done_msg"].show()
			self.no_cover()
			self.running = "true"
			self.counter = 0
			self.counter2 = 0
			self.counter3 = 0
			self.counter_download = 0
			self.counter_exist = 0
			self.counter_no_poster = 0
			self.t_elapsed = 0
			self.menulist = []
			self.count_movies = len(self.m_list)
			self["exist"].setText(_("Exist: %s") % "0")
			self["no_poster"].setText(_("No Cover: %s") % "0")
			self["download"].setText(_("Download: %s") % "0")
			self["done_msg"].setText(_("Searching..."))
			self.counter_a = 0
			self.starttime = 0
			self.t_start_time = time.clock()
			self.s_supertime = time.time()
			self.cm_list = self.m_list[:]
			self.search_list = []
			self.exist_list = []
			self.check = "false"
			self["done_msg"].setText(_("Creating Search List.."))
			for each in sorted(self.cm_list):
				(title, path) = each
				path = re.sub(self.file_format + "$", '.jpg', path)
				if os.path.exists(path):
					self.counter2 += 1
					print "EMC iMDB: Cover vorhanden - %s" % title
					self.display_exist(title, path)
				else:
					elem2 = (title, path)
					self.search_list.append(elem2)

			#print "exist:", self.exist_list
			#print "search:", self.search_list
			self.imdb_start()

	def __init__(self, session, data):
		Screen.__init__(self, session, data)

		self["actions"] = HelpableActionMap(self, "EMCimdb",
		{
			"EMCEXIT":	self.exit,
			#"green":	self.keySave,
			#"cancel":	self.keyClose,
			"EMCOK":	self.ok,
		}, -1)

		(title, o_path) = data.pop()
		self.title = title
		self.o_path = o_path
		self.menulist = []
		self["menulist"] = imdblist([])
		self["poster"] = Pixmap()
		self["info"] = Label(_("Searching for %s") % self.title)
		self["menulist"].onSelectionChanged.append(self.showInfo)
		self.check = "false"
		self.path = "/tmp/tmp.jpg"
		self.cover_count = 0
		self.search_check = 0
		self.einzel_start_time = time.clock()
		
		self.picload = ePicLoad()
		#self.picload.PictureData.get().append(self.showCoverCallback)
		
		if config.EMC.imdb.singlesearch.value == "0":
			self.searchCover(self.title)
			#self.search_done()
		
		if config.EMC.imdb.singlesearch.value == "1":
			self.searchtvdb(self.title)
			#self.search_done()
		
		if config.EMC.imdb.singlesearch.value == "2":
			self.searchcsfd(self.title)
			#self.search_done()
		
		if config.EMC.imdb.singlesearch.value == "3":
			self.searchcsfd(self.title)
			self.searchtvdb(self.title)
			self.searchCover(self.title)

	def showCovers_tvdb(self, data, title):
		bild = re.findall('<poster>(.*?)</poster>', data)
		if bild:
			print "EMB iMDB: Cover Select - %s" % title
			self.cover_count = self.cover_count + 1
			print "http://www.thetvdb.com/banners/_cache/%s" % bild[0]
			tvdb_url = "http://www.thetvdb.com/banners/_cache/%s" % bild[0]
			print "bild:", tvdb_url
			self.menulist.append(showCoverlist(title, tvdb_url, self.o_path, "tvdb: "))
		else:
			#self["info"].setText(_("Nothing found for %s") % title)
			print "EMC iMDB tvdb: keine infos gefunden - %s" % title

		self["menulist"].l.setList(self.menulist)
		self["menulist"].l.setItemHeight(28)
		self.search_check += 1 
		if not config.EMC.imdb.singlesearch.value == "3":		
			self.check = "true"
			self.showInfo()
			self.einzel_end_time = time.clock()
			self.einzel_elapsed = (self.einzel_end_time - self.einzel_start_time)
			self["info"].setText(_("found %s covers in %.1f sec") % (self.cover_count, self.einzel_elapsed))

	def parseWebpage(self, data, type, title, url, cover_path, season, episode):
		self.counting += 1
		self.start_time = time.clock()
		if type == "movie":
			list = []
			list = re.findall('original_title":"(.*?)".*?"poster_path":"(.*?)"', data, re.S)
			if list:
				purl = "http://image.tmdb.org/t/p/%s%s" % (config.EMC.imdb.themoviedb_coversize.value, list[0][1])
				self.counter_download += 1
				self.end_time = time.clock()
				elapsed = (self.end_time - self.start_time) * 10
				self.menulist.append(imdb_show(title, cover_path, str(elapsed), "", title))
				if not fileExists(cover_path):
					downloadPage(purl, cover_path).addErrback(self.dataError)
			else:
				self.counter_no_poster += 1
				self.menulist.append(imdb_show(title, cover_path, _("N/A"), "", title))

			# get description
			if config.EMC.imdb.savetotxtfile.value:
				idx = []
				idx = re.findall('"id":(.*?),', data, re.S)
				if idx:
					iurl = "http://api.themoviedb.org/3/movie/%s?api_key=8789cfd3fbab7dccf1269c3d7d867aff&language=de" % idx[0]
					getPage(iurl, headers={'Content-Type':'application/x-www-form-urlencoded'}).addCallback(self.getInfos, id, type, cover_path).addErrback(self.dataError)

		elif type == "serie":
			list = []
			list = re.findall('<seriesid>(.*?)</seriesid>', data, re.S)
			if list:
				purl = "http://www.thetvdb.com/banners/_cache/posters/%s-1.jpg" % list[0]
				#self.guilist.append(((cleanTitle, True, filename),))
				self.counter_download += 1
				self.end_time = time.clock()
				elapsed = (self.end_time - self.start_time) * 10
				self.menulist.append(imdb_show(title, cover_path, str(elapsed), "", title))
				if not fileExists(cover_path):
					downloadPage(purl, cover_path).addErrback(self.dataError)

				# get description
				if config.EMC.imdb.savetotxtfile.value:
					if season and episode:
						iurl = "http://www.thetvdb.com/api/2AAF0562E31BCEEC/series/%s/default/%s/%s/de.xml" % (list[0], str(int(season)), str(int(episode)))
						getPage(iurl, headers={'Content-Type':'application/x-www-form-urlencoded'}).addCallback(self.getInfos, id, type, cover_path).addErrback(self.dataError)
			else:
				self.counter_no_poster += 1
				self.menulist.append(imdb_show(title, cover_path, _("N/A"), "", title))

		self.count = ("%s: %s " + _("from") + " %s") % (self.showSearchSiteName, self.counting, self.count_total)
		self["info"].setText(self.count)
		self["no_poster"].setText(_("No Cover: %s") % str(self.counter_no_poster))
		self["exist"].setText(_("Exist: %s") % str(self.counter_exist))
		self["download"].setText(_("Download: %s") % str(self.counter_download))
		self["menulist"].l.setList(self.menulist)
		self["menulist"].l.setItemHeight(image())
		self.check = True

		if self.counting == self.count_total:
			self.e_supertime = time.time()
			total_time = self.e_supertime - self.s_supertime
			avg = (total_time / self.count_total)
			self.done = ("%s " + _("movies in") + " %.1f " + _("sec found. Avg. Speed:") + " %.1f " + _("sec.")) % (self.count_total, total_time, avg)
			self["done_msg"].setText(self.done)
			self.running = False

	def imdb(self):
		if self.running:
			print "EMC iMDB: Search already Running."

		elif not self.running:
			print "EMC iMDB: Search started..."
			self["done_msg"].show()
			self.no_cover()
			self.running = True
			self.counter_download = 0
			self.counter_exist = 0
			self.counter_no_poster = 0
			self.t_elapsed = 0
			self.menulist = []
			self.count_movies = len(self.m_list)
			self["exist"].setText(_("Exist: %s") % "0")
			self["no_poster"].setText(_("No Cover: %s") % "0")
			self["download"].setText(_("Download: %s") % "0")
			self["done_msg"].setText(_("Searching..."))
			self.starttime = 0
			self.t_start_time = time.clock()
			self.s_supertime = time.time()
			self.cm_list = self.m_list[:]
			self.search_list = []
			self.exist_list = []
			self.check = False
			self["done_msg"].setText(_("Creating Search List.."))
			self.counting = 0
			self.count_total = len(self.cm_list)
			urls = []
			for each in sorted(self.cm_list):
				(title, path) = each
				cover_path = re.sub(self.file_format + "$", '.jpg', path)
				if os.path.exists(cover_path):
					self.counter_exist += 1
					self.counting += 1
					self.menulist.append(imdb_show(title, cover_path, _("Exist"), "", title))
					self["m_info"].setText(title)
					self["no_poster"].setText(_("No Cover: %s") % str(self.counter_no_poster))
					self["exist"].setText(_("Exist: %s") % str(self.counter_exist))
					self["download"].setText(_("Download: %s") % str(self.counter_download))
					self["menulist"].l.setList(self.menulist)
					self["menulist"].l.setItemHeight(image())
					self.check = True
					print "EMC iMDB: Cover vorhanden - %s" % title
				else:
					filename = path
					title = getMovieNameWithoutPhrases(getMovieNameWithoutExt(title))
					if re.search('[Ss][0-9]+[Ee][0-9]+', title) is not None:
						season = None
						episode = None
						seasonEpisode = re.findall('.*?[Ss]([0-9]+)[Ee]([0-9]+)', title, re.S|re.I)
						if seasonEpisode:
							(season, episode) = seasonEpisode[0]
						name2 = re.sub('[Ss][0-9]+[Ee][0-9]+.*[a-zA-Z0-9_]+','', title, flags=re.S|re.I)
						url = 'http://thetvdb.com/api/GetSeries.php?seriesname=%s&language=de' % name2.replace(' ','%20')
						urls.append(("serie", title, url, cover_path, season, episode))
					else:
						url = 'http://api.themoviedb.org/3/search/movie?api_key=8789cfd3fbab7dccf1269c3d7d867aff&query=%s&language=de' % title.replace(' ','%20')
						urls.append(("movie", title, url, cover_path, None, None))

			if len(urls) != 0:
				ds = defer.DeferredSemaphore(tokens=2)
				downloads = [ds.run(self.download, url).addCallback(self.parseWebpage, type, title, url, cover_path, season, episode).addErrback(self.dataError) for type, title, url, cover_path, season, episode in urls]
				finished = defer.DeferredList(downloads).addErrback(self.dataError2)
			else:
				self["done_msg"].setText(_("No Movies found!"))

import time
from tree import Tree

import parallel_cell_enumeration as p_cell

import parallel_masterprob as p_ma
import pre_process as pre
import subprob as sub


# Generate data sets of different scales and then test different seeds. 
# export OMP_NUM_THREADS=2  (Environment Variable  OMP_NUM_THREADS sets the number of threads)

if __name__ == "__main__":

    start_all = time.clock()
   
    NUM_CORES = 64
    
    #Parallel
    pool = Pool(processes=NUM_CORES)
    pool = None
	
    # Different size of test data set M, K, N
    M_list = [1]  #[1, 4, 8, 16, 32] 
    K_list = [2]  #[2, 4, 6]
    N_list = [10]  #[4, 8, 12]  
            
    # Generate test data sets
    for i_1 in xrange(len(M_list)):
        for i_2 in xrange(len(K_list)):