写了个Sunday算法的实现....

F8LEFT

heihu 发表于 2015-4-15 19:11
使用F8老师的Sunday算法还是没法查找到文件字符串，使用古老的方法到是可以找到的，请F8老是指点

     没啥好说的了，多少人为了提高算法的效率而不断的钻研。我这边因为环境问题所以测试得挺少的，所以估计有bug，跟踪一下改改就好了。     你的方法时间复杂度最坏为O(n^m)，而我的最坏为O(n*m)，经过查表修改的话最好可以提升到O(n)，也就是说基本上把原来的Src从头到尾扫描一遍就知道有没有该子字符串。这两个算法效率不在同一个等级上，要咋比较。

F8LEFT

heihu 发表于 2015-4-15 19:11
使用F8老师的Sunday算法还是没法查找到文件字符串，使用古老的方法到是可以找到的，请F8老是指点

测了一下，是可以对大数据文件进行操作的，请检查一下用法有没有错。还有我的代码在今天曾经修改过一次，请注意更新。
另外，关于我前面说的效率问题，还是用实际结果来表明吧：

1. #include <iostream>
   
2. #include <string>
   
3. #include <fstream>
   
4. #include <time.h>
   
5. #include "Sunday.h"
   
6. using namespace std;
   
7. 
   
8. int memfind(const char *mem, const char *str, int sizem, int sizes);
   
9. int main()
   
10. {
    
11.         //char Src[] = "fgjsderiodfda1546egdjkjdkfdadghh";
    
12.         //char Sub[] = "fda";
    
13.         /*char Src[] = {
    
14.                 0xBC, 0xBC, 0xBC, 0xBC, 0xBC, 0xBC, 0x1C, 0x65, 0x1F, 0x65, 0x1F, 0x65, 0xD1, 0x6D, 0xF1, 0xB6,
    
15.                 0x5A, 0xDF, 0x16, 0xD5, 0xF1, 0xA6, 0x5F, 0x4E, 0x91, 0xDF, 0xB6, 0x51, 0xD6, 0xF5, 0x1A, 0x65,
    
16.                 0xF1, 0x65, 0xBD, 0xF1, 0x65, 0x1F, 0x65, 0x16, 0xB5, 0x1F, 0xB6, 0x51, 0x65, 0x1E, 0x91, 0xDF,
    
17.                 0x65, 0x89, 0x76, 0x51, 0x6F, 0x19, 0x84, 0xDF, 0x65, 0x1B, 0x6D, 0xF5, 0x1B, 0x6F, 0x8B, 0x4A,
    
18.                 0xE9, 0x6F, 0x1B, 0x6D, 0xC5, 0xB1, 0x98, 0x76, 0x51, 0xD6, 0x57, 0x49, 0x8E, 0xA5, 0x61, 0xB9,
    
19.                 0x81, 0x65, 0x1E, 0x41, 0xB6, 0x5F, 0x1D, 0x65, 0x1D, 0x64, 0x8D, 0x91, 0x65, 0xD1, 0x65, 0x6D
    
20.         };
    
21.         char Sub[] = {0x65,0x1F, 0x65};*/
    
22.         ifstream ifile("F:\\新番\\第十七课.rar", ios::binary);
    
23.         ifile.seekg(0, ios::end);
    
24.         unsigned int szSrcLen = ifile.tellg();
    
25.         ifile.seekg(0, ios::beg);
    
26.         char* Src = new char[szSrcLen+1];
    
27.         ifile.read(Src, szSrcLen);
    
28.         ifile.close();
    
29.         char Sub[] = {
    
30.                 0x76, 0x41, 0xDB, 0x0C, 0xBF, 0x3C, 0x44, 0xAB
    
31.         };
    
32.         unsigned int dwTimeNew, dwTimeOld;
    
33.         dwTimeNew = clock();
    
34.         cout<<FSunday::Sunday(Src, szSrcLen, Sub, sizeof(Sub))<<endl;
    
35.         dwTimeOld = clock();
    
36.         cout<<"<FSunday::Sunday,耗时"<<dwTimeOld - dwTimeNew<<"ms"<<endl;
    
37.         dwTimeNew = clock();
    
38.         cout<<FSunday::SundayF(Src, szSrcLen, Sub, sizeof(Sub))<<endl;
    
39.         dwTimeOld = clock();
    
40.         cout<<"<FSunday::SundayF,耗时"<<dwTimeOld - dwTimeNew<<"ms"<<endl;
    
41.         dwTimeNew = clock();
    
42.         cout<<FSunday::SundayB(Src, szSrcLen, Sub, sizeof(Sub))<<endl;
    
43.         dwTimeOld = clock();
    
44.         cout<<"<FSunday::SundayB,耗时"<<dwTimeOld - dwTimeNew<<"ms"<<endl;
    
45.         dwTimeNew = clock();
    
46.         cout<<FSunday::SundayW(Src, szSrcLen, Sub, sizeof(Sub))<<endl;
    
47.         dwTimeOld = clock();
    
48.         cout<<"<FSunday::SundayW,耗时"<<dwTimeOld - dwTimeNew<<"ms"<<endl;
    
49.         dwTimeNew = clock();
    
50.         cout<<FSunday::SundayDW(Src, szSrcLen, Sub, sizeof(Sub))<<endl;
    
51.         dwTimeOld = clock();
    
52.         cout<<"<FSunday::SundayDW,耗时"<<dwTimeOld - dwTimeNew<<"ms"<<endl;
    
53.         dwTimeNew = clock();
    
54.         cout<<memfind(Src, Sub, szSrcLen, sizeof(Sub))<<endl;
    
55.         dwTimeOld = clock();
    
56.         cout<<"memfind,耗时"<<dwTimeOld - dwTimeNew<<"ms"<<endl;
    
57.        
    
58.         cout << "Hello world!" << endl;
    
59.         delete []Src;
    
60.        
    
61.         system("pause");
    
62.         return 0;
    
63. }
    
