[SPL] tworzenie iteratora, w miejsce 2 pętli jedna w drugiej Opcje

[DeyV]

Odkąd poznałem możliwości SPL jestem pod dużym wrażeniem możliwości podsuwanych tam pomysłow, i coraz częściej staram się z nich korzystać.

Zacząłem stosować iteratory, i rzeczywiście - okazały się w wielu przypadkach bardzo przydatne, zmiejszając ilość (chyba ) pamięci, którą musi zaalokować pamięć, i przyspieszając jego działanie w wielu przypadkach (mniejsza ilość pętli)

Zastanawiam się jednak, czy istnieje jakiś prosty sposób na tworzenie iteratoró w nieco bardziej złożonych przypadkach.

Zacznijmy od jakiegoś prostego przypadku. Np. mamy 2 tablice, a potrzebna jest nam jedna, w której znajdują się wszystkie kombinacje elementów z tych 2 powyższych (czyli każdy z każdym).
Normalnie rozwiązanie bardzo proste.
Dwa foreach, jeden drugim, i generowanie tablicy wynikowej.

[PHP] pobierz, plaintext 
<?php
 
$aOwoce = array( 'jabłko', 'banan', 'wiśnia' );
$aKolory = array( 'niebieski', 'czerwony' );
$aWynik = array();
foreach( $aOwoce as $sOwoc ){
   foreach( $aKolory as $sKolor ){
		$aWynik[] =  $sKolor  . ' '.  $sOwoc ;
	}
}
?>
[PHP] pobierz, plaintext 

Jednak w ten sposób przechowujemy całą tą tablicę zupełnie niepotrzebnie, bo tak naprawdę do dalszego działania programu będziemy potrzebowali 1, kolejny jej element w danym momencie....
Oczywiście - nawet na chłopski rozum można napisać odpowiedni iterator, wymaga jednak całkiem złożonego algorytmu sprawdzania kolejnych elementów i ich zwracania.
A problem wydaje mi się na tyle standardowy, że powinny być jakieś "standardowe" rozwiązania - chyba że mam po prostu zaćmę i czegoś oczywistego nie udało mi sie dotychczas zauważyć...

// ps. i nie próbujcie mi odpowiedzieć, że są jakieś standardowe funkcje do łączenia tablic, bo normalnie ... zamorduję

[bela]

Trochę to zagmatwane, ale czy chcesz połączyć 2 tabele ? A czy przypadkiem nie można wykorzystać array_merge" title="Zobacz w manualu PHP" target="_manual ?

[Vengeance]

hmm... odpowiednie interfejsy deklarujesz i juz na obiekcie bedacym iteratorem mozes stosowac funkcje array_*

[hawk]

Standardowego rozwiązania nie będzie raczej, bo ktoś musiałby po prostu napisać odpowiedni iterator i tyle. A samo napisanie takiego iteratora jest proste. Przyjmuje w konstruktorze 2 argumenty (tablice), dla każdej robi count() i zapamiętuje, ma 2 liczniki pozycji i inkrementuje tak żeby przelecieć wszystkie kombinacje. Jaki tam złożony algorytm...

A wszystkie pomysły z array_* są bez sensu bo właśnie nie chcemy łączyć tych tablic i po to używamy iteratora, prawda?

[DeyV]

oczywiście, hawk.
Mimo to miałem nadzieję, że żucicsz jakimś ciekawym linkiem o tej tematyce.
Ale fakt - faktem. Po napisaniu nie wygląda to już nawet tak groźnie, i choć ciągle się zastanawiam, czy napisane jest optymalnie (jakoś dużo tych warunków mi się zrobiło :/ ) to jednak działa w pełni zgodnie z założeniami.

Dla wątpiących:

[PHP] pobierz, plaintext 
<?php
 
/**
 * @date 9.02.2005
 */
class GenerateNames implements Iterator
{
 
	private $aFirst, $aSecond = array();
	private $iFirstCount, $iSecondCout = 0;
	private $iFirstIt, $iSecondIt = 0;
 
 
	function __construct( $aFirst, $aSecond ){
		$this->aFirst = $aFirst;
		$this->aSecond = $aSecond;
 
		$this->iFirstCount = count( $this->aFirst );
		$this->iSecondCout = count( $this->aSecond );
 
	}
 
	/** Rewind the Iterator to the first element.
	 */
	function rewind() {
		$this->iFirstIt = $this->iSecondIt = 0;
	}
 
