小编R..*_*R..的帖子

好吧,所以我听起来不像白痴我会更明确地陈述问题/要求:

• 针(模式)和haystack(要搜索的文本)都是C样式的以空字符结尾的字符串.没有提供长度信息; 如果需要,必须计算.
• 函数应该返回指向第一个匹配的指针,或者NULL如果找不到匹配项.
• 不允许发生失败案件.这意味着任何具有非常量(或大常量)存储要求的算法都需要具有分配失败的后备情况(并且后备保养中的性能因此导致最坏情况的性能).
• 实现是在C中,虽然没有代码的算法(或链接到这样的)的良好描述也很好.

......以及"最快"的意思:

• 确定性O(n)where n= haystack长度.(但是O(nm)如果它们与更强大的算法组合以给出确定性O(n)结果,则可以使用通常(例如滚动哈希)算法的思想.
• 从不执行(可测量;一些时钟if (!needle[1])等等)比天真蛮力算法更糟糕,特别是在非常短的针上,这可能是最常见的情况.(无条件的重预处理开销是不好的,因为试图以可能的针头为代价来改善病理针的线性系数.)
• 给定任意针和干草堆,与任何其他广泛实现的算法相比,具有相当或更好的性能(不低于搜索时间长50%).
• 除了这些条件,我将保留"最快"开放式的定义.一个好的答案应该解释为什么你认为你建议"最快"的方法.

我目前的实现比glibc实现的双向大约慢10%和8倍(取决于输入).

更新:我目前的最佳算法如下:

• 对于长度为1的针,请使用strchr.
• 对于长度为2-4的针,使用机器字一次比较2-4个字节,如下所示:在每次迭代时从大海捞针以16位或32位整数预加载针,并从大海捞针中循环旧字节输出/新字节.大海捞针的每个字节都只读取一次,并对0(字符串结束)和一个16位或32位比较进行检查.
• 对于长度> 4的针,使用具有错误移位表的双向算法(如Boyer-Moore),该移位表仅应用于窗口的最后一个字节.为了避免初始化1kb表的开销,这对于许多中等长度的针来说是一个净损失,我保留一个位数组(32字节)标记移位表中的哪些条目被初始化.未设置的位对应于从不出现在针中的字节值,可以进行全针长度移位.

我脑海中留下的重大问题是:

• 有没有办法更好地利用坏班次表？Boyer-Moore通过向后扫描(从右到左)充分利用它,但是双向扫描需要从左到右扫描.
• 我在一般情况下找到的唯一两个可行的候选算法(没有内存或二次性能条件)是有序字母表上的双向和字符串匹配.但是,是否存在易于检测的情况,其中不同的算法将是最佳的？当然,空间算法中的许多O(m)(其中m是针长)可以用于m<100左右.如果针对针的简单测试可能仅需要线性时间,那么也可以使用最坏情况二次方的算法.

奖励积分:

• 假设针和干草堆都是结构良好的UTF-8,你能提高性能吗？(对于字节长度不同的字符,良好的形式在针和haystack之间强加了一些字符串对齐要求,并且当遇到不匹配的头字节时允许自动2-4字节移位.但这些约束是否会超出你的范围最大后缀计算,良好的后缀转换等已经为您提供了各种算法？)

注意:我很清楚那里的大多数算法,而不是它们在实践中的表现.这是一个很好的参考,所以人们不会继续给我作为评论/答案的算法参考:http://www-igm.univ-mlv.fr/~lecroq/string/index.html

我正在学习Objective-C和Cocoa并且遇到过这样的声明:

Cocoa框架期望全局字符串常量而不是字符串文字用于字典键,通知和异常名称,以及一些带字符串的方法参数.

我只使用更高级别的语言,所以从来没有必要考虑字符串的细节.字符串常量和字符串文字之间有什么区别？

除了%hn和%hhn(指定h或hh指定指向对象的大小),格式说明符的h和hh修饰符有printf什么意义？

由于标准要求的默认促销适用于可变函数,因此不可能将类型char或short(或其任何有符号/无符号变体)的参数传递给printf.

根据7.19.6.1(7),h修饰符:

指定以下d,i,o,u,x或X转换规范适用于short int或unsigned short int参数(该参数将根据整数提升进行提升,但其值应转换为short int或打印前的unsigned short int); 或者后续的n转换规范适用于指向short int参数的指针.

如果参数实际上是类型short或unsigned short,则促销int后转换回short或unsigned short将产生与促销相同的值int而不进行任何转换.因此,对于类型的参数short或unsigned short,%d,%u等应给予相同的结果到%hd,%hu等.(并且同样地对于char类型和hh).

据我所知,h或者hh修饰符可能有用的唯一情况是当参数将其传递int到范围之外时,short或者unsigned short …

每7.5,

[errno]扩展为具有int类型的可修改的lvalue175,其值由多个库函数设置为正错误号.未指定errno是宏还是使用外部链接声明的标识符.如果为了访问实际对象而禁止宏定义,或者程序定义名为errno的标识符,则行为未定义.

175)宏errno不必是对象的标识符.它可能会扩展为函数调用产生的可修改的左值(例如,*errno()).

