473,322 Members | 1,911 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

_efficiently_ obtain n-th word from a std::string


Hi!

I need a routine like:

std::string nth_word(const std::string &s, unsigned int n) {
// return n-th word from the string, n is 0-based
// if 's' contains too few words, return ""
// 'words' are any sequences of non-whitespace characters
// leading, trailing and multiple whitespace characters
// should be ignored.
// eg. "These are four\t\twords\t\t".
}

I am currenlty using something like:

std::string nth_word(const std::string& source, unsigned int n) {
// the addition of " " allows for the extraction of the last
// word, after which ss would go eof() below if not for the space
stringstream ss(source+" ");
string s;
for(unsigned int k=0;k<=n;k++) {
ss >s;
if(!ss.good()) return ""; // eof
}
return s;
}

which is fine, except it performs poorly. Before I'm flamed
with accusations of premature optimization, let me tell you
that I profiled my code and over 50% of time is spent in this
routine. This does not surprise me -- I am extracting words
from text files in the order of GB and it takes annoyingly
long...

I'm thinking of a combination of find_first_not_of and
find_first_of, but before I code it, perhaps somebody can
comment on this? I have a gut feeling that some nasty
strtok hack would be even faster, would it? Or is there
perhaps some other, performance-oriented way like traversing
s.c_str() with a pointer and memcpying out the relevant part?

TIA,
- J.
May 9 '07 #1
11 2868
Jacek Dziedzic wrote:
>
Hi!

I need a routine like:

std::string nth_word(const std::string &s, unsigned int n) {
// return n-th word from the string, n is 0-based
// if 's' contains too few words, return ""
// 'words' are any sequences of non-whitespace characters
// leading, trailing and multiple whitespace characters
// should be ignored.
// eg. "These are four\t\twords\t\t".
}

I am currenlty using something like:

std::string nth_word(const std::string& source, unsigned int n) {
// the addition of " " allows for the extraction of the last
// word, after which ss would go eof() below if not for the space
stringstream ss(source+" ");
string s;
for(unsigned int k=0;k<=n;k++) {
ss >s;
if(!ss.good()) return ""; // eof
}
return s;
}

which is fine, except it performs poorly. Before I'm flamed
with accusations of premature optimization, let me tell you
that I profiled my code and over 50% of time is spent in this
routine. This does not surprise me -- I am extracting words
from text files in the order of GB and it takes annoyingly
long...

I'm thinking of a combination of find_first_not_of and
find_first_of, but before I code it, perhaps somebody can
comment on this? I have a gut feeling that some nasty
strtok hack would be even faster, would it? Or is there
perhaps some other, performance-oriented way like traversing
s.c_str() with a pointer and memcpying out the relevant part?
Nah. If efficiency is critical, I have found the istream interface a
bad solution.

Nothing like a state machine.

// warning - brain dump - not compiled ever - not tested - use at your
own peril

#include <cctype>

std::string nth_word(const std::string& source, unsigned int n)
{

enum state_type { inspace, inword };

std::string::const_iterator l_iter = source.begin();
const std::string::const_iterator l_end = source.end();

if ( l_end == l_iter )
{
return "";
}
std::string::const_iterator l_beg_word = l_iter;

state_type state = ( std::isspace( * l_iter ) ) ? inspace : inword;

int word_count = state == inspace ? 0 : 1;

++ l_iter;

while ( l_end != l_iter )
{

switch ( state )
{
case inspace :

if ( std::isspace( * l_iter ) ) break;
state = inword;
l_beg_word = l_iter;
++ word_count;
break;

case inword :

if ( ! std::isspace( * l_iter ) ) break;
state = inspace;

if ( n == word_count )
{
return std::string( l_beg_word, l_iter );
}
break;
}

++ l_iter;
}

switch ( state )
{
case inspace :
return "";
case inword :
if ( n == word_count )
{
return std::string( l_beg_word, l_iter );
}
return "";
}

return "";
}
May 9 '07 #2
Gianni Mariani wrote:
Jacek Dziedzic wrote:
....
> which is fine, except it performs poorly. Before I'm flamed
....

oh - I forgot to mention, if you extend the state machine a little, you
can apply the state machine to an entire file. Then you can mmap the
entire file and never copy the file into and out of buffers.
May 9 '07 #3
Hi

Jacek Dziedzic wrote:
I need a routine like:

std::string nth_word(const std::string &s, unsigned int n) {
// return n-th word from the string, n is 0-based
// if 's' contains too few words, return ""
// 'words' are any sequences of non-whitespace characters
// leading, trailing and multiple whitespace characters
// should be ignored.
// eg. "These are four\t\twords\t\t".
}

