- mongodb - 在 MongoDB mapreduce 中,如何展平值对象?
- javascript - 对象传播与 Object.assign
- html - 输入类型 ="submit"Vs 按钮标签它们可以互换吗?
- sql - 使用 MongoDB 而不是 MS SQL Server 的优缺点
我正在尝试找到一个与 strstr
类似的函数,该函数从字符串的末尾开始搜索子字符串。
最佳答案
标准 C 库没有“反向 strstr”函数,因此您必须自己查找或编写。
我想出了几个我自己的解决方案,并在这个线程中添加了一些测试和基准测试代码以及其他功能。对于那些好奇,在我的笔记本电脑(Ubuntu karmic,amd64 架构)上运行的输出如下所示:
$ gcc -O2 --std=c99 strrstr.c && ./a.out
#1 0.123 us last_strstr
#2 0.440 us theo
#3 0.460 us cordelia
#4 1.690 us digitalross
#5 7.700 us backwards_memcmp
#6 8.600 us sinan
您的结果可能不同,并且根据您的编译器和库,结果的顺序也可能不同。
要从字符串的开头获取匹配的偏移量(索引),使用指针算法:
char *match = last_strstr(haystack, needle);
ptrdiff_t index;
if (match != NULL)
index = match - haystack;
else
index = -1;
现在,落叶松(请注意,这纯粹是用 C 语言编写的,我对 C++ 的了解不够好,无法给出答案):
#include <string.h>
#include <stdlib.h>
/* By liw. */
static char *last_strstr(const char *haystack, const char *needle)
{
if (*needle == '\0')
return (char *) haystack;
char *result = NULL;
for (;;) {
char *p = strstr(haystack, needle);
if (p == NULL)
break;
result = p;
haystack = p + 1;
}
return result;
}
/* By liw. */
static char *backwards_memcmp(const char *haystack, const char *needle)
{
size_t haylen = strlen(haystack);
if (*needle == '\0')
return (char *) haystack;
size_t needlelen = strlen(needle);
if (needlelen > haylen)
return NULL;
const char *p = haystack + haylen - needlelen;
for (;;) {
if (memcmp(p, needle, needlelen) == 0)
return (char *) p;
if (p == haystack)
return NULL;
--p;
}
}
/* From http://stuff.mit.edu/afs/sipb/user/cordelia/Diplomacy/mapit/strrstr.c
*/
static char *cordelia(const char *s1, const char *s2)
{
const char *sc1, *sc2, *psc1, *ps1;
if (*s2 == '\0')
return((char *)s1);
ps1 = s1 + strlen(s1);
while(ps1 != s1) {
--ps1;
for (psc1 = ps1, sc2 = s2; ; )
if (*(psc1++) != *(sc2++))
break;
else if (*sc2 == '\0')
return ((char *)ps1);
}
return ((char *)NULL);
}
/* From http://stackoverflow.com/questions/1634359/
is-there-a-reverse-fn-for-strstr/1634398#1634398 (DigitalRoss). */
static char *reverse(const char *s)
{
if (s == NULL)
return NULL;
size_t i, len = strlen(s);
char *r = malloc(len + 1);
for(i = 0; i < len; ++i)
r[i] = s[len - i - 1];
r[len] = 0;
return r;
}
char *digitalross(const char *s1, const char *s2)
{
size_t s1len = strlen(s1);
size_t s2len = strlen(s2);
const char *s;
if (s2len == 0)
return (char *) s1;
if (s2len > s1len)
return NULL;
for (s = s1 + s1len - s2len; s >= s1; --s)
if (strncmp(s, s2, s2len) == 0)
return (char *) s;
return NULL;
}
/* From http://stackoverflow.com/questions/1634359/
is-there-a-reverse-fn-for-strstr/1634487#1634487 (Sinan Ünür). */
char *sinan(const char *source, const char *target)
{
const char *current;
const char *found = NULL;
if (*target == '\0')
return (char *) source;
size_t target_length = strlen(target);
current = source + strlen(source) - target_length;
while ( current >= source ) {
if ( (found = strstr(current, target)) ) {
break;
}
current -= 1;
}
return (char *) found;
}
/* From http://stackoverflow.com/questions/1634359/
is-there-a-reverse-fn-for-strstr/1634441#1634441 (Theo Spears). */
char *theo(const char* haystack, const char* needle)
{
size_t needle_length = strlen(needle);
const char* haystack_end = haystack + strlen(haystack) - needle_length;
const char* p;
size_t i;
if (*needle == '\0')
return (char *) haystack;
for(p = haystack_end; p >= haystack; --p)
{
for(i = 0; i < needle_length; ++i) {
if(p[i] != needle[i])
goto next;
}
return (char *) p;
next:;
}
return 0;
}
/*
* The rest of this code is a test and timing harness for the various
* implementations above.
*/
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Check that the given function works. */
static bool works(const char *name, char *(*func)(const char *, const char *))
{
struct {
const char *haystack;
const char *needle;
int offset;
} tests[] = {
{ "", "", 0 },
{ "", "x", -1 },
{ "x", "", 0 },
{ "x", "x", 0 },
{ "xy", "x", 0 },
{ "xy", "y", 1 },
{ "xyx", "x", 2 },
{ "xyx", "y", 1 },
{ "xyx", "z", -1 },
{ "xyx", "", 0 },
};
const int num_tests = sizeof(tests) / sizeof(tests[0]);
bool ok = true;
for (int i = 0; i < num_tests; ++i) {
int offset;
char *p = func(tests[i].haystack, tests[i].needle);
if (p == NULL)
offset = -1;
else
offset = p - tests[i].haystack;
if (offset != tests[i].offset) {
fprintf(stderr, "FAIL %s, test %d: returned %d, haystack = '%s', "
"needle = '%s', correct return %d\n",
name, i, offset, tests[i].haystack, tests[i].needle,
tests[i].offset);
ok = false;
}
}
return ok;
}
/* Dummy function for calibrating the measurement loop. */
static char *dummy(const char *haystack, const char *needle)
{
return NULL;
}
/* Measure how long it will take to call the given function with the
given arguments the given number of times. Return clock ticks. */
static clock_t repeat(char *(*func)(const char *, const char *),
const char *haystack, const char *needle,
long num_times)
{
clock_t start, end;
start = clock();
for (long i = 0; i < num_times; ++i) {
func(haystack, needle);
}
end = clock();
return end - start;
}
static clock_t min(clock_t a, clock_t b)
{
if (a < b)
return a;
else
return b;
}
/* Measure the time to execute one call of a function, and return the
number of CPU clock ticks (see clock(3)). */
static double timeit(char *(*func)(const char *, const char *))
{
/* The arguments for the functions to be measured. We deliberately
choose a case where the haystack is large and the needle is in
the middle, rather than at either end. Obviously, any test data
will favor some implementations over others. This is the weakest
part of the benchmark. */
const char haystack[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"b"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
const char needle[] = "b";
/* First we find out how many repeats we need to do to get a sufficiently
long measurement time. These functions are so fast that measuring
only a small number of repeats will give wrong results. However,
we don't want to do a ridiculously long measurement, either, so
start with one repeat and multiply it by 10 until the total time is
about 0.2 seconds.
Finally, we measure the dummy function the same number of times
to get rid of the call overhead.
*/
clock_t mintime = 0.2 * CLOCKS_PER_SEC;
clock_t clocks;
long repeats = 1;
for (;;) {
clocks = repeat(func, haystack, needle, repeats);
if (clocks >= mintime)
break;
repeats *= 10;
}
clocks = min(clocks, repeat(func, haystack, needle, repeats));
clocks = min(clocks, repeat(func, haystack, needle, repeats));
clock_t dummy_clocks;
dummy_clocks = repeat(dummy, haystack, needle, repeats);
dummy_clocks = min(dummy_clocks, repeat(dummy, haystack, needle, repeats));
dummy_clocks = min(dummy_clocks, repeat(dummy, haystack, needle, repeats));
return (double) (clocks - dummy_clocks) / repeats / CLOCKS_PER_SEC;
}
/* Array of all functions. */
struct func {
const char *name;
char *(*func)(const char *, const char *);
double secs;
} funcs[] = {
#define X(func) { #func, func, 0 }
X(last_strstr),
X(backwards_memcmp),
X(cordelia),
X(digitalross),
X(sinan),
X(theo),
#undef X
};
const int num_funcs = sizeof(funcs) / sizeof(funcs[0]);
/* Comparison function for qsort, comparing timings. */
int funcmp(const void *a, const void *b)
{
const struct func *aa = a;
const struct func *bb = b;
if (aa->secs < bb->secs)
return -1;
else if (aa->secs > bb->secs)
return 1;
else
return 0;
}
int main(void)
{
bool ok = true;
for (int i = 0; i < num_funcs; ++i) {
if (!works(funcs[i].name, funcs[i].func)) {
fprintf(stderr, "%s does not work\n", funcs[i].name);
ok = false;
}
}
if (!ok)
return EXIT_FAILURE;
for (int i = 0; i < num_funcs; ++i)
funcs[i].secs = timeit(funcs[i].func);
qsort(funcs, num_funcs, sizeof(funcs[0]), funcmp);
for (int i = 0; i < num_funcs; ++i)
printf("#%d %.3f us %s\n", i+1, funcs[i].secs * 1e6, funcs[i].name);
return 0;
}
关于c++ - strstr 是否有反向功能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1634359/
我正在构建一个 RCP 应用程序,其中每个季度都会更新功能/插件。因此,如果用户选择自动更新功能/插件,则会下载更新插件的新 jar,但旧插件仍在使用我不再使用的磁盘空间。 我厌倦了删除包含旧 jar
我如何从外部 Controller 功能中调用 Controller 内部的功能,例如电话间隙回调功能 这是 Controller 外部定义的功能 function onDeviceReady()
如果某个功能(例如 MediaSource)可用,我如何使用 Google Dart 检查。 new MediaSource() 抛出一个错误。如何以编程方式检查此类或功能是否存在?有任何想法吗?是否
我正在尝试运行 Azure Orchestrations,突然我开始从 statusQueryGetUri 收到错误: 协调器函数“UploadDocumentOrchestrator”失败:函数“U
我见过 iPhone 上的应用程序,如果在 3.0 上运行,将使用 3.0 功能/API,例如应用内电子邮件编辑器,如果在 2.x 上运行,则不使用这些功能,并退出应用程序以启动邮件相反。 这是怎么做
这是 DB 规范化理论中的一个概念: Third normal form is violated when a non-key field is a fact about another non-ke
如果我定义 #if SOMETHING #endif 而且我还没有在任何地方定义 SOMETHING。 #if 中的代码会编译吗? 最佳答案 当#if的参数表达式中使用的名称未定义为宏时(在所有其他宏
我刚刚澄清了 A* 路径查找应该如何在两条路径具有相等值的 [情况] 下运行,无论是在计算期间还是在结束时,如果有两条相等的短路径。 例如,我在我的起始节点,我可以扩展到两个可能的节点,但它们都具有相
Java有没有类似下面的东西 宏 一种遍历所有私有(private)字段的方法 类似于 smalltalk symbols 的东西——即用于快速比较静态字符串的东西? 请注意,我正在尝试为 black
这个程序应该将华氏度转换为摄氏度: #include int main() { float fahrenheit, celsius; int max, min, step;
当打开PC缓存功能后, 软件将采用先进先出的原则排队对示波器采集的每一帧数据, 进行帧缓存。 当发现屏幕中有感兴趣的波形掠过时, 鼠标点击软件的(暂停)按钮, 可以选择回看某一帧的波形
我有一个特殊的(虚拟)函数,我想在沙盒环境中使用它: disable.system.call eval(parse(text = 'model.frame("1 ~ 1")'), envir = e
使用新的 Service 实现,我是否必须为我的所有服务提供一个 Options 方法? 使用我的所有服务当前使用的旧 ServiceBase 方法,OPTIONS 返回 OK,但没有 Access-
我正在阅读 Fogus 的关于 Clojure 的喜悦的书,在并行编程章节中,我看到了一个函数定义,它肯定想说明一些重要的事情,但我不知道是什么。此外,我看不到这个函数有什么用 - 当我执行时,它什么
我有大量的 C 代码,大部分代码被注释掉和/或 #if 0。当我使用 % 键匹配 if-else 的左括号和右括号时,它也匹配注释掉的代码。 有没有办法或vim插件在匹配括号时不考虑注释掉或#if 0
我有这个功能: map(map(fn x =>[x])) [[],[1],[2,3,4]]; 产生: val it = [[],[[1]],[[2],[3],[4]]] 我不明白这个功能是如何工作的。
我使用 Visual Studio 代码创建了一个函数应用程序,然后发布了它。功能应用程序运行良好。我现在在功能门户中使用代码部署功能(KUDU)并跳过构建。下面是日志 9:55:46 AM
我有一个数据框df: userID Score Task_Alpha Task_Beta Task_Charlie Task_Delta 3108 -8.00 Easy Easy
我真的无法解决这个问题: 我有一个返回数据框的函数。但是,数据框仅打印在我的控制台中,尽管我希望将其存储在工作空间中。我怎样才能做到这一点? 样本数据: n <- 32640 t <- seq(3*p
有没有办法找出所有可能的激活器命令行选项? activator -help仅提供最低限度的可用选项/功能列表,但所有好的东西都隐藏起来,即使在 typesafe 网站在线文档中也不可用。 到目前为止,
我是一名优秀的程序员,十分优秀!