Публичная реализация канатов в C#?

Question

Существует ли публичная реализация структуры данных Rope в C#?

Answer 1

Для чего это стоит, вот неизменная реализация Java. Вы могли бы, вероятно, преобразовать его в C# менее чем за час.

Answer 2

Я не знаю о реализации Rope (хотя, вероятно, есть одна!), Но если вы только после выполнения конкатенации, StringBuilder сделает эту работу.

Answer 3

BigList<T> класс из Wintellect Power Collections (библиотека структуры данных 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"Ожидается, что будет быстрее, чем StringBuilder в C#.

Вы можете установить Power Collections от NuGet:

Install-Package XAct.Wintellect.PowerCollections

Answer 4

Вот публичная реализация Ropes в C#, основанная на неизменной реализации Java, перечисленной выше. Обратите внимание, что вы не получите тех же преимуществ полиморфизма, что и в java-версии, поскольку строки не могут быть унаследованы, а CharSequence не существует в C#.