Post #178,581
10/9/04 12:22:32 AM
|
I don't know - multimap
as I read through the example, I could see why he went from a hash to a hash of arrays -- perl dosn't really have a multimap facility that I know of.
As I looked at with C++ & STL; I thought, why are we putting it in an array at all?
#include <iostream>
#include <map>
#include <vector>
#include <string>
int main(int argc, char **argv)
{
std::map<std::string, std::string> den;
den["one"] = "a";
den["two"] = "b";
den["three"] = "c";
den["four"] = "b";
den["five"] = "c";
den["six"] = "a";
den["seven"] = "b";
std::multimap<std::string , std::string> norm;
for (std::map<std::string, std::string>::iterator i = den.begin(); i != den.end(); i++)
{
norm.insert(std::pair<std::string, std::string>(i->second, i->first));
}
std::string s;
std::multimap<std::string, std::string>::iterator pos;
for (std::multimap<std::string, std::string >::iterator i = norm.begin(); i != norm.end(); i++)
{
if (s != i->first)
{
s = i->first;
std::cout << i->first << ":";
for (pos = norm.lower_bound(i->first); pos != norm.upper_bound(i->first); ++pos)
{
std::cout << pos->second << " ";
}
std::cout << std::endl;
}
}
std::cout << std::endl;
}
I'll admit a lot of wasted effort for the formatted output. But, given the times for data lookup...
|
Post #178,606
10/9/04 12:17:47 PM
|
Re: I don't know - multimap
I thought about it, but then decided to stay true to the original format. May be Todd wanted to do something with arrays later...
Your version is more efficient, too.
--
... a reference to Presidente Arbusto.
-- [link|http://itre.cis.upenn.edu/~myl/languagelog/archives/001417.html|Geoffrey K. Pullum]
|
Post #178,607
10/9/04 12:25:52 PM
|
Why the worry about efficiency?
You're comparing with Perl. Pretty much anything is at least 10x faster in C than Perl. Any semi-sane C++ version will be faster. And take less memory. If programmer time is less important than those factors, then Perl is definitely the wrong language.
Furthermore standard programming advice - which I follow even in Perl - is to not micro-optimize. Concentrate on making the design clean, and if performance is a problem later (it usually isn't), then benchmark for the hotspots and optimize that. Always thinking about efficiency looks a heck of a lot like micro-optimizing to me.
Cheers,
Ben
I have come to believe that idealism without discipline is a quick road to disaster, while discipline without idealism is pointless. -- Aaron Ward (my brother)
|
Post #178,608
10/9/04 12:30:44 PM
|
I worry about efficiency
because I deliberately picked O(n^2) that looks clean to someone who doesn't care to go into STL's intricacies. I could have gotten O(n log n). I think it's a good trade-off for a sample code, but I am used to be aware of such trade-offs. AT the level I usually program, that kind of decision is a difference between 12,000 traps per second and 4,000 traps per second.
--
... a reference to Presidente Arbusto.
-- [link|http://itre.cis.upenn.edu/~myl/languagelog/archives/001417.html|Geoffrey K. Pullum]
|
Post #178,612
10/9/04 12:59:07 PM
|
Ah
Yeah, I tend to be aware of O(n) vs O(n*log(n)). If my data set is small I might go for the worse one, but might not.
One nice thing about Perl is that often the most obvious way to write something is also pretty good algorithmically. That is because you reach for hashes early, which have average performance O(1). (Worst case O(n), I've never seen that happen accidentally though...)
So the Perl solution offered is O(n) average case, with an unlikely worst case performance of O(n^2).
Cheers,
Ben
I have come to believe that idealism without discipline is a quick road to disaster, while discipline without idealism is pointless. -- Aaron Ward (my brother)
|
Post #178,610
10/9/04 12:41:13 PM
|
C vs Perl - efficiency - untrue for me
I'm almost always bottlenecked on IO. Well, maybe not any more with the new arrays. But for my type of data munging for data warehouse work, Perl has been a fast as C when I did my simple tests.
|
Post #178,613
10/9/04 1:11:47 PM
|
Point - but you may want to rebenchmark
I know that historically on Linux, Perl's I/O performance was not up to snuff. I don't remember the exact cause, but the situation was bad enough that with a default compile it could be faster to read data and split it into lines inside of Perl rather than have Perl do that splitting!
I believe that this has since been fixed.
Another vague memory tells me that enabling Unicode processing can add significant overhead to Perl's I/O.
And, of course, the default Perl 5.8 that shipped with Red Hat 9 was compiled with threads and significantly underperformed any version of Perl that you'd be likely to compile for yourself. People benchmarking that gave rise to a myth that Perl 5.8 was a lot slower than 5.6. Nope. If you compile with the same options, the speeds are basically equivalent. But the version of 5.8 shipped by Red Hat was slower than their version of 5.6. Here are [link|http://mathforum.org/epigone/modperl/clikingspimp/1068515972.2699.131.camel@localhost.localdomain|some benchmarks] that a friend of mine did.
Cheers,
Ben
I have come to believe that idealism without discipline is a quick road to disaster, while discipline without idealism is pointless. -- Aaron Ward (my brother)
|