64. 
    
65. int memfind(const char *mem, const char *str, int sizem, int sizes)
    
66. {
    
67.         int da,i,j;
    
68.         if (sizes == 0) da = strlen(str);
    
69.         else da = sizes;
    
70.         for (i = 0; i < sizem; i++)
    
71.         {
    
72.                 for (j = 0; j < da; j ++)
    
73.                 {
    
74.                         if (mem[i+j] != str[j])
    
75.                                 break;
    
76.                 }
    
77.                 if (j == da)
    
78.                         return i;
    
79.         }
    
80.         return -1;
    
81. }

复制代码

    测试文件大小124MB,Sub位置112359584(0x6B278A0),应该算是够大的了，测试结果如下：

     注意一下，这个文件只有100来MB大小，时间相差近3倍，如果再弄大点的，子字符串再长点的话，时间差将会变得更大。所以，改进这个算法还是有必要的。比如，子字符串扩展到32位的时候结果如下：

    时间差在10倍以上！！！其余的就不多解析了

heihu

测试时候是直接填写的要查找的字符串所以查找不到，要用十六进制才能查找，谢谢F8老师啦

heihu

F8LEFT 发表于 2015-4-15 20:22
没啥好说的了，多少人为了提高算法的效率而不断的钻研。我这边因为环境问题所以测试得挺少的，所以 ...

不是说我用发的那个查找代码来跟你的算法比较，在处理大数据的时候根本就没法比的，那个只能用来查数据量小的,在小数据情况下的话可能没有多少区别{:soso_e113:}。因为用你的算法没查到所以用这个试了下

menglv

怎么将上面的组装在一起？就是组装成可以编译的源代码。

menglv

120M的文件vb打开到数组，只需要250毫秒，这里打开居然用了9703ms，当然这一切都是在我的IBM X60里面测试的。
我的X60用了ssd固态硬盘，win10只需要10秒以内启动。
为什么第二个计时会那么长？

F8LEFT

menglv 发表于 2015-5-24 17:43
120M的文件vb打开到数组，只需要250毫秒，这里打开居然用了9703ms，当然这一切都是在我的IBM X60里面测试 ...

第一、代码该如何封装，那是你的问题了。看你喜欢怎么封装就怎么封装吧。代码应该是没有问题的。
第二、读取文件一般是读一段判断一段的。至于你读文件为啥这么慢，我怎么会知道啊，检查一下自己的代码吧。
第三、看我代码中的注释，我想注释是足够的。SundayF是原始的Sunday算法！！！

menglv

这里的测试文件是30Mb
看来在比较复杂的查找SundayF还是有一定的优势的
Offset      0  1  2  3  4  5  6  7   8  9  A  B  C  D  E  F

00000000   00 00 00 00 00 00 00 00  00 00 00 00 00 FD FD F0                ??
00000010   00 00 00 00 00 00 00 00  00 00 00 00 00 FD FD F0                ??
00000020   00 00 00 00 00 00 00 00  00 00 00 00 00 FD FD F0                ??
......
Offset      0  1  2  3  4  5  6  7   8  9  A  B  C  D  E  F

01DFFFC0   00 00 FD FD F0 00 00 00  00 00 00 00 00 00 00 00     ??         
01DFFFD0   00 00 FD FD F0 00 00 00  00 00 00 00 00 00 00 00     ??         
01DFFFE0   00 00 FD FD F0 00 00 00  00 00 00 00 00 00 00 00     ??         
01DFFFF0   00 00 FD FD F0 00 00 00  00 00 00 00 00 FD FD F1     ??       ??

当查找00 00 FD FD F0 00 00 00  00 00 00 00 00 FD FD F1时确实是Sunday最快。

menglv

好像不是很方便改成模糊hex查找。
有点明白了，原来那五个过程是不一样的，所以时间也不一样。
总体来说还是一个很不错的算法。

menglv

menglv 发表于 2015-5-25 11:42
好像不是很方便改成模糊hex查找。
有点明白了，原来那五个过程是不一样的，所以时间也不一样。
总体来说 ...

不好意思，刚刚看到支持模糊查找了，强力支持楼主，下来测试一下效率。