Graal Forums - Programming Exercise #3

Graal Forums (https://forums.graalonline.com/forums/index.php)

- NPC Scripting (https://forums.graalonline.com/forums/forumdisplay.php?f=8)

- - Programming Exercise #3 (https://forums.graalonline.com/forums/showthread.php?t=79189)

Quote:

Originally Posted by Inverness (Post 1382644)

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

Quote:

Originally Posted by DrakilorP2P (Post 1382566)

Won't that miss the "AAAAAAAAA" pattern that occurs twice in "AAAAAAAAAA"?

bah, didn't think about that :o

Quote:

Originally Posted by cbkbud (Post 1382643)

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.

Quote:

Originally Posted by Inverness (Post 1382731)

You need to like completely redo your script.

Yes, this is why I did not bother calculating the loops in your script. :p

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

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));
  }
}

Quote:

Originally Posted by Inverness (Post 1382731)

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.

Quote:

Originally Posted by Tolnaftate2004 (Post 1382741)

(you're all 1 order higher). :3

So are you.

PHP Code:


		
			
function findpatterns(str) {
  instances=oompaloompa(str);
  return instances;
}

Quote:

Originally Posted by Inverness (Post 1382759)

So are you.

Now that's just uncalled for. :cry:

Quote:

Originally Posted by DustyPorViva (Post 1382769)

PHP Code:


		
			
function findpatterns(str) {

  instances=oompaloompa(str);

  return instances;

}

You so win.

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.

Quote:

Originally Posted by zokemon (Post 1382880)

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.

Quote:

Originally Posted by zokemon (Post 1382880)

how many people here don't know what big-O is.

*Raises hand in embarrasment*

Quote:

Originally Posted by Rapidwolve24 (Post 1382901)

*Raises hand in embarrasment*

Pffft!

PHP Code:

3/0

Dumb noobs.