|
|
Posted by Henk Verhoeven on 10/23/05 22:48
Thomas,
If the reference count does not help you, I think you have two options
here:
1) under each non-unique key, put another array and put all copies in
that array. To check if a node is already visited, get its key, then
search sequentially through the array that is under the key to see if
one of the nodes in there is identical to the currently visited one.
However, you need a way to distinguish copies from references. AFAIK you
can only do this in php4 by changing the value of one variable and see
if the other variable changes too. But then you have to put (or change)
the original value back, and all this without copying (i have not
figured out how to do that, don't know if it can be done at all). In php
5 you can use === with objects, but not with arrays. Of course if you
have many copies of some of the nodes, the sequential searching can
become very resource-consuming (exponentially slower with the number of
copies of the same node).
2) *make* the copies different. As described on the manual page, values
that are formally copies are actually kept as references as long as they
are unchanged. Assuming only arrays and objects can serve as nodes in
the graph, if you can change each node and then change it back to its
original state, php will create a real copy for each, and probably not
undo that if you change it back to its original state. Real copies
probably have different first parts of the debug_zval_dump() values. So
after you have modified each node, you can store its unique key for
lookup to detect recursion. Of course this will be expensive (slow) if
there are many copies to be "realized", but the slowdonwn will be liniar
with the number of copies to realize, so with large searches with many
copies of the same node this will be a lot faster then option 1)
Maybe you can even combine these strategies, but that may complicate
things more then you like.
Hope this helps.
Greetings,
Henk Verhoeven,
www.phpPeanuts.org.
Thomas Mlynarczyk wrote:
> Also sprach Henk Verhoeven:
>
>
>>Maybe debug_zval_dump() can be of use for getting an unique key? See
>>http://www.php.net/manual/en/function.debug-zval-dump.php
>>(the part about refcount is confusing, but maybe you do only need the
>>first (string(11)) part of the output)
>
>
> An interesting function - especially because of the refcount. I do not quite
> see yet how I could use it for getting a unique key (the point being to get
> different values for different things even if they are identical copies),
> but I will have a closer look at this function. Thanks for the suggestion.
>
> Greetings,
> Thomas
>
>
Navigation:
[Reply to this message]
|