| View previous topic :: View next topic |
| Author |
Message |
Vladimir Grigoriev
Guest
|
 Posted: Fri May 11, 2007 6:01 pm Post subject: Design question |
 |
|
I have an array of character strings and a corresponding array of bit fields
(flags). In one module I need to search through the character array to get
a corresponding flag. In another module the process is reverse i.e. having a
flag I need to get a character string.
Initially I placed character strings in lexical order and used the
well-known binary search algorithm to get target string and consequently a
corresponding flag. However in this case I have difiiculties in searching
through the array of bit fields that to get a corresponding character
string. For example if I have a bit field '00000040'b I should look through
the whole bit field array that to get a position of the element in array and
consequently to get the same position of the corresponding string
Is any structures/algorithms to make both searching as quick and convenient
as possible?
Vladimir Grigoriev |
|
| Back to top |
|
 |
Duane Hebert
Guest
|
| Posted: Fri May 11, 2007 6:09 pm Post subject: Re: Design question |
|
|
"Vladimir Grigoriev" <vlad.moscow (AT) mail (DOT) ru> wrote in message
news:4644687f (AT) newsgroups (DOT) borland.com...
| Quote: | I have an array of character strings and a corresponding array of bit
fields (flags). In one module I need to search through the character array
to get a corresponding flag. In another module the process is reverse i.e.
having a flag I need to get a character string.
Initially I placed character strings in lexical order and used the
well-known binary search algorithm to get target string and consequently a
corresponding flag. However in this case I have difiiculties in searching
through the array of bit fields that to get a corresponding character
string. For example if I have a bit field '00000040'b I should look
through the whole bit field array that to get a position of the element in
array and consequently to get the same position of the corresponding
string
Is any structures/algorithms to make both searching as quick and
convenient as possible?
|
You may want to take a look at boost multi index stuff.
http://www.boost.org/libs/multi_index/doc/index.html
A multi index map comes to mind... |
|
| Back to top |
|
|
Vladimir Grigoriev
Guest
|
| Posted: Fri May 11, 2007 7:19 pm Post subject: Re: Design question |
|
|
"Duane Hebert" <spoo (AT) flarn (DOT) com> wrote in message
news:46446af5 (AT) newsgroups (DOT) borland.com...
Thanks. I will look. The problem is that I need to program the algorithm in
other language then C++. The simpler algorithm is the better. The arrays are
const static so I need not many methods but only searching.
Vladimir Grigoriev |
|
| Back to top |
|
|
Dennis Cote
Guest
|
| Posted: Fri May 11, 2007 7:52 pm Post subject: Re: Design question |
|
|
Vladimir Grigoriev wrote:
| Quote: |
The problem is that I need to program the algorithm in
other language then C++. The simpler algorithm is the better. The arrays are
const static so I need not many methods but only searching.
|
Vladimir,
You can use a binary search on the strings because they are in sorted
order. To speed up your bitfield lookups you need to create a sorted
list of bitfields with associated pointers to, or indexes of, the
corresponding string. This will allow you to do the same fast binary
search for a bitfield. Having found the bitfield you can use the
associated pointer or index to get the corresponding string.
This will require you to build a second pair of arrays at runtime that
are initialized using your existing static arrays. One array will hold
bitfield values, the other will hold the index of the associated string
in the existing string array. These arrays can be populated using a
single scan through the existing static arrays. After they are populated
you need to sort the bitfield array.
The trick is to keep the bitfield values and associated string index
values paired while sorting. The easiest way to do this is to put them
together in a structure (assuming your language supports this). Then you
only need to have a customized comparison function based on the bitfield
values for use by the sorting routine. If you are building a custom sort
routine you could have it swap elements in both arrays when required.
Once you have a sorted array of bitfields you can use a binary search to
do fast bitfield lookups, get the associated string index, and then get
the associated string from the existing array.
HTH
Dennis Cote |
|
| Back to top |
|
|
Duane Hebert
Guest
|
| Posted: Fri May 11, 2007 7:53 pm Post subject: Re: Design question |
|
|
"Vladimir Grigoriev" <vlad.moscow (AT) mail (DOT) ru> wrote in message
news:46447aaf$1 (AT) newsgroups (DOT) borland.com...
| Quote: |
"Duane Hebert" <spoo (AT) flarn (DOT) com> wrote in message
news:46446af5 (AT) newsgroups (DOT) borland.com...
You may want to take a look at boost multi index stuff.
http://www.boost.org/libs/multi_index/doc/index.html
A multi index map comes to mind...
Thanks. I will look. The problem is that I need to program the algorithm
in other language then C++. The simpler algorithm is the better. The
arrays are const static so I need not many methods but only searching.
|
The search requirement was what made me think of a map.
Maps have log(n) complexity for searches based on key. The
problem is that you still have linear search based on the data side.
If I had to approach this manually, I would like try a structure to emulate
a pair, insert into an array sorted on one side of the pair, write a binary
search for that side, build a hash for the second side... I haven't read
the
code from boost but it may give you some ideas. |
|
| Back to top |
|
|
Vladimir Grigoriev
Guest
|
| Posted: Fri May 11, 2007 8:08 pm Post subject: Re: Design question |
|
|
"Dennis Cote" <dennis.cote (AT) gmail (DOT) com> wrote in message
news:46448325$1 (AT) newsgroups (DOT) borland.com...
| Quote: | Vladimir Grigoriev wrote:
Vladimir,
You can use a binary search on the strings because they are in sorted
order. To speed up your bitfield lookups you need to create a sorted list
of bitfields with associated pointers to, or indexes of, the corresponding
string. This will allow you to do the same fast binary search for a
bitfield. Having found the bitfield you can use the associated pointer or
index to get the corresponding string.
This will require you to build a second pair of arrays at runtime that are
initialized using your existing static arrays. One array will hold
bitfield values, the other will hold the index of the associated string in
the existing string array. These arrays can be populated using a single
scan through the existing static arrays. After they are populated you need
to sort the bitfield array.
The trick is to keep the bitfield values and associated string index
values paired while sorting. The easiest way to do this is to put them
together in a structure (assuming your language supports this). Then you
only need to have a customized comparison function based on the bitfield
values for use by the sorting routine. If you are building a custom sort
routine you could have it swap elements in both arrays when required.
Once you have a sorted array of bitfields you can use a binary search to
do fast bitfield lookups, get the associated string index, and then get
the associated string from the existing array.
HTH
Dennis Cote
|
The question is does the stuff with sorting the array of pairs <bit field,
pointer> give me profit compared with simple linear search in the bit field
array? The arrays I am speaking have dimension equal to 40 (or so) elements.
Vladimir Grigoriev |
|
| Back to top |
|
|
Duane Hebert
Guest
|
| Posted: Fri May 11, 2007 8:36 pm Post subject: Re: Design question |
|
|
| Quote: | The question is does the stuff with sorting the array of pairs <bit field,
pointer> give me profit compared with simple linear search in the bit
field array? The arrays I am speaking have dimension equal to 40 (or so)
elements.
|
I sort of thought that you were implying something a lot larger.
It's hard to imagine any benefit from sorting with 40 elements. You're
likely to incurr
more overhead by sorting and maintaining sorted arrays. It depends
a lot on what you're doing. I would likely leave it unsorted unless
profiling
showed some bottleneck due to the search. |
|
| Back to top |
|
|
Bob Gonder
Guest
|
| Posted: Fri May 11, 2007 8:53 pm Post subject: Re: Design question |
|
|
Vladimir Grigoriev wrote:
| Quote: | The question is does the stuff with sorting the array of pairs <bit field,
pointer> give me profit compared with simple linear search in the bit field
array?
|
The profit is you only sort it once, or hard code the sorted array.
| Quote: | The arrays I am speaking have dimension equal to 40 (or so) elements.
|
For searching a 40 element integer array in memory, I wouldn't bother
with the computational overhead of the binary search.
You are looking at an average 20 reads vs. 5, but practically no
computation between reads, and sequential scan is probably cache
friendly.
For top speed, I'd be looking for a great/fast hash for instant 1-read
lookups. |
|
| Back to top |
|
|
Dennis Cote
Guest
|
| Posted: Fri May 11, 2007 9:51 pm Post subject: Re: Design question |
|
|
Vladimir Grigoriev wrote:
| Quote: |
The question is does the stuff with sorting the array of pairs <bit field,
pointer> give me profit compared with simple linear search in the bit field
array? The arrays I am speaking have dimension equal to 40 (or so) elements.
|
For arrays of that size there is almost certainly no benefit unless you
do these lookups very often so that this becomes a significant part of
your total execution time.
Dennis Cote |
|
| Back to top |
|
|
Vladimir Grigoriev
Guest
|
| Posted: Fri May 11, 2007 10:15 pm Post subject: Re: Design question |
|
|
"Dennis Cote" <dennis.cote (AT) gmail (DOT) com> wrote in message
news:46449ef5$1 (AT) newsgroups (DOT) borland.com...
| Quote: | For arrays of that size there is almost certainly no benefit unless you do
these lookups very often so that this becomes a significant part of your
total execution time.
Dennis Cote
|
However for the array of characters string I use the bibary search
algorithm. 
O'k, the search in the array of bit fields will be done only on reply of an
user request to display character strings which correspond to given bit
fields' set.
Vladimir Grigoriev |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
