5

In context of the realization of a project I need to find the k-longest sequences in PHP. There are many ways to implement this - but which algorithm is the fastest for PHP?

Which algorithm would you implement? (overview)

Which one is most-efficient and dynamic (numbers, strings, etc)? (fast?, time for n-elems?)

How would you implement it? (example)

Thank you!

Post Scriptum

I'm about to implement the ONISI k-nearest neightbour algorithm. The longest sequences are visualised in this schematic. The interaction history since t and the immediate history. This shematic gives a brief overview on the ONISI algorithm.enter image description here

The total/immediate-history-elements are strings representing a $state --> $action pattern. This means, considering the first 3 elements of schematic (1), data would be displayed, for instance, like: $immediate_history = array( array( "s2" => "a2" ), array( "s3" => "a3" ), array( "s1" => "a1" ) [..] );

Still any questions about the problematic?

Cheers!

Community
  • 1
  • 1
19h
  • 819
  • 9
  • 20
  • 2
    What have you tried so far? Also, you can't represent the whole of schematic (1) with a PHP array in the way you've presented it, because PHP array keys have to be unique. Doing it as a sequence of sub-arrays would be one alternative, eg: `array( array("s2" => "a2"), array("s3" => "a3"), array("s1" => "a1"),...)` – John Carter Apr 29 '11 at 11:07
  • The representation is not as important as the algorithm for the analysis of the array for finding the k-longest sequence, of course, it might be represented like that - but nearly every representation can be implemented into a standardized algorithm. I changed my example after your alternative. I already have been experimenting wit Tries, but it seemed inadequate for the actual case. – 19h Apr 29 '11 at 11:10
  • 1
    Try this one: http://codegolf.stackexchange.com/ – OZ_ Apr 29 '11 at 23:02
  • 1
    My (personal) advice is: if you are really worried about performance, don't implement it in PHP, use an external function in a compiled language (C/C++ for instance) – Ivan May 23 '11 at 10:59

1 Answers1

1

Which algorithm would you implement? (overview)

KNN is a special case of a variable-bandwidth, kernel density "balloon" estimator with a uniform kernel

Which one is most-efficient and dynamic (numbers, strings, etc)? (fast?, time for n-elems?)

I depends on your data structure. An array is defnetly slower. But use of better and advanced structure will speed things up.

How would you implement it? (example)

I highly doubt anyone will give you this here as the program is not a small one. You have to do this on your own.

Community
  • 1
  • 1
footy
  • 5,803
  • 13
  • 48
  • 96