并行生成暴力 [英] Parallelize brute force generation

问题描述

我为此进行了很多搜索，但是找不到我可以抓住的东西.我正在寻找的是如何使该算法并行化.它的并行方式(例如多线程或多处理或什至是分布式计算)无关紧要，但是我如何精确地在节点或内核之间分配工作呢?

I've searched a lot for this, but was unable to find something I could grasp my head around. What I'm searching for is how to make this algorithm parallel. It doesn't matter the way its parallel, such as multithreaded or multiprocessing or even distributed computing, but how exactly would I split up the work between nodes or cores?

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)))

推荐答案

要做的第一件事就是对1-liner疾病着迷；-)也就是说，并行处理本身就增加了许多复杂性，因此您想要保持您的代码尽可能简单和透明.这是推广@BasSwinckels的建议的方法.不短！但这非常有效:无论您有多少个内核，它都会将您的CPU仪表固定在墙上.

First thing you have to do is get disenchanted with 1-liner disease ;-) That is, parallel processing adds many complexities of its own, so you want to keep your code as simple and transparent as possible. Here's a way that generalizes @BasSwinckels's suggestion. It's not short! But it's very effective: it will nail your CPU meter to the wall no matter how many cores you have.

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)

这有很多方面，因为您想要的是块状":各种大小的字符串.如果问题的结构更加统一，则通常更容易使用并行的头.但是笨拙可以处理-只需要更多代码即可.

There are multiple pieces to this because what you want is "lumpy": strings of a variety of sizes. Parallel gimmicks are usually easier the more utterly uniform the structure of the problem. But lumpiness can be handled - it just takes more code.

请注意assert语句和num_done的无用"计算.并行代码增加了复杂性的全新维度，因此请帮自己一个忙，并从一开始就防御性地进行代码.您将尝试许多根本行不通的事情-每个人都会发生.

Do note the assert statements, and the "useless" computations of num_done. Parallel code adds brand new dimensions of complexity, so do yourself a favor and code defensively from the start. You're going to try many things that simply won't work - that happens to everyone.

也请注意，即使没有多个内核，也可以摆脱1线性疾病，这是一种更有效的方法:对于较长的字符串，一次计算和加入prefix会在更长的过程中节省数以十亿计的冗余联接运行.

Note too that breaking free of 1-liner disease also gives a more efficient approach, even without multiple cores: computing and joining the prefix just once for the longer strings will save countless billions of redundant joins over the course of longer runs.

玩得开心:-)

这篇关于并行生成暴力的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！