Graal Forums Programming Exercise #3
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

#31
03-27-2008, 07:47 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by Inverness Anyhow, if the goal is "to make this as efficient as possible with graal script" then you should be measuring based on time to complete instead of your big-O thing since the hard-coded functions do have a notable speed difference.
The hard-coded for-loop is some multiple constant faster than the graal script for-loop. This does not change the big-O.

If I pass a large enough string, an O(n^2) algorithm will always be faster than an O(n^3).

Here are some hints:
linear search: searching by iteration.
obj.index, obj.pos, obj.positions are most likely using linear search. What this means is that there is a 'hidden' for loop within script that use these functions. If N is obj.length() or obj.size(), obj.positions takes about N loops to find all occurences of your substring. obj.pos and obj.index on average take N/2 loops.

The 'in' operator when used with arrays is also using linear search (most likely). This again takes on average N/2 loops. Other uses of it are likely O(1).
obj.remove uses linear search as well.

Maybe more later... ;x
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/

Last edited by Tolnaftate2004; 03-27-2008 at 08:15 AM..
#32
03-27-2008, 06:34 PM
 Chompy ¯\(º_o)/¯ Join Date: Sep 2006 Location: Norway Posts: 2,815
Quote:
 Originally Posted by DrakilorP2P Won't that miss the "AAAAAAAAA" pattern that occurs twice in "AAAAAAAAAA"?
bah, didn't think about that :o
 __________________
#33
03-27-2008, 09:04 PM
 Inverness Incubator Join Date: Aug 2004 Location: Houston, Texas Posts: 3,613
Quote:
 Originally Posted by cbkbud I bet I could beat my previous time of 12 seconds by triggering my web server which would use awesome fast PHP to find patterns, then return them to Graal. Slower than some, but surely faster than 12 seconds?
You need to like completely redo your script. My thing runs in 0.00138 seconds or so on average.
 __________________
#34
03-27-2008, 09:44 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by Inverness You need to like completely redo your script.
Yes, this is why I did not bother calculating the loops in your script.

e: Just made the realization that obj.substring() also contains a hidden for loop. Which makes all big-O calculations I did wrong (you're all 1 order higher). :3
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/

Last edited by Tolnaftate2004; 03-27-2008 at 10:09 PM..
#35
03-27-2008, 10:25 PM
 napo_p2p oh snaps Join Date: Sep 2003 Location: Pismo Beach, California Posts: 2,118
 PHP Code: ``` function findpatterns(str) {  temp.loc = 0;  temp.l = temp.str.length();  temp.results = new[0];    while (temp.loc < temp.l) {    temp.len = 2;    while (temp.len <= (temp.l - temp.loc)) {      temp.seq = temp.str.substring(temp.loc, temp.len);      temp.("count_" @ temp.seq)++;      if (temp.("count_" @ temp.seq) == 2) {        temp.results.add(temp.seq);      }      temp.len++;    }    temp.loc++;  }  for (temp.r: temp.results) {    echo(temp.r @ ": " @ temp.("count_" @ temp.r));  }}  ```
 __________________ Scito hoc super omnia. Haec vita est tua una sola. Dum vita superest, utere maxime quoque puncto, momento, et hora quae habes. Tempus neminem non manet. Noli manere tempus. Carpe Diem Seize the Day.

Last edited by napo_p2p; 03-27-2008 at 10:27 PM.. Reason: .
#36
03-27-2008, 10:52 PM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
Quote:
 Originally Posted by Inverness You need to like completely redo your script. My thing runs in 0.00138 seconds or so on average.
I know, I'm not going to bother though since I couldn't beat anyone.
 __________________
#37
03-27-2008, 11:00 PM
 Inverness Incubator Join Date: Aug 2004 Location: Houston, Texas Posts: 3,613
Quote:
 Originally Posted by Tolnaftate2004 (you're all 1 order higher). :3
So are you.
 __________________
#38
03-27-2008, 11:16 PM
 DustyPorViva Will work for food. Maybe Join Date: Sep 2003 Location: Maryland, USA Posts: 9,589
 PHP Code: ``` function findpatterns(str) {  instances=oompaloompa(str);  return instances;}  ```
#39
03-27-2008, 11:21 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by Inverness So are you.
Now that's just uncalled for.
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
#40
03-28-2008, 02:28 AM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
Quote:
 Originally Posted by DustyPorViva PHP Code: ``` function findpatterns(str) {   instances=oompaloompa(str);   return instances; }  ```
You so win.
 __________________
#41
03-28-2008, 05:32 PM
 zokemon That one guy... Join Date: Mar 2001 Location: Sonoma County, California Posts: 2,925
 You guys seriously having this much trouble? It's not that hard... Just boring; which is why I won't do it! Also, It's funny how many people here don't know what big-O is.
 __________________ Do it with a DON!
#42
03-28-2008, 08:20 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by zokemon You guys seriously having this much trouble? It's not that hard... Just boring; which is why I won't do it! Also, It's funny how many people here don't know what big-O is.
Give us pseudocode, then.
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
#43
03-28-2008, 08:55 PM
 Rapidwolve24 North* Join Date: Oct 2007 Location: Massachusetts Posts: 178
Quote:
 Originally Posted by zokemon how many people here don't know what big-O is.
*Raises hand in embarrasment*
#44
03-29-2008, 08:01 AM
 xXziroXx Master of Puppets Join Date: May 2004 Location: Sweden Posts: 5,288
Quote:
 Originally Posted by Rapidwolve24 *Raises hand in embarrasment*
x2
 __________________ Contact Informationemail: [email protected] "A delayed game is eventually good, but a rushed game is forever bad." - Shigeru Miyamoto
#45
04-06-2008, 02:29 PM
 Horrified Rediculously inactive Join Date: Jul 2007 Posts: 961
 Pffft! PHP Code: ``` 3/0  ``` Dumb noobs.

 Tags pattern-matching, programming-exercise