在C#中公开实现ropes？

Question

C#中是否有Rope数据结构的公共实现？

Answer 1

不管怎么说，here is an immutable Java implementation。您可能会在不到一个小时的时间内将其转换为C#。

Answer 2

我不知道有Rope实现(虽然可能有！)，但是如果你只想做连接，StringBuilder就可以完成这项工作。

Answer 3

来自Wintellect Power Collections (一个C#数据结构库)的BigList<T>类在某种程度上类似于C#：http://docs.pushtechnology.com/docs/4.5.7/dotnet/externalclient/html/class_wintellect_1_1_power_collections_1_1_big_list_3_01_t_01_4.html

我测量了它的性能，它在“字符串插入的开始”中表现得很好：

const int InsertCount = 150000;

var startTime = DateTime.Now;
var ropeOfChars = new BigList<char>();
for (int i = 0; i < InsertCount; i++)
{
    ropeOfChars.Insert(0, (char)('a' + (i % 10)));
}
Console.WriteLine("Rope<char> time: {0}", DateTime.Now - startTime);

startTime = DateTime.Now;
var stringBuilder = new StringBuilder();
for (int i = 0; i < InsertCount; i++)
{
    stringBuilder.Insert(0, (char)('a' + (i % 10)));
}
Console.WriteLine("StringBuilder time: {0}", DateTime.Now - startTime);

结果：

Rope<char> time: 00:00:00.0468740
StringBuilder time: 00:00:05.1471300

但它在“插入字符串的中间”时表现不佳：

const int InsertCount = 150000;

var startTime = DateTime.Now;
var ropeOfChars = new BigList<char>();
for (int i = 0; i < InsertCount; i++)
{
    ropeOfChars.Insert(ropeOfChars.Count / 2, (char)('a' + (i % 10)));
}
Console.WriteLine("Rope<char> time: {0}", DateTime.Now - startTime);

startTime = DateTime.Now;
var stringBuilder = new StringBuilder();
for (int i = 0; i < InsertCount; i++)
{
    stringBuilder.Insert(stringBuilder.Length / 2, (char)('a' + (i % 10)));
}
Console.WriteLine("StringBuilder time: {0}", DateTime.Now - startTime);

结果：

Rope<char> time: 00:00:15.0229452
StringBuilder time: 00:00:04.7812553

我不确定这是一个错误还是低效的实现，但是"rope of chars“应该比C#中的StringBuilder更快。

您可以从NuGet安装电源收集器：

Install-Package XAct.Wintellect.PowerCollections