我正在尝试优化我必须使用相同的速度优化使其更具可读性的问题。我的问题在于:
允许的功能:write.c,没有别的。
编写一个程序,它接受两个字符串并显示没有双打的字符串,这些字符出现在其中一个字符串中。
显示将按命令行中出现的字符顺序排列,后面跟一个\ n。
正如您所看到的,在主要部分中,您需要将两个参数字符串(argv[1]
和argv[2]
)放入我们的函数中(void remove_dup(char *str, char *str2)
在使用GCC编译之后。该临时数组将在检测到重复后保存字符的ASCII值。例如,str1 = "hello"
和str2 = "laoblc"
。预期的输出将使用write函数作为“heloabc”。
然而,GCC抱怨是因为我有一个数组下标,我的临时字符数组用我的字符串索引填充零。为了停止编译器投诉,我不得不将字符串索引转换为int以将ASCII值保存在临时数组中。这将是我们的检查器,它将根据字符的值确定字符串中是否存在重复。再次重新编译,但这次使用警告标志:gcc -Wextra -Werror -Wall remove_dup.c
。这是我得到的错误:
remove_dup:11错误:数组下标的类型为'char'[-Werror,-Wchar-subscripts]
if (temp[str[i]] == 0) ^~~~~~~
remove_dup:13错误:数组下标的类型为'char'[-Werror,-Wchar-subscripts]
temp[str[i]] = 1; ^~~~~~~
remove_dup:21错误:数组下标的类型为'char'[-Werror,-Wchar-subscripts]
if (temp[str2[i]] == 0) ^~~~~~~~
remove_dup.c:23错误:数组下标的类型为'char'[-Werror,-Wchar-subscripts]
temp[str2[i]] = 1; ^~~~~~~~
现在我真正的问题是,如何在不使用任何类型的投射到我的阵列的情况下获得同样的效率但是这个程序正在运行O(m + n)
,其中m
是我们的第一个字符串,n
是我们的第二个字符串。
这是代码:
void remove_dup(char *str, char *str2)
{
int temp[10000] = {0};
int i;
i = 0;
while (str[i])
{
if (temp[(int)str[i]] == 0)
{
temp[(int)str[i]] = 1;
write(1, &str[i], 1);
}
i++;
}
i = 0;
while (str2[i])
{
if (temp[(int)str2[i]] == 0)
{
temp[(int)str2[i]] = 1;
write(1, &str2[i], 1);
}
i++;
}
}
int main(int argc, char *argv[])
{
if (argc == 3)
remove_dup(argv[1], argv[2]);
write(1, "\n", 1);
return (0);
}
我希望这对我解释的逻辑结构足够清楚。我可能有语法错误,所以忍受我:)。
在这里施放没有性能损失。
但是,根据经验,通常最好尽可能避免显式转换。您可以通过更改以下内容来执行此操作:
temp[(int)str[i]]
至:
temp[+str[i]]
这将通过通常的算术转换工作。
但是,您的代码还有另一个问题。你可以问:为什么gcc会发出这样烦人的警告信息呢?
一个答案是他们只是喜欢烦人。更好的猜测是,在大多数平台上,char
是signed
--请参阅Is char signed or unsigned by default? - 所以如果你的字符串碰巧有一个大于127的ASCII字符(即小于零),你就会有一个错误。
解决此问题的一种方法是替换:
temp[(int)str[i]]
有:
temp[str[i] + 128]
(并将int temp[10000] = {0}
改为int temp[256 + 128] = {0}
)。无论char
的默认标志如何,这都将有效。
现在我真正的问题是,如何在不使用任何类型的投射到我的阵列的情况下获得同样的效率但是
我不相信在C中进行转换会产生运行时惩罚。无论如何,C中的所有内容都是数字。我相信它只是告诉编译器是的,你知道你使用了错误的类型并且相信它没问题。
请注意,char
可以签名。负数可能会潜入那里。
这个程序运行为O(m * n),其中m是我们的第一个字符串,n是我们的第二个字符串。
不,它以O(n)运行。 O(m * n)将是你为另一个字符迭代一个字符串。
for( int i = 0; i < strlen(str1); i++ ) {
for( int j = 0; j < strlen(str2); j++ ) {
...
}
}
但是你在两个独立的循环中一个接一个地循环遍历每个字符串。这是O(m + n),即O(n)。
改进。首先,temp
只需要保持char
范围,最多是256
。让我们给它一个变量名称来描述它的作用,chars_seen
。
最后,不需要存储完整的整数。通常我们会使用bool
from stdbool.h
,但我们可以使用signed char
定义我们自己的stdbool.h
,这是#ifndef bool
可能会做的。我们肯定将它包装在一个#ifndef bool
typedef signed char bool;
#endif
bool chars_seen[256] = {0};
中,所以我们使用提供的系统,如果可用的话,它会比我们用什么类型的布尔值更好。
i
您可以通过消除for( ; *str != '\0'; str++ ) {
if( !chars_seen[(size_t)*str] ) {
chars_seen[(size_t)*str] = 1;
write(1, str, 1);
}
}
来获得更多性能,而是直接递增指针。不仅性能更高,而且这使得许多字符串和数组操作更简单。
size_t
请注意,我正在向int
投掷,而不是 if( !chars_seen[(size_t)*str]++ ) {
write(1, str, 1);
}
,因为这是索引的正确类型。
您可以通过使用后增量来减少触摸,这是否有助于取决于您的编译器。
inline void display_chars_no_dups( const char *str, bool chars_seen[]) {
for( ; *str != '\0'; str++ ) {
if( !chars_seen[(size_t)*str]++ ) {
write(1, str, 1);
}
}
}
最后,为了避免重复代码并将其扩展为使用任意数量的字符串,我们可以编写一个函数,该函数接收所看到的字符集并显示一个字符串。我们将给编译器提示内联它,尽管它的使用有问题。
main
然后int main(int argc, char *argv[]) {
bool chars_seen[256] = {0};
for( int i = 1; i < argc; i++ ) {
display_chars_no_dups( argv[i], chars_seen );
}
write(1, "\n", 1);
}
分配看到的字符数组,并根据需要多次调用该函数。
qazxswpoi