我不清楚这是否足以要求&errno不是违反约束.C语言具有左值(例如寄存器存储类变量;但是这些变量只能是自动的,因此errno无法定义),&运算符是违反约束的.

如果&errno是合法的C,是否需要保持不变？

我的观点是,如果由于需要能够保存或(-1)的任何可能值,C实现不能满足某些stdio函数(特别是fputc/ fgetc)的规范.这个推理是否正确？sizeof(int)==1intunsigned charEOF

(显然sizeof(int)不能为1,如果CHAR_BIT是8,由于所需的最小范围int,所以我们隐含地仅讨论与CHAR_BIT>=16例如DSP的实现,其中典型的实现将是独立实现而不是托管实现,因此不需要提供stdio.)

编辑:在阅读了答案和一些链接引用后,对托管实现可能有效的方式有一些想法sizeof(int)==1:

首先,一些引用:

7.19.7.1(2-3):

如果未设置stream指向的输入流的结束指示符并且存在下一个字符,则fgetc函数将该字符作为转换为int的unsigned char获取并为该流提前关联的文件位置指示符(如果定义).

如果设置了流的结束指示符,或者流处于文件结尾,则设置流的结束指示符并且fgetc函数返回EOF.否则,fgetc函数返回stream指向的输入流中的下一个字符.如果发生读取错误,则设置流的错误指示符,并且fgetc函数返回EOF.

7.19.8.1(2):

fread函数在ptr指向的数组中,从stream指向的流中读取大小由size指定的nmemb元素.对于每个对象,对fgetc函数进行大小调用,并按顺序读取存储在unsigned char数组中的结果,该数组恰好覆盖对象.流的文件位置指示符(如果已定义)按成功读取的字符数提前.

思考:

• 读回unsigned char范围之外的值int可能只是在实现中具有未定义的实现定义的行为.这是特别令人不安,因为它意味着使用fwrite和fread存储二进制结构(这同时导致不可移植的文件,应该是你可以在任何单个实现便携执行操作)可能出现的工作只是默默地失败.基本上总是导致未定义的行为.我接受的实现可能没有一个可用的文件系统,但它的很多难以接受的实现可以有一个文件系统,当你试图用它那就会自动调用鼻鬼,没有办法判断它的不可用. 现在,我意识到行为是实现定义的,而不是不确定的,它不是这么不安,我想这可能是一个有效的(虽然不受欢迎)的实现.

• 实现sizeof(int)==1可以简单地将文件系统定义为空且只读.然后,就没有办法应用程序可以读取本身写的,只从一个输入设备的任何数据stdin可能被实现为只给予积极的char配合在价值观int.

编辑(再次):从C99理由,7.4:

EOF传统上是-1,但可以是任何负整数,因此可以与任何有效的字符代码区分开.

这似乎表明sizeof(int)可能不是1,或者至少这是委员会的意图.

首先,这不是浮点新手问题.我知道浮点运算的结果(更不用说超越函数)通常不能准确表示,并且大多数终止小数不能完全表示为二进制浮点数.

也就是说,每个可能的浮点值完全对应于一个二元有理数(一个有理数p/q,其中q是2的幂),而这又有一个精确的十进制表示.

我的问题是:你如何有效地找到这个精确的十进制表示？sprintf类似的函数通常只指定多个有效数字来唯一确定原始浮点值; 它们不一定打印精确的十进制表示.我知道我使用过的一种算法,但它很慢,指数O(e^2)在哪里e.这是一个大纲:

