Funkcja wybierająca największą wartość Opcje

[impimp94]

Witam!
Czy jest jakaś funckja w php, która umożliwi mi wybranie największej liczby np.: spośrud 5 liczb?
czy może musze robić to ręcznie i bardzo długo np.:

Kod

$a = 12;
$b = 3456;
$c = 6;
$d = 9887;
$e = 0;
if ($a > $b) {
// kod
}
// i tak dalej

Z góry dzięki za pomoc

[Spawnm]

możesz dac wszystkie do tablicy i posortować dzięki czemu $tablica[0] = max
albo max" title="Zobacz w manualu PHP" target="_manual

z manuala:

[PHP] pobierz, plaintext 
<?php
$array = array(1, 2, 5, 7, 4);
echo max($array); // 7
?>
[PHP] pobierz, plaintext 

Ten post edytował Spawnm 6.04.2009, 16:18:47

[dr_bonzo]

Taaa, sortowanie, przeciez to bez sensu skoro jest wlasnie max()

[Spawnm]

no to przecież podałem

a to z sortowaniem uznajmy za ciekawostkę

[TomASS]

Taaa, sortowanie, przeciez to bez sensu skoro jest wlasnie max()

Ta sama złożoność obliczeniowa - O(n)

Ten post edytował TomASS 6.04.2009, 18:51:05

[dr_bonzo]

Ta sama, czy zartujesz?

[TomASS]

Odpowiedz mi, bardzo proszę, na dwa pytania:
1. jaką złożoność ma sortowanie?
2. jaką złożoność ma max()?

[nospor]

@TomASS jak jestes w stanie posortowac dane jedną iteracją to ty jestes normalnie gość

[TomASS]

Jestem w stanie posortować liczby całkowite (bo o takich tu mówię), jedną pętlą for...

[nospor]

no a w tej jednej petli sa kolejne.

No ale moge sie mylic, moze matematyka ruszyla do przodu przez te kilka lat wiec pokaz mi prosze ten kod

[TomASS]

Proszę bardzo:
sortowanie kubełkowe


Albo inny pomysł:
Lecisz pętlą po całej tablicy i zapamiętujesz ile razy wystąpiła dana liczba. Potem już tylko wystarczy wyświetlić odpowiednią ilość liczb:

[PHP] pobierz, plaintext 
<?php
$arrDane = array();
$iRozmiarTablicy = 30;
/*
 * Losowanie elementów
 */
for($i=0;$i<$iRozmiarTablicy;$i++){
    $arrDane[]=rand(0,$iMaxValue);
}
/*
 * Wyświetlenie nieposortowanej tabeli
 */
echo '<pre>'; 
    print_r($arrDane);
echo '</pre>';
 
/*
 * Sortowanie tabeli
 */
for($i=0;$i<$iRozmiarTablicy;$i++){
    $arrSort[$arrDane[$i]]++;
}
/*
 * Wyświetlenie posortowanej tabeli
 */
echo '<pre>'; 
    print_r($arrSort);
echo '</pre>';
?>
[PHP] pobierz, plaintext 

[nospor]

Proszę bardzo:
sortowanie kubełkowe

Jest on najczęściej stosowany, gdy liczby w zadanym przedziale są rozłożone jednostajnie, ma on wówczas złożoność Θ(n). W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n2).

Poza tym nawet w przypadku optymalnym nie jest to tylko jedna iteracja.
Wyliczenie max to jest jedna iteracja niezaleznie czy to jest przypadek optymalny czy nie

Albo inny pomysł:
Lecisz pętlą po całej tablicy i zapamiętujesz ile razy wystąpiła dana liczba. Potem już tylko wystarczy wyświetlić odpowiednią ilość liczb:

[shazarre]

Podejrzewam, że teraz wszyscy czytający ten temat próbują rozkminić co takiego TomASS wymyślił, ale ja Wam mogę z całą pewnością oznajmić, iż nasze (a przynajmniej większości) rozumienie sortowania mija się zdecydowanie z jego własnym.

[TomASS]

Drogi kolego shazarre.

Podejrzewam, że teraz wszyscy czytający ten temat próbują rozkminić