	/** Return the current element.
	 */
	function current() {
		return $this->aFirst[ $this->iFirstIt ] .' '. $this->aSecond[ $this->iSecondIt ];
	}
 
	/** Return the key of the current element.
	 */
	function key() {
		return  $this->iFirstIt .'-'. $this->iSecondIt;
	}
 
	/** Move forward to next element.
	 */
	function next(){
		if( $this->iSecondIt < $this->iSecondCout -1 ) {
			++$this->iSecondIt;
		}
		else{
			$this->iSecondIt = 0;
			++$this->iFirstIt;	
		}
	}
 
	/**  sprawdza czy nie przekroczyliśmy jeszcze zakresu
	 * @return bool
	 */
	function valid() {
		return $this->iFirstCount > $this->iFirstIt  &&  $this->iSecondCout > $this->iSecondIt ;
	}
}
 
 
$Element = new GenerateNames( 
			array( 'jabłko', 'wiśnia', 'banan' ),
			array( 'czerwone', 'bordowa', 'żółty' ) );
 
foreach( $Element as $iKey => $sWord ) {
	echo $iKey . ' => ' . $sWord . '<br />';			
}
 
 
?>
[PHP] pobierz, plaintext 

mile widziane oczywiście propozycje poprawy tego kodu...

//ps. a jeśli ktoś się zastanawia, czy jest sens tworzenia taiej ilości kodu, zamiast zaprezentowanych powyżej dwóch pętli - niech wyobrazi sobie, że ten iterator nie pracuje na 2 tylko na np. 4 tablicach. I policzy - jakiej wielkości byłaby tablica wynikowa....

[hawk]

Kod jest dobry. Nic dodać nic ująć.

Taki przykład z dwiema tablicami faktycznie może wydawać się przerośnięty, ale tak już jest z przykładami. Wystarczy wymyśleć jakieś bardziej zakręcone kryteria łączenia tablic i już proporcje się wyrównują.

Dla lepszej ilustracji, podam iterator, który kiedyś wymyśliłem. Co prawda w Javie, ale to bez znaczenia. Niech ktoś to spróbuje zrobić kodem proceduralnym .

1) Jest sobie drzewko w pamięci. Robimy prosty (?) iterator depth-first. No, taki prosty to on nie jest, ale wystarczy poszukać kodu - standard.

2) Robimy interfejs Chooser...

Kod

public interface Chooser {
  public boolean choose(TreeElement te);
}

...który po prostu dostaje element i mówi czy mu się podoba, czy nie.

3) Robimy ChoosingIterator...

Kod

class ChoosingIterator implements Iterator {
  public ChoosingIterator(Iterator i, Chooser c) {
    //...
  }
  //...
}

... który filtruje output zwykłego iteratora drzewkowego wykorzystując Chooser.

4) Skutek? Zrobiliśmy z tego w programie operującym na wielkich drzewach rozszerzalny system wyszukiwania. Piszesz jedną klasę implementującą Chooser, system wpina ci to w menu i już masz najgłupsze nawet kryteria wyszukiwania z Find / Find next / przewijaniem na początek dokumentu itd.

Wyszło off-topic, ale to tak w zastępstwie linka, którego dopominał się DeyV. . Morał opowieści: iteratory rulez.

[DeyV]

dla zainteresowanych dodam, żę bardzo podobny to tego, co podał Hawk, przykład obsługi drzew w oparciu o iterator jest proponowany również przez SPL.

Zainteresowanych odsłym do kodu Iteratora struktury katalogów, w którym bardzo łatwo można zobaczyć sposó pisania filtrów, ograniczających wyświetlanie informacji. Np. usuwanie . i .. lub wszystkich folderów zaczynających sie na aa

Jedyne co w tym wszystkim odrobinę boli, to to, że na potrzeby drzewka tworzy się wiele zagłębiających się obiektów, czyli odpowiednik bardzo nielubianego przez wielu w pisaniu strukturalnym, kod rekurencyjny.

[hawk]

Zawsze możesz sobie napisać iterator drzewek/katalogów, który bazuje na iteracji, nie na rekurencji.

A skoro wszystko i tak bazuje na interfejsach, możesz sobie podpiąć swój iterator w miejsce RecursiveDirectoryIterator, i reszta kodu tego nie zauważy. Chociaż DirectoryFilterDots niestety wymaga RecursiveIterator. Tutaj IMHO Boerger źle to zrobił, bo DirectoryIterator nie implementuje RecursiveIterator. Ale pewnie miał swoje powody.

