Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > rope vs. string

Reply
Thread Tools

rope vs. string

 
 
James Aguilar
Guest
Posts: n/a
 
      03-27-2005
Hey all,

I have a program that runs the Manber-Myers suffix array search algorithm
with longest common prefix values. I need an efficient way to represent a
sequential array of characters to be passed into the algorithm. Here are
the features I need for the representation:

* Must be randomly accessible in constant time
* Must be capable of efficiently storing strings of more than 10 million
characters

Here are some plusses:

* Dereferencing an iterator should be fast, not just constant time, but
quick constant time, since it will be happening often (at least (size of
pattern) + log(size of text) times)
* Incrementing an iterator should be similarly fast

It would also be useful if this representation provided an efficient method
of extracting all the characters for the problem from the standard input
(again, no less than 5 million characters, randomly distributed among A, C,
G, and T).

Now, here's the question: which is better for this problem, a string or a
rope. If a rope would be best, can you offer any guidance as to ways to
make the use of the rope as fast and painless as possible (if that is the
preferable representation).

- JFA1


 
Reply With Quote
 
 
 
 
Ivan Vecerina
Guest
Posts: n/a
 
      03-27-2005
"James Aguilar" <(E-Mail Removed)> wrote in message
news:d2532a$g4q$(E-Mail Removed)...
Hi James,
> I have a program that runs the Manber-Myers suffix array search algorithm
> with longest common prefix values. I need an efficient way to represent a
> sequential array of characters to be passed into the algorithm. Here are
> the features I need for the representation:
>
> * Must be randomly accessible in constant time
> * Must be capable of efficiently storing strings of more than 10 million
> characters
>
> Here are some plusses:
>
> * Dereferencing an iterator should be fast, not just constant time, but
> quick constant time, since it will be happening often (at least (size of
> pattern) + log(size of text) times)
> * Incrementing an iterator should be similarly fast
>
> It would also be useful if this representation provided an efficient
> method of extracting all the characters for the problem from the standard
> input (again, no less than 5 million characters, randomly distributed
> among A, C, G, and T).
>
> Now, here's the question: which is better for this problem, a string or a
> rope. If a rope would be best, can you offer any guidance as to ways to
> make the use of the rope as fast and painless as possible (if that is the
> preferable representation).


The implementation of rope::iterator is somewhat more complex than for
string (where it is basically a pointer), and will introduce an overhead.

The only true advantage of a rope (i.e. the non-standard rope class from
the SGI STL) is that it supports efficient *editing* of a small portion
of the string (not just replacing, but also inserting/deleting/splicing
subsequences within the original string). Unless this is relevant to
what you need to do, there is no point in using rope instead of string.

The caveat with std::string, depending on how the platform you use
implements the standard library, is to try to avoid unnecessary copies
of the data structure (be careful to pass the strings as references
whenever possible, to avoid object copies in case your implementation
does not use reference-counting).

In case top performance is critical, passing the input as a file
and mapping it into memory (with platform-specific mmap/MapViewOfFile),
will most likely be the fastest approach at run-time.

Note also that your algorithm could be templated on the iterator type,
allowing it to be used on any type of source data range.


I hope this helps,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Brainbench MVP for C++ <> http://www.brainbench.com


 
Reply With Quote
 
 
 
 
James Aguilar
Guest
Posts: n/a
 
      03-27-2005
Oh! Thanks for the help. I didn't realize the rope was not in -the- STL.
I got the sense from the site that I was reading that it was. If it's not
standard, I'm not going to mess with it, as it is only for a homework
assignment. Thank you so much for your advice nonetheless.

- JFA1


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Give Them Enough Rope, They Will Hang Themselves ... Lawrence D'Oliveiro NZ Computing 0 05-11-2010 09:04 AM
rope python-emacs problem Rustom Mody Python 2 10-16-2008 06:53 AM
rope class (heavyweight string) castironpi Python 0 09-02-2008 06:33 PM
"more than enough rope" Giles Bowkett Ruby 7 12-06-2006 02:41 AM
sgi rope experiences? =?ISO-8859-1?Q?S=F6ren?= C++ 0 07-29-2003 12:04 AM



Advertisments