2

在练习多线程时,我希望简单地构建一个可以计算字符集的所有可能组合(即暴力破解/匹配)并在线程之间分配工作的应用程序,以便真正测量并亲眼看到线程如何影响算法在不同系统上的时间。

到目前为止,计算这个的算法对我来说是一个很大的挑战。在最近的一个线程上(向这个简单的算法添加多线程的有效方法是什么?)我似乎明白了我需要做的事情(轻松传递每个字符范围的特定部分来分配工作),尽管该算法根本不起作用,而且我对复杂性的理解不足以在我的应用程序中修复它。

以一种简单的迭代方式,我如何计算给定字符集的每个组合,具有特定长度(即长度为 5?)

例如:

unsigned char range[] = "abcdefghijklmnopqrstuvwxyz0123456789";
brute_force(range, len); //character set, length of string to compute all combinations of
//...

我将非常感谢能减轻一些在找到正确概念时的压力。

4

2 回答 2

2

一种方法:

void brute_force(String range, int len) {
        for (int i = 0; i < range.length(); ++i) {
           final String x  = "" + range.charAt(i);
           Thread t = new Thread(){
               public void run() { brute_force(x, range[].replace(x, ""), len); };
            };
            t.start();
        }
}

将在哪里brute_force(String, String, int)生成组合。

于 2011-04-30T14:44:39.093 回答
0

5个元素的直接迭代暴力破解:

for c1 in set {
for c2 in set {
for c3 in set {
for c4 in set {
for c5 in set {
    test(c1,c2,c3,c4,c5);
}}}}}

要在线程之间划分工作,只需为每个线程分配一个单独的“开始部分”。所以第一个线程处理以'a'开头的所有病房,第二个线程处理'b',依此类推。(如果你有超过 26 个线程,那么第一个得到 'aa' 第二个 'ab' 等等......


如果您想要一个随着长度更好地扩展的解决方案,那么最好递归地表述问题(如果您愿意,可以将其转换为使用显式堆栈的版本):

unsigned char charset = /**/
unsigned int setsize = sizeof charset;

bool test(combination);   

function bruteforce(output, n){
  /* Goes through all character combinations of length n,
     writing them in output and calling test on them afterwards */
  if(n == 0){
    test(output);
  }else{
    for(int i=0; i<setsize; i++){
      output[n-1] = charset[i];
      bruteforce(output, n-1);
    }
  }
}

unsigned char my_output[final_length];
bruteforce(my_output, final_length);
于 2011-04-30T14:36:10.497 回答