alphabet的每种可能组合。我希望提出一些建议，以改进算法，或减少运行时间。但是，任何其他建议也可以接受。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
static const char alphabet[] =
"abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789";
static const int alphabetSize = sizeof(alphabet) - 1;
void bruteImpl(char* str, int index, int maxDepth)
{
for (int i = 0; i < alphabetSize; ++i)
{
str[index] = alphabet[i];
if (index == maxDepth - 1) printf("%s\n", str);
else bruteImpl(str, index + 1, maxDepth);
}
}
void bruteSequential(int maxLen)
{
char* buf = malloc(maxLen + 1);
for (int i = 1; i <= maxLen; ++i)
{
memset(buf, 0, maxLen + 1);
bruteImpl(buf, 0, i);
}
free(buf);
}
int main(void)
{
bruteSequential(3);
return 0;
}
#1 楼
我将跳过审阅OP的代码，其他人已经对其进行了很好的审阅。相反，我只是要展示一个更快的版本并进行解释。什么是算法？
基本上，算法的工作方式是创建一个保存
alphaLen^2模式的缓冲区，其中alphaLen是字母的长度。模式是一种组合，例如"aaaaa\n"。使用alphaLen^2模式的原因是因为缓冲区已预先填充了已经设置为所有可能组合的最后2个字母。因此，例如，缓冲区最初看起来像（对于5个长度的模式）：输出缓冲区，然后将第三个字母递增到最后一个字母。这涉及写该字母"aaaaa\naaaab\naaaac\n ... aaa99\n" (62*62 patterns, 23064 bytes in length)
次（每个模式一次）。所以第一次迭代是这样的：最后一封信。如果回绕了，则第五个到最后一个字母也将更新，依此类推。一直持续到第一个字母回绕为止，这时我们完成了。它有多快？输出到
write()，这样我的硬盘速度就不会成为限制因素。我尝试了5种字母模式的OP程序，但对我来说却花费了太长时间（203秒）。因此，我将使用爱德华估计的18秒作为OP的程序。我还在计算机上测试了Edward的程序，并编写了第二个程序，在该程序中我扩展了该算法以对最后3个字符进行硬编码，而不是对2个字符进行硬编码。结果如下： alphaLen^2 您可以看到，该算法非常快速。
代码
/>这两个程序都可以在GitHub上找到。我将在下面显示2个字符的变体：
"aabaa\naabab\naabac\n ... aab99\n"
^ ^ ^ ^
| | | |
+------+------+-----------+----- Characters written to buffer (62*62 changes)
评论
\ $ \ begingroup \ $
您可以在其中包含一些处理更多字符排列的测试吗？有些算法使用较小的数据集会比使用较大的数据集表现更好，所以我很好奇这将如何执行
\ $ \ endgroup \ $
–syb0rg
2014年12月21日在18:13
\ $ \ begingroup \ $
@ syb0rg您是指字母中的更多字符还是更长的长度模式？告诉我您要测试的字母长度和/或图案长度是多少，我将对其进行测试。
\ $ \ endgroup \ $
– JS1
2014年12月21日在21:15
\ $ \ begingroup \ $
请使用更长的图案。我敢肯定，您的代码与其他代码相比仍然可以很好地运行，但是我仍然很好奇。
\ $ \ endgroup \ $
–syb0rg
2014年12月21日在22:49
\ $ \ begingroup \ $
@ syb0rg我添加了7次长度。请注意，这将生成超过28 TB的数据。时间符合预期，约为6倍长度的62倍。我不会将其运行为长度8，因为它将花费一天的时间来运行。
\ $ \ endgroup \ $
– JS1
2014-12-22在2:45
\ $ \ begingroup \ $
+1-干得好！我用其他两种算法确认了准确性，并且还指出，即使我将版本中的缓冲区大小提高到类似大小，该算法也明显更快（我的计算机上为0.5 s对9.1 s）。
\ $ \ endgroup \ $
–爱德华
2014年12月26日13:07
#2 楼
在此程序中，bruteImpl是一个紧密循环。即使可以节省一些时间，我也不会优化其他任何事情，因为无论如何，大多数时间都将浪费在运行bruteImpl上。一次运行memset不会节省您的时间，因为它运行了...多次。但是，将长度设置为5时，bruteImpl被称为... 15264777次。这绝对是值得优化的东西。我认为性能上的最大限制是
printf。控制台输出通常有点慢。如果删除printf，而改为使它成为小循环计数器，则会得到2秒的长度设置为5（我添加了全局count变量来强制循环执行任何操作，每次使用puts都会增加）。 />另一个问题是编译器无法删除的递归。但是，在这种情况下，似乎需要递归（不使用@ 200_success建议的堆栈的迭代算法比您的慢9倍），因此不值得删除它（无论如何您都必须模拟堆栈结构）。在许多算法中，递归比迭代慢，但有时只是需要。实际上，做任何涉及算法值的事情都比较慢。例如，我尝试添加memcmp和strcmp代替puts。 memcmp使您的算法慢6倍，而strcmp使您的算法慢10倍。如果memcmp已经相当慢，则您的算法已经足够快。有时候优化只是不值得的-编译器已经做得很好。评论
\ $ \ begingroup \ $
我喜欢您提出的所有观点，但是添加一些代码示例以显示您的意思将使这个答案真正生效。我明白了你的意思，所以+1。
\ $ \ endgroup \ $
–syb0rg
2014年1月4日20:18
#3 楼
我想说这作为递归解决方案几乎是无可挑剔的。作为稍微有点荒谬的优化，您可以将bruteSequential()调用移至for循环之前，因为您知道输出字符串的长度将永远不会减少。然后可以将其与i结合使用，以用于char* buf = calloc(maxLen + 1, sizeof(char));
作为辅助函数，应将
len声明为memset()。#4 楼
我发现有些东西可以帮助您改善代码。优先选择迭代而不是递归
递归函数通常是完成编程任务的好方法，但是在内存和时间方面需要权衡。具体来说，通常可以通过从递归函数转换为交互函数来减少或消除函数调用的计算成本，并减少或消除内存开销。使用索引的代码通常具有易于阅读和理解的优势：
<43 78q因此，例如，该代码可能是这样呈现的：
for (int i = 0; i < alphabetSize; ++i) {
str[index] = alphabet[i];
// ...
很可能通过转换左侧也使用指针可以节省更多时间。
使用实用的最低级别的I / O
使用
printf之类的库函数很方便，但不一定是最有效的。诸如printf("%s\n", str);之类的东西必须遍历str的内存，以寻找终止的NUL字符，如果您已经知道长度，则可能不需要。 如果可行的话，减少I / O。当您可以用内存访问代替I / O时，可以节省时间。但是，底层操作系统可能已经缓冲了I / O，因此唯一可以检查的方法就是对其进行测量。作为使用所有这些建议的替代实现：
for (const char *a = alphabet; *a; ++a) {
str[index] = *a;
// ...
结果
我修改了原始驱动程序，如下所示：
// create a large buffer
static const int BUFFLEN=1024*100;
void brute2(int maxLen)
{
char* indices = malloc(maxLen + 1);
char* terminal = indices+maxLen;
char *printbuff = malloc(BUFFLEN);
char *pbend = &printbuff[BUFFLEN-1];
char *b = printbuff;
*pbend = 'int main(int argc, char *argv[])
{
if (argc != 3) {
puts("Usage: brute iterations old|new\n");
return 1;
}
int iterations = atoi(argv[1]);
if (argv[2][0] == 'o')
bruteSequential(iterations);
else
brute2(iterations);
}
';
++indices[0];
char *p;
while (*terminal == 0) {
// print value
for (p = indices; *p; ++p)
;
for (--p ; p >= indices; --p) {
*b++ = alphabet[*p-1];
if (b == pbend) {
fwrite(printbuff, 1, b-printbuff, stdout);
b = printbuff;
}
}
*b++ = '\n';
if (b == pbend) {
fwrite(printbuff, 1, b-printbuff, stdout);
b = printbuff;
}
// increment values
int carry = 1;
for (++p ; carry; ++p) {
if ((*p += carry) > alphabetSize) {
*p = 1;
carry = 1;
} else {
carry = 0;
}
}
}
fwrite(printbuff, 1, b-printbuff, stdout);
free(indices);
free(printbuff);
}
这使我可以安排各种组合的时间。例如，在我的计算机上，使用该版本计算所有5个字符的组合花费了55秒，而使用原始版本则花费了65秒以上。将输出重定向到
/dev/null消除了实际磁盘I / O的开销（在这种情况下为5.2 GB），并且揭示了我的计算机上新版本花费了大约8.9 s，而原始版本花费了18秒或两倍的时间。 />评论
\ $ \ begingroup \ $
现代的优化编译器将优化具有索引的数组的迭代，而该索引直接通过指针进行迭代
\ $ \ endgroup \ $
– Mark K Cowan
17年2月20日在9:18
\ $ \ begingroup \ $
@MarkKCowan：我想您会发现编译器会生成不同的代码。在提出建议时，我还对结果进行了计时，发现使用指针始终具有速度优势。其他编译器和机器可能会产生不同的结果。测量是找出产生更快代码的方法。
\ $ \ endgroup \ $
–爱德华
17年2月20日在13:33
\ $ \ begingroup \ $
当然，这取决于编译器，我使用的是GCC v6.3.1，并检查它生成的程序集而不是基准测试
\ $ \ endgroup \ $
– Mark K Cowan
17年2月20日在14:13
#5 楼
您不需要bruteSequential for中的memset，只需在达到最大深度时在末尾添加'buf[i]='for';'： t甚至需要它，因为bruteSequential的q4312079q中的一个简单的q4312079q就足够了，但这可能会简化它评论
\ $ \ begingroup \ $
您不需要放置str [maxDepth] ='\ 0';在循环中。您可以将其移至malloc之后，因为它只需要运行一次。
\ $ \ endgroup \ $
–rolfl
2014年1月3日，13：26
\ $ \ begingroup \ $
@rolfl否，因为他也会创建较短的字符串，因此在这种情况下200_success的答案是正确的
\ $ \ endgroup \ $
–棘轮怪胎
2014年1月3日14:15
\ $ \ begingroup \ $
公平的观点，但是，您至少可以将其移动到递归之外，并将其称为maxLen次，而不是数万亿！
\ $ \ endgroup \ $
–rolfl
2014年1月3日14:25
评论
蛮力是类别，而不是算法。指定此代码应该执行的操作可能有用，而不仅仅是说它是蛮力的。可能保存下一个人来阅读一两分钟：）。@Corbin我出于代码目的进行了编辑。维基百科也说这是一种算法;）
考虑问题的另一种方法是以62为基数。但是，这不一定会产生更好的代码。
只是一个小想法，未经测试。对于较大的maxLen，首先获取maxLen / 2的所有可能字符串，然后创建所有组合。这将使用更多的内存，但时间可能会更快。面临的挑战是确定何时使用这种方法以及何时像现在一样简单地进行暴力破解。
您应该将此线程的标题更改为更有意义的名称。蛮力不是算法，蛮力搜索是（请参考）