1. 将尾数转换为十进制整数.你可以通过拉开这些位来直接读取尾数,或者你可以编写一个凌乱的浮点循环,首先将该值乘以2的幂,使其在1 <= x <10的范围内,然后拉通过转换为int,减去并乘以10,一次关闭一个数字.
2. 通过重复乘以或除以2来应用指数.这是对您生成的十进制数字串的操作.每次~3次乘法将在左侧添加一个额外的数字.每个单独的dividion将在右侧添加一个额外的数字.

这真的是最好的吗？我对此表示怀疑,但我不是浮点专家,我无法找到一种方法对数字的浮点表示进行基数10计算,而不会遇到不精确结果的可能性(乘以或除以除了你知道你有空闲位之外,除了2的幂之外的任何东西都是浮点数的有损操作.

根据C标准(6.5.2.2第6段)

如果表示被调用函数的表达式具有不包含原型的类型,则对每个参数执行整数提升,并将具有float类型的参数提升为double.这些被称为默认参数促销.如果参数的数量不等于参数的数量,则行为未定义.如果函数是使用包含原型的类型定义的,并且原型以省略号(,...)结尾,或者促销后的参数类型与参数类型不兼容,则行为未定义.如果函数是使用不包含原型的类型定义的,并且促销后的参数类型与促销后的参数类型不兼容,则行为未定义,但以下情况除外:

• 一个提升类型是有符号整数类型,另一个提升类型是相应的无符号整数类型,并且该值可在两种类型中表示;
• 这两种类型都是指向字符类型或空格的限定或不合格版本的指针.

因此,一般来说,只要传递的值适合两种类型,传递int到需要unsigned int(或反之亦然)的可变函数是没有错的.但是,printf读取规范(7.19.6.1第9段):

如果转换规范无效,则行为未定义.如果任何参数不是相应转换规范的正确类型,则行为未定义.

签名/未签名不匹配也不例外.

这是否意味着printf("%x", 1)调用未定义的行为？

在POSIX的基本原理中有一个注意事项,强制CHAR_BIT为8是一个让步,以保持与C99的对齐而不抛弃套接字/网络,但我从来没有看到冲突究竟是什么的解释.有没有人有轶事或引用为什么它被认为是必要的？

编辑:我已经得到了很多关于为什么它CHAR_BIT成为8的原因的猜测答案,我同意,但我真正想要的是C99与POSIX中的网络技术之间的技术冲突是什么.我最好的猜测是它与C99有关,要求uint*_t是精确大小的类型(没有填充),而inttypes.h之前在POSIX中没有提出这样的要求.

当我尝试使用ssh中的mysqldump进行备份时,我在机器10.64.1.1上运行以下命令.它给出以下错误.

mysqldump --user=test -p=password --host=10.64.1.2 --tab=. databasename tablename

mysqldump: Got error: 1045: Access denied for user 'test'@'10.64.1.1' (using password: YES) 当试图连接

但是,我可以使用相同的用户和密码访问mysql.

mysql --user=test -p[password]

当前用户: test@10.64.1.1

SSL: Not in use

当前寻呼机: stdout

使用outfile: ''

使用分隔符: ;

服务器版本: 5.0.91-50-log Percona SQL Server, Revision 73 (GPL)

协议版本: 10

连接: 10.64.1.2 via TCP/IP

更新:

如果我执行以下mysql文档:--password[=password]或-p[password].

由于我的密码包含特殊符号@,因此Mysql无法正确检测用户.它抱怨说:

mysqldump: Got error: 1044: Access denied for user 'test'@'%' to database

我来自C/Unix背景,在shell脚本方面有很多经验,有些在Perl,elisp等方面.但现在我正在进行一些工作,我需要开发基于Web的交互式界面,我需要学习JavaScript.我的问题是,我在网上找到的用于学习JavaScript的所有资源似乎都针对的是从未编程的观众,他们的作者似乎并没有好多少.一旦我看到"验证用户输入以减轻服务器的负担"作为JS的一个重要用途,我想尖叫,我觉得我不相信作者所说的任何其他内容.;-)

任何人都可以为想要学习JS作为新语言的有经验的程序员推荐好的资源吗？理想情况下,我想在线开始,但也欢迎死树建议,特别是如果我可以在线预览它们.