平行蠻力生成

Question

我已經爲此搜尋了很多東西，但無法找到可以抓住我的頭的東西。我正在尋找的是如何使這個算法平行。它的並行方式無關緊要，比如多線程或多處理甚至分佈式計算，但是究竟是如何將節點或內核之間的工作分開？

def bruteforce(charset, maxlength): 
    return (''.join(candidate) 
     for candidate in itertools.chain.from_iterable(itertools.product(charset, repeat=i) 
     for i in range(1, maxlength + 1))) 

Answer 1

你必須做的第一件事就是不要理會1-liner疾病;-)也就是說，並行處理增加了它自己的許多複雜性，所以你想保持你的代碼儘可能簡單和透明。這是一種推廣@BasSwinckels建議的方法。這並不短！但它是非常有效的：無論您擁有多少核心，它都會將您的CPU計量器釘在牆上。

CHARSET = "abcdefghijklmnopqrstuvwxyx" 
MAX_LENGTH = 6 # generate all strings from CHARSET with length 1 thru MAX_LENGTH 
NUM_PROCESSES = None # defaults to all available cores 

from itertools import product 

# string_gen is what the workers run. Everything else 
# runs in the main program. 
def string_gen(prefix, suffix_len, length): 
    # Generate all strings of length `length` starting with `prefix`. 
    # If length > suffix_len, only the last suffix_len characters 
    # need to be generated. 
    num_done = 0 
    if length <= suffix_len: 
     assert prefix == "" 
     for t in product(CHARSET, repeat=length): 
      result = "".join(t) 
      # do something with result 
      num_done += 1 
    else: 
     assert len(prefix) + suffix_len == length 
     for t in product(CHARSET, repeat=suffix_len): 
      result = prefix + "".join(t) 
      # do something with result 
      num_done += 1 
    return num_done 

def record_done(num): 
    global num_done 
    num_done += num 
    print num_done, "done so far" 

def do_work(pool, strings_per_chunk=1000000): 
    # What's the most chars we can cycle through without 
    # exceeding strings_per_chunk? Could do with this 
    # logs, but I'm over-reacting to 1-liner disease ;-) 
    N = len(CHARSET) 
    suffix_len = 1 
    while N**suffix_len <= strings_per_chunk: 
     suffix_len += 1 
    suffix_len -= 1 
    print "workers will cycle through the last", suffix_len, "chars" 

    # There's no point to splitting up very short strings. 
    max_short_len = min(suffix_len, MAX_LENGTH) 
    for length in range(1, max_short_len + 1): 
     pool.apply_async(string_gen, args=("", suffix_len, length), 
         callback=record_done) 
    # And now the longer strings. 
    for length in range(max_short_len + 1, MAX_LENGTH + 1): 
     for t in product(CHARSET, repeat=length-suffix_len): 
      prefix = "".join(t) 
      pool.apply_async(string_gen, args=(prefix, suffix_len, length), 
          callback=record_done) 

if __name__ == "__main__": 
    import multiprocessing 
    pool = multiprocessing.Pool(NUM_PROCESSES) 
    num_done = 0 
    do_work(pool) 
    pool.close() 
    pool.join() 
    expected = sum(len(CHARSET)**i 
        for i in range(1, MAX_LENGTH + 1)) 
    assert num_done == expected, (num_done, expected) 

有很多件，因爲你想要的是「塊」：各種大小的字符串。並行噱頭通常更容易使問題結構更加完全一致。但是可以處理塊狀 - 它只需要更多的代碼。

請注意assert聲明以及num_done的「無用」計算。並行代碼增加了複雜性的全新維度，所以從一開始就爲自己做一個好處和代碼防禦。你會嘗試許多根本無法工作的事情 - 這發生在每個人身上。

請注意，即使沒有多核心，打破1-liner疾病也提供了一個更有效的方法：計算並加入prefix只需一次更長的字符串將在長時間運行過程中節省數以億計的冗餘連接。

玩得開心:-)

Answer 2

如果我理解你的生成器表達式正確，你正試圖從1生成所有長度的話.. maxlength給予一定的字母表。

我不知道你想如何拆分你的問題（你有N工人嗎？），但一個明顯的方法是將第一個字母分開單詞列表，將它們交給各種並行工作者，然後所有人都必須將字母的所有可能組合加到0 .. maxlength - 1之後。