Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #31  
Old 03-27-2008, 07:47 AM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Inverness View Post
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..
Reply With Quote
  #32  
Old 03-27-2008, 06:34 PM
Chompy Chompy is offline
¯\(º_o)/¯
Chompy's Avatar
Join Date: Sep 2006
Location: Norway
Posts: 2,815
Chompy is just really niceChompy is just really niceChompy is just really nice
Send a message via MSN to Chompy
Quote:
Originally Posted by DrakilorP2P View Post
Won't that miss the "AAAAAAAAA" pattern that occurs twice in "AAAAAAAAAA"?
bah, didn't think about that :o
__________________
Reply With Quote
  #33  
Old 03-27-2008, 09:04 PM
Inverness Inverness is offline
Incubator
Inverness's Avatar
Join Date: Aug 2004
Location: Houston, Texas
Posts: 3,613
Inverness is a jewel in the roughInverness is a jewel in the rough
Quote:
Originally Posted by cbkbud View Post
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.
__________________
Reply With Quote
  #34  
Old 03-27-2008, 09:44 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Inverness View Post
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..
Reply With Quote
  #35  
Old 03-27-2008, 10:25 PM
napo_p2p napo_p2p is offline
oh snaps
napo_p2p's Avatar
Join Date: Sep 2003
Location: Pismo Beach, California
Posts: 2,118
napo_p2p has a spectacular aura aboutnapo_p2p has a spectacular aura about
Send a message via AIM to napo_p2p Send a message via MSN to napo_p2p
PHP Code:
function findpatterns(str) {
  
temp.loc 0;
  
temp.temp.str.length();
  
temp.results = new[0];
  
  while (
temp.loc temp.l) {
    
temp.len 2;
    while (
temp.len <= (temp.temp.loc)) {
      
temp.seq temp.str.substring(temp.loctemp.len);
      
temp.("count_" temp.seq)++;
      if (
temp.("count_" temp.seq) == 2) {
        
temp.results.add(temp.seq);
      }
      
temp.len++;
    }
    
temp.loc++;
  }

  for (
temp.rtemp.results) {
    echo(
temp.": " 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: .
Reply With Quote
  #36  
Old 03-27-2008, 10:52 PM
cbk1994 cbk1994 is offline
the fake one
cbk1994's Avatar
Join Date: Mar 2003
Location: San Francisco
Posts: 10,718
cbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond repute
Send a message via AIM to cbk1994
Quote:
Originally Posted by Inverness View Post
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.
__________________
Reply With Quote
  #37  
Old 03-27-2008, 11:00 PM
Inverness Inverness is offline
Incubator
Inverness's Avatar
Join Date: Aug 2004
Location: Houston, Texas
Posts: 3,613
Inverness is a jewel in the roughInverness is a jewel in the rough
Quote:
Originally Posted by Tolnaftate2004 View Post
(you're all 1 order higher). :3
So are you.
__________________
Reply With Quote
  #38  
Old 03-27-2008, 11:16 PM
DustyPorViva DustyPorViva is offline
Will work for food. Maybe
DustyPorViva's Avatar
Join Date: Sep 2003
Location: Maryland, USA
Posts: 9,589
DustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond repute
Send a message via AIM to DustyPorViva Send a message via MSN to DustyPorViva
PHP Code:
function findpatterns(str) {
  
instances=oompaloompa(str);
  return 
instances;

Reply With Quote
  #39  
Old 03-27-2008, 11:21 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Inverness View Post
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 :/
Reply With Quote
  #40  
Old 03-28-2008, 02:28 AM
cbk1994 cbk1994 is offline
the fake one
cbk1994's Avatar
Join Date: Mar 2003
Location: San Francisco
Posts: 10,718
cbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond repute
Send a message via AIM to cbk1994
Quote:
Originally Posted by DustyPorViva View Post
PHP Code:
function findpatterns(str) {
  
instances=oompaloompa(str);
  return 
instances;

You so win.
__________________
Reply With Quote
  #41  
Old 03-28-2008, 05:32 PM
zokemon zokemon is offline
That one guy...
zokemon's Avatar
Join Date: Mar 2001
Location: Sonoma County, California
Posts: 2,925
zokemon is a jewel in the roughzokemon is a jewel in the rough
Send a message via ICQ to zokemon Send a message via AIM to zokemon Send a message via MSN to zokemon Send a message via Yahoo to 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.
__________________
Do it with a DON!
Reply With Quote
  #42  
Old 03-28-2008, 08:20 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by zokemon View Post
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 :/
Reply With Quote
  #43  
Old 03-28-2008, 08:55 PM
Rapidwolve24 Rapidwolve24 is offline
North*
Join Date: Oct 2007
Location: Massachusetts
Posts: 178
Rapidwolve24 is on a distinguished road
Send a message via AIM to Rapidwolve24 Send a message via MSN to Rapidwolve24
Quote:
Originally Posted by zokemon View Post
how many people here don't know what big-O is.
*Raises hand in embarrasment*
Reply With Quote
  #44  
Old 03-29-2008, 08:01 AM
xXziroXx xXziroXx is offline
Master of Puppets
xXziroXx's Avatar
Join Date: May 2004
Location: Sweden
Posts: 5,288
xXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant future
Send a message via AIM to xXziroXx Send a message via MSN to xXziroXx
Quote:
Originally Posted by Rapidwolve24 View Post
*Raises hand in embarrasment*
x2
__________________

"A delayed game is eventually good, but a rushed game is forever bad." - Shigeru Miyamoto
Reply With Quote
  #45  
Old 04-06-2008, 02:29 PM
Horrified Horrified is offline
Rediculously inactive
Join Date: Jul 2007
Posts: 961
Horrified is on a distinguished road
Send a message via ICQ to Horrified Send a message via AIM to Horrified Send a message via MSN to Horrified Send a message via Yahoo to Horrified
Pffft!

PHP Code:
3/
Dumb noobs.
Reply With Quote
Reply

Tags
pattern-matching, programming-exercise

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

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 Jump


All times are GMT +2. The time now is 03:05 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.