[antao]

Hello World...

przeprowadzając testy (w pętli : x10 000) wyszło że:

-> system z iteracją: śr. czas wykonania jednej pętli

[PHP] pobierz, plaintext 
<?php
foreach( $Element as $iKey => $sWord ) {
	echo $iKey . ' => ' . $sWord . '<br />';			
}
?>
[PHP] pobierz, plaintext 

wynosi 0,0005207s (pamięć >32MB)

-> pętla

[PHP] pobierz, plaintext 
<?php
foreach( $aOwoce as $sWord => $sOwoc ){
   foreach( $aKolory as $iKey => $sKolor ){
	   echo $sWord .'=>'. $iKey .' '. $sKolor  .' '.  $sOwoc .'<br />';
	}
}
?>
[PHP] pobierz, plaintext 

śr. czas: 0,0002610s (pamięć >31MB)

tak więc różnica w szybkości wynosi 199,5%...

"wąskie gardło" ?

[PHP] pobierz, plaintext 
<?php
$this->aFirst = $aFirst;
		$this->aSecond = $aSecond;
?>
[PHP] pobierz, plaintext 

z 2 robią się 4...

//ps. a jeśli ktoś się zastanawia, czy jest sens tworzenia taiej ilości kodu, zamiast zaprezentowanych powyżej dwóch pętli - niech wyobrazi sobie, że ten iterator nie pracuje na 2 tylko na np. 4 tablicach. I policzy - jakiej wielkości byłaby tablica wynikowa....

z tego co widzę, klasa GenerateNames jest przystosowana do obsługi tylko 2 tablic, czyli żeby obsłużyć np. 4 tablice trzeba klasę znacznie rozbudować ?

[ennics]

// ps. i nie próbujcie mi odpowiedzieć, że są jakieś standardowe funkcje do łączenia tablic, bo normalnie ... zamorduję 

array_combine
a iteracja to ciekawy temat, całkiem niedawno skróciłem tym sposobem
dużą część kodu, w połączeniu z wbudowanymi funkcjami operującymi na tablicach można dużo zdziałać.

[dr_bonzo]

@ennics: Ale array_combine nie utworzy tego co chcial osiagnac.
@DeyV: moj pierwszy Iterator dziala podobnie jak twoj 'GenerateNames', z tym ze u ciebie beda problemu z tablicami indeksowanymi inaczej niz intami poczawszy od zera (dlatego ja wykonuje przeindeksowanie).

Moje iteratory:

Drugi 'Kombinacje_Tablic_2' uzywa funkcji next(), current(), reset() itd, sa one wolniejsze i uniemozliwiaja uzywanie elementow pustych ( 0, "" ).

Pierwszy 'Kombinacje_Tablic' przeindeksowuje tablice tak zeby byly indeksowane integerami (szybszy dostep do danych, kontrola indeksow za pomoca liczb -- zapamietuje ilosc elementow i indeks aktualnego , brak bugu z pustymi elelmentami)

Dla 1000 powtorzen (samo przelecenie tablic, bez printowania indeksow i elementow):
- 2xzagniezdzony foreach: 0.25s
- pierwszy iterator: 0.89s
- drugi iterator: 1.09s

Wnioski: foreach najszybsze (zaraz sprawdze dla wiekszej ilosci tablic), przeindeksowanie tablic przyspiesza iteracje.

[PHP] pobierz, plaintext 
<?php
class Kombinacje_Tablic implements Iterator
{
	private $aArray_A = array();
	private $aArray_B = array();
 
	private $iCurrent_A = 0;
	private $iCurrent_B = 0;
 
	private $iCount_A = 0;
	private $iCount_B = 0;
 
	public function __construct( $aArray_A, $aArray_B )
	{
		// arrays will be indexed with integers
		foreach ( $aArray_A as $key => $value )
		{
			$this->aArray_A[] = $value;
		}
 
		foreach ( $aArray_B as $key => $value )
		{
			$this->aArray_B[] = $value;
		}
 
		$this->iCount_A = count( $this->aArray_A );
		$this->iCount_B = count( $this->aArray_B );
 
		$this->iCurrent_A = 0;
		$this->iCurrent_B = 0;
	}
 
	public function rewind()
	{
		$this->iCurrent_A = 0;
		$this->iCurrent_B = 0;
	}
 
