c# - 在 C# 中公开实现绳索？

Question

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

Answer 1

对于它的价值，这是一个不可变的 Java 实现。您可能会在不到一个小时内将其转换为 C#。

Answer 2

我不知道 Rope 实现（尽管可能有一个！），但如果您只是在进行连接之后，StringBuilder将完成这项工作。

Answer 3

Wintellect Power Collections（C# 数据结构库）中的BigList<T>类在某种程度上类似于绳索： 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”预计会比StringBuilderC# 中的更快。

您可以从 NuGet 安装 Power Collections：

Install-Package XAct.Wintellect.PowerCollections

Answer 4

这是 C# 中 Ropes 的公共实现，基于上面列出的不可变 java 实现。请注意，您不会获得与 java 版本相同的多态性好处，因为字符串不能被继承，并且 CharSequence 在 C# 中本机不存在。