I am currenlty using something like:

std::string nth_word(const std::string& source, unsigned int n) {
// the addition of " " allows for the extraction of the last
// word, after which ss would go eof() below if not for the space
stringstream ss(source+" ");
string s;
for(unsigned int k=0;k<=n;k++) {
ss >s;
if(!ss.good()) return ""; // eof
}
return s;
}

which is fine, except it performs poorly. Before I'm flamed
with accusations of premature optimization, let me tell you
that I profiled my code and over 50% of time is spent in this
routine. This does not surprise me -- I am extracting words
from text files in the order of GB and it takes annoyingly
long...
I'm afraid that your efforts will not help much.
If your n-th word starts at position i in your text file, you will have
to inspect all preceding positions to know that (well, not entirely
true, in some circumstances you can skip a character, but that doesn't
really matter). If your text contains billions of characters, that might
take very long.

The single overhead that could be avoided is copying strings that you
don't need at all. It would of course be enough to iterate over the
string and count the number of words until you have found the n-th word.
If you go architecture dependent, mmx or other streaming instructions
might be able to help you (I really don't know... mmx has comparison
instructions for 8 packed bytes, but I wonder if this will provide any
speed-up, as you would have to check results for each byte)
I'm thinking of a combination of find_first_not_of and
find_first_of, but before I code it, perhaps somebody can
comment on this? I have a gut feeling that some nasty
strtok hack would be even faster, would it? Or is there
perhaps some other, performance-oriented way like traversing
s.c_str() with a pointer and memcpying out the relevant part?
I would not recommend any of those...

Use a string::iterator. Inspect the individual characters. Have a
current state (word, non-word), update the state according to what you
read. Count toggles. Construct a string from the n-th word.

Markus
May 9 '07 #4
Markus Moll wrote:
Hi

Jacek Dziedzic wrote:
> I need a routine like:

std::string nth_word(const std::string &s, unsigned int n) {
// return n-th word from the string, n is 0-based
// if 's' contains too few words, return ""
// 'words' are any sequences of non-whitespace characters
// leading, trailing and multiple whitespace characters
// should be ignored.
// eg. "These are four\t\twords\t\t".
}

I am currenlty using something like:

std::string nth_word(const std::string& source, unsigned int n) {
// the addition of " " allows for the extraction of the last
// word, after which ss would go eof() below if not for the space
stringstream ss(source+" ");
string s;
for(unsigned int k=0;k<=n;k++) {
ss >s;
if(!ss.good()) return ""; // eof
}
return s;
}

which is fine, except it performs poorly. Before I'm flamed
with accusations of premature optimization, let me tell you
that I profiled my code and over 50% of time is spent in this
routine. This does not surprise me -- I am extracting words
from text files in the order of GB and it takes annoyingly
long...

I'm afraid that your efforts will not help much.
If your n-th word starts at position i in your text file, you will have
to inspect all preceding positions to know that (well, not entirely
true, in some circumstances you can skip a character, but that doesn't
really matter). If your text contains billions of characters, that might
take very long.
Fortunately I'm only splitting individual lines into words.
I don't need to search through the file or anything like that,
only something like

for all lines in the file {
depending on word 0 in the line, extract some other word from the line
convert this word to a double, operate on it, output result
}
The single overhead that could be avoided is copying strings that you
don't need at all. It would of course be enough to iterate over the
string and count the number of words until you have found the n-th word.
If you go architecture dependent, mmx or other streaming instructions
might be able to help you (I really don't know... mmx has comparison
instructions for 8 packed bytes, but I wonder if this will provide any
speed-up, as you would have to check results for each byte)
I'd like that to be portable.
> I'm thinking of a combination of find_first_not_of and
find_first_of, but before I code it, perhaps somebody can
comment on this? I have a gut feeling that some nasty
strtok hack would be even faster, would it? Or is there
perhaps some other, performance-oriented way like traversing
s.c_str() with a pointer and memcpying out the relevant part?

I would not recommend any of those...

Use a string::iterator. Inspect the individual characters. Have a
current state (word, non-word), update the state according to what you
read. Count toggles. Construct a string from the n-th word.
So, Gianni's approach. I will try that, thanks.

- J.
May 9 '07 #5
Gianni Mariani wrote:
Gianni Mariani wrote:
>Jacek Dziedzic wrote:
...
>> which is fine, except it performs poorly. Before I'm flamed
...

