Forum PHP.pl

Witam, mam proste pytanko.
Czy w PHP są wbudowane funkcje:
1. wyszukiwanie binarne w posortowanej tablicy
2. wyszukiwanie liczb pierwszych w zadanym przedziale

wiem, że istnieje array_search Link do manuala, ale nie ma informacji o złożoności algorytmu.

Z pewnych przyczyn muszę przepisać program z C++ na PHP
Posiadam własną implementacje sita Atkina, tylko nie ma sensu stosować własnych rozwiązań, jeżeli są zaimplementowane w standardzie.

Implementacje PHP są dostosowane do struktury danych, jaka jest wykorzystywana. W przypadku tablic nie ma sensu robić wyszukiwania binarnego, gdyż są one zaimplementowane jako tablice z haszowaniem i funkcja array_search() z tego właśnie faktu korzysta. Gdybyś sam sobie coś takiego napisał, wcale nie działałoby to szybciej od domyślnych funkcji, które w dodatku mają tę przewagę, że są napisane w C.

Ten post edytował Zyx 17.05.2009, 11:43:48

dzięki za odpowiedź, trochę szkoda, ale faktycznie to jest zrozumiałe
aczkolwiek dla tablicy liczb całkowitych hashowanie jest bez sensu

czyli złożoność array_search jest liniowa? (IMG:http://forum.php.pl/style_emoticons/default/blinksmiley.gif)

Co ma rodzaj przechowywanych danych do haszowania? Nic. Tekst to też przecież nic innego, jak ciąg liczb. Ponadto - PESYMISTYCZNA złożoność, a to trochę co innego, niż średnia złożoność, która jest dużo niższa. Tablice PHP służyły już pokoleniom programistów i wydajnościowo nie mam im specjalnie nic do zarzucenia. Quicksort też ma kwadratową pesymistyczną złożoność i nie przeszkadza mu to jakoś w byciu najlepszym algorytmem sortującym ogólnego przeznaczenia.

Ponadto jak już tak bardzo potrzebujesz dokładnego odzwierciedlenia, również pod względem wydajnościowym, zainstaluj PHP 5.3 i odwiedź: http://docs.php.net/manual/en/spl.datastructures.php

Ten post edytował Zyx 17.05.2009, 15:01:31

Quicksort złożoność przeciętną ma klasy O(n log n)
a wyszukiwanie przy użyciu array_search, złożoność przeciętną klasy O(n), tej samej co pesymistyczna...
po za tym, przy odpowiednich zabiegach można osiągnąć złożoność pesymistyczną O(n log n) w sortowaniu, nikt nie nakazuje stosowania czystego Quicksorta ;p

i poco liczbę zamieniać na ciąg liczb? w dodatku dłuższy i trudniejszy do porównania

a co do php 5.3 to nie bardzo ode mnie zależy jaka wersja jest na serwerze/systemie

Ten post edytował binary_search 17.05.2009, 18:57:28

Rany, ale problemy robisz... wygląda na to, że wiesz, jak działają tablice z haszowaniem. Więc sobie przelicz, jakie jest prawdopodobieństwo, że wszystkie elementy tablicy wylądują w tym samym kubełku. Uwierz trochę w programistów, którzy to pisali... jeśli sobie ponumerujesz indeksy od 0 do n, to na pewno oni nie są aż takimi idiotami, by wybrać funkcję haszującą, która wrzuci je wszystkie w jedno miejsce i zrobi z tego listę dwukierunkową.

Ten post edytował Zyx 17.05.2009, 19:01:21