Programming Exercise #3

[Tolnaftate2004]

Originally Posted by Inverness

No comment on what I posted?

You've irritated me.

Yours is still O(n³).

e: The new standard set by DrakilorP2P, O(n²)
@Ziro: Will keep that in mind.

[Inverness]

Originally Posted by Tolnaftate2004

Yours is still O(n³).

e: The new standard set by DrakilorP2P, O(n²)

What the hell are you talking about?

Increased speed of script:

PHP Code:

function findpatterns(str) {
  temp.time = timevar2;
  temp.outc = {};
  temp.out = {};
  for (temp.i = 2; temp.i < temp.str.length(); temp.i ++) {
    for (temp.e = 0; temp.e < temp.str.length(); temp.e ++) {
      if (temp.e + temp.i > temp.str.length() - 1) {
        continue;
      }
      temp.sub = temp.str.substring(temp.e, temp.i);
      temp.p = temp.str.positions(temp.sub);
      if (temp.p.size() > 1) {
        if (temp.outc.index(temp.sub) < 0) {
          temp.outc.add(temp.sub);
          temp.out.add(temp.sub @ ":" @ temp.p.size());
        }
      }
    }
  }
  echo("Time: " @ timevar2 - temp.time);
  return temp.out;
} 


[Tolnaftate2004]

Originally Posted by Inverness

What the hell are you talking about?

This is big O notation, it is how we measure the efficiency of algorithms, without being hardware-specific. The O stands for order, which can take 2 meanings:

1. In mathematics, O(f) is for all terms order f and above. f is usually a function where the parameter is much less than 1 (error terms).
2. In computer science O(f) is the major factor in determining algorithm efficiency. f is a function of n, which is a whole number.

For example, the quicksort algorithm is O(n log n) [for every item to sort, it takes log base 2 of n loops to find its place].

[napo_p2p]

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