擂台：改进 String.CompareOrdinal 性能
--------------------编程问答-------------------- string s0 = "A quick brown fox jumps over a lazy jog. ";--------------------编程问答-------------------- --------------------编程问答-------------------- 袁峰？ 真的假的 --------------------编程问答-------------------- 我也姓袁，在学习c#，可能的话加下我ＱＱ546541056 --------------------编程问答--------------------
static int CompareOrdinal_Leaf(string s1, string s2)
{
if (s1 == null && s2 == null)
return 0;
if (s1 == null)
return -1;
if (s2 == null)
return 1;
int min_len = s1.Length <= s2.Length ? s1.Length : s2.Length;
char[] a1 = s1.ToCharArray();
char[] a2 = s2.ToCharArray();
for (int i = 0; i < min_len; i++)
{
if (a1[i] > a2[i])
return 1;
if (a1[i] < a2[i])
return -1;
}
if (s1.Length > s2.Length)
return 1;
if (s1.Length < s2.Length)
return -1;
return 0;
}
自己写的函数，运行结果 （不用 native 好慢啊）
Short 12887.7371 ms -100000000
Long 63571.6361 ms -10000000
Total time 76459.3732 ms
用系统原生的函数，运行结果
Short 5321.3044 ms -100000000
Long 3575.2044 ms -10000000
Total time 8896.5088 ms
--------------------编程问答-------------------- 哈哈，楼上的太太慢了。重写。 --------------------编程问答-------------------- --------------------编程问答-------------------- Mark一下，回家写，大学的时候用Pascal时间实现过KMP... --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答--------------------
unsafe static int MyCompare(string a, string b)
{
int pre, len, tmp;
tmp = a.Length - b.Length;
if (tmp > 0)
{
len = a.Length;
pre = 1;
}
else if (tmp < 0)
{
len = b.Length;
pre = -1;
}
else
{
len = a.Length;
pre = 0;
}
fixed (char* pa = a)
fixed (char* pb = b)
{
for (int i = 0; i < len; i++)
{
int re = (int)(*pa) - (int)(*pb);
if (re != 0)
return re;
}
}
return pre;
}
String.CompareOrdinal
=====================
Short 3995.7456 ms -100000000
Long 4226.0768 ms -10000000
Total time 8221.8224 ms
MyCompare
=========
Short 2864.1184 ms -100000000
Long 11726.8624 ms -10000000
Total time 14590.9808 ms
--------------------编程问答-------------------- 上面代码作废，写完没检查。。。
下修正
static int MyCompare(string a, string b)
{
int pre, len, tmp;
tmp = a.Length - b.Length;
if (tmp > 0)
{
len = b.Length;
pre = 1;
}
else if (tmp < 0)
{
len = a.Length;
pre = -1;
}
else
{
len = a.Length;
pre = 0;
}
for (int i = 0; i < len; i++)
{
int re = (int)(a[i]) - (int)(b[i]);
if (re != 0)
return re;
}
return pre;
}
MyCompare
================
Short 2743.9456 ms -100000000
Long 21961.5792 ms -10000000
Total time 24705.5248 ms --------------------编程问答-------------------- 看来长的比较难 --------------------编程问答-------------------- 指针快一些
unsafe static int MyCompareUnsafe(string a, string b)
{
int pre, len, tmp;
tmp = a.Length - b.Length;
if (tmp > 0)
{
len = b.Length;
pre = 1;
}
else if (tmp < 0)
{
len = a.Length;
pre = -1;
}
else
{
len = a.Length;
pre = 0;
}
fixed (char* pa = a)
fixed (char* pb = b)
{
for (int i = 0; i < len; i++)
{
int re = (int)(*(pa + i)) - (int)(*(pb + i));
if (re != 0)
return re;
}
}
return pre;
}
MyCompareUnsafe
===================
Short 2824.0608 ms -100000000
Long 11566.632 ms -10000000
Total time 14390.6928 ms --------------------编程问答-------------------- 可以对N次进行比较结果进行缓存, 进而可将N次的比较时间, 简化成1次比较时间 + (N - 1) 循环累加时间 --------------------编程问答-------------------- 不可以缓存，这只是性能测试程序。
有没有人看过汇编指令？ --------------------编程问答-------------------- mark 下，发现string.CompareOrdinalHelper 对长的比较速度非常惊人。 --------------------编程问答-------------------- mark下，回头来看。
不用Native Code有难度。 --------------------编程问答-------------------- --------------------编程问答-------------------- 看了一下CompareOrdinalHelper(string strA, string strB)的实现，真不是一般的复杂。
自己写的代码要慢很多了。 --------------------编程问答-------------------- --------------------编程问答--------------------
static unsafe int StringCompare2(string a, string b)
{
fixed (char* pa = a, pb = b)
{}
return 1;
}
最快的方式 能想到的 就是用指针吧
但是这样的一个程序
Short 1933.5937 ms 100000000
就花了这么多时间
LZ的程序才
Short 2364.2578 ms -100000000
只有400ms的时间能做什么?
Short 1933.5937 ms 100000000 --------------------编程问答-------------------- Short 3316.4063 ms -100000000
Long 4416.0156 ms -10000000
我已经是极限了...
为什么系统的快,因为系统的string类中有一个private 的char类型字段m_firstChar;
指示string的第一个char字符
系统使用fixed (char* chRef = &m_firstChar)方式获得指针 1940 ms
而我们需要使用fixed (char* chRef = (string)s1)方式获得指针 2270 ms
相差了300 ms的效率 而且是2个string 就相差了近 650 ms的效率
不过即使如此,就算减去650ms 我写的程序的效率也是没有系统高......
--------------------编程问答-------------------- 我的
static int StringCompare2(string a, string b)
{
int min_len = 0;
try
{
min_len = a.Length > b.Length ? b.Length : a.Length;
}
catch
{
if (a == b)
return 0;
if (a != null)
return 1;
if (b != null)
return -1;
}
unsafe
{
fixed (char* pa = a, pb = b)
{
int i = 0;
if (min_len < 16)
{
while (min_len > i)
{
if (pa[i] != pb[i])
{
return pa[i] > pa[i] ? 1 : -1;
}
i++;
}
}
i = min_len - aaa(pa, pb, min_len);
if (i == min_len)
{
if (min_len == b.Length)
{
return min_len == a.Length ? 0 : 1;
}
return -1;
}
while (true)
{
if (pa[i] != pb[i])
{
return pa[i] > pa[i] ? 1 : -1;
}
i++;
}
}
}
return 1;
throw new Exception("不可能");
}
Short 4071 ms -100000000
Long 3890 ms -10000000
系统的
Short 2310 ms -100000000
Long 1978 ms -10000000
好吧 我放弃了
static int StringCompare2(string a, string b)
{
int min_len = 0;
try
{
min_len = a.Length > b.Length ? b.Length : a.Length;
}
catch
{
if (a == b)
return 0;
if (a != null)
return 1;
if (b != null)
return -1;
}
unsafe
{
fixed (char* pa = a, pb = b)
{
int i = min_len - aaa(pa, pb, min_len);
if (i == min_len)
{
if (min_len == b.Length)
{
return min_len == a.Length ? 0 : 1;
}
return -1;
}
while (true)
{
if (pa[i] != pb[i])
{
return pa[i] > pa[i] ? 1 : -1;
}
i++;
}
}
}
}
private static unsafe int aaa(char* pa, char* pb, int charCount)
{
while (charCount >= 32)
{
if (*((long*)pa) != *((long*)pb))
{
return charCount;
}
if (*((long*)(pa + 4)) != *((long*)(pb + 4)))
{
return charCount;
}
if (*((long*)(pa + 8)) != *((long*)(pb + 8)))
{
return charCount;
}
if (*((long*)(pa + 12)) != *((long*)(pb + 12)))
{
return charCount;
}
if (*((long*)(pa + 16)) != *((long*)(pb + 16)))
{
return charCount;
}
if (*((long*)(pa + 20)) != *((long*)(pb + 20)))
{
return charCount;
}
if (*((long*)(pa + 24)) != *((long*)(pb + 24)))
{
return charCount;
}
if (*((long*)(pa + 28)) != *((long*)(pb + 28)))
{
return charCount;
}
pa += 32;
pb += 32;
charCount -= 32;
}
while (charCount >= 8)
{
if (*((long*)pa) != *((long*)pb))
{
return charCount;
}
if (*((long*)(pa + 4)) != *((long*)(pb + 4)))
{
return charCount;
}
pa += 8;
pb += 8;
charCount -= 8;
}
return charCount;
}
--------------------编程问答-------------------- 在Release模式下
我的胜一次 败一次
我的
Short 1786 ms -100000000
Long 1286 ms -10000000
系统的
Short 1311 ms -100000000
Long 1872 ms -10000000 --------------------编程问答-------------------- --------------------编程问答-------------------- static int CompareOrdinal_Leaf(string s1, string s2)
{
if (s1 == null && s2 == null)
return 0;
if (s1 == null)
return -1;
if (s2 == null)
return 1;
int min_len = s1.Length <= s2.Length ? s1.Length : s2.Length;
char[] a1 = s1.ToCharArray();
char[] a2 = s2.ToCharArray();
for (int i = 0; i < min_len; i++)
{
if (a1[i] > a2[i])
return 1;
if (a1[i] < a2[i])
return -1;
}
if (s1.Length > s2.Length)
return 1;
if (s1.Length < s2.Length)
return -1;
return 0;
}
--------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- if (*((long*)pa) != *((long*)pb))
{
return charCount;
}
return charCount 是错的，应该看第一个字符的差。 --------------------编程问答-------------------- 哎，太复杂
--------------------编程问答-------------------- 居然可以用 unsafe 指针， 不是不能调用 native code 吗
--------------------编程问答-------------------- 哎，太复杂
--------------------编程问答--------------------
这个是4个char 一起判断,只要不对就说明其中有一个错了
然后再一个一个判断 --------------------编程问答--------------------
不能用只能想超越系统的不可能的吧....
-----------------------------------------------------------
char:2个字节 16位
int：4个字节 32位
long：8字节 64位
改用long的指针,一次可以判断4和char,如果相同判断下4个
如果不同,返回当前位置
然后程序再进行逐位判断 --------------------编程问答-------------------- 我刚上论坛，大家以后多照顾！ --------------------编程问答--------------------
--------------------编程问答--------------------
第三版....完整源码如下,使用Ctrl+F5,(不调试模式)运行,才能比系统的快,
调试模式就比系统的慢
--------------------编程问答-------------------- 楼上的不就是反编译系统的 String.CompareOrdinal 代码吗。。。。。。。
static int StringCompare(string s1, string s2)
{
return String.CompareOrdinal(s1, s2);
}
static int StringCompare2(string a, string b)
{
int min_len = 0;
try
{
min_len = a.Length > b.Length ? b.Length : a.Length;
}
catch
{
if (a == b)
return 0;
if (a != null)
return 1;
if (b != null)
return -1;
}
unsafe
{
fixed (char* pa = a, pb = b)
{
int i = min_len < 8 ? 0 : min_len - aaa((long*)pa, (long*)pb, min_len);
if (i != min_len)
{
while (i <= min_len)
{
if (pa[i] != pb[i])
{
return pa[i] > pb[i] ? 1 : -1;
}
i++;
}
}
if (min_len == b.Length)
{
return min_len == a.Length ? 0 : 1;
}
return -1;
}
}
}
private static unsafe int aaa(long* pa, long* pb, int charCount)
{
while (charCount >= 32)
{
if (*pa != *pb)
{
return charCount;
}
if (*(pa + 1) != *(pb + 1))
{
charCount -= 4;
return charCount;
}
if (*(pa + 2) != *(pb + 2))
{
charCount -= 8;
return charCount;
}
if (*(pa + 3) != *(pb + 3))
{
charCount -= 12;
return charCount;
}
if (*(pa + 4) != *(pb + 4))
{
charCount -= 16;
return charCount;
}
if (*(pa + 5) != *(pb + 5))
{
charCount -= 20;
return charCount;
}
if (*(pa + 6) != *(pb + 6))
{
charCount -= 24;
return charCount;
}
if (*(pa + 7) != *(pb + 7))
{
charCount -= 28;
return charCount;
}
pa += 8;
pb += 8;
charCount -= 32;
}
while (charCount >= 8)
{
if (*pa != *pb)
{
return charCount;
}
if (*(pa + 1) != *(pb + 1))
{
charCount -= 4;
return charCount;
}
pa += 2;
pb += 2;
charCount -= 8;
}
return charCount;
}
static long CompareLoop(string s1, string s2, int count, out int result)
{
result = 0;
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < count; i++)
{
result += StringCompare(s1, s2);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
static long CompareLoop2(string s1, string s2, int count, out int result)
{
result = 0;
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < count; i++)
{
result += StringCompare2(s1, s2);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
static void Main(string[] args)
{
//StringCompare2("aaaaa", "aaaab");
string s0 = "A quick brown fox jumps over a lady jog. ";
string s1 = String.Empty;
for (int i = 0; i < 10; i++)
{
s1 = s1 + s0;
}
string s2 = s1 + "A";
int count = 10 * 1000 * 1000;
int result1;
int result2;
double t1;
double t2;
Console.WriteLine("系统方法");
t1 = CompareLoop("b", "a", count * 10, out result1);
t2 = CompareLoop(s1, s2, count, out result2);
Console.WriteLine("Short {0} ms {1} ", t1, result1);
Console.WriteLine("Long {0} ms {1} ", t2, result2);
Console.WriteLine("自定义方法");
t1 = CompareLoop2("b", "a", count * 10, out result1);
t2 = CompareLoop2(s1, s2, count, out result2);
Console.WriteLine("Short {0} ms {1} ", t1, result1);
Console.WriteLine("Long {0} ms {1} ", t2, result2);
Console.Read();
}
这样都行？
题目要求不能用 unsafe --------------------编程问答-------------------- Wow! Very nice post. I so love it..
<a href=http://www.popbrandcaps.com>monster hats</a>
monster hats
<a href="http://www.popbrandcaps.com" title="monster hats">monster hats</a>
[url=http://www.popbrandcaps.com monster hats] --------------------编程问答-------------------- 厉害啊 --------------------编程问答-------------------- 学习！！！ --------------------编程问答--------------------
public static int CompareOrdinal(string strA, string strB)
{
if (strA == strB)
{
return 0;
}
if (strA == null)
{
return -1;
}
if (strB == null)
{
return 1;
}
return CompareOrdinalHelper(strA, strB);
}
private static unsafe int CompareOrdinalHelper(string strA, string strB)
{
int num = Math.Min(strA.Length, strB.Length);
int num2 = -1;
fixed (char* str = ((char*) strA))
{
char* chPtr = str;
fixed (char* str2 = ((char*) strB))
{
char* chPtr2 = str2;
char* chPtr3 = chPtr;
char* chPtr4 = chPtr2;
while (num >= 10)
{
if (*(((int*) chPtr3)) != *(((int*) chPtr4)))
{
num2 = 0;
break;
}
if (*(((int*) (chPtr3 + 2))) != *(((int*) (chPtr4 + 2))))
{
num2 = 2;
break;
}
if (*(((int*) (chPtr3 + 4))) != *(((int*) (chPtr4 + 4))))
{
num2 = 4;
break;
}
if (*(((int*) (chPtr3 + 6))) != *(((int*) (chPtr4 + 6))))
{
num2 = 6;
break;
}
if (*(((int*) (chPtr3 + 8))) != *(((int*) (chPtr4 + 8))))
{
num2 = 8;
break;
}
chPtr3 += 10;
chPtr4 += 10;
num -= 10;
}
if (num2 == -1)
{
goto Label_0101;
}
chPtr3 += num2;
chPtr4 += num2;
int num3 = chPtr3[0] - chPtr4[0];
if (num3 != 0)
{
return num3;
}
return (chPtr3[1] - chPtr4[1]);
Label_00E7:
if (*(((int*) chPtr3)) != *(((int*) chPtr4)))
{
goto Label_0105;
}
chPtr3 += 2;
chPtr4 += 2;
num -= 2;
Label_0101:
if (num > 0)
{
goto Label_00E7;
}
Label_0105:
if (num > 0)
{
int num4 = chPtr3[0] - chPtr4[0];
if (num4 != 0)
{
return num4;
}
return (chPtr3[1] - chPtr4[1]);
}
return (strA.Length - strB.Length);
}
}
}
以上为源码
--------------------编程问答--------------------
不错。不过短的应该可以更快。 --------------------编程问答-------------------- 差太远。不贴了。。 --------------------编程问答-------------------- --------------------编程问答--------------------
系统的是这样的吗? --------------------编程问答--------------------
这个才是系统的吧 --------------------编程问答-------------------- 可以用 unsafe， 不能调用 native code。
--------------------编程问答--------------------
这个不好意思了....昨天通宵了..现在有点迷糊了...实在看不出了 --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答--------------------
在 unsafe 前加一句
if (min_len != 0)
{
int diff = a[0] - b[0];
if (diff != 0)
return diff;
} --------------------编程问答--------------------
=.=....这个优化太有针对性了吧,,,,万一来2个字符给你比较.... --------------------编程问答-------------------- 我到是想到一个,可以开多线程不......... --------------------编程问答--------------------
假设你比较的是英文单词或中文字，第一个不同的可能性很大。 --------------------编程问答-------------------- --------------------编程问答-------------------- 很好用 --------------------编程问答-------------------- 来学习！ --------------------编程问答-------------------- --------------------编程问答-------------------- study~ --------------------编程问答-------------------- 比这个能比出什么来？效率差别不在于这个 --------------------编程问答-------------------- 学习中，不错不错 --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答--------------------
厉害啊！！！！ --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- 呵呵。。。。。。。。。。用系统的 --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
内容存入剪贴
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
这么长。。。
--------------------编程问答--------------------
不是很明白呀。
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
牛逼！！！！！！
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
过来 学习下
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
补充：.NET技术 , C#
