IWETHEY v. 0.3.0 | TODO
1,095 registered users | 1 active user | 0 LpH | Statistics
Login | Create New User
IWETHEY Banner

Welcome to IWETHEY!

IWETHEY Home / IWETHEY Board / Theory and Practice of Programming Forum / I worry about efficiency
Post #178,608
by Arkadiy
Picture of Arkadiy
10/9/04 12:30:44 PM
Reply
New 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
by ben_tilly
10/9/04 12:59:07 PM
Reply
New 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)
     Perl frustrations - (tuberculosis) - (45) - Oct. 7, 2004, 03:55:53 PM EDT
         Simple solution - (ben_tilly) - (10) - Oct. 7, 2004, 05:31:13 PM EDT
             Bleh. - (admin) - (3) - Oct. 7, 2004, 04:42:49 PM EDT
                 That's because you approached it wrong - (ben_tilly) - (2) - Oct. 7, 2004, 05:22:57 PM EDT
                     I'm gradually warming up to it - (deSitter) - Oct. 7, 2004, 09:08:18 PM EDT
                     That should be in the man page. - (static) - Oct. 8, 2004, 02:17:42 AM EDT
             Is this a sort of typecasting? - (tuberculosis) - (2) - Oct. 7, 2004, 05:36:33 PM EDT
                 It's a reference -NT - (Simon_Jester) - Oct. 7, 2004, 06:00:50 PM EDT
                 Sort of - (ben_tilly) - Oct. 7, 2004, 06:10:14 PM EDT
             Interesting.... - (Simon_Jester) - (2) - Oct. 7, 2004, 05:58:41 PM EDT
                 The solution would have its own problems - (ben_tilly) - (1) - Oct. 7, 2004, 06:27:50 PM EDT
                     <bow> thank you. -NT - (Simon_Jester) - Oct. 7, 2004, 11:14:47 PM EDT
         THank you for stepping on this rake - (Arkadiy) - (33) - Oct. 7, 2004, 05:20:48 PM EDT
             He was overcomplicating it - (ben_tilly) - (32) - Oct. 7, 2004, 05:30:04 PM EDT
                 Well, maybe - (tuberculosis) - (17) - Oct. 7, 2004, 05:43:24 PM EDT
                     Agreed - (ben_tilly) - (16) - Oct. 7, 2004, 06:12:17 PM EDT
                         Agree its a mistake - (tuberculosis) - (15) - Oct. 7, 2004, 06:36:09 PM EDT
                             Same here. - (admin) - Oct. 7, 2004, 06:45:32 PM EDT
                             Right - (ben_tilly) - Oct. 7, 2004, 06:56:48 PM EDT
                             Shame about the inertia. Python's design is "least surprise" - (FuManChu) - (12) - Oct. 7, 2004, 10:02:43 PM EDT
                                 When I started with Perl... - (ben_tilly) - (11) - Oct. 7, 2004, 10:53:12 PM EDT
                                     On Perl 6 - (pwhysall) - (3) - Oct. 8, 2004, 01:53:55 AM EDT
                                         Re: On Perl 6 - (Yendor) - Oct. 8, 2004, 08:37:56 AM EDT
                                         I had a nice response to this typed up - (ben_tilly) - (1) - Oct. 8, 2004, 12:54:37 PM EDT
                                             Many thanks for that - (pwhysall) - Oct. 9, 2004, 02:53:04 AM EDT
                                     We're having a little brown bag on Ruby - (tuberculosis) - (4) - Oct. 8, 2004, 12:46:50 PM EDT
                                         Re: We're having a little brown bag on Ruby - (JimWeirich) - (3) - Oct. 11, 2004, 06:55:34 AM EDT
                                             Shhh! Anonymous Todd works at some other... - (CRConrad) - Oct. 11, 2004, 07:36:30 AM EDT
                                             I might have been there - (tuberculosis) - (1) - Oct. 11, 2004, 12:55:46 PM EDT
                                                 Re: I might have been there - (JimWeirich) - Oct. 11, 2004, 01:14:57 PM EDT
                                     Re: strict -- have you seen pychecker? - (FuManChu) - (1) - Oct. 8, 2004, 01:02:20 PM EDT
                                         No I hadn't, thanks - (ben_tilly) - Oct. 8, 2004, 01:08:02 PM EDT
                 BTW Arkadiy, I'm still waiting for a response - (ben_tilly) - (13) - Oct. 8, 2004, 12:57:52 PM EDT
                     I am not saying it's shorter in C... - (Arkadiy) - (10) - Oct. 8, 2004, 03:22:09 PM EDT
                         And now for my real comment - (ben_tilly) - (2) - Oct. 8, 2004, 03:34:09 PM EDT
                             May be it's a hindsight thing - (Arkadiy) - (1) - Oct. 8, 2004, 03:47:36 PM EDT
                                 It could be many things - (ben_tilly) - Oct. 8, 2004, 06:13:45 PM EDT
                         I don't know - multimap - (Simon_Jester) - (6) - Oct. 9, 2004, 12:22:32 AM EDT
                             Re: I don't know - multimap - (Arkadiy) - (5) - Oct. 9, 2004, 12:17:47 PM EDT
                                 Why the worry about efficiency? - (ben_tilly) - (4) - Oct. 9, 2004, 12:25:52 PM EDT
                                     I worry about efficiency - (Arkadiy) - (1) - Oct. 9, 2004, 12:30:44 PM EDT
                                         Ah - (ben_tilly) - Oct. 9, 2004, 12:59:07 PM EDT
                                     C vs Perl - efficiency - untrue for me - (broomberg) - (1) - Oct. 9, 2004, 12:41:13 PM EDT
                                         Point - but you may want to rebenchmark - (ben_tilly) - Oct. 9, 2004, 01:11:47 PM EDT
                     Here's a smalltalk version - (tuberculosis) - (1) - Oct. 8, 2004, 06:16:21 PM EDT
                         Yes, think of a reference as a pointer - (ben_tilly) - Oct. 8, 2004, 06:43:04 PM EDT

You are delightfully evil. Come sit by me.
318 ms