12

Is there a public implementation of the Rope data structure in C#?

luvieere
  • 37,065
  • 18
  • 127
  • 179
  • 6
    If you have a scenario where this data structure is more optimal than a string builder, I would be curious to know what it is. It has been my experience that rope data structures are almost never a win over the raw speed of native string or string builder operations in typical cases, so I am very interested to see realistic scenarios where its a win. – Eric Lippert Dec 07 '09 at 22:24
  • I'm so very much curious as you are... that's why there goes another question! – luvieere Dec 07 '09 at 22:37
  • 2
    For one task, I want to start from an empty string and then insert a character in the middle of a string for millions of times. A string will not be efficient in this case. Rope may not be right in its original form, but we can adapt it to my particular application. – user172818 May 18 '12 at 19:15

4 Answers4

15

For what its worth, here is an immutable Java implementation. You could probably convert it to C# in less than an hour.

Juliet
  • 80,494
  • 45
  • 196
  • 228
14

I'm not aware of a Rope implementation (though there probably is one!), but if you're only after doing concatenation, StringBuilder will do the job.

Richard
  • 29,854
  • 11
  • 77
  • 120
  • Very true here. I did an implementation in C# a while ago where I used a 'linked list' of char arrays and no matter what, it could not beat the StringBuilder class. The problem comes when you are trying to tie those together for concatenation, you do not have access to a couple of native methods that the StringBuilder class has access to for allocating a buffer and copying the characters in. – esac Dec 15 '09 at 17:42
  • 1
    @esac - could you post your C# implementation (hopefully under a LGPL / BSD type license)? Perhaps we could investigate some additional strategies for perf. – torial Mar 15 '12 at 20:33
  • @torial: unfortunately I do not have that anymore. I did this for prototyping back when I was on the Windows team at Microsoft, so even if I had it, I could no share it out, sorry! – esac Mar 18 '12 at 20:56
2

The BigList<T> class from Wintellect Power Collections (a C# data structure library) is somehow similar to rope: 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

I measured its performance and it performs pretty well in "start of string inserts":

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);

Results:

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

But it performs not well in "middle of string inserts":

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);

Results:

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

I am not sure if this is a bug or unefficient implementation, but "rope of chars" is expected to be faster that StringBuilder in C#.

You can install Power Collections from NuGet:

Install-Package XAct.Wintellect.PowerCollections
Svetlin Nakov
  • 1,599
  • 18
  • 19
1

Here is a public implementation of Ropes in C#, based on the immutable java implementation listed above. Note that you won't get the same polymorphism benefits as the java version because strings can't be inherited and CharSequence doesn't exist natively in C#.

Adam
  • 49
  • 1
  • 7