	public function key()
	{
		return ( $this->iCurrent_A . &#092;"x\" . $this->iCurrent_B );
	}
 
	public function current()
	{
		return ( $this->aArray_A[ $this->iCurrent_A ] . &#092;"::\" . $this->aArray_B[ $this->iCurrent_B ] );
	}
 
	public function next()
	{
		if ( $this->iCurrent_B < $this->iCount_B - 1 )
		{
			$this->iCurrent_B++;
		}
		else 
		{
			$this->iCurrent_A++;
			$this->iCurrent_B = 0;
		}
	}
 
	public function valid()
	{
		return ( ( $this->iCurrent_A < $this->iCount_A ) && ( $this->iCurrent_B < $this->iCount_B ) );
	}
}
 
 
/*****************************************************************/
		/*
		current(), next(), itd.
 
		If the array contains empty elements (0 or \"\", the empty string) then this function 
		will return FALSE for these elements as well. This makes it impossible to d
termine 
		if you are really at the end of the list in such an array using current(). To 
		properly traverse an array that may contain empty elements, use the each() function.
		*/
class Kombinacje_Tablic_2 implements Iterator
{
	private $aArray_A = array();
	private $aArray_B = array();
 
	public function __construct( $aArray_A, $aArray_B )
	{
		$this->aArray_A = $aArray_A;
		$this->aArray_B = $aArray_B;
 
		reset( $this->aArray_A );
		reset( $this->aArray_B );
	}
 
	public function rewind()
	{
		reset( $this->aArray_A );
		reset( $this->aArray_B );
	}
 
	public function key()
	{
		return ( key( $this->aArray_A ) . &#092;"x\" . key( $this->aArray_B ) );
	}
 
	public function current()
	{
		return ( current( $this->aArray_A ) . &#092;"::\" . current( $this->aArray_B ) );
	}
 
	public function next()
	{
		if ( next( $this->aArray_B ) === FALSE )
		{
			next( $this->aArray_A );
			reset( $this->aArray_B );
		}
	}
 
	public function valid()
	{
		return ( ( current( $this->aArray_A ) !== FALSE ) && ( current( $this->aArray_B ) !== FALSE ) );
	}
}
 
/*****************************************************************/
 
$aKolory = array( 'niebieski', 'czerwony' );
$aOwoce = array( 'jabłko', 'baban', 'wiśnia' );
 
$dane = new Kombinacje_Tablic( $aKolory, $aOwoce );
//$dane = new Kombinacje_Tablic_2( $aKolory, $aOwoce );
foreach ( $dane as $key => $value )
{
	print( &#092;"[$key] ==&gt; $value<br />\" );
}
?>
[PHP] pobierz, plaintext 

[DeyV]

antao - ciekawy test, jednak nie do końca odpowiedni.
Zobacz, że w moim przykładzie (z 2 pętlami) tworzona była 3 tablica - do wykorzystania później.
Dopiero tą tablicę można by potraktować foreach, i dopiero to byłby dokładny odpowiednik kodu z iteratorem.
A wtedy zużycie pamięci się zwiększy conajmnie 4 krotnie. (jak sądzę )

"wąskie gardło" ?
...
z 2 robią się 4... smile.gif

Jednak nie. php ma bardzo ciekawą technologię kopiowania tablic on edit.
Oznacza to, że tak długo, jak któraś z tych tablic nie zostanie wyedytowana, tak dlugo w pamięci przechowywana jest tylko 1 jej instancja, a my odwołujemy ię niejako do jej referencji.
Dopiero podczas wprowadzania zmian w którejś z nich - tworzą się osobne kopie.
Jeśli masz php postawione na linuksie i xdebug - polecam przeprowadzenie dokładnego testu - ja widziałem kiedyś taki, i byłem naprawdę zaskoczony tym, jak mało pamięci zostało zużyte na skopiowanie tablicy.

z tego co widzę, klasa GenerateNames jest przystosowana do obsługi tylko 2 tablic, czyli żeby obsłużyć np. 4 tablice trzeba klasę znacznie rozbudować ?

Tak naprawdę - wystarczły dodać liczniki dla każdej z tych tablic, zmierzyć ich wielkość, i odpowiednio rozbudować warunek.

hawk - temat - rzeka - cieszę się jednak, że udało nam sie tu zainteresować nim kilka kolejnych osób.

[dr_bonzo]

At last!

[PHP] pobierz, plaintext 
<pre>
<?php
/**
 *@author dr_bonzo
 */
 
class Kombinacje_Tablic implements Iterator
{
	// wczytane tablice
	private $aArrays;
 
	private $iNumber_of_arrays = 0;
 
	// ilosci elementow w kazdej z tablic
	private $aCount_array = array();
 
	// aktualne indeksy tablic
	private $aCurrent_indexes = array();
 
	public function __construct( $aArrays )
	{
		// przeindeksowanie
		$i = 0;
 
		foreach ( $aArrays as $aArray )
		{
			foreach ( $aArray as $key => $value )
			{
				$this->aArrays[ $i ][] = $value;
			}
 
			// zlicz wielkosc tablic
			$this->aCount_array[ $i ] = count( $aArray );
  //		  print( \"[$i]:: {$this->aCount_array[ $i ]}<br />\" );
 
			// i wyzeruj counterki
			$this->aCurrent_indexes[ $i ] = 0;
			$i++;
		}
 
		$this->iNumber_of_arrays = $i;
	}
 
	public function rewind()
	{
		for ( $i = 0; $i < $this->iNumber_of_arrays; $i++ )
		{
			$this->aCurrent_indexes[ $i ] = 0;
		}
	}
 
	public function key()
	{
		$sKey = '';
 
		for ( $i = 0; $i < $this->iNumber_of_arrays; $i++ )
		{
			$sKey .= 'x' . $this->aCurrent_indexes[ $i ];
		}
 
		return substr( $sKey, 1 );
	}
 
	public function current()
	{
		$sCurrent = '';
 
		for ( $i = 0; $i < $this->iNumber_of_arrays; $i++ )
		{
			$sCurrent .= ':' . $this->aArrays[ $i ][ $this->aCurrent_indexes[ $i ] ];
		}
 
		return substr( $sCurrent, 1 );
	}
 
	public function next()
	{
//		print( \"next()<br />\" );
		$i = $this->iNumber_of_arrays - 1;
 
		if ( $this->aCurrent_indexes[ $i ] < $this->aCount_array[ $i ] )
		{
			$this->aCurrent_indexes[ $i ]++;
		}
 
		while ( ( $this->aCurrent_indexes[ $i ] >= $this->aCount_array[ $i ] ) && ( $i > 0 ) )
		{
			$this->aCurrent_indexes[ $i ] = 0;
			$this->aCurrent_indexes[ $i - 1 ]++;
			$i--;
		}
	}
 
	public function valid()
	{
//		print( \"validating<br />\" );
 
		if ( $this->iNumber_of_arrays === 0 )
		{
			return FALSE;
		}
 
		if ( $this->aCurrent_indexes[ 0 ] === $this->aCount_array[ 0 ] )
		{
			return FALSE;
		}
		else 
		{
			return TRUE;
		}
	}
}
 
/*****************************************************************/
 
$aKolory = array( 'niebieski', 'czerwony' );
$aOwoce = array( 'jabłko', 'banan', 'wiśnia' );
$aSome_array_1 = array( 'a1fas', 'a25se5', 'a3da5' );
$aSome_array_2 = array( 'b1adf', 'b2aeuj', 'b333' );
$aSome_array_3 = array( 'c1fas', 'c2cse5', 'c33' );
 
/*
$dane = new Kombinacje_Tablic( array( $aKolory, $aOwoce, $aSome_array_1, $aSome_array_2, $aSome_array_3 ) );
$dane = new Kombinacje_Tablic( array( $aKolory, $aOwoce, $aSome_array_1, $aSome_array_2 ) );
$dane = new Kombinacje_Tablic( array( $aKolory, $aOwoce, $aSome_array_1 ) );
$dane = new Kombinacje_Tablic( array( $aKolory, $aOwoce ) );
$dane = new Kombinacje_Tablic( array( $aKolory ) );
*/
$dane = new Kombinacje_Tablic( array( $aKolory, $aOwoce, $aSome_array_1, $aSome_array_2, $aSome_array_3 ) );
 
foreach ( $dane as $key => $value )
{
	print( &#092;"[$key] ==&gt; $value<br />\" );
}
?>
</pre>
[PHP] pobierz, plaintext 

Dla tych 5ciu tablic: 0.08 s (@ PII 350), ktos chce porownac foreach'e ?

Oczywiscie dziala prawidlowo dla 0, 1ej i dwoch tablic.