• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

[PHP] Strona drzewa genealogicznego - kod szukający połączenia między osobami w drzewie szuka za długo

VPS Starter Arubacloud
0 głosów
207 wizyt
pytanie zadane 13 sierpnia 2018 w PHP przez Maciek123233 Gaduła (3,400 p.)

Witam, od kilku dni tworzę stronę drzewa genealogicznego, próbuję stworzyć funkcję do znalezienia połączenia między osobami, niestety chociaż funkcja działa, to wyszukuje osoby tylko do ok. 10 etapów, ponieważ dla dalszych odległości funkcja ładuje się za długo. Oto sposób zapisu danych osobowych w bazie danych SQL: są 3 tabele:

pierwsza "osoby" - zawiera ID osoby, imię, nazwisko, płeć, datę i miejsce narodzin i śmierci itd.

druga "rodziny" - zawiera ID rodziny, ID matki i ID ojca

trzecia "dzieci" - zawiera ID dziecka i ID rodziny

stworzyłem dwie tabele "rodziny" i "dzieci" ponieważ w jednej rodzinie dzieci może być więcej, po prostu z danej rodziny łatwiej jest wyjąć dzieci, które są w osobnej tabeli. Wyszukiwarka i drzewo działają bardzo dobrze, ale plik php który ma znaleść połączenie nie daje rady. Ponieważ ten kod ma ponad 200 linii napiszę co prostu jak działa:

Do funkcji szukaj_połączenia() przekazuję Id osoby początkowej i Id osoby końcowej i ograniczenie wyszukania do 5

Wyszukuję i zapisuję wszystkie osoby w odległości 5 kroków od osoby początkowej (razem z połączeniem) np.

[0] -> Jan Kowalski (Id: 123), [1] -> jego mama (Id: 234), [2] -> jego babcia (Id: 1321), [3] -> jego prababcia (Id: 12), [4] -> jego praprababcia (Id: 666)

Takich połączeń w odległości 5 kroków jest (w zależności od osoby) ok. 30 - 50. Te wszystkie połączenia znowu daję do funkcji, tym razem daję ograniczenie wyszukiwania do 10 (w tablicach jest już 5 osób, więc chodzi o kolejne 5), w założeniu miałem poszerzać zakres wyszukiwania o 5, za każdym razem gdy funkcja zwróci wszystkie połączenia a osoba docelowa nie została znaleziona (szukaj osoby docelowej w promieniu 5.. 10.. 15.. 20.. kroków itd.) Niestety ponieważ z każdym krokiem liczba osób drastycznie rośnie, wyszukiwarka znajduje osoby do ok. 10 kroków (to jest ok. 700 osób), dla dalszych połączeń strona kręci się bez końca.

I tutaj moje pytanie, czy jest jakiś sposób lepszego zapisu danych i/lub lepszego sposobu wyszukującego to połączenie? Mogę jeszcze tylko powiedzieć, że na stronie Myheritage, która wyświetla drzewa genealogiczne, wyszukiwanie połączenia trwa pół sekundy, nawet gdy dwie osoby są od siebie bardzo daleko.

Zdaję sobie sprawę że moje pytanie skomplikowane i zagmatwane, ale w razie jakichkolwiek wątpliwości proszę o zadanie pytania w komentarzach.

komentarz 13 sierpnia 2018 przez Tomek Sochacki Ekspert (227,510 p.)
a szukałeś w necie algorytmu dla drzewa genealogicznego? Jest trochę materiałów o tym, kiedyś czytałem jedną analizę algorytmu w C++, wieczorem jak bede przy pc to sprobuje odszukać w swoich archiwach linków.
komentarz 14 sierpnia 2018 przez Maciek123233 Gaduła (3,400 p.)
Szukam ale nie mogę nic znaleźć. Jeśli może to poszukaj, bardzo mi na tym zależy.

1 odpowiedź

0 głosów
odpowiedź 14 sierpnia 2018 przez Tomek Sochacki Ekspert (227,510 p.)
A tu czytałeś? Są opisane różne problemy itp. Nie wgłębiałem się w cały artykuł, tak tylko pobieżnie poczytałem i wydaje mi się, że tu znajdziesz naprowadzenie jak ogarnąć taki algorytm i jaką strukturę dobrać.

https://medium.freecodecamp.org/all-you-need-to-know-about-tree-data-structures-bceacb85490c
komentarz 15 sierpnia 2018 przez Maciek123233 Gaduła (3,400 p.)
Ten artykuł byłby przydatny gdybym w drzewie miał tylko siebie, rodziców, dziadków, pradziadków, prapradziadków itd. bo na każdą osobę przypada wtedy dwóch rodziców i tyle. A u mnie sprawa jest dużo bardziej skomplikowana, każda osoba może mieć partnera (nawet nie jednego) i dzieci. (w tym drzewie jest prawie 100 tys. osób, a rekordzista ma 3 partnerki i 19 dzieci)

Podobne pytania

0 głosów
0 odpowiedzi 1,040 wizyt
pytanie zadane 18 marca 2017 w Inne języki przez aborolabis Nowicjusz (120 p.)
0 głosów
0 odpowiedzi 107 wizyt
+1 głos
2 odpowiedzi 151 wizyt
pytanie zadane 5 października 2021 w Matematyka, fizyka, logika przez HUBSON2912 Obywatel (1,300 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...