Ja z kolei podejrzewam, że nawet nie zadałeś sobie trudu aby zrozumieć to co napisałem. Nie winię Cię jednak za to - ale nie mierz wszystkich swoją miarą.

co takiego TomASS wymyślił

Nie ja to wymyśliłem. Podejrzewam, że wymyślił to twórca wspaniałej książki o algorytmach - Pan Thomas (zbieżność imion?) Cormen. Algorytm "Counting Sort" jest szeroko opisywany np. tutaj (jeśli wolisz czytać po polsku, to proszę bardzo).

Kod w C++ masz tutaj. Nie widzę nigdzie zagnieżdżonych pętli. Złożoność obliczeniowa jest O(n) (dobra, niech będzie O(n+k), zmienna nie ma tutaj znaczenia). Natomiast tutaj masz aplet Javy pokazujący jak to działa.

ale ja Wam mogę z całą pewnością oznajmić

Widać jaką miałeś pewność - swoje "widzimisie".

nasze (a przynajmniej większości) rozumienie sortowania mija się zdecydowanie z jego własnym

Tak - jakie to jest sortowanie rozumiane przez "większość"? Ja np. mogę zgodzić się z takim pojęciem:

"Sortowanie – jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.

Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwieniu stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka."

I to właśnie robię algorytmem Counting Sort, mało tego - żąda tego (pośrednio) autor wątku - posortowania i wybór ostatniego/pierwszego elementu. Chciałbym poznać Twoje (większości?) rozumienie słowa "sortowanie".

Wczytując się w niuanse tego algorytmu, znaleźć można zmienną o wartości największego elementu:

[PHP] pobierz, plaintext 
<?php
$k = max($tablica);
?>
[PHP] pobierz, plaintext 

otóż, funkcja max() (jak nospor słusznie zauważył: "Wyliczenie max to jest jedna iteracja niezaleznie czy to jest przypadek optymalny czy nie") również działa w czasie O(n) co nie wpływa w żaden sposób na jakość algorytmu (przypominam, że O(k*n) = O(n), gdzie k jest dowolną, ale skończoną wartością).

Aby jeszcze bardziej zobrazować Ci działanie tego algorytmu, pokusiłem się o napisanie go w PHP:

[PHP] pobierz, plaintext 
<?php
function countSortTomass($arrToSort){
    $arrSorted = array();
    $k = max($arrToSort);
    $length = count($arrToSort)-1;
    
    $arrTmp = array();
    for ($i=0;$i<=$k;$i++){
        $arrTmp[$i]=0;
    }
    
    for ($i=0;$i<=$length;$i++){ 
        $arrTmp[$arrToSort[$i]]++; 
        $arrSorted[]=0;
    }
    
    for ($i=1;$i<=$k;$i++){ 
        $arrTmp[$i] = $arrTmp[$i] + $arrTmp[$i-1]; 
    }
    
    for ($i=$length;$i>=0;$i--){
        $arrSorted[$arrTmp[$arrToSort[$i]]-1]=$arrToSort[$i];
         $arrTmp[$arrToSort[$i]]--; 
    }
    return $arrSorted;
}
 
$arrayToSorting = array(1,7,6,10,7,1,5,7,10,3);
$sorted = countSortTomass($arrayToSorting);
echo '<pre>';
    print_r($sorted);
echo '</pre>';
?>
[PHP] pobierz, plaintext 

Nie ma żadnych pętli zagnieżdżonych. Złożoność obliczeniowa to O(n) (dla formalistów O(n+k)).

Kluczowym momentem jest zliczanie elementów:

[PHP] pobierz, plaintext 
<?php
for ($i=0;$i<=$length;$i++){ 
        $arrTmp[$arrToSort[$i]]++; 
}
?>
[PHP] pobierz, plaintext 

o którym pisałem wcześniej, lecz kolega shazarre nie raczył tego zagłębić.

odpalając

[PHP] pobierz, plaintext 
<?php
$arrayToSorting = array(12,3456,6,9887,0);
$sorted = countSortTomass($arrayToSorting);
echo '<pre>';
    print_r($sorted);
echo '</pre>';
?>
[PHP] pobierz, plaintext 

