使用
StringComparer comparer1 = StringComparer.Ordinal;
代替
IComparable v
IComparable w
comparer1.Compare(v, w)
解决了运行时问题。
我已经在Java和C#中完成了一些有关排序算法(例如Quicksort,Mergesort)的基准测试。
我使用Java 7和.NET Framework 4.5来实现和执行算法。结果表明,所有算法都可以使用Java获得更好的运行时。
Quicksort的一些示例运行时:
C#
爪哇
然后,我使用性能分析工具完成了一些测量工作:C#将75%的运行时用于字符串比较(即CompareTo),而Java仅将2%的运行时用于比较。
为什么字符串比较在C#中如此昂贵,而在Java中却如此?
编辑:我还测试了C#排序函数Arrays.sort(INPUT),对于n = 1000000,它可以实现约3000毫秒,所以我不认为代码是问题。但不管怎么说:
这是Quicksort的代码:
public class Quicksort {
public static void sort(IComparable[] a) {
sort(a, 0, a.Length - 1);
}
private static void sort(IComparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}
private static int partition(IComparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
IComparable v = a[lo];
while (true) {
while (less(a[++i], v))
if (i == hi) break;
while (less(v, a[--j]))
if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
public static IComparable select(IComparable[] a, int k) {
if (k < 0 || k >= a.Length) {
throw new Exception("Selected element out of bounds");
}
Rnd.Shuffle(a);
int lo = 0, hi = a.Length - 1;
while (hi > lo) {
int i = partition(a, lo, hi);
if (i > k) hi = i - 1;
else if (i < k) lo = i + 1;
else return a[i];
}
return a[lo];
}
private static bool less(IComparable v, IComparable w) {
return (v.CompareTo(w) < 0);
}
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
Quicksort的测量如下:
Stopwatch.Restart();
Quicksort.sort(stringArray);
Stopwatch.Stop();
EDIT2:有人想看看Java版本。这与我只使用Comparable而不是IComparable和Array.length而不是Array.Length完全相同
所以我不认为代码是问题
我不敢苟同。在两种情况下,您不会比较相同的事物。诚然,您也没有向我们展示如何生成字符串等,但是Java和.NET会执行不同的默认字符串比较,这无济于事。
从Java的String.compareTo
:
按字典顺序比较两个字符串。
从.NET的String.CompareTo
:
此方法使用当前区域性执行单词(区分大小写和区分区域性)的比较。
毫不奇怪,这比进行纯粹的字典比较要慢。
仅将.NET与自身进行比较时,很容易看到这一点。
using System;
using System.Diagnostics;
using System.Text;
class Test
{
static void Main()
{
string[] source = GenerateRandomStrings();
string[] workingSpace = new string[source.Length];
CopyAndSort(source, workingSpace);
Stopwatch sw = Stopwatch.StartNew();
for (int i = 0; i < 1000; i++)
{
CopyAndSort(source, workingSpace);
}
sw.Stop();
Console.WriteLine("Elapsed time: {0}ms",
(long) sw.Elapsed.TotalMilliseconds);
}
static string[] GenerateRandomStrings()
{
Random rng = new Random();
string[] ret = new string[10000];
for (int i = 0; i < ret.Length; i++)
{
ret[i] = GenerateRandomString(rng);
}
return ret;
}
static string GenerateRandomString(Random rng)
{
char[] chars = new char[30];
for (int i = 0; i < chars.Length; i++)
{
chars[i] = (char) rng.Next('A', 'z' + 1);
}
return new string(chars);
}
static void CopyAndSort(string[] original, string[] workingSpace)
{
Array.Copy(original, 0, workingSpace, 0, original.Length);
Array.Sort(workingSpace);
// Array.Sort(workingSpace, StringComparer.Ordinal);
}
}
自己尝试,CopyAndSort
根据是否指定序数字符串比较器来改变方法。这是多以序号比较器速度更快,至少在我的箱子。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句