code review / efficient lookup techniques...
James
I am in the process of learning C++. I have been given a task to complete
which involves mapping strings to a value. The minimum length of a string is
4 characters and only uses lowercase alphabetic characters. It needs to work
with more than just ASCII, (e.g., EBCDIC) I need to do this mapping without
using any standard containers. I immediately thought of using a 4 dimintinal
array of values to do a very fast lookup:
#define DEPTH (UCHAR_MAX + 1)
void* array[DEPTH][DEPTH][DEPTH][DEPTH];
However, this uses way to much memory. So, I thought of using the following
table:
#define DEPTH 27
void* array[DEPTH][DEPTH][DEPTH][DEPTH];
Which should handle all lowercase letters. However, I need to translate the
character value to an index into this array. So, here is what I have come up
with so far:
#include <iostream>
#include <climits>
#include <cctype>
#include <cstring>
#include <cassert>
class translator
{
static unsigned char g_chars[UCHAR_MAX + 1];
static char const* const g_alpha;
public:
translator()
{
for (int i = 0; i <= UCHAR_MAX; ++i)
{
if (isalpha(i) && islower(i))
{
for (int a = 0; a < 26; ++a)
{
if (i == g_alpha[a])
{
g_chars[i] = a;
break;
}
}
}
}
}
public:
inline int operator [] (char c) const
{
return g_chars[(unsigned int)c];
}
};
unsigned char
translator::g_chars[UCHAR_MAX + 1] = { 0 };
char const* const
translator::g_alpha = "abcdefghijklmnopqrstuvwxyz";
static translator g_translator;
template<typename TR, typename T>
class cmap
{
typedef TR (*fp_command) (T);
struct table
{
fp_command m_fp[27][27][27][27];
};
private:
table m_table;
public:
cmap(fp_command fp_default)
{
for (std::size_t i1 = 0; i1 < 27; ++i1)
{
for (std::size_t i2 = 0; i2 < 27; ++i2)
{
for (std::size_t i3 = 0; i3 < 27; ++i3)
{
for (std::size_t i4 = 0; i4 < 27; ++i4)
{
m_table.m_fp[i1][i2][i3][i4] = fp_default;
}
}
}
}
}
private:
inline fp_command& prv_find(char const* name)
{
assert(strlen(name) >= 4);
return m_table.m_fp
[g_translator[name[0]]]
[g_translator[name[1]]]
[g_translator[name[2]]]
[g_translator[name[3]]];
}
inline fp_command prv_find(char const* name) const
{
assert(strlen(name) >= 4);
return m_table.m_fp
[g_translator[name[0]]]
[g_translator[name[1]]]
[g_translator[name[2]]]
[g_translator[name[3]]];
}
public:
void add(char const* name, fp_command cmd)
{
prv_find(name) = cmd;
}
inline TR exec(char const* name, T P) const
{
return prv_find(name)(P);
}
};
void
command_north(char const* str)
{
std::cout << "void command_north(char const* "
<< str
<< ")"
<< std::endl;
}
void
command_south(char const* str)
{
std::cout << "void command_south(char const* "
<< str
<< ")"
<< std::endl;
}
void
command_east(char const* str)
{
std::cout << "void command_east(char const* "
<< str
<< ")"
<< std::endl;
}
void
command_west(char const* str)
{
std::cout << "void command_west(char const* "
<< str
<< ")"
<< std::endl;
}
void
command_attack(char const* str)
{
std::cout << "void command_attack(char const* "
<< str
<< ")"
<< std::endl;
}
void
command_unknown(char const* str)
{
std::cout << "void command_unknown(char const* "
<< str
<< ")"
<< std::endl;
}
int main()
{
{
static cmap<void, char const*> cm_normal(command_unknown);
static cmap<void, char const*> cm_reverse(command_unknown);
cm_normal.add("north", command_north);
cm_normal.add("south", command_south);
cm_normal.add("east", command_east);
cm_normal.add("west", command_west);
cm_normal.add("attack", command_attack);
cm_reverse.add("north", command_south);
cm_reverse.add("south", command_north);
cm_reverse.add("east", command_west);
cm_reverse.add("west", command_east);
cm_reverse.add("attack", command_attack);
cm_normal.exec("north", "Message1");
cm_normal.exec("south", "Message2");
cm_normal.exec("east", "Message3");
cm_normal.exec("west", "Message4");
cm_normal.exec("west", "Message5");
cm_normal.exec("weild", "Message6");
cm_normal.exec("attack", "Big Monster!");
cm_normal.exec("fight", "Message7");
cm_normal.exec("1234xx566", "Message8");
cm_normal.exec("zzzz", "Message9");
std::cout << "----------------------------" << std::endl;
cm_reverse.exec("north", "Message1");
cm_reverse.exec("south", "Message2");
cm_reverse.exec("east", "Message3");
cm_reverse.exec("west", "Message4");
cm_reverse.exec("west", "Message5");
cm_reverse.exec("weild", "Message6");
cm_reverse.exec("attack", "Big Monster!");
cm_reverse.exec("fight", "Message7");
cm_reverse.exec("1234xx566", "Message8");
cm_reverse.exec("zzzz", "Message9");
}
return 0;
}
It seems to work, but I am a but uneasy... What do you all think of this? Am
I going about solving the problem in an ass-backwards manner?
Thanks.
BTW, can you think of a faster way to perform the lookup process???
Chris M. Thomasson
> BTW, this is homework. I hope I am not out of line here...
>
>
> I am in the process of learning C++. I have been given a task to complete
> which involves mapping strings to a value. The minimum length of a string
> is 4 characters and only uses lowercase alphabetic characters. It needs to
> work with more than just ASCII, (e.g., EBCDIC) I need to do this mapping
> without using any standard containers. I immediately thought of using a 4
> dimintinal array of values to do a very fast lookup:
4 dimensional
of course!
ARGH.
Chris M. Thomasson
"James" <n...@spam.invalid> wrote in message news:hde75o$rt5$1...@aioe.org...
>
>
> I am in the process of learning C++. I have been given a task to complete
> which involves mapping strings to a value. The minimum length of a string
> is 4 characters and only uses lowercase alphabetic characters.
I should clarify... The minimum length of a string is 4, and the maximum
characters evaluated are 4. So the following commands are going to map to
identical functions:
hello
hell
hell1234
> It needs to work with more than just ASCII, (e.g., EBCDIC) I need to do
> this mapping without using any standard containers. I immediately thought
> of using a 4 dimintinal array of values to do a very fast lookup:
[...]
James
news:hdeehj$5m3$1...@aioe.org...
OOPS! The last two posts were using the wrong account. Sorry Chris! I am
Chris' cousin and am learning C++ at the local community college.
;^(...
Paul N
> BTW, this is homework. I hope I am not out of line here...
>
> I am in the process of learning C++. I have been given a task to complete
> which involves mapping strings to a value. The minimum length of a string is
> 4 characters and only uses lowercase alphabetic characters. It needs to work
> with more than just ASCII, (e.g., EBCDIC) I need to do this mapping without
> using any standard containers. I immediately thought of using a 4 dimintinal
> array of values to do a very fast lookup:
>
> #define DEPTH (UCHAR_MAX + 1)
>
> void* array[DEPTH][DEPTH][DEPTH][DEPTH];
>
> However, this uses way to much memory.
Do you *need* to do it quickly, or is this a requirement that you have
added yourself to the task you were set?
If speed is not an issue, I would be inclined to write a routine that
converts each of the letters into a number and then multiply up. For
instance, set a to be the value of the first letter, b the second, c
the third and d the fourth according to the arrangement
'a' = 1, 'b' = 2, ... 'z' = 26, 0 if string already finished
and then compute
value = a + b * 27 + c * 27*27 + d * 27*27*27
The converting function is pretty quick in ASCII (just a subtraction,
as long as you have some string left) and only a little slower for
EBCDIC.
Hope that helps.
Paul.
James
news:4a9e2c7b-58ad-442c...@g23g2000yqh.googlegroups.com...
> On 10 Nov, 23:29, "James" <n...@spam.invalid> wrote:
>> BTW, this is homework. I hope I am not out of line here...
>>
>> I am in the process of learning C++. I have been given a task to complete
>> which involves mapping strings to a value. The minimum length of a string
>> is
>> 4 characters and only uses lowercase alphabetic characters. It needs to
>> work
>> with more than just ASCII, (e.g., EBCDIC) I need to do this mapping
>> without
>> using any standard containers. I immediately thought of using a 4
>> dimintinal
>> array of values to do a very fast lookup:
>>
>> #define DEPTH (UCHAR_MAX + 1)
>>
>> void* array[DEPTH][DEPTH][DEPTH][DEPTH];
>>
>> However, this uses way to much memory.
>
> Do you *need* to do it quickly, or is this a requirement that you have
> added yourself to the task you were set?
I am going for some extra credits...
;^)
> If speed is not an issue, I would be inclined to write a routine that
> converts each of the letters into a number and then multiply up. For
> instance, set a to be the value of the first letter, b the second, c
> the third and d the fourth according to the arrangement
>
> 'a' = 1, 'b' = 2, ... 'z' = 26, 0 if string already finished
>
> and then compute
>
> value = a + b * 27 + c * 27*27 + d * 27*27*27
>
> The converting function is pretty quick in ASCII (just a subtraction,
> as long as you have some string left) and only a little slower for
> EBCDIC.
>
> Hope that helps.
I am not sure I understand. Are you suggesting to use the computed value as
a key in a binary tree or something?
James
> "Paul N" <gw7...@aol.com> wrote in message
> news:4a9e2c7b-58ad-442c...@g23g2000yqh.googlegroups.com...
>> On 10 Nov, 23:29, "James" <n...@spam.invalid> wrote:
>>> BTW, this is homework. I hope I am not out of line here...
>>>
>>> I am in the process of learning C++. I have been given a task to
>>> complete
>>> which involves mapping strings to a value. The minimum length of a
>>> string is
>>> 4 characters and only uses lowercase alphabetic characters. It needs to
>>> work
>>> with more than just ASCII, (e.g., EBCDIC) I need to do this mapping
>>> without
>>> using any standard containers. I immediately thought of using a 4
>>> dimintinal
>>> array of values to do a very fast lookup:
>>>
>>> #define DEPTH (UCHAR_MAX + 1)
>>>
>>> void* array[DEPTH][DEPTH][DEPTH][DEPTH];
>>>
>>> However, this uses way to much memory.
>>
>> Do you *need* to do it quickly, or is this a requirement that you have
>> added yourself to the task you were set?
>
> I am going for some extra credits...
>
> ;^)
I guess you could say that the technique I used is basically equal to a
(UCHAR_MAX + 1)-ary trie.
Dann Corbit
Of course, the real answer is to use STL or Boost, but you can just make
a simple hash table.
http://en.wikipedia.org/wiki/Hash_table
Thomas J. Gritzan
> BTW, this is homework. I hope I am not out of line here...
>
>
> I am in the process of learning C++. I have been given a task to
> complete which involves mapping strings to a value. The minimum length
> of a string is 4 characters and only uses lowercase alphabetic
> characters. It needs to work with more than just ASCII, (e.g., EBCDIC) I
> need to do this mapping without using any standard containers. I
> immediately thought of using a 4 dimintinal array of values to do a very
> fast lookup:
> BTW, can you think of a faster way to perform the lookup process???
I don't know if it is faster, but you could use a binary search on a
sorted array:
1) build an array of (key, value) pairs
2) sort the array using std::lexicographical_compare, strcmp or a
hand-written loop
3) search the lookup string in the array with binary search using above
compare function.
http://en.wikipedia.org/wiki/Binary_search_algorithm
--
Thomas
Paavo Helde
> BTW, this is homework. I hope I am not out of line here...
>
>
> I am in the process of learning C++. I have been given a task to
> complete which involves mapping strings to a value. The minimum length
> of a string is 4 characters and only uses lowercase alphabetic
> characters. It needs to work with more than just ASCII, (e.g., EBCDIC)
> I need to do this mapping without using any standard containers. I
> immediately thought of using a 4 dimintinal array of values to do a
> very fast lookup:
Such a 4-dimensional array is quite large, and according to your example,
very sparse. Accessing it in random fashion will probably cause a lot of
cache misses, so it is not given that this is the fastest lookup
possible.
A tag of 4 characters/bytes immediately suggests that you could interpret
those 4 characters as 32-bit unsigned integers (unsigned is needed, as
signed integers can have trap values). (This should work for EBCDIC as
well as far as both your source code and the initial data for
initializing the map are in the same codepage.) Thus the mapping is
simplified to integer-to-value. One could hold these in a sorted array
and perform a binary search (or even a linear search in an unsorted array
if the number of entries is small, placing the more frequent commands in
the beginning).
Below are just some stylistic comments...
>
>
> #define DEPTH (UCHAR_MAX + 1)
why #define?
>
> void* array[DEPTH][DEPTH][DEPTH][DEPTH];
>
>
> However, this uses way to much memory. So, I thought of using the
> following table:
>
>
> #define DEPTH 27
Why 27? (instead of 26)
>
> void* array[DEPTH][DEPTH][DEPTH][DEPTH];
>
>
> Which should handle all lowercase letters. However, I need to
> translate the character value to an index into this array. So, here is
> what I have come up with so far:
>
>
>
>
> #include <iostream>
> #include <climits>
> #include <cctype>
> #include <cstring>
> #include <cassert>
>
>
>
>
> class translator
> {
> static unsigned char g_chars[UCHAR_MAX + 1];
> static char const* const g_alpha;
Why static? And g_alpha could be a local variable instead (to a string
literal which is static anyway).
>
>
> public:
> translator()
> {
> for (int i = 0; i <= UCHAR_MAX; ++i)
> {
> if (isalpha(i) && islower(i))
> {
> for (int a = 0; a < 26; ++a)
> {
> if (i == g_alpha[a])
> {
> g_chars[i] = a;
> break;
> }
> }
> }
> }
> }
>
>
> public:
> inline int operator [] (char c) const
> {
> return g_chars[(unsigned int)c];
> }
> };
>
> unsigned char
> translator::g_chars[UCHAR_MAX + 1] = { 0 };
>
> char const* const
> translator::g_alpha = "abcdefghijklmnopqrstuvwxyz";
>
> static translator g_translator;
Why static?
Why extra braces?
> static cmap<void, char const*> cm_normal(command_unknown);
> static cmap<void, char const*> cm_reverse(command_unknown);
Why static?
Given that the number of used entries in the map is 5 as in your example,
it is quite certain that anything which uses a compact map (of size about
20 bytes) will be faster than your solution (using more than 500000
bytes) (of course assuming there is any kind of memory caching present in
the system). But as this is homework, the correctness of the solution
should be what matters, and the speed should not be an issue at all (as
long as the demo completes before the professor gets bored ;-).
hth
Paavo
James Kanze
> "James" <n...@spam.invalid> wrote innews:hde75o$rt5$1...@aioe.org:
[...]
> > #define DEPTH 27
> Why 27? (instead of 26)
For the final '\0' when the string is less than 4 characters.
He could save a little memory by making the first dimension 26.
If he implemented it as a true trie, he would probably save a
lot more, since a lot of the sub-tries would probably be empty;
a dynamically constructed trie would definitely be a legitimate
answer to the problem, and would probably be rather fast. In
which case, something like:
struct TrieNode
{
void* action;
TrieNode* next[16];
};
would do the trick.
--
James Kanze
James
news:Xns9CC1C54A...@216.196.109.131...
> "James" <n...@spam.invalid> wrote in news:hde75o$rt5$1...@aioe.org:
>
>> BTW, this is homework. I hope I am not out of line here...
>>
>>
>> I am in the process of learning C++. I have been given a task to
>> complete which involves mapping strings to a value. The minimum length
>> of a string is 4 characters and only uses lowercase alphabetic
>> characters. It needs to work with more than just ASCII, (e.g., EBCDIC)
>> I need to do this mapping without using any standard containers. I
>> immediately thought of using a 4 dimintinal array of values to do a
>> very fast lookup:
>
> Such a 4-dimensional array is quite large, and according to your example,
> very sparse.
If I understand you correctly, yes I agree; storing 5 objects in a memory
hog of a data-structure is wasteful indeed.
> Accessing it in random fashion will probably cause a lot of
> cache misses, so it is not given that this is the fastest lookup
> possible.
I admit that is a cop out, however I don't really want to get into the
"hardware level" jest yet. However, AFAICT, there would be an upper bound on
the number of cache misses per-call to 'cmap::prv_find()'? The size of the
data-structure is static and that's that, so to speak.
> A tag of 4 characters/bytes immediately suggests that you could interpret
> those 4 characters as 32-bit unsigned integers (unsigned is needed, as
> signed integers can have trap values).
Do you mean something like:
typedef unsigned int uint32_type;
typedef char assert_s
[
sizeof(uint32_type) == sizeof(char) * 4
&& sizeof(uint32_type) * CHAR_BIT == 32
? 1 : -1
];
typedef char cmd_buffer[4];
union cmd
{
cmd_buffer buffer;
uint32_type whole;
};
then decoding 4 chars at once like:
union cmd c;
char const* const string = "command";
c.whole = *((*uint32_type)string);
?
> (This should work for EBCDIC as
> well as far as both your source code and the initial data for
> initializing the map are in the same codepage.) Thus the mapping is
> simplified to integer-to-value. One could hold these in a sorted array
> and perform a binary search (or even a linear search in an unsorted array
> if the number of entries is small, placing the more frequent commands in
> the beginning).
Please correct me if I am way off base here but I think the complexity for
the simple and naive algorithm I posted should be O(8) complexity for insert
and lookup operations. This tells me that storing a large amount of items in
the array will have no impact on the complexity whatsoever. I cannot exactly
claim that for a binary search whose complexity parameters can be effected
by N.
> Below are just some stylistic comments...
[...]
>> int main()
>> {
>> {
>
> Why extra braces?
This is probably going to sound retarded, but I personally like to
encapsulate everything in main within an extra scope in order to ensure that
all objects are destructed before I actually return from main. Imagine I
wanted to print a final message that occurs after all messages from the
object dtors are printed:
#include <iostream>
struct foo
{
~foo()
{
std::cout << "~foo()" << std::endl;
}
};
int main()
{
foo f;
std::cout << "the program is finished" << std::endl;
return 0;
}
If I want the output to be like:
~foo()
the program is finished
I might do something like:
int main()
{
{
foo f;
}
std::cout << "the program is finished" << std::endl;
return 0;
}
Does that make any sense at all?
;^o
>> static cmap<void, char const*> cm_normal(command_unknown);
>> static cmap<void, char const*> cm_reverse(command_unknown);
>
> Why static?
They blow the stack on a Windows platform. BTW, I don't really see a need
for dynamic memory allocation here.
[...]
>> BTW, can you think of a faster way to perform the lookup process???
>
> Given that the number of used entries in the map is 5 as in your example,
> it is quite certain that anything which uses a compact map (of size about
> 20 bytes) will be faster than your solution (using more than 500000
> bytes) (of course assuming there is any kind of memory caching present in
> the system).
I fully intend to insert many command strings with random names assigned to
random command functions. I have to turn this in on Monday. IMVVVHO, the
sparse 256-ary array based tree should work fine for the large data-set.
> But as this is homework, the correctness of the solution
> should be what matters, and the speed should not be an issue at all (as
> long as the demo completes before the professor gets bored ;-).
LOL!
The only reason why I am doing this is so I can get some extra credit. I am
interested in getting a good grade, and plan on becoming at least a fairly
decent programmer. Perhaps I can even make some $$$ in the future.
Paavo Helde
> "Paavo Helde" <myfir...@osa.pri.ee> wrote in message
> news:Xns9CC1C54A...@216.196.109.131...
>> "James" <n...@spam.invalid> wrote in news:hde75o$rt5$1...@aioe.org:
>>
>>> BTW, this is homework. I hope I am not out of line here...
>>>
>>>
>>> I am in the process of learning C++. I have been given a task to
>>> complete which involves mapping strings to a value. The minimum
>>> length of a string is 4 characters and only uses lowercase
>>> alphabetic characters. It needs to work with more than just ASCII,
>>> (e.g., EBCDIC) I need to do this mapping without using any standard
>>> containers. I immediately thought of using a 4 dimintinal array of
>>> values to do a very fast lookup:
>>
>> Such a 4-dimensional array is quite large, and according to your
>> example, very sparse.
>
> If I understand you correctly, yes I agree; storing 5 objects in a
> memory hog of a data-structure is wasteful indeed.
>
>
>
>
>> Accessing it in random fashion will probably cause a lot of
>> cache misses, so it is not given that this is the fastest lookup
>> possible.
>
> I admit that is a cop out, however I don't really want to get into the
> "hardware level" jest yet. However, AFAICT, there would be an upper
> bound on the number of cache misses per-call to 'cmap::prv_find()'?
> The size of the data-structure is static and that's that, so to speak.
Sure there is an upper bound. This does not mean that the approach is the
fastest. The big-O calculations only make sense if N is large, with N=5
they are meaningless.
>
>
>> A tag of 4 characters/bytes immediately suggests that you could
>> interpret those 4 characters as 32-bit unsigned integers (unsigned is
>> needed, as signed integers can have trap values).
>
> Do you mean something like:
>
>
>
>
> typedef unsigned int uint32_type;
>
>
> typedef char assert_s
> [
> sizeof(uint32_type) == sizeof(char) * 4
> && sizeof(uint32_type) * CHAR_BIT == 32
> ? 1 : -1
>];
>
>
> typedef char cmd_buffer[4];
>
>
> union cmd
> {
> cmd_buffer buffer;
> uint32_type whole;
> };
>
>
>
>
> then decoding 4 chars at once like:
>
>
> union cmd c;
>
> char const* const string = "command";
>
> c.whole = *((*uint32_type)string);
>
>
> ?
Why so complex? What I had in mind whas something like
char const* const s = "command";
typedef unsigned char uc; // for brevity
uint32_t x = (uc(s[0])<<24) | (uc(s[1])<<16) | (uc(s[2])<<16) | uc(s[3]);
>
>
>
>
>> (This should work for EBCDIC as
>> well as far as both your source code and the initial data for
>> initializing the map are in the same codepage.) Thus the mapping is
>> simplified to integer-to-value. One could hold these in a sorted
>> array and perform a binary search (or even a linear search in an
>> unsorted array if the number of entries is small, placing the more
>> frequent commands in the beginning).
>
> Please correct me if I am way off base here but I think the complexity
> for the simple and naive algorithm I posted should be O(8) complexity
> for insert and lookup operations. This tells me that storing a large
> amount of items in the array will have no impact on the complexity
> whatsoever. I cannot exactly claim that for a binary search whose
> complexity parameters can be effected by N.
>
>
>
>
>> Below are just some stylistic comments...
>
> [...]
>
>
>>> int main()
>>> {
>>> {
>>
>> Why extra braces?
>
> This is probably going to sound retarded, but I personally like to
> encapsulate everything in main within an extra scope in order to
> ensure that all objects are destructed before I actually return from
> main. Imagine I wanted to print a final message that occurs after all
> messages from the object dtors are printed:
OK, but you did not have that final printout in the original example.
>
>
>>> static cmap<void, char const*> cm_normal(command_unknown);
>>> static cmap<void, char const*> cm_reverse(command_unknown);
>>
>> Why static?
>
> They blow the stack on a Windows platform. BTW, I don't really see a
> need for dynamic memory allocation here.
>
OK, but for the homework only. In real life you cannot really use static
data, as this is hostile to multi-threading.
>
>
> [...]
>
>>> BTW, can you think of a faster way to perform the lookup process???
>>
>> Given that the number of used entries in the map is 5 as in your
>> example, it is quite certain that anything which uses a compact map
>> (of size about 20 bytes) will be faster than your solution (using
>> more than 500000 bytes) (of course assuming there is any kind of
>> memory caching present in the system).
>
> I fully intend to insert many command strings with random names
> assigned to random command functions. I have to turn this in on
> Monday. IMVVVHO, the sparse 256-ary array based tree should work fine
> for the large data-set.
Yes, if N is large, the big-O rules should kick in. If N is >100000, then
certainly your data structure is optimal.
>
>
>
>
>> But as this is homework, the correctness of the solution
>> should be what matters, and the speed should not be an issue at all
>> (as long as the demo completes before the professor gets bored ;-).
>
> LOL!
>
> The only reason why I am doing this is so I can get some extra credit.
> I am interested in getting a good grade, and plan on becoming at least
> a fairly decent programmer. Perhaps I can even make some $$$ in the
> future.
I can understand that. Your solution is quite fine in my mind, as a
homework. I would not bet though that you can get some extra credit by
that. If I were a professor I would probably like it more if you
implemented a custom binary search function, instead of creating large
data arrays containing mostly emptiness. Especially the motivation is
very vague - you claim this is the fastest approach, without doing any
measurements to back up your claim. I would at least make a prototype
with std::map and compare with your approach, to see if the "O(8)" claim
is justified.
Note that in real life your solution has little chances. In a real
program nobody wants to have a component which cannot be multithreaded
and takes 1000 times more memory than necessary, even if might work a bit
faster than the alternatives. It seems you have misunderstood the goal of
professional programming. It is usually not about producing the fastest
code possible - it is all about finishing the project in the schedule,
with code having acceptable correctness, speed, size, ease-of-usage,
etc., for the end user, plus acceptable in-house maintainability.
hth
Paavo
James Kanze
> "Paavo Helde" <myfirstn...@osa.pri.ee> wrote in message
> > A tag of 4 characters/bytes immediately suggests that you
> > could interpret those 4 characters as 32-bit unsigned
> > integers (unsigned is needed, as signed integers can have
> > trap values).
So can unsigned. Unsigned char is the only type which isn't
allowed to have trap values.
In theory, at least. But all systems are requires to support
values up to 2^32-1 in an unsigned long, so it doesn't matter.
> Do you mean something like:
> typedef unsigned int uint32_type;
> typedef char assert_s
> [
> sizeof(uint32_type) == sizeof(char) * 4
> && sizeof(uint32_type) * CHAR_BIT == 32
> ? 1 : -1
> ];
> typedef char cmd_buffer[4];
> union cmd
> {
> cmd_buffer buffer;
> uint32_type whole;
> };
> then decoding 4 chars at once like:
> union cmd c;
> char const* const string = "command";
> c.whole = *((*uint32_type)string);
> ?
More likely, he was thinking of something like:
uint_fast32_t i = ((c[0] & 0xFF) << 24)
| ((c[1] & 0xFF) << 16)
| ((c[2] & 0xFF) << 8)
| ((c[3] & 0xFF) );
This is guaranteed to work on any machine.
> > (This should work for EBCDIC as well as far as both your
> > source code and the initial data for initializing the map
> > are in the same codepage.) Thus the mapping is simplified to
> > integer-to-value. One could hold these in a sorted array and
> > perform a binary search (or even a linear search in an
> > unsorted array if the number of entries is small, placing
> > the more frequent commands in the beginning).
> Please correct me if I am way off base here but I think the
> complexity for the simple and naive algorithm I posted should
> be O(8) complexity for insert and lookup operations.
There is no such thing as O(8). The complexity is O(1). But
the constant overhead is high due to the lack of locality. It's
a relatively poor space/speed trade-off, given that on modern
machines, excess space results in a noticeable slow-down.
Better solutions exist.
> This tells me that storing a large amount of items in the
> array will have no impact on the complexity whatsoever.
Array access is O(1), regardless of the size of the array. But
that's purely a theoretical figure. In practice, if the array
is very sparsely populated, the program will run slower,
compared to other algorithms.
> I cannot exactly claim that for a binary search whose
> complexity parameters can be effected by N.
Binary search is O(lg n). For small n (less than a couple of
hundred), the difference is not significant. (In the tests I've
done, binary search on a sorted vector or std::map beats hash
coding up to somewhere between 150 and 200 entries. Even though
hash coding is O(1) and the binary search or std::map are O(ln
n). Big O complexity is only significant when the number of
elements becomes large. (How large depends on the difference in
the big O factor. The difference between constant and quadratic
can become significant very quickly. The difference between
constant an logrithmic does't become significant until you
really do have a lot of entries.
> > Below are just some stylistic comments...
> [...]
> >> int main()
> >> {
> >> {
> > Why extra braces?
> This is probably going to sound retarded, but I personally
> like to encapsulate everything in main within an extra scope
> in order to ensure that all objects are destructed before I
> actually return from main.
That's interesting. Generally (in actual applications---not
necessarily is homework type projects), main will only be a
couple of function calls, maybe one to check the command line
arguments, and one to do the actual work; in the case of a Unix
like filter, you might put the loop over the filenames in main,
but that's about it.
Rather than extra braces, I'd just put the processing itself in
a separate function. (But this is perhaps more a production
code consideration. If you don't have command line options or
arguments, configuration files, etc., it's probably overkill.)
> Imagine I wanted to print a final message that occurs after
> all messages from the object dtors are printed:
You can't, because you don't know the order the destructors of
static objects will be called:-).
[...]
> >> static cmap<void, char const*> cm_normal(command_unknown);
> >> static cmap<void, char const*> cm_reverse(command_unknown);
> > Why static?
> They blow the stack on a Windows platform.
You can change the default stack size at link time, if that's
all that's bothering you.
> BTW, I don't really see a need for dynamic memory allocation
> here.
For large tables, it doesn't hurt anything. It costs the same
to allocate int[5] and int[5000000]. In the first case, that
cost has to be amortised over accessing 5 elements, which means
it may be significant. In the second, it's amortised over
accessing 5000000 elements, which means that it's practically
nothing.
> [...]
> >> BTW, can you think of a faster way to perform the lookup
> >> process???
> > Given that the number of used entries in the map is 5 as in
> > your example, it is quite certain that anything which uses a
> > compact map (of size about 20 bytes) will be faster than
> > your solution (using more than 500000 bytes) (of course
> > assuming there is any kind of memory caching present in the
> > system).
> I fully intend to insert many command strings with random
> names assigned to random command functions. I have to turn
> this in on Monday. IMVVVHO, the sparse 256-ary array based
> tree should work fine for the large data-set.
You mean a 4*27 array, don't you. 4*256 probably won't fit into
memory.
If you're looking for the simplest solution, then linear search
is fine. If the number of entries because too large, you can
either sort the array and use binary search, or switch to a trie
or a hash table. (I'd probably use a trie, but I've a certain
experience with this sort of code, and it probably wouldn't take
me more than an hour to implement it. If you've never done
anything similar before, it could easily take a day or two, once
you've fully understood the algorithm.)
> > But as this is homework, the correctness of the solution
> > should be what matters, and the speed should not be an issue
> > at all (as long as the demo completes before the professor
> > gets bored ;-).
>
> LOL!
> The only reason why I am doing this is so I can get some extra
> credit. I am interested in getting a good grade, and plan on
> becoming at least a fairly decent programmer. Perhaps I can
> even make some $$$ in the future.
If making money is your goal, the commercial side generally pays
a lot better:-). (Bill Gate's original Basic used a linear
search in the name table. It was, in fact, recommended to use
the most frequently used variables at the beginning of the
program, so they would be at the front of the table.)
--
James Kanze
James
> "James" <n...@spam.invalid> wrote in news:hdip65$283$1...@aioe.org:
>> "Paavo Helde" <myfir...@osa.pri.ee> wrote in message
>> news:Xns9CC1C54A...@216.196.109.131...
>>> "James" <n...@spam.invalid> wrote in news:hde75o$rt5$1...@aioe.org:
>>> Accessing it in random fashion will probably cause a lot of
>>> cache misses, so it is not given that this is the fastest lookup
>>> possible.
>>
>> I admit that is a cop out, however I don't really want to get into the
>> "hardware level" jest yet. However, AFAICT, there would be an upper
>> bound on the number of cache misses per-call to 'cmap::prv_find()'?
>> The size of the data-structure is static and that's that, so to speak.
>
> Sure there is an upper bound. This does not mean that the approach is the
> fastest. The big-O calculations only make sense if N is large, with N=5
> they are meaningless.
Agreed.
>>> A tag of 4 characters/bytes immediately suggests that you could
>>> interpret those 4 characters as 32-bit unsigned integers (unsigned is
>>> needed, as signed integers can have trap values).
>>
>> Do you mean something like:
[...]
>> ?
>
> Why so complex?
Ummm, I don't know. That's just what popped out...
;^/
> What I had in mind whas something like
>
> char const* const s = "command";
>
> typedef unsigned char uc; // for brevity
>
> uint32_t x = (uc(s[0])<<24) | (uc(s[1])<<16) | (uc(s[2])<<16) | uc(s[3]);
[...]
>>>> int main()
>>>> {
>>>> {
>>>
>>> Why extra braces?
>>
>> This is probably going to sound retarded, but I personally like to
>> encapsulate everything in main within an extra scope in order to
>> ensure that all objects are destructed before I actually return from
>> main. Imagine I wanted to print a final message that occurs after all
>> messages from the object dtors are printed:
>
> OK, but you did not have that final printout in the original example.
It's a habit.
>>>> static cmap<void, char const*> cm_normal(command_unknown);
>>>> static cmap<void, char const*> cm_reverse(command_unknown);
>>>
>>> Why static?
>>
>> They blow the stack on a Windows platform. BTW, I don't really see a
>> need for dynamic memory allocation here.
>>
>
> OK, but for the homework only. In real life you cannot really use static
> data, as this is hostile to multi-threading.
I am NOT a threading expert in any way shape or form, however AFAICT, the
following pseudo-code would be 100% thread-safe, and does not need any
synchronization primitives:
// [snip translator impl code]
static translator const* g_translator = NULL;
// [snip cmap impl code]
typedef cmap<void, char const*> cmap_type;
static cmap_type const* g_cmdmap = NULL;
#define ARRAY_DEPTH(t) (sizeof(t) / sizeof(t[0]))
static char const* g_cmds[] =
{
"north",
"east",
"west",
"south",
"wield"
};
extern "C"
void* pthread_entry(void* state)
{
for (;;)
{
g_commands->exec(g_cmds[rand() % ARRAY_DEPTH(g_cmds)]);
}
return NULL;
}
int main()
{
{
static translator const l_translator;
static cmap_type cmdmap(command_unknown);
// make the above visible to the outside world...
g_translator = &l_translator;
g_cmdmap = &cmdmap;
// add all of the commands in g_cmds to the cmdmap
// create threads
// join threads
}
return 0;
}
All mutations to shared data are done before the threads are created. All of
the static data-structures are fully initialized before the threads are
created. Threads perform read-only accessed to the command map and it's
translator.
Am I missing anything obvious here?
>> [...]
>>
>>>> BTW, can you think of a faster way to perform the lookup process???
>>>
>>> Given that the number of used entries in the map is 5 as in your
>>> example, it is quite certain that anything which uses a compact map
>>> (of size about 20 bytes) will be faster than your solution (using
>>> more than 500000 bytes) (of course assuming there is any kind of
>>> memory caching present in the system).
>>
>> I fully intend to insert many command strings with random names
>> assigned to random command functions. I have to turn this in on
>> Monday. IMVVVHO, the sparse 256-ary array based tree should work fine
>> for the large data-set.
>
> Yes, if N is large, the big-O rules should kick in. If N is >100000, then
> certainly your data structure is optimal.
That's what I was hoping for.
>>> But as this is homework, the correctness of the solution
>>> should be what matters, and the speed should not be an issue at all
>>> (as long as the demo completes before the professor gets bored ;-).
>>
>> LOL!
>>
>> The only reason why I am doing this is so I can get some extra credit.
>> I am interested in getting a good grade, and plan on becoming at least
>> a fairly decent programmer. Perhaps I can even make some $$$ in the
>> future.
>
> I can understand that. Your solution is quite fine in my mind, as a
> homework.
Thank you! :^)
> I would not bet though that you can get some extra credit by
> that. If I were a professor I would probably like it more if you
> implemented a custom binary search function, instead of creating large
> data arrays containing mostly emptiness.
Humm... I still have time to change it to a binary search. In fact, since I
can use 32-bit unsigned integers, I think the following hashed tree
implementation I came up with should work out quite well:
http://groups.google.com/group/comp.programming/browse_frm/thread/b6394b5bb7c59ac1
What do you think of that? Should I use it instead? Humm...
> Especially the motivation is
> very vague - you claim this is the fastest approach, without doing any
> measurements to back up your claim. I would at least make a prototype
> with std::map and compare with your approach, to see if the "O(8)" claim
> is justified.
You are 100% correct. I should test it against a std::map. BTW, the reason
why I use O(8) is because there are 4 access to the translator table, and 4
access to the 4D table in the command map regardless of how many items are
in the "container".
> Note that in real life your solution has little chances. In a real
> program nobody wants to have a component which cannot be multithreaded
> and takes 1000 times more memory than necessary, even if might work a bit
> faster than the alternatives.
AFAICT, I do think it can be multi-threaded ___IF___ all the commands are
inserted ___BEFORE___ any threads are created. In fact, well, I hope I don't
make a massive retarded fool out of my self here, but I think you could add
commands to the map while threads are reading it by using an atomic swap.
The data-structure is static such that it does not grow or shrink, and the
memory cells are the size of a function pointer. So, if the function pointer
is the size of a void* pointer, and I have atomic swap that can operate on
pointers, then an update to the map could look like this:
fp_command cmap::add(char const* name, fp_command cmd)
{
fp_command& cell = prv_find(name);
return atomic_swap(&cell, cmd);
}
This would overwrite commands that already exist and return the previous
value. If this is unacceptable, you could might be able to use atomic
compare and swap:
bool cmap::add_cas(char const* name, fp_command cmp, fp_command cmd)
{
fp_command& cell = prv_find(name);
return atomic_cas(&cell, cmp, cmd);
}
I have no idea if it will actually work the way I think it should work or
not! I am most likely missing something important.
YIKES!
> It seems you have misunderstood the goal of
> professional programming.
Oh crap!
;^(...
> It is usually not about producing the fastest
> code possible - it is all about finishing the project in the schedule,
> with code having acceptable correctness, speed, size, ease-of-usage,
> etc., for the end user, plus acceptable in-house maintainability.
I will definitely keep those wise words in mind. Thanks Paavo for all your
valuable input, I really do appreciate it!
:^)
Chris M. Thomasson
news:cb86e410-4c20-45ad...@37g2000yqm.googlegroups.com...
I am seriously thinking about using the following tree algorithm:
http://groups.google.com/group/comp.programming/browse_frm/thread/b6394b5bb7c59ac1
James Kanze
> "James" <n...@spam.invalid> wrote innews:hdip65$283$1...@aioe.org:
[...]
> It seems you have misunderstood the goal of professional
> programming. It is usually not about producing the fastest
> code possible - it is all about finishing the project in the
> schedule, with code having acceptable correctness, speed,
> size, ease-of-usage, etc., for the end user, plus acceptable
> in-house maintainability.
The goal is not "producing the fastest code possible", but
"producing the code as fast as possible":-).
--
James Kanze
James
news:hdj9pt$hqi$1...@aioe.org...
DAMN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
My cousin is going to kill me. He let me borrow his laptop so I can complete
this damn college course. It's loaded with some of his programming examples
and code sketches. I think I will just use a different newsreader. BTW, any
suggestions on a decent news reader? I don't want to send news out on the
wrong Outlook account again.
Chris M. Thomasson
[...]
> AFAICT, I do think it can be multi-threaded ___IF___ all the commands are
> inserted ___BEFORE___ any threads are created. In fact, well, I hope I
> don't make a massive retarded fool out of my self here, but I think you
> could add commands to the map while threads are reading it by using an
> atomic swap. The data-structure is static such that it does not grow or
> shrink, and the memory cells are the size of a function pointer. So, if
> the function pointer is the size of a void* pointer, and I have atomic
> swap that can operate on pointers, then an update to the map could look
> like this:
>
>
> fp_command cmap::add(char const* name, fp_command cmd)
> {
> fp_command& cell = prv_find(name);
>
> return atomic_swap(&cell, cmd);
> }
>
>
> This would overwrite commands that already exist and return the previous
> value. If this is unacceptable, you could might be able to use atomic
> compare and swap:
>
> bool cmap::add_cas(char const* name, fp_command cmp, fp_command cmd)
> {
> fp_command& cell = prv_find(name);
>
> return atomic_cas(&cell, cmp, cmd);
> }
>
>
>
> I have no idea if it will actually work the way I think it should work or
> not! I am most likely missing something important.
>
> YIKES!
James, you should focus on your class instead of multi-threading. However,
to my amazement, memory visibility aside, you're idea would actually work!
Wow!
Chris M. Thomasson
I want my damn laptop back!!! I coming over to you're house to thrash you.
LOL, just kidding James.
;^D
You can go ahead and delete my Outlook account if you want. BTW, I use the
PAN newsreader on Linux and it works fairly well.
Chris M. Thomasson
[...]
> OOPS! The last two posts were using the wrong account. Sorry Chris! I am
> Chris' cousin and am learning C++ at the local community college.
You better get an A+!
;^)
James
> On Nov 12, 5:01 pm, "James" <n...@spam.invalid> wrote:
>> "Paavo Helde" <myfirstn...@osa.pri.ee> wrote in message
>
>> typedef unsigned int uint32_type;
>
>> typedef char assert_s
>> [
>> sizeof(uint32_type) == sizeof(char) * 4
>> && sizeof(uint32_type) * CHAR_BIT == 32
>> ? 1 : -1
>> ];
>
>> typedef char cmd_buffer[4];
>
>> union cmd
>> {
>> cmd_buffer buffer;
>> uint32_type whole;
>> };
>
>> then decoding 4 chars at once like:
>
>> union cmd c;
>
>> char const* const string = "command";
>
>> c.whole = *((*uint32_type)string);
>
>> ?
>
> More likely, he was thinking of something like:
>
> uint_fast32_t i = ((c[0] & 0xFF) << 24)
> | ((c[1] & 0xFF) << 16)
> | ((c[2] & 0xFF) << 8)
> | ((c[3] & 0xFF) );
>
> This is guaranteed to work on any machine.
Yeah. I don't quite know why I used a union.
>> > (This should work for EBCDIC as well as far as both your
>> > source code and the initial data for initializing the map
>> > are in the same codepage.) Thus the mapping is simplified to
>> > integer-to-value. One could hold these in a sorted array and
>> > perform a binary search (or even a linear search in an
>> > unsorted array if the number of entries is small, placing
>> > the more frequent commands in the beginning).
>
>> Please correct me if I am way off base here but I think the
>> complexity for the simple and naive algorithm I posted should
>> be O(8) complexity for insert and lookup operations.
>
> There is no such thing as O(8). The complexity is O(1).
Yikes! I was errounsly counting each diminsion as a seperate access:
return m_table.m_fp
[g_translator[name[0]]]
[g_translator[name[1]]]
[g_translator[name[2]]]
[g_translator[name[3]]];
Humm... Okay. I count 4 separate accesses into the g_translator table. I
also count a single access into the m_table.m_fp table. Why would that not
be O(5)? I guess I need to break out of that line of thinking.
Thanks James.
> But
> the constant overhead is high due to the lack of locality. It's
> a relatively poor space/speed trade-off, given that on modern
> machines, excess space results in a noticeable slow-down.
> Better solutions exist.
>
>> This tells me that storing a large amount of items in the
>> array will have no impact on the complexity whatsoever.
>
> Array access is O(1), regardless of the size of the array. But
> that's purely a theoretical figure. In practice, if the array
> is very sparsely populated, the program will run slower,
> compared to other algorithms.
>
>> I cannot exactly claim that for a binary search whose
>> complexity parameters can be effected by N.
>
> Binary search is O(lg n). For small n (less than a couple of
> hundred), the difference is not significant. (In the tests I've
> done, binary search on a sorted vector or std::map beats hash
> coding up to somewhere between 150 and 200 entries. Even though
> hash coding is O(1) and the binary search or std::map are O(ln
> n).
have you tries using std::map as buckets in a static hash map?
struct my_map
{
std::map<...> m_buckets[DEPTH];
};
?
> Big O complexity is only significant when the number of
> elements becomes large. (How large depends on the difference in
> the big O factor. The difference between constant and quadratic
> can become significant very quickly. The difference between
> constant an logrithmic does't become significant until you
> really do have a lot of entries.
I am going to populate the table with very many of entries (e.g., hundreds
of thousands).
>> > Below are just some stylistic comments...
>
>> [...]
>
>> >> int main()
>> >> {
>> >> {
>
>> > Why extra braces?
>
>> This is probably going to sound retarded, but I personally
>> like to encapsulate everything in main within an extra scope
>> in order to ensure that all objects are destructed before I
>> actually return from main.
>
> That's interesting. Generally (in actual applications---not
> necessarily is homework type projects), main will only be a
> couple of function calls, maybe one to check the command line
> arguments, and one to do the actual work; in the case of a Unix
> like filter, you might put the loop over the filenames in main,
> but that's about it.
>
> Rather than extra braces, I'd just put the processing itself in
> a separate function. (But this is perhaps more a production
> code consideration. If you don't have command line options or
> arguments, configuration files, etc., it's probably overkill.)
Do you think it's a bad habit of mine to add the extra braces? A separate
function would most certainly work very well.
>> Imagine I wanted to print a final message that occurs after
>> all messages from the object dtors are printed:
>
> You can't, because you don't know the order the destructors of
> static objects will be called:-).
Touch�!
:^)
> [...]
>> >> static cmap<void, char const*> cm_normal(command_unknown);
>> >> static cmap<void, char const*> cm_reverse(command_unknown);
>
>> > Why static?
>
>> They blow the stack on a Windows platform.
>
> You can change the default stack size at link time, if that's
> all that's bothering you.
>
>> BTW, I don't really see a need for dynamic memory allocation
>> here.
>
> For large tables, it doesn't hurt anything. It costs the same
> to allocate int[5] and int[5000000]. In the first case, that
> cost has to be amortised over accessing 5 elements, which means
> it may be significant. In the second, it's amortised over
> accessing 5000000 elements, which means that it's practically
> nothing.
I clearly need to change my line of thinking wrt this issue. When I polish
this up I will post the code again so you call all see if I have learned
anything...
;^)
>> [...]
>
>> >> BTW, can you think of a faster way to perform the lookup
>> >> process???
>
>> > Given that the number of used entries in the map is 5 as in
>> > your example, it is quite certain that anything which uses a
>> > compact map (of size about 20 bytes) will be faster than
>> > your solution (using more than 500000 bytes) (of course
>> > assuming there is any kind of memory caching present in the
>> > system).
>
>> I fully intend to insert many command strings with random
>> names assigned to random command functions. I have to turn
>> this in on Monday. IMVVVHO, the sparse 256-ary array based
>> tree should work fine for the large data-set.
>
> You mean a 4*27 array, don't you. 4*256 probably won't fit into
> memory.
I made a stupid mistake! I was thinking of the translator array which is 256
elements wide.
Humm... I do still think of the 4*27 array as being similar to a 4-level
27-are trie. Am I off my rocker James?!
;^/
> If you're looking for the simplest solution, then linear search
> is fine. If the number of entries because too large, you can
> either sort the array and use binary search, or switch to a trie
> or a hash table. (I'd probably use a trie, but I've a certain
> experience with this sort of code, and it probably wouldn't take
> me more than an hour to implement it. If you've never done
> anything similar before, it could easily take a day or two, once
> you've fully understood the algorithm.)
I created this tree with this homework problem in mind:
http://groups.google.com/group/comp.programming/browse_frm/thread/b6394b5bb7c59ac1
Do you think I should use it instead of the 4D array?
>> > But as this is homework, the correctness of the solution
>> > should be what matters, and the speed should not be an issue
>> > at all (as long as the demo completes before the professor
>> > gets bored ;-).
>>
>> LOL!
>
>> The only reason why I am doing this is so I can get some extra
>> credit. I am interested in getting a good grade, and plan on
>> becoming at least a fairly decent programmer. Perhaps I can
>> even make some $$$ in the future.
>
> If making money is your goal, the commercial side generally pays
> a lot better:-). (Bill Gate's original Basic used a linear
> search in the name table. It was, in fact, recommended to use
> the most frequently used variables at the beginning of the
> program, so they would be at the front of the table.)
:^)
BTW, thank you for all of your expert advise James! I have been lurking
around this news groups for a while and you're input is invaluable, IMVHO of
course.
;^)
James
>>> Please correct me if I am way off base here but I think the
>>> complexity for the simple and naive algorithm I posted should
>>> be O(8) complexity for insert and lookup operations.
>>
>> There is no such thing as O(8). The complexity is O(1).
>
> Yikes! I was errounsly counting each diminsion as a seperate access:
>
> return m_table.m_fp
> [g_translator[name[0]]]
> [g_translator[name[1]]]
> [g_translator[name[2]]]
> [g_translator[name[3]]];
>
> Humm... Okay. I count 4 separate accesses into the g_translator table.
That could be rewritten as:
size_t d1 = g_translator[name[0]];
size_t d2 = g_translator[name[1]];
size_t d3 = g_translator[name[2]];
size_t d4 = g_translator[name[3]];
return m_table.m_fp[d1][d2][d3][d4];
Actually, there are 4 accesses to the name array:
char c1 = name[0];
char c2 = name[1];
char c3 = name[2];
char c4 = name[3];
size_t d1 = g_translator[c1];
size_t d2 = g_translator[c2];
size_t d3 = g_translator[c3];
size_t d4 = g_translator[c4];
return m_table.m_fp[d1][d2][d3][d4];
Can I legitimately claim that the code above is O(1)?
Please help me clear my ignorance!
;^(
[...]
Chris M. Thomasson
news:M%9Lm.24129$Wf2....@newsfe23.iad...
> "James" <n...@spam.invalid> wrote in message news:hdj9lo$hmq$1...@aioe.org...
[...]
>> not! I am most likely missing something important.
>>
>> YIKES!
>
> James, you should focus on your class instead of multi-threading. However,
> to my amazement, memory visibility aside, you're idea would actually work!
>
> Wow!
Just to clarify, you will need to use acquire/release semantics if there is
any data that is dependant on the insertion. For instance, if thread `A'
created datum `D' and inserted a command to the map that gave other threads
access to `D', then you would need to ensure that D is rendered into a fully
visible and coherent state before it becomes visible to threads other than
`A'.
Chris M. Thomasson
> "James Kanze" <james...@gmail.com> wrote in message
> news:2a34dd7b-d0dc-4194...@n35g2000yqm.googlegroups.com...
>> Rather than extra braces, I'd just put the processing itself in
>> a separate function. (But this is perhaps more a production
>> code consideration. If you don't have command line options or
>> arguments, configuration files, etc., it's probably overkill.)
>
> Do you think it's a bad habit of mine to add the extra braces? A separate
> function would most certainly work very well.
I sometimes do the exact same thing. So, no I don't think it's a bad
habit...
lol
[...]
James
news:MPG.2564d8dea...@news.eternal-september.org...
> In article <hdfd1h$cfl$1...@aioe.org>, n...@spam.invalid says...
[...]
> Of course, the real answer is to use STL or Boost, but you can just make
> a simple hash table.
> http://en.wikipedia.org/wiki/Hash_table
:^)
I think the whole point of implementing this is to teach us how much it
sucks to create these algorithms of scratch. Using a std::map is going to be
great!
Unfortunately, one of the requirements is NO STL.
damn.
James
news:M%9Lm.24129$Wf2....@newsfe23.iad...
> "James" <n...@spam.invalid> wrote in message news:hdj9lo$hmq$1...@aioe.org...
[...]
>> not! I am most likely missing something important.
>>
>> YIKES!
>
> James, you should focus on your class instead of multi-threading.
Ouch!
> However, to my amazement, memory visibility aside, you're idea would
> actually work!
>
> Wow!
You are kidding me right!? "Chris Thomasson the Thread Monkey" actually
thinks it would work?
Wow indeed!
:^D
lol
James
Since I can encode a command string into a 32-bit unsigned integer, what
about using this optimized tree algorithm:
http://groups.google.com/group/comp.programming/msg/671b1cd40f72777d
?
James Kanze
> "James Kanze" <james.ka...@gmail.com> wrote in message
[...]
> >> Please correct me if I am way off base here but I think the
> >> complexity for the simple and naive algorithm I posted
> >> should be O(8) complexity for insert and lookup operations.
> > There is no such thing as O(8). The complexity is O(1).
> Yikes! I was errounsly counting each diminsion as a seperate
> access:
> return m_table.m_fp
> [g_translator[name[0]]]
> [g_translator[name[1]]]
> [g_translator[name[2]]]
> [g_translator[name[3]]];
> Humm... Okay. I count 4 separate accesses into the
> g_translator table. I also count a single access into the
> m_table.m_fp table. Why would that not be O(5)?
Because there's no such thing as O(5). Big-O ignores any
constant multipliers, so O(5) would be the same thing as O(1).
[...]
> > Binary search is O(lg n). For small n (less than a couple
> > of hundred), the difference is not significant. (In the
> > tests I've done, binary search on a sorted vector or
> > std::map beats hash coding up to somewhere between 150 and
> > 200 entries. Even though hash coding is O(1) and the binary
> > search or std::map are O(ln n).
> have you tries using std::map as buckets in a static hash map?
> struct my_map
> {
> std::map<...> m_buckets[DEPTH];
> };
> ?
What would that buy you? If you've got more than two or three
entries in a bucket, your hash function is no good; change it,
and not the structure of the hash table.
> > Big O complexity is only significant when the number of
> > elements becomes large. (How large depends on the
> > difference in the big O factor. The difference between
> > constant and quadratic can become significant very quickly.
> > The difference between constant an logrithmic does't become
> > significant until you really do have a lot of entries.
> I am going to populate the table with very many of entries
> (e.g., hundreds of thousands).
In which case, a hash table or a tree might be the most
appropriate solution. If you really have more than a hundred
thousand, your original solution would be fine as well; the
table won't be as sparse as that; after all, there are only
475254 possible entries.
Otherwise: the advantage of a dynamically allocated trie is that
it doesn't use anywhere near as much memory if the table really
is sparse, since empty branches are represented by null
pointers.
[...]
> > Rather than extra braces, I'd just put the processing itself
> > in a separate function. (But this is perhaps more a
> > production code consideration. If you don't have command
> > line options or arguments, configuration files, etc., it's
> > probably overkill.)
> Do you think it's a bad habit of mine to add the extra braces?
> A separate function would most certainly work very well.
In your context, no. Professionally, programs tend to be a lot
more complicated, have options, read configuration files, and
things like that. Which means that main is pretty much taken up
by calling the functions to do all this, and doesn't contain any
of the program logic.
> >> [...]
> >> >> BTW, can you think of a faster way to perform the lookup
> >> >> process???
> >> > Given that the number of used entries in the map is 5 as in
> >> > your example, it is quite certain that anything which uses a
> >> > compact map (of size about 20 bytes) will be faster than
> >> > your solution (using more than 500000 bytes) (of course
> >> > assuming there is any kind of memory caching present in the
> >> > system).
> >> I fully intend to insert many command strings with random
> >> names assigned to random command functions. I have to turn
> >> this in on Monday. IMVVVHO, the sparse 256-ary array based
> >> tree should work fine for the large data-set.
> > You mean a 4*27 array, don't you. 4*256 probably won't fit
> > into memory.
> I made a stupid mistake! I was thinking of the translator
> array which is 256 elements wide.
Yes, but it's only one dimension.
> Humm... I do still think of the 4*27 array as being similar to
> a 4-level 27-are trie. Am I off my rocker James?!
It's basically the same thing, except that you have
pre-allocated all possible combinations up front. When "all
possible combinations" is less than 500000, and you count on
several hundred thousand being filled, no problem. But what
happens when your prof decides that for the next exercise,
you're to remove the maximum length of four restriction:-)? Or
simply increase it to 32---I think you'll agree that
pre-allocating for all possible combinations is not going to
work then; it has to be something dynamically built up.
> > If you're looking for the simplest solution, then linear
> > search is fine. If the number of entries because too large,
> > you can either sort the array and use binary search, or
> > switch to a trie or a hash table. (I'd probably use a trie,
> > but I've a certain experience with this sort of code, and it
> > probably wouldn't take me more than an hour to implement it.
> > If you've never done anything similar before, it could
> > easily take a day or two, once you've fully understood the
> > algorithm.)
> I created this tree with this homework problem in mind:
> http://groups.google.com/group/comp.programming/browse_frm/thread/b63...
> Do you think I should use it instead of the 4D array?
I don't know. I don't like hash tables with a fixed number of
buckets. It's not that hard to grow them (unless there are
iterators into them).
--
James Kanze
James
> On Nov 12, 10:30 pm, "James" <n...@spam.invalid> wrote:
>> "James Kanze" <james.ka...@gmail.com> wrote in message
>
> [...]
>> >> Please correct me if I am way off base here but I think the
>> >> complexity for the simple and naive algorithm I posted
>> >> should be O(8) complexity for insert and lookup operations.
>
>> > There is no such thing as O(8). The complexity is O(1).
>
>> Yikes! I was errounsly counting each diminsion as a seperate
>> access:
>
>> return m_table.m_fp
>> [g_translator[name[0]]]
>> [g_translator[name[1]]]
>> [g_translator[name[2]]]
>> [g_translator[name[3]]];
>
>> Humm... Okay. I count 4 separate accesses into the
>> g_translator table. I also count a single access into the
>> m_table.m_fp table. Why would that not be O(5)?
>
> Because there's no such thing as O(5). Big-O ignores any
> constant multipliers, so O(5) would be the same thing as O(1).
Okay. So, if an operation take a fixed number of steps to solve a problem,
you can label it as having O(1) complexity even if the number of steps is a
thousand. Am I correcting my erroneous line of thinking wrt Big-O notation,
or screwing it at all over again?
;^)
> [...]
>> > Binary search is O(lg n). For small n (less than a couple
>> > of hundred), the difference is not significant. (In the
>> > tests I've done, binary search on a sorted vector or
>> > std::map beats hash coding up to somewhere between 150 and
>> > 200 entries. Even though hash coding is O(1) and the binary
>> > search or std::map are O(ln n).
>
>> have you tries using std::map as buckets in a static hash map?
>
>> struct my_map
>> {
>> std::map<...> m_buckets[DEPTH];
>> };
>
>> ?
>
> What would that buy you? If you've got more than two or three
> entries in a bucket, your hash function is no good; change it,
> and not the structure of the hash table.
Well, AFFLICT, the only thing it would buy you is that the pressure could be
taken off a single std::map. Which one would be better:
1: a single std::map with 8192000 items in it
2: or 8192 std::maps with only 8192 items in each one
This is probably really naive, but I think that distributing the load across
N std::map's should help out when the number of items gets really huge.
I know I must be missing something here.
;^(...
>> > Big O complexity is only significant when the number of
>> > elements becomes large. (How large depends on the
>> > difference in the big O factor. The difference between
>> > constant and quadratic can become significant very quickly.
>> > The difference between constant an logrithmic does't become
>> > significant until you really do have a lot of entries.
>
>> I am going to populate the table with very many of entries
>> (e.g., hundreds of thousands).
>
> In which case, a hash table or a tree might be the most
> appropriate solution. If you really have more than a hundred
> thousand, your original solution would be fine as well; the
> table won't be as sparse as that; after all, there are only
> 475254 possible entries.
Yeah. I intend on filling up the command map with many random strings, and
assigning them to random functions. Something like:
struct random_string
{
static void generate(char* buf, size_t size)
{
for (size_t i = 0; i < size; ++i)
{
int c;
do
{
c = rand() % (UCHAR_MAX + 1);
}
while (! isalpha(c));
buf[i] = tolower(c);
}
}
};
struct random_command
{
typedef void (*fp_command) (chat const*);
static void command_1(char const* msg) {}
static void command_2(char const* msg) {}
static void command_3(char const* msg) {}
static void command_4(char const* msg) {}
// and on and on
static fp_command generate()
{
static fp_command const g_cmds[] =
{
command_1,
command_2,
command_3,
command_4
// blah, blah
};
return g_cmds[rand() % (sizeof(g_cmds) / sizeof(fp_command))];
}
};
int main()
{
{
#define DEPTH 400000
struct recall
{
char m_cmd[4];
fp_command m_fp;
};
recall* r = new recall[DEPTH];
for (size_t i = 0; i < 400000; ++i)
{
random_string::generate(r[i].m_cmd, 4);
r[i].m_fp = random_command::generate();
// add the string r[i].m_cmd with the function r[i].m_fp to the
map
}
for (size_t i = 0; i < 400000; ++i)
{
fp_command fp = // lookup r[i].m_cmd
// check for correctness
if (fp != r[i].m_fp)
{
throw std::exception();
}
}
delete [] r;
}
return 0;
}
> Otherwise: the advantage of a dynamically allocated trie is that
> it doesn't use anywhere near as much memory if the table really
> is sparse, since empty branches are represented by null
> pointers.
Indeed!
> [...]
>> > Rather than extra braces, I'd just put the processing itself
>> > in a separate function. (But this is perhaps more a
>> > production code consideration. If you don't have command
>> > line options or arguments, configuration files, etc., it's
>> > probably overkill.)
>
>> Do you think it's a bad habit of mine to add the extra braces?
>> A separate function would most certainly work very well.
>
> In your context, no. Professionally, programs tend to be a lot
> more complicated, have options, read configuration files, and
> things like that. Which means that main is pretty much taken up
> by calling the functions to do all this, and doesn't contain any
> of the program logic.
Okay. So, I am safe for now...
;^)
>> >> [...]
>
>> >> >> BTW, can you think of a faster way to perform the lookup
>> >> >> process???
>
>> >> > Given that the number of used entries in the map is 5 as in
>> >> > your example, it is quite certain that anything which uses a
>> >> > compact map (of size about 20 bytes) will be faster than
>> >> > your solution (using more than 500000 bytes) (of course
>> >> > assuming there is any kind of memory caching present in the
>> >> > system).
>
>> >> I fully intend to insert many command strings with random
>> >> names assigned to random command functions. I have to turn
>> >> this in on Monday. IMVVVHO, the sparse 256-ary array based
>> >> tree should work fine for the large data-set.
>
>> > You mean a 4*27 array, don't you. 4*256 probably won't fit
>> > into memory.
>
>> I made a stupid mistake! I was thinking of the translator
>> array which is 256 elements wide.
>
> Yes, but it's only one dimension.
>
>> Humm... I do still think of the 4*27 array as being similar to
>> a 4-level 27-are trie. Am I off my rocker James?!
>
> It's basically the same thing, except that you have
> pre-allocated all possible combinations up front.
Thank you for clarifying. I am not nuts after all!
:^)
> When "all
> possible combinations" is less than 500000, and you count on
> several hundred thousand being filled, no problem. But what
> happens when your prof decides that for the next exercise,
> you're to remove the maximum length of four restriction:-)?
Then the algorithm will be rendered into a totally useless state!
Ouch!
> Or
> simply increase it to 32---I think you'll agree that
> pre-allocating for all possible combinations is not going to
> work then; it has to be something dynamically built up.
100% totally agreed. Luckily, I am getting more and more comfortable with
tree data-structures...
>> > If you're looking for the simplest solution, then linear
>> > search is fine. If the number of entries because too large,
>> > you can either sort the array and use binary search, or
>> > switch to a trie or a hash table. (I'd probably use a trie,
>> > but I've a certain experience with this sort of code, and it
>> > probably wouldn't take me more than an hour to implement it.
>> > If you've never done anything similar before, it could
>> > easily take a day or two, once you've fully understood the
>> > algorithm.)
>
>> I created this tree with this homework problem in mind:
>
>> http://groups.google.com/group/comp.programming/browse_frm/thread/b63...
>
>> Do you think I should use it instead of the 4D array?
>
> I don't know. I don't like hash tables with a fixed number of
> buckets. It's not that hard to grow them (unless there are
> iterators into them).
I am only using the hash table to take pressure of a single tree. Is this a
boneheaded line of thinking James?
BTW, I think I am learning more on this group about practical programming
practices than in the classroom!
:^o
thanks everyone!
James Kanze
You've got it this time. All that Big-O does is characterize
the way the complexity increases as the problem becomes bigger.
It doesn't take constant factors into consideration, because in
the end, they depend on the machine and the optimizer. Thus, in
the above, the compiler will generate a certain number of
multiplications, in order to implement the multi-dimensional
indexing. On some machines, particularly older ones,
multiplication was extremely slow, and the above access would be
domintated by the multiplications, rather than the memory
accesses. On a modern machine, the reverse is generally true.
But in either case, the access will take a constant time, even
if that constant isn't known, and varies from one machine to the
next, or one compiler to the next.
(On modern machines, that's not strictly true either. The
access time will vary depending on things like locality, which
the Big-O notation doesn't take into account.)
> > [...]
> >> > Binary search is O(lg n). For small n (less than a couple
> >> > of hundred), the difference is not significant. (In the
> >> > tests I've done, binary search on a sorted vector or
> >> > std::map beats hash coding up to somewhere between 150 and
> >> > 200 entries. Even though hash coding is O(1) and the binary
> >> > search or std::map are O(ln n).
> >> have you tries using std::map as buckets in a static hash map?
> >> struct my_map
> >> {
> >> std::map<...> m_buckets[DEPTH];
> >> };
> >> ?
> > What would that buy you? If you've got more than two or three
> > entries in a bucket, your hash function is no good; change it,
> > and not the structure of the hash table.
> Well, AFFLICT, the only thing it would buy you is that the
> pressure could be taken off a single std::map.
Yes, but if you've implemented and are using the hash table,
there's no point in using the std::map as well. It doesn't buy
you anything.
> Which one would be better:
> 1: a single std::map with 8192000 items in it
> 2: or 8192 std::maps with only 8192 items in each one
3: 9000000 or 10000000 std::vector, with one or two items in
each, and a linear search in the vector.
> This is probably really naive, but I think that distributing
> the load across N std::map's should help out when the number
> of items gets really huge.
> I know I must be missing something here.
Maybe the fact that you already have a hash table, which should
be distributing the load over 9 or 10 million vectors (or maps,
if that's what you're using). And the resulting load is small
enough, or should be, that linear search in a vector or a list
like structure should be faster than accessing into a map.
[...]
> Yeah. I intend on filling up the command map with many random
> strings, and assigning them to random functions. Something
> like:
> struct random_string
> {
> static void generate(char* buf, size_t size)
> {
> for (size_t i = 0; i < size; ++i)
> {
> int c;
> do
> {
> c = rand() % (UCHAR_MAX + 1);
> }
> while (! isalpha(c));
Ouch. Why not something like:
c = "abcdefghijklmnopqrstuvwxyz"[rand() % 26];
and forego the inner loop?
> buf[i] = tolower(c);
> }
> }
> };
[...]
> >> Do you think I should use it instead of the 4D array?
> > I don't know. I don't like hash tables with a fixed number of
> > buckets. It's not that hard to grow them (unless there are
> > iterators into them).
> I am only using the hash table to take pressure of a single
> tree. Is this a boneheaded line of thinking James?
Sort of. Hash tables have a certain complexity. Done
correctly, the allow constant time access. You've paid for the
complexity of the hash table; there's no point in adding in the
complexity of a tree as well. One or the other. (Generally,
I've favored hash tables in the past. Compared to std::map,
they have two disadvantages, however. The first is that you
need a good hash function, or they don't work well, and a naïve
user won't necessarily know how to provide such a function. The
second is that std::map is already written, and is part of the
standard, so every other C++ programmer who reads your code
should understand its use; the same isn't true of your hand
written hash table.)
--
James Kanze
Chris M. Thomasson
On Nov 13, 5:54 am, "James" <n...@spam.invalid> wrote:
> > I am only using the hash table to take pressure of a single
> > tree. Is this a boneheaded line of thinking James?
> Sort of. Hash tables have a certain complexity. Done
> correctly, the allow constant time access. You've paid for the
> complexity of the hash table; there's no point in adding in the
> complexity of a tree as well. One or the other. (Generally,
> I've favored hash tables in the past. Compared to std::map,
> they have two disadvantages, however. The first is that you
> need a good hash function, or they don't work well, and a na�ve
> user won't necessarily know how to provide such a function. The
> second is that std::map is already written, and is part of the
> standard, so every other C++ programmer who reads your code
> should understand its use; the same isn't true of your hand
> written hash table.)
IMHO, one reason why it might be a good idea to use tree's as hash buckets
is that provides "natural" parallelism in the context of multi-threading.
Also, you don't need to worry about expanding/contracting the size of the
hash table. Multiple threads can search for, and add/remove, items that hash
into different buckets in parallel.
James Kanze
> "James Kanze" <james.ka...@gmail.com> wrote in message
> news:c5e99f7b-909a-4512...@t2g2000yqn.googlegroups.com...
> On Nov 13, 5:54 am, "James" <n...@spam.invalid> wrote:
> [...]
> > > I am only using the hash table to take pressure of a
> > > single tree. Is this a boneheaded line of thinking James?
> > Sort of. Hash tables have a certain complexity. Done
> > correctly, the allow constant time access. You've paid for
> > the complexity of the hash table; there's no point in adding
> > in the complexity of a tree as well. One or the other.
> > (Generally, I've favored hash tables in the past. Compared
> > to std::map, they have two disadvantages, however. The
> > first is that you need a good hash function, or they don't
> > work well, and a naïve user won't necessarily know how to
> > provide such a function. The second is that std::map is
> > already written, and is part of the standard, so every other
> > C++ programmer who reads your code should understand its
> > use; the same isn't true of your hand written hash table.)
> IMHO, one reason why it might be a good idea to use tree's as
> hash buckets is that provides "natural" parallelism in the
> context of multi-threading. Also, you don't need to worry
> about expanding/contracting the size of the hash table.
> Multiple threads can search for, and add/remove, items that
> hash into different buckets in parallel.
True parallelization (multiple threads on multiple cores) does
introduce additional considerations. But I'm still not
convinced: if I understand you correctly, you'd put a lock (or
other synchronization) on the bucket, rather than on the
complete table. But how does this affect how you manage the
bucket. What I'm saying is that maintaining the bucket as a
classical array, with linear search, should be faster (and will
certainly require less memory) than maintaining it as a balanced
tree (with O(lg n) lookup inside the bucket) because there
should never be more than a couple of entries in each bucket.
I don't see where the algorithm used in managing the buckets
affects whether you need a lock at the table level, or just at
the bucket level---as far as I can tell, the only time you'd
need a lock at the table level is when increasing the number of
buckets.
--
James Kanze
Chris M. Thomasson
On Nov 23, 12:01 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> "James Kanze" <james.ka...@gmail.com> wrote in message
> news:c5e99f7b-909a-4512...@t2g2000yqn.googlegroups.com...
> On Nov 13, 5:54 am, "James" <n...@spam.invalid> wrote:
> [...]
> > > > I am only using the hash table to take pressure of a
> > > > single tree. Is this a boneheaded line of thinking James?
> > > Sort of. Hash tables have a certain complexity. Done
> > > correctly, the allow constant time access. You've paid for
> > > the complexity of the hash table; there's no point in adding
> > > in the complexity of a tree as well. One or the other.
> > > (Generally, I've favored hash tables in the past. Compared
> > > to std::map, they have two disadvantages, however. The
> > > first is that you need a good hash function, or they don't
> > > work well, and a na�ve user won't necessarily know how to
> > > provide such a function. The second is that std::map is
> > > already written, and is part of the standard, so every other
> > > C++ programmer who reads your code should understand its
> > > use; the same isn't true of your hand written hash table.)
> > IMHO, one reason why it might be a good idea to use tree's as
> > hash buckets is that provides "natural" parallelism in the
> > context of multi-threading. Also, you don't need to worry
> > about expanding/contracting the size of the hash table.
> > Multiple threads can search for, and add/remove, items that
> > hash into different buckets in parallel.
> True parallelization (multiple threads on multiple cores) does
> introduce additional considerations. But I'm still not
> convinced: if I understand you correctly, you'd put a lock (or
> other synchronization) on the bucket, rather than on the
> complete table.
A rw-mutex per-table and per-bucket is okay. FWIW, here is a "decent"
rw-mutex implementation:
http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic/65822
> But how does this affect how you manage the
> bucket.
I am not sure I understand you correctly. I can say that the synchronization
of table operations (e.g., expand/contract) can effect the choice of
per-bucket synchronization. Furthermore, the per-bucket sync has an effect
on the choice of data-structure you can use for handling hash collisions on
a per-bucket basis. All of the methods have there own tradeoffs.
> What I'm saying is that maintaining the bucket as a
> classical array, with linear search, should be faster (and will
> certainly require less memory) than maintaining it as a balanced
> tree (with O(lg n) lookup inside the bucket) because there
> should never be more than a couple of entries in each bucket.
>
>
> I don't see where the algorithm used in managing the buckets
> affects whether you need a lock at the table level, or just at
> the bucket level---as far as I can tell, the only time you'd
> need a lock at the table level is when increasing the number of
> buckets.
WRT lock-based synchronization, reader and writer threads always need to
gain shared access to the "dynamic" table _before_ they gain access the
per-bucket rwlock. A writer thread that wishes to alter the dimensions/size
of the table upgrades the shared access to exclusive and expands the table
when no readers or writers are accessing it. A thread that wants to
explicitly set the size can simple acquire exclusive table access.