Graal Forums Programming Exercise #3
 User Name Remember Me? Password
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

 Thread Tools Search this Thread Display Modes
#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

 Thread Tools Search this Thread Search this Thread: Advanced Search Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General Forums     Graal Main Forum (English)         Hello and Goodbyes         Birthday Forum         Guild Life         Job Forum             Global Scripting Team             Playerworld Administration Team             Forum moderation Team             Graal Kingdoms Team             Graal Zone Team             Wiki Administration Team         Server Maintenance         Discussions en Francais (Français)         Diskussionsforum (Deutsch)     Forum Rules and documentation     Non-Graal-related threads Graal V6 forums     Announcements     Your opinion     Questions about V6     Feature request     Bug Report Gold Servers     Graal Kingdoms         Markets         Kingdoms             Dustari             Forest             Crescent Pirates             Samurai             Zormite Republic         Graal Kingdoms Events         Information             Gods         GK Suggestions         GK Bugs     Zone         Gfx submissions         Information         Zone Suggestions.         Zone Bugs         Zone News         Zone PC PlayerWorlds     PlayerWorlds Main Forum         Playerworld Related Information     Playerworld Staff Openings     Bomy Island Main Forum         Kingdoms Main Forum         Events and Activities         Bugs and Future Improvements             New Races     Classic Main Forum         Classic News         Classic Bugs and suggestions         Hiring for Classic     Delteria Main Forum         Delteria News         Delteria Bugs and suggestions         Hiring for Delteria     Era Main Forum         Era News         Era Bugs and improvements         Hiring for Era         Era Wiki     N-Pulse Main Forum         N-Pulse News         N-Pulse Bugs and suggestions         Hiring for N-Pulse     Unholy Nation Main Forum         Unholy Nation News         Unholy Nation Bugs and improvements         Hiring for Unholy Nation     Valikorlia Main Forum         Valikorlia News         Valikorlia Bugs and suggestions         Hiring for Valikorlia     Zodiac Main Forum         Zodiac News         Zodiac Bugs and suggestions         Hiring for Zodiac Development Forums     Level Design     Graphic Design     Sounds & Music     Gani Construction     Videos     NPC Scripting         New Scripting Engine (GS2)         Old Scripting Engine (GS1)         Code Gallery     Tech Support         Bug Reports (No posting)     Future Improvements Private forums

All times are GMT +2. The time now is 10:05 AM.

 -- Graal Forums - Author on top -- Mobile -- Graal Forums - Old Layout Contact Us - Graal - Archive - Privacy Statement - Top