Czy istnieją alternatywne struktury danych niż tablica w PHP, gdzie mogę korzystać z różnych technik indeksowania?

Question

Ostatnio miałem problem z tablicą zawierającą setki tysięcy wartości i jedyną rzeczą, którą chciałem zrobić, było sprawdzenie, czy wartość była już obecna. W moim przypadku były to adresy IP z dziennika serwera sieciowego. Więc w zasadzie coś takiego:

in_array(ip2long(ip),$myarray) spełnił swoje zadanie

Jednak zwiększona czas odnośnika dramatycznie i 10k z wyszukiwań trwało około 17 sekund lub więcej.

Więc w tym przypadku nie obchodziło mnie, czy mam duplikaty, czy nie, po prostu musiałem sprawdzić istnienie. Mogłem więc przechowywać adresy IP w indeksie tak:

isset($myarray[ip2long($ip)]) 

i bom czasy lookup spadła z 17 sekund (i więcej) do statycznego czasie 0,8 sekundy za 10k wyszukiwań. Jako wartość wpisu tablicy użyłem właśnie int 1.

Myślę, że indeks tablicy jest prawdopodobnie oparty na niektórych drzewach b, które powinny mieć log (n) czas wyszukiwania i indeks na mapie.

W moim przypadku używanie indeksu działało poprawnie, ale czy są jakieś struktury danych, w których mogę użyć hashmapów jako indeksu wartości, gdzie wiele wartości może również zająć (zdaję sobie sprawę, że ma to sens tylko wtedy, gdy nie ma zbyt wielu duplikatów i nie mogę efektywnie używać żądań zasięgu/wyszukiwania, co jest podstawową zaletą struktur drzewa?

Answer 1

Istnieje cały szereg alternatyw datastructures poza prostych tablic w SPL library wiązanych z PHP, w tym związane listy, stosy, hałdy, kolejki itp

Podejrzewam jednak, można dokonać logika dużo bardziej wydajne, jeśli masz flipped twoją tablicę, co pozwala ci wykonać wyszukiwanie na kluczu (używając funkcji array_key_exists()) zamiast szukać wartości. Indeks tablicy to hash, a nie btree, co zapewnia bardzo szybki bezpośredni dostęp za pomocą klucza.

Jeśli jednak pracujesz z wpisami 10k w tablicy, prawdopodobnie lepiej wykorzystasz bazę danych, w której możesz zdefiniować swoje własne indeksy.

Answer 2

Tablice mają sekwencyjną kolejność i szybki dostęp do niektórych elementów, ponieważ nie trzeba przechodzić przez drzewo lub pracować z sekwencyjną strukturą listy.

Zestaw jest oczywiście szybszy, ponieważ sprawdzane są tylko unikalne elementy, a nie wszystkie elementy (w tablicy).

Drzewa są dobre dla przykładowych posortowanych struktur. Możesz zaimplementować drzewo z adresami IP posortowanymi według ich zasięgów, wtedy możesz zdecydować szybciej, jeśli to IP istnieje, czy nie. Nie jestem pewien, czy PHP zapewnia takie niestandardowe struktury drzewa. Sądzę, że musisz to zaimplementować samemu, ale zajmie to około pół godziny.

Znajdziesz przykładowe kody w Internecie dla takich struktur drzewa.

Answer 3

Masz również rozszerzenie chdb (stałe rozszerzenie bazy danych) - które idealnie do tego pasuje.

Answer 4

jak już odpowiedział, można użyć zupełnie nowych klas przedstawionych przez SPL http://www.php.net/spl

ale widocznie nie są one tak szybko, jak ludzie myślą. prawdopodobnie nie są one realizowane zgodnie z naszymi oczekiwaniami. to jest moja opinia, że ​​splfixedarray, na przykład, nie jest prawdziwa tablica, ale hashtable jako tablice klasyczny PHP

ale też masz jakieś alternatywne rozwiązania

pierwszy można zapisać swój wynik w bazie danych. Zapytania są szybkie, ponieważ indeksy db może być lepiej zoptymalizowane niż datastructure php

można użyć http://www.php.net/sqlite3 i przechowywania wyników w tymczasowej bazy danych (plik lub w pamięci)

Proponuję plik tymczasowy, ponieważ don” t należy załadować wszystko do pamięci, a dodatkowo można dodać każdy wiersz osobno (używając na przykład http://www.php.net/fgets)

HTH!

Nie krępuj się poprawić mój angielski