ETA: След като публикувахте своя код, мога да ви кажа, че има прост начин да правите това, което правите МНОГО по-бързо (>100 пъти по-бързо).
Виждам, че това, което правите, е да добавите честота в скоби към всеки елемент в списък с низове. Вместо да броите всички елементи всеки път (което, както можете да потвърдите с помощта на cProfile, е най-голямото тясно място във вашия код), можете просто да създадете речник, който съпоставя всеки елемент с неговата честота. По този начин трябва само да преминете през списъка два пъти - веднъж, за да създадете честотния речник, веднъж, за да го използвате, за да добавите честота.
Тук ще покажа новия си метод, ще определя времето и ще го сравня със стария метод, като използвам генериран тестов случай. Тестовият случай дори показва, че новият резултат е напълно идентичен със стария. Забележка: Всичко, на което наистина трябва да обърнете внимание по-долу, е new_method.
import random
import time
import collections
import cProfile
LIST_LEN = 14000
def timefunc(f):
t = time.time()
f()
return time.time() - t
def random_string(length=3):
"""Return a random string of given length"""
return "".join([chr(random.randint(65, 90)) for i in range(length)])
class Profiler:
def __init__(self):
self.original = [[random_string() for i in range(LIST_LEN)]
for j in range(4)]
def old_method(self):
self.ListVar = self.original[:]
for b in range(len(self.ListVar)):
self.list1 = []
self.temp = []
for n in range(len(self.ListVar[b])):
if not self.ListVar[b][n] in self.temp:
self.list1.insert(n, self.ListVar[b][n] + '(' + str(self.ListVar[b].count(self.ListVar[b][n])) + ')')
self.temp.insert(0, self.ListVar[b][n])
self.ListVar[b] = list(self.list1)
return self.ListVar
def new_method(self):
self.ListVar = self.original[:]
for i, inner_lst in enumerate(self.ListVar):
freq_dict = collections.defaultdict(int)
# create frequency dictionary
for e in inner_lst:
freq_dict[e] += 1
temp = set()
ret = []
for e in inner_lst:
if e not in temp:
ret.append(e + '(' + str(freq_dict[e]) + ')')
temp.add(e)
self.ListVar[i] = ret
return self.ListVar
def time_and_confirm(self):
"""
Time the old and new methods, and confirm they return the same value
"""
time_a = time.time()
l1 = self.old_method()
time_b = time.time()
l2 = self.new_method()
time_c = time.time()
# confirm that the two are the same
assert l1 == l2, "The old and new methods don't return the same value"
return time_b - time_a, time_c - time_b
p = Profiler()
print p.time_and_confirm()
Когато стартирам това, получава времена от (15.963812112808228, 0.05961179733276367), което означава, че е около 250 пъти по-бързо, въпреки че това предимство зависи както от това колко дълги са списъците, така и от разпределението на честотата във всеки списък. Сигурен съм, че ще се съгласите, че с това предимство в скоростта вероятно няма да е необходимо да използвате мултипроцесор :)
(Оригиналния ми отговор е оставен по-долу за бъдещи поколения)
ETA: Между другото, струва си да се отбележи, че този алгоритъм е приблизително линеен по отношение на дължината на списъците, докато кодът, който сте използвали, е квадратичен. Това означава, че се представя с още по-голямо предимство, колкото по-голям е броят на елементите. Например, ако увеличите дължината на всеки списък до 1000000, изпълнението му отнема само 5 секунди. Въз основа на екстраполация, старият код ще отнеме повече от ден :)
Зависи от операцията, която извършвате. Например:
import time
NUM_RANGE = 100000000
from multiprocessing import Process
def timefunc(f):
t = time.time()
f()
return time.time() - t
def multi():
class MultiProcess(Process):
def __init__(self):
Process.__init__(self)
def run(self):
# Alter string + test processing speed
for i in xrange(NUM_RANGE):
a = 20 * 20
thread1 = MultiProcess()
thread2 = MultiProcess()
thread1.start()
thread2.start()
thread1.join()
thread2.join()
def single():
for i in xrange(NUM_RANGE):
a = 20 * 20
for i in xrange(NUM_RANGE):
a = 20 * 20
print timefunc(multi) / timefunc(single)
На моята машина многопроцесорната операция отнема само ~60% от времето на еднопоточната.
person
David Robinson
schedule
08.01.2012
