1

I have to create an really huge tree to solve the game of peg solitaire.
It has to be in PHP.
Although I have experience in PHP, it's mostly doing web dev, so I have no experience with memory management and large data structures, which I would normally handle in C++, but this is a test for a job.
I will solve it with some kind of backtracking with depth first search, so the tree doesn't get so huge, but at any point in time, I have to have a list of all the open nodes, which I plan to achieve with a simple array of references.
Is this efficient? should I do it with a SPL linked list or something else rather?
I already tested that an array can grow only limited by the RAM.

Petruza
  • 11,744
  • 25
  • 84
  • 136

2 Answers2

1

It seems to me that php handles array and object very efficiently, see here Does PHP take RAM when defining variable from variable and taking instance of object to another variable?. So maybe a binary tree would be good? You can also make your own extension if you are good in C++.

Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72
1

HAKMEM item 75 or Ins & Outs of Peg Solitaire (ISBN: 0-19-286145-X).

And don't use arrays.

Margus
  • 19,694
  • 14
  • 55
  • 103
  • Thanks for the link. Also, can you justify your advice against arrays? and what alternative should I use? thanks. – Petruza Jul 31 '11 at 12:56
  • @Petruza That would be a really bad start from a job applicant. In short http://codereview.stackexchange.com/questions/3714/why-didnt-they-like-this-code – Margus Jul 31 '11 at 14:34
  • Ok, that link shows how poor performance on a test didn't get the job. I understand that. I mean, why do you advice against using arrays in PHP and what alternative should I use instead? – Petruza Jul 31 '11 at 21:56