Forum PHP.pl

Witajcie mój problem brzmi następująco mam do napisania klase która w sposób rekurencyjny ma realizować potęgowanie i taką napisałem,

kolejną rzeczą jest to że obiekt tej klasy ma buforować wyniki i wykorzystać bufor zamiast wykonywania metody

co przez to rozumiecie?

Ten post edytował lord2105 17.08.2010, 17:07:35

Przekazuj w parametrze funkcji tablicę zawierająca wyniki poprzednich mnożeń - każde wywołanie dodaje nowy rezultat do tablicy - pod koniec powinieneś otrzymać tablicę z wynikami potęgi począwszy od 1 - zapamiętujesz ją we właściwości metody jako podtablicę z kluczem będącym twoją liczbą.

Przy kolejnych wywołaniach sprawdzasz czy dla danej liczby nie istnieje już tablica, jeśli tak to sprawdzasz czy zawiera wartość którą chcesz obliczyć - zwracasz ją. W przeciwnym wypadku bierzesz ostatnią wartość tablicy - powiedzmy w tablicy masz potęgę 3 liczby 2, ty szukasz potęgi 6 liczby 2 - zamiast stosować rekurencję od potęgi 1, stosujesz od 3 bo masz obliczoną jej wartość.

Pisane na szybko więc nie daję głowy że jest ok (przy moim pokrętnym rozumieniu matematyki zdziwiłbym się gdyby było).

Po części chwyciłem o co Wam chodzi lecz bufor powinien występować bezpośrednio w klasie czy też przy wywoływaniu obiektu, pokaże co do tej pory napisałem w pliku class.calculate.php:

[PHP] pobierz, plaintext 
<?php
 
//Class calculating power in a recursive
	class calculate_power
	{	
		private $base;
		private $index;
 
		public function getResult($base, $index)
		{
 
		//declaration variables
			$this->base = $base;
			$this->index = $index;
 
				if ($this->index == 0) {
					$result = 1;
				}
				else {
					$new_index = new calculate_power;
 
					$result = $this->base * $new_index->getResult($this->base, $this->index-1);
				}
 
				return $result;
		}
	}
?>
[PHP] pobierz, plaintext 

czy da sie zastosować bufor w tej klasie? Czy też jest on zbędny?

i show.php

[PHP] pobierz, plaintext 
<?php
require ('class.calculate.php');
 
	$x = 3;
	$y = 3;
 
	$calculator = new calculate_power;
 
	echo $calculator->getResult($x,$y);
 
?>
[PHP] pobierz, plaintext 

Ten post edytował lord2105 17.08.2010, 17:43:57

Lepiej bezpośrednio w klasie, ponieważ wtedy, przy kolejnych obliczeniach, klasa już będzie miała wykonaną część obliczeń.

@lord105 - nie wywołuj rekurencyjnie w metodzie tworzenia nowego obiektu. To kompletnie bez sensu. Wywołuj samą metodę tego samego obiektu np.

[PHP] pobierz, plaintext 
public function getResult($x,$y) {
  $this->getResult($x,$y-1); //czy jak tam to zaimplementujesz
}
[PHP] pobierz, plaintext 

@flashdev - na upartego to można cache zadeklarować jako właściwość statyczną - wtedy wszystkie obiekty będą operowały na jednym. Unikamy dzięki temu zbędnej redundancji.

Flashdev: Twoja metoda jest dobra dla dużych potęg, jednak dla niższych niekoniecznie. Zwróć uwagę na konieczność sprawdzania czy dana potęga już aby nie wystąpiła w trakcie obliczeń. Jak chcesz rozwiązać ten akurat problem? Deklarowanie tablicy wyników potęg typu przykładowo dla 5 array( 1 => 5, 2 => 25, 4 => 625, 8 => 390625) a potem sprawdzając czy mnożenie potęgi aktualnej * 2 jest większe od wymaganej? Jeśli tak wykonaj operację, dodaj do tablicy potęg i rób dalej rekurencję. Jeśli nie leć dodaj bezpośrednio niższą potęgę i sprawdź czy większa od wymaganej. Jeśli nie dodaj potęgę a wynik pomnóż przez odpowiadającą mu wartość. I tak aż do osiągnięcia właściwej potęgi. Trochę zagmatwanie napisałem, ale chyba rozumiesz o co chodzi.

