string comparision in a file

[rakesh]

Hi,
I have a requirement in which I need to search a string in a file
stored on a harddisk. String which needs to be searched would be
stored in a file with delimiter as new line character. some of the
ways of doing this are

1. Read each line and do string compare immediately.
2. Read each line, add each string into a stl vector and search for
the given string using stl bineary_search algorithm.

It would be helpful if someone could give me comparison of which would
be the best method among the above mentioned ways of handling
searching. I would also welcome any other better of handling searching
string in a file.

Thanks,
Rakesh.

 

[John Harrison]

Hi,
I have a requirement in which I need to search a string in a file
stored on a harddisk. String which needs to be searched would be
stored in a file with delimiter as new line character. some of the
ways of doing this are

1. Read each line and do string compare immediately.
2. Read each line, add each string into a stl vector and search for
the given string using stl bineary_search algorithm.

It would be helpful if someone could give me comparison of which would
be the best method among the above mentioned ways of handling
searching. I would also welcome any other better of handling searching
string in a file.

The first way is better in every respect. It is quicker, it uses less memory
and it is simpler to code. Sometimes the simplest way is the best.

john

 

[Richard Herring]

The first way is better in every respect. It is quicker, it uses less memory
and it is simpler to code.

Also the second way is wrong. binary_search only works on sorted data
:-(

Sometimes the simplest way is the best.

However, I wonder whether Rakesh is really searching for a string which
matches an entire line in the file, or only a part of the line?

If the latter, it might be worth his while to research more
sophisticated string search algorithms. Boyer-Moore is one, but there
are many others, and they be much more efficient than a naive linear
search.

 

[pengfei]

If you need to search your string nearly hundred times within a minute,
and -
your search will be conducted in a file which contains thousands of
strings(lines) , and -
you don't have to worry about your memory capacity, then -
you'd better use the second method.

The reason for it, from my point of view, is :
STL vector/list is implemented with a much better algorithm for searching an
element, very good efficiency.
It helps save time, but it also causes bigger memory consumption.

For a small job, you can just choose the first method, as mentioned by John.

pengfei

 

[Thomas Matthews]

Hi,
I have a requirement in which I need to search a string in a file
stored on a harddisk. String which needs to be searched would be
stored in a file with delimiter as new line character. some of the
ways of doing this are

1. Read each line and do string compare immediately.
2. Read each line, add each string into a stl vector and search for
the given string using stl bineary_search algorithm.

It would be helpful if someone could give me comparison of which would
be the best method among the above mentioned ways of handling
searching. I would also welcome any other better of handling searching
string in a file.

Thanks,
Rakesh.

If your system supports muli-tasking (multi-threading or whatever),
you could have one task reading lines into a buffer while another
task searches a given line.

This would assume that reading a line takes longer than searching it
and there is considerable overhead time when reading a line (such as
hard-drive start-up time, seeking time, etc.). Although these
timings usually only appear when the number of lines to read in
is huge; or the I/O overhead times are really slow.

Hmmm, why do things simple when you can have some fun making them
more complex? ;-)

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[David Rubin]

Hi,
I have a requirement in which I need to search a string in a file
stored on a harddisk. String which needs to be searched would be
stored in a file with delimiter as new line character. some of the
ways of doing this are

1. Read each line and do string compare immediately.
2. Read each line, add each string into a stl vector and search for
the given string using stl bineary_search algorithm.

It depends on where you expect to find the target string (on average),
and how much of each string you need to search before you can
determine that it doesn't match. It also depends on how large the file
is since you have to store it in-core with the second approach. If the
file is static, you can do some optimizations such as build an
auxiliary index (file), use a database, etc.

/david

 

[Jerry Coffin]

Hi,
I have a requirement in which I need to search a string in a file
stored on a harddisk. String which needs to be searched would be
stored in a file with delimiter as new line character. some of the
ways of doing this are

1. Read each line and do string compare immediately.

This is basically an O(N) algorithm.

2. Read each line, add each string into a stl vector and search for
the given string using stl bineary_search algorithm.

For binary_search to be meaningful, the items in the vector would
first have to be sorted. The sort (by itself) is slower than the
first search.

The second method makes sense if and only if you can read and sort the
data once, and then do multiple searches on the data. In that case,
the initial read/sort step is still O(N * log N), but each subsequent
search is O(log N), whereas in the first case, each search is O(N).

For string searching, I prefer Sunday's variant of
Boyer-Moore-Horspool string searching. Assuming the string you're
searching for is long and low in repitition, it can be quite fast.
OTOH, this is often overkill -- in a reasonably typical situation, the
real bottleneck will be in the I/O.