Także uzyskamy prawidłowy wynik (jak chciał autor postu) w czasie porównywalnym (przy nieskończonej ilości danych w takim samym czasie) co max() czyli O(n)

Ten post edytował TomASS 6.04.2009, 23:18:29

[krowal]

No ale generalnie dyskusja zaczęła się od tego żeby udowodnić że sortowanie da się zrobić JEDNĄ iteracją.

TomASSJ: estem w stanie posortować liczby całkowite (bo o takich tu mówię), jedną pętlą for...

Jak widać nie jesteś w stanie
Poza tym sortowanie przez zliczanie to nie jest szczyt szczytów jeśli chodzi o przydatność algorytmu bo niestety jak każdy z algorytmów sortowania ten też ma swoje wady. Faktycznie wydajny jest, ale tylko w określonych sytuacjach.

[TomASS]

Po pierwsze:

Ta sama, czy zartujesz?

Sytuacja zaczęła się od tego, że twierdziłem, że sortowanie liczb całkowitych ma taką samą złożoność obliczeniową jak max() - co jak widać udowodniłem i nie żartowałem

Po drugie:

1. @TomASS jak jestes w stanie posortowac dane jedną iteracją to ty jestes normalnie gość
2. no a w tej jednej petli sa kolejne.

Umiem jedną iteracją.
Sortowanie właściwe to jedna pętla - bez żadnych zgłębień kolejnych pętli - jest to robione tak jak max w JEDNEJ itereacji. Reszta forów jest tylko do "znośnej" prezentacji wyników. Po za tym, okej, nawet jakby było 100 forów pod sobą to i tak złożoność obliczeniowa byłaby O(100n) czyli O(n). Ale faktycznie, zwrot że "tylko" jedną mogę posortować nie był przeze mnie idealnie trafiony.

Po trzecie:

Poza tym sortowanie przez zliczanie to nie jest szczyt szczytów jeśli chodzi o przydatność algorytmu bo niestety jak każdy z algorytmów sortowania ten też ma swoje wady.

Dla liczb całkowitych ma najlepszą złożoność obliczeniową i jest szczytem szyczytów - znasz algorytm sortowania o lepszej złożoności (nawet z tymi wadami - o których wspomniałem)?

Po czwarte:

Faktycznie wydajny jest, ale tylko w określonych sytuacjach.

To zaznaczyłem na samym początku, że chodzi o liczby całkowite, dodatkowo zmienia klucze i jest niestabilny - ale w tym przykładzie nie przeszkadza to niczemu.


Po piąte:
Dzięki za odpowiedzieć - jak widać shazarre podczas gdy nie mógł "rozkminić" stwierdził, że nikt z Was nie doczyta tego, ani nie zrozumie (albo zrozumie na opak) - na szczęście się mylił, co krowal udowodnił

Ten post edytował TomASS 7.04.2009, 07:31:56

[dr_bonzo]

@TomASS:

To zaznaczyłem na samym początku, że chodzi o liczby całkowite, dodatkowo zmienia klucze i jest niestabilny - ale w tym przykładzie nie przeszkadza to niczemu.

No wlasnie nie na poczatku...

Ta sama złożoność obliczeniowa - O(n)

-> wprowadzasz zamieszanie - nie informujesz ze myslales o sortowaniu tylko liczb calkowitych

Odpowiedz mi, bardzo proszę, na dwa pytania:

1. jaką złożoność ma sortowanie?

2. jaką złożoność ma max()?

1. a ktory algorytm?
zalezy od algorytmu i mozliwosci jego zastosowania od O(n), O(nlog(n)), O(n^2) i w gore
2. O(n), ale i tak bedzie w praktyce szybsze niz jakiekolwiek sortowanie, i mniej pamieci zuzyje niz kubelkowe

Takze, twoje wypowiedzi byly niejasne, niepelne i sie czepiasz ze my sie ich czepiamy.


edit: pozatym Counting Sort:

A summary of the algorithm is as follows.
1. Find the highest and lowest elements of the set

- LOL, rzeczywiscie przydatny algorytm do tego konkretnego problemu.

Ten post edytował dr_bonzo 7.04.2009, 08:09:19