Jednym zdaniem: "Dla względnie małych potęg naddatek operacji sprawdzających odbije się negatywnie na wydajności i ta rekurencja puszczona wprost na koprocesor wykona się znacznie szybciej, bo ma on dedykowane rejestry do tego typu zadań."

Specjalnie nie podałem gotowego algorytmu, żeby zmusić czytelnika do myślenia. Ale widzę, że nie znając jeszcze tego prostego algorytmu już udało Ci się wykonać jego analizę wydajnościową

Poniżej przedstawiam mój (no bez przesady, jaki tam mój... ja nie wymyślam na poczekaniu takich mądrych rzeczy) algorytm.



To cały algorytm - jedna pętla. Nie jest to co prawda rekursja, ale jak wiadomo rekursję można zrealizować iteracyjnie i vice versa.

Tak przy okazji to dokładnie w ten sam sposób działa algorytm szybkiego mnożenia, tylko że tam zamiast *=, będzie +=, oraz niezmiennik mnożenia (1), będzie zastąpiony niezmiennikiem dodawania (0).

Ten post edytował flashdev 18.08.2010, 10:25:11

Swój algorytm oparłem o logiczne przemyślenie kroków, bez optymalizacji w stylu "przechodzimy na binarkę", czyli cały czas trzymając się systemu dziesiętnego Po przeskoku zyskamy, ale nadal dla odpowiednio niskich potęg różnica będzie albo niezauważalna, albo bardzo mała by konieczne było wprowadzenie szybkiego potęgowania. Jeśli zaś już mielibyśmy to optymalizować to, przynajmniej w C, zmiana z i++ na ++i też przyniesie wzrost szybkości. A że kod mi wygląda podobnie do C to użycie czegoś w stylu register dla i ( o ile język ten to umożliwia) jeszcze bardziej by zwiększyło wydajność.

Ogólnie jednak rzecz ujmując na pomysł z ifem na bitowej reprezentacji potęgi nie wpadłem, a faktycznie przyspiesza całość bo rozwiązuje problem "potem sprawdzając czy mnożenie potęgi aktualnej * 2 jest większe od wymaganej" w sposób nie wymagający dużej ilości sprawdzeń. Raptem jedno by sprawdzić czy binarna wersja ma ustawione 1 dla tejże pozycji Pomysł prosty i wydajny jednocześnie. Człowiek uczy się jednak całe życie. Dzięki flashdev za wskazówkę bo na bank się kiedyś mi przyda, zważywszy, że co jakiś czas bawię się binarnie z liczbami.

No skoro ta różnica będzie niezauważalna, albo nawet bardzo mała, to po co komplikować sobie życie i wprowadzać jakieś if`y?

A co do tego algorytmu, to gwarantuję Ci, że gdziekolwiek nie spojrzysz na jakieś sprzętowe implementacje potęgowania, lub gotowe wbudowane funkcje w języki programowania, to właśnie będzie to tak zrobione.

A i należy jeszcze pamiętać, że tutaj wspomniany przez Ciebie koprocesor będzie miał wątpliwe zastosowanie, bo już przy skromnym wykładniku potęgi > 32 i postawie potęgi równej 2 wychodzimy poza zakres int, więc jest konieczne użycie własnego typu danych.

Dziękuję bardzo za wyczerpujące odpowiedzi ale czy może ktoś powiedzieć w którym Dokłanie miejscu bufor powinien zbierać informacje a w którym sprawdzać czy dany wynik już wystąpił?

Ponieważ nie wytłumaczyłem (uznałem to za oczywiste) co robi moja funkcja bin, a autor tematu dopytuje się o nią na PW zamieszczam poniżej co miałem na myśli.

[PHP] pobierz, plaintext 
// funkcja zwraca kolejny ($num_bit) bit liczby $n
function bin($num_bit, $n){
 return (( 1 << $num_bit ) & $n ) ? 1 : 0;
}
[PHP] pobierz, plaintext