🚀 go-pugleaf

On Fri, 31 Jul 2009 15:28:14 +0200, Michał  
<jeslichceszwiedzieczapyta@gazeta.pl> wrote:

> Chciałbym przekonwertować drzewo w postaci:
>
> ID_LIŚCIA-RODZIC,ID_LIŚCIA-RODZIC,ID_LIŚCIA-RODZIC
>
> na drzewo zmiennych tablicowych czyli np takie coś:
>
> 39892->0,37783->0,17373->0,4327->17373
>
> na:
>
> 0
> ->	39892
> ->	17373
> 	->	4327

> Jak to najszybciej zrobić bo obecnie mam algorytm który polega na  
> wpisywaniu do tablicy kolejnych elementów (tablica jest przekazywana  
> przez parametr) i potem jeśli mamy nowy szukamy dla niego miejsca i tak  
> w kółko. Tyle że wpisane miejsca przechowuje w tablicy referencji czyli  
> wszystko jest buforowane... i dla testowych danych (3800 elementów) trwa  
> to niestety całe 25 sekund.
> Użyta jest tablica asocjacyjna. Czy ona może aż tak bardzo spowalniać?

Nie. Asocjacje są szybkie w PHP.

> Czas który chciałbym osiągnąć to góra 2 sekundy. Może to nie możliwe?

Nie podałeś jaką konketnie chcesz strukturę na wyjściu, ale zakładając  
typowe
potrzeby:

--8<-----------------------------------------------------------------------

function makeTree( $input, $myRoot=0 )
{
   $lut=array();
   foreach( $input as $child => $parent )
   {
     $lut[ $parent ][ $child ] = &$lut[ $child ];
   }
   return $lut[ $myRoot ];
}

-->8-----------------------------------------------------------------------

dla wejścia:

Array
(
     [50] => 100
     [25] => 50
     [200] => 0
     [300] => 0
     [100] => 200
)

daje wyjście:

Array
(
     [200] => Array
         (
             [100] => Array
                 (
                     [50] => Array
                         (
                             [25] =>
                         )

                 )

         )

     [300] =>
)

O(n), obliczeniowo i pamięciowo. Przerobienie stringu na tablicę wejściową
zostawiam jako trening dla czytelnika ;-)

HTH,
-- 
Mariusz 'koder' Chwalba