[TomASS]

wprowadzasz zamieszanie - nie informujesz ze myslales o sortowaniu tylko liczb calkowitych

Jasno napisałem już w pierwszym/drugim poście:

liczby całkowite (bo o takich tu mówię)

1. a ktory algorytm?

Zazwyczaj pyta się o minimalną złożoność - nie o maksymalną.

TomASS (pierwszy post): Ta sama złożoność obliczeniowa - O(n)
dr_bonzo: Ta sama, czy zartujesz?

TomASS:
1. jaką złożoność ma sortowanie?
2. jaką złożoność ma max()?

Dalej twierdzę, że dla liczb całkowitych mają takie same złożoności.

O(n), O(nlog(n)), O(n^2)

nawet O(n^n) albo nawet O(!n^!n) i co z tego? Minimalna dla liczb całkowitych to taka sama jak dla max().

O(n), ale i tak bedzie w praktyce szybsze niz jakiekolwiek sortowanie, i mniej pamieci zuzyje niz kubelkowe

Nie mówię o praktyce tylko o złożoności.

Takze, twoje wypowiedzi byly niejasne

Bo nie doczytałeś. Mam całą teorię wyłożyć?

niepelne

Książkę musiałbym napisać. Dałem linki, powiedziałem jak metody się nazywają - czego chcieć więcej? Później jak krowie na rowie musiałem dać przykłady w różnych językach, aplety itd. aby niektórzy zrozumieli.

i sie czepiasz ze my sie ich czepiamy.

Czepiam się, jak ktoś nie doczyta/nie zrozumie i się czepia

A summary of the algorithm is as follows.
1. Find the highest and lowest elements of the set

I co z tego, jaki to ma wpływ na złożoność - żaden - nadal jest O(n) i jest robione sortowanie w jednej iteracji.

- LOL, rzeczywiscie przydatny algorytm do tego konkretnego problemu.

Okej - niech będzie tak jak pisałem O(4n+O(max())+k).

Ten post edytował TomASS 7.04.2009, 08:27:13

[nospor]

@TomASS w funkcji countSortTomass() korzystasz z max():
$k = max($arrToSort);

no, i tyle w temacie z mojej strony

Napisales mi ze jestes w stanie posortowac jedną iteracją a nie jestes. na dodatek by posortowac uzywasz funkcji, co do której pisales ze jestes w stanie zrobic tak samo szybko jak ona

Podsumowując temat:
do wyliczenia wartosci maksymalnej uzywa sie algorytmu do wyliczenia wartosci maksymalnej a nie sortowania

[TomASS]

@TomASS w funkcji countSortTomass() korzystasz z max():
$k = max($arrToSort);

Się pytam - i co z tego? Tak zgadza się, coś co używa max() musi być wolniejsze niż samo max() - to oczywiste, ale może mieć tą samą złożoność obliczeniową.

a to z sortowaniem uznajmy za ciekawostkę

i w kategorii ciekawostki to traktuję

do wyliczenia wartosci maksymalnej uzywa sie algorytmu do wyliczenia wartosci maksymalnej a nie sortowania

oczywiście, że do wartości maksymalnej służy funkcja max(), nigdzie nie twierdziłem inaczej.

o do której pisales ze jestes w stanie zrobic tak samo szybko jak ona

Nie pisałem, że tak samo szybko, tylko mają taką samą złożoność (jest różnica pomiędzy szybkością a złożonością)

Napisales mi ze jestes w stanie posortowac jedną iteracją a nie jestes

Jedną iteracją miałem na myśli, bez pętli zagnieżdżonych, Ty zresztą też:

no a w tej jednej petli sa kolejne.

i nie ma pętli w pętli. A jesteś pewien, że w max() nie ma kilku pętli pod sobą (dla różnych argumentów)?

podsumowując:

do wyliczenia wartosci maksymalnej uzywa sie algorytmu do wyliczenia wartosci maksymalnej a nie sortowania

a do tego (cytat z mojego pierwszego postu) sortowanie liczb całkowitych i max() to:

Ta sama złożoność obliczeniowa - O(n)

Ten post edytował TomASS 7.04.2009, 08:59:09