oh - I forgot to mention, if you extend the state machine a little, you
can apply the state machine to an entire file. Then you can mmap the
entire file and never copy the file into and out of buffers.
thanks, I'll try that,
- J.
May 9 '07 #6
Jacek Dziedzic wrote:
Markus Moll wrote:
.....
>I'm afraid that your efforts will not help much.
If your n-th word starts at position i in your text file, you will
have to inspect all preceding positions to know that (well, not
entirely true, in some circumstances you can skip a character, but
that doesn't really matter). If your text contains billions of
characters, that might take very long.

Fortunately I'm only splitting individual lines into words.
I don't need to search through the file or anything like that,
only something like

for all lines in the file {
depending on word 0 in the line, extract some other word from the line
convert this word to a double, operate on it, output result
}
sounds like a job for a database.

select v4 where v0 = "THIS ONE";

Index on v0 and you can find all your values very quickly.

Try dumping your gigabytes of data into Postgresql or maybe sqllite.

I've used postgresql with a few hunded million rows and a few
"appropriate" indexes and the answers pop out rather quickly.
May 9 '07 #7
Gianni Mariani wrote:
Gianni Mariani wrote:
>Jacek Dziedzic wrote:
...
>> which is fine, except it performs poorly. Before I'm flamed
...

oh - I forgot to mention, if you extend the state machine a little, you
can apply the state machine to an entire file. Then you can mmap the
entire file and never copy the file into and out of buffers.
And i the performances are really the problem, this would be much
better, even if the program structure can suffer a little bit. The
string is totally useless, and each new string is a "new", end each
"new" is waste of time.

Try using an istream_iterator to directly iterate through your input
file in order to implement your state machine.

Regards,

Zeppe
May 9 '07 #8
Gianni Mariani wrote:
Jacek Dziedzic wrote:
>Markus Moll wrote:
....
>>I'm afraid that your efforts will not help much.
If your n-th word starts at position i in your text file, you will
have to inspect all preceding positions to know that (well, not
entirely true, in some circumstances you can skip a character, but
that doesn't really matter). If your text contains billions of
characters, that might take very long.

Fortunately I'm only splitting individual lines into words.
I don't need to search through the file or anything like that,
only something like

for all lines in the file {
depending on word 0 in the line, extract some other word from the line
convert this word to a double, operate on it, output result
}

sounds like a job for a database.

select v4 where v0 = "THIS ONE";

Index on v0 and you can find all your values very quickly.

Try dumping your gigabytes of data into Postgresql or maybe sqllite.

I've used postgresql with a few hunded million rows and a few
"appropriate" indexes and the answers pop out rather quickly.
Thanks for the advice, but that would be way overkill.
What I do is perform postprocessing on raw results of
computer simulations. I usually have to process several
tens of files, each approx 1GB in size. These files are
only processed _once_ (if I don't mess up) so storing them
inside a database would not really help. Anyway, people
around me would give me weird looks if I wanted to put
all this GBs of numbers inside a database, I am a part
of a small minority of non-Fortran users here :), co C++
is weird enough :/.

thanks,
- J.
May 9 '07 #9
On May 9, 1:18 pm, Jacek Dziedzic
<jacek.dziedzic.n.o.s.p....@gmail.comwrote:
I need a routine like:
std::string nth_word(const std::string &s, unsigned int n) {
// return n-th word from the string, n is 0-based
// if 's' contains too few words, return ""
// 'words' are any sequences of non-whitespace characters
// leading, trailing and multiple whitespace characters
// should be ignored.
// eg. "These are four\t\twords\t\t".
}
I am currenlty using something like:
std::string nth_word(const std::string& source, unsigned int n) {
// the addition of " " allows for the extraction of the last
// word, after which ss would go eof() below if not for the space
stringstream ss(source+" ");
string s;
for(unsigned int k=0;k<=n;k++) {
ss >s;
if(!ss.good()) return ""; // eof
Just a detail, but good() may be false after reading the last
word correctly. What you want here is:

if ( ! ss ) {
return "" ;
}

(If you do this, you don't have to add the extra space at the
end of the initializer of ss.)

Even better would be to move the condition up into the loop
condition. Something like:

std::istringstream ss( source ) ;
std::string s ;
while ( n 0 && ss >s ) {
-- n ;
}
return ss ? s : std::string() ;
}
return s;
}
which is fine, except it performs poorly. Before I'm flamed
with accusations of premature optimization, let me tell you
that I profiled my code and over 50% of time is spent in this
routine. This does not surprise me -- I am extracting words
from text files in the order of GB and it takes annoyingly
long...
I'm thinking of a combination of find_first_not_of and
find_first_of, but before I code it, perhaps somebody can
comment on this? I have a gut feeling that some nasty
strtok hack would be even faster, would it? Or is there
perhaps some other, performance-oriented way like traversing
s.c_str() with a pointer and memcpying out the relevant part?
For starters, you say you're processing a text file. Do you
offen call nth_word on the same string, with different values of
n? If so, you're doing a lot of duplicate work; if extract
every word, you've basically changed an O(n) algorithm into an
O(n^2). If performance is an issue, that's the first thing I'd
consider.

Other than that, std::istringstream does a lot of copying. I've
occasionally used something like:

template< std::ctype_base::mask mask >
class CTypeIs : public std::unary_function< char, bool >
{
public:
typedef std::ctype< char >
CType ;
CTypeIs( std::locale const& l = std::locale() )
: myCType( &std::use_facet< CType >( l ) )
{
}

bool operator()( char ch ) const
{
return myCType->is( mask, ch ) ;
}

private:
CType const* myCType ;
} ;

void
split(
std::vector< std::string >&
dest,
std::string const& source )
{
static CTypeIs< std::ctype_base::space const
isBlank ;
dest.clear() ;
std::string::const_iterator
end = source.end() ;
std::string::const_iterator
current =
std::find_if( source.begin(), end,
std::not1( isBlank ) ) ;
while ( current != end ) {
std::string::const_iterator
start = current ;
current = std::find_if( current, end, isBlank ) ;
dest.push_back( std::string( start, current ) ) ;
current = std::find_if( current, end,
std::not1( isBlank ) ) ;
}
}

to break up a line into fields.

CTypeIs is, of course, in my usual tools library, so I don't
have to write it every time. Note too that it does nothing to
guarantee the lifetime of the facet it is using---this is up to
the caller, but in practice is almost never a problem. Also,
the actual object is a local variable, and so won't be
constructed until the function is actually called. Thus giving
the user time to set the global locale.

Depending on what you are doing with the words, building the
vector may or may not be necessary as well. In the end, if you
can work directly with the two iterators which define the word,
you can avoid any copy what so ever.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

May 10 '07 #10
On May 9, 3:07 pm, Gianni Mariani <gi3nos...@mariani.wswrote:

[...]
state_type state = ( std::isspace( * l_iter ) ) ? inspace : inword;
Just a reminder. The call to isspace here is undefined
behavior, and in practice, doesn't give correct results on most
machines. It's generally preferrable to use <locale>, but at
the very least, you have to cast:

std::isspace( static_cast< unsigned char >( *l_iter ) ) ;

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

May 10 '07 #11
James Kanze wrote:
[...]
thank you,
- J.
May 13 '07 #12

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: HB2 | last post by:
Is it possible to obtain the IP address of my desktop using a Visual Basic command?
6
by: G. | last post by:
This is an obvious bug in the String.Replace function: //load a XML string into a document XmlDocument doc = new XmlDocument(); doc.LoadXml("<test id='' />"); //Obtain the string...
4
by: Ed Willis | last post by:
We have several offices that have a DSL or Cable modem where the IP address is dynamic and changes often. I created a VB app that obtains the IP address but it obtains the IP address within the...
4
by: Daniel R. Rossnagel | last post by:
I can obtain Where clauses, order by, group by, of a consultation SQL, by means of some class similar to codemodel
0
by: godsmustbcrazy | last post by:
Here is my problem. Brand new SQL Server 2005 Installation 1. Create a database "Test" 2. Create a database user "Domain\user" and set user mapping to "Test" with datareader, datawriter...
1
by: VictorG | last post by:
Hello, The below C# code works fine in obtaining the windows user's account SID when the user is local to the machine. It throws a "Not Found" exception when trying top obtain the SID for a...
1
by: =?Utf-8?B?TWFydGluVA==?= | last post by:
I have a problem to obtain the children in IIS when I create a folder directly in c:\inetput\wwwroot\*. If a create with Visual Studio it's OK. This is the code I use to obtain the object IIS. ...
8
by: ThunderMusic | last post by:
Hi, We need to serialize (binary) objects containing generic collections. The thing is, when we try to get the objects back (deserialize) with a different instance of the application, we receive...
3
by: JurgenvonOerthel | last post by:
I want to replace one element in a list<stringby a list<stringand I need to obtain an iterator to the first element in the inserted list. In code: void...
0
by: Andrea | last post by:
Hi, I've a problem reading a field containing a crypted string. I read the field via JDBC but when I decrypt the string I obtain a sequence of strange characters (if I output them I obtain a...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.