11

Problem abstrakcyjny: Mam wykres około 250 000 węzłów, a średnia łączność to około 10. Znalezienie połączenia węzła jest długim procesem (powiedzmy 10 sekund). Zapisanie węzła do bazy danych zajmuje również około 10 sekund. Mogę sprawdzić, czy węzeł jest już obecny w db bardzo szybko. Zezwalając na współbieżność, ale nie mając więcej niż 10 długich żądań na raz, w jaki sposób przejdziesz przez wykres, aby najszybciej uzyskać jak największy zasięg.Algorytm przemierzania dobrego wykresu

Konkretny problem: próbuję zeskrobać strony użytkowników witryny. Aby odkryć nowych użytkowników, pobieram listę znajomych od już znanych użytkowników. Zaimportowałem już około 10% wykresu, ale utknąłem w cyklach lub używałem zbyt dużo pamięci pamiętając zbyt wiele węzłów.

Moja obecna implementacja:

def run() : 
    import_pool = ThreadPool(10) 
    user_pool = ThreadPool(1) 
    do_user("arcaneCoder", import_pool, user_pool) 

def do_user(user, import_pool, user_pool) : 
    id = user 
    alias = models.Alias.get(id) 

    # if its been updates in the last 7 days 
    if alias and alias.modified + datetime.timedelta(days=7) > datetime.datetime.now() : 
     sys.stderr.write("Skipping: %s\n" % user) 
    else : 
     sys.stderr.write("Importing: %s\n" % user) 
     while import_pool.num_jobs() > 20 : 
      print "Too many queued jobs, sleeping" 
      time.sleep(15) 

     import_pool.add_job(alias_view.import_id, [id], lambda rv : sys.stderr.write("Done Importing %s\n" % user)) 

    sys.stderr.write("Crawling: %s\n" % user) 
    users = crawl(id, 5) 
    if len(users) >= 2 : 
     for user in random.sample(users, 2) : 
      if (user_pool.num_jobs() < 100) : 
       user_pool.add_job(do_user, [user, import_pool, user_pool]) 

def crawl(id, limit=50) : 
    '''returns the first 'limit' friends of a user''' 
    *not relevant* 

Problemy obecnej realizacji:

  • utknie w klik że już importowane, co tracić czas i importujący gwinty są bezczynne.
  • Dodamy więcej, gdy zostaną wskazane.

W związku z tym mile widziane poprawki są mile widziane, a także pełne poprawki. Dzięki!

+1

Jakiś związek z Robertem Tarjanem, odkrywcą kilku znanych algorytmów graficznych (!)? –

+0

:) Niestety, tylko miasto na Węgrzech, z którego oboje otrzymaliśmy nasze nazwisko. Ale oboje kochamy komputery i matematykę. –

+0

Niezwiązane z pytaniem, ale pamiętaj, że sys.stderr.write ("... \ n") można zastąpić przez print >> sys.stderr, "..." (nie ma potrzeby "\ n", a użycie bardziej typowego polecenia print). – EOL

Odpowiedz

7

Aby zapamiętać identyfikatory już odwiedzonych użytkowników, trzeba mieć mapę długości 250,000 całkowitymi. To daleko od "za dużo". Po prostu zachowaj taką mapę i przesuwaj się tylko przez krawędzie, które prowadzą do już nieodkrytych użytkowników, dodając je do tej mapy w momencie znalezienia takiej krawędzi.

O ile widzę, jesteś blisko wdrożenia pierwszego wyszukiwania (BFS). Sprawdź google o szczegółach tego algorytmu. I, oczywiście, nie zapomnij o muteksach - będziesz ich potrzebować.

+0

użytkownicy są w rzeczywistości ciągami znaków o średniej długości 15. Próbowałem mieć dykta z {nazwa_użytkownika1: Prawda, nazwa_użytkownika2: Prawda}, ale to szybko osiągnęło 100% pamięci i maszyna została zablokowana. Być może jest to po prostu nieefektywne w Pythonie, aby użyć dyktowania? –

+0

jednym z możliwych rozwiązań byłoby po prostu przechowywanie skrótów nazw użytkownika – cobbal

+0

również, zestaw jest lepiej przystosowany do tego typu przechowywania niż dyktafonu – cobbal

2

Jestem bardzo zdezorientowany, dlaczego potrzeba 10 sekund, aby dodać węzeł do DB. To brzmi jak problem. Jakiej bazy danych używasz? Czy masz poważne ograniczenia platformy?

Dzięki nowoczesnym systemom i ich olbrzymim zapędom pamięci polecam miłą prostą pamięć podręczną. Powinieneś być w stanie stworzyć bardzo szybki bufor informacji o użytkowniku, który pozwoliłby ci uniknąć powtarzania pracy. Po napotkaniu już węzła przerwij przetwarzanie. To pozwoli uniknąć kolejek na zawsze w klikach.

Jeśli chcesz zezwolić na ponowne podłączenie istniejących węzłów po pewnym czasie, możesz użyć last_visit_number, który byłby wartością globalną w dB. Jeśli węzeł ma tę liczbę, to jest to indeksowanie, które ją napotkało. Jeśli chcesz automatycznie ponownie odwiedzać dowolne węzły, wystarczy przejść do parametru last_visit_number przed rozpoczęciem indeksowania.

Według twojego opisu, nie jestem całkiem pewien, jak utkniesz.

Edytuj ------ Właśnie zauważyłem, że masz konkretne pytanie. Aby zwiększyć szybkość pobierania nowych danych, śledziłbym liczbę przypadków, w których dany użytkownik był połączony z Twoimi danymi (zaimportowany lub jeszcze nie zaimportowany). Wybierając użytkownika do indeksowania, wybrałbym użytkowników, którzy mają małą liczbę linków. W szczególności wybrałbym najniższą liczbę linków lub losowy wybór spośród użytkowników o najniższej liczbie linków.

Jacob

+0

10 sekund pochodzi z konieczności zeskanowania kilku stron informacji na użytkownika, a następnie przekształcenia go do mojego formatu bazy danych. Większość czasu to czas sieci. –

+0

Jeśli chodzi o wybór nowych użytkowników, bardzo interesujące.Spróbuję zliczać inlinks dla użytkowników i tylko spidering od nisko inlinkowanych użytkowników. –

+0

Dlaczego tak mało wątków? Martwisz się, że cię zablokują? Zamierzałem zasugerować hash dla każdego węzła (a.la Pavel). Jedną z rzeczy, które możesz zrobić, to utworzyć inkrementujący identyfikator i użyć prostej tabeli odwzorowań, aby połączyć się z nimi. – TheJacobTaylor

2

Nie ma określonego algorytmu, który pomógłby zoptymalizować budowę wykresu od zera. Tak czy inaczej, będziesz musiał odwiedzić każdy węzeł przynajmniej raz. Niezależnie od tego, czy robisz to, depth first lub breadth first, nie ma to znaczenia z punktu widzenia prędkości. Theran poprawnie wskazuje w komentarzu poniżej, że pierwsze wyszukiwanie wszerz, poprzez wcześniejsze eksplorowanie bliższych węzłów, może dać ci bardziej użyteczny wykres, zanim cały wykres zostanie zakończony; to może lub nie powinno Cię martwić. Zauważa także, że najczystsza wersja pierwszego wyszukiwania jest zaimplementowana przy użyciu rekurencji, co może potencjalnie stanowić problem dla Ciebie. Pamiętaj, że rekurencja nie jest wymagana; możesz dodać niecałkowicie zbadane węzły do ​​stosu i przetwarzać je liniowo, jeśli chcesz.

Jeśli wykonujesz proste sprawdzenie istnienia dla nowych węzłów (O (1), jeśli użyjesz skrótu do sprawdzenia), cykle nie będą w ogóle problemem. Cykle stanowią problem, jeśli nie przechowujesz pełnego wykresu. Możesz zoptymalizować wyszukiwanie za pomocą wykresu, ale sam krok konstrukcyjny zawsze zajmie czas liniowy.

Zgadzam się z innymi plakatami, że rozmiar wykresu nie powinien stanowić problemu. 250 000 nie jest zbyt duże!

Odnośnie równoczesnej realizacji; wykres jest aktualizowany przez wszystkie wątki, więc musi to być zsynchronizowana struktura danych. Ponieważ jest to Python, możesz użyć modułu Queue do przechowywania nowych linków, które mają być przetwarzane przez twoje wątki.

+1

Funkcja BFS może być lepsza, ponieważ najpierw przyjrzy się najbliższym węzłom, a początkowo najprawdopodobniej przekaże użyteczny podzbiór. BFS pozwala także uniknąć ryzyka rekurencji na poziomie 250 000 poziomów i może utrzymać kolejkę w tym samym DB, co końcowy wykres (zakładając RDBMS). – Theran

+1

Z pewnością można utworzyć DFS bez problemu śledzenia głębokiego stosu: jedyną istotną różnicą między DFS i BFS jest BFS, do którego dodaje się węzły do ​​kolejki; w DFS: stos. Ten sam algorytm, inna struktura danych - a więc odmienna semantyka. –

+0

@ Theran, Michael: +1 dzięki - odpowiedź dostosowana do wyjaśnienia. –

0

Chociaż można powiedzieć, że uzyskanie listy znajomych zajmuje sporo czasu (10 sekund lub więcej), wariant algorytmu dobrej starej Dijkstry prostu może pracować:

  1. Get dowolny węzeł.
  2. Uzyskaj połączenie z dowolnego węzła, który został już załadowany.
  3. Jeśli drugi koniec nie został jeszcze załadowany, dodaj węzeł do wykresu.
  4. Przejdź do kroku 2.

Sztuką jest wybrać połączenie ładowanego krok 2 w inteligentny sposób. Kilka krótkich uwag na ten temat:

  • Powinieneś w pewien sposób zapobiec dwukrotnemu lub częstszemu ładowaniu tego samego połączenia. Wybranie losowego połączenia i odrzucenie go, jeśli zostało już wczytane, jest bardzo nieefektywne, jeśli szukasz wszystkich połączeń.
  • Jeśli chcesz w końcu załadować wszystkie połączenia, załaduj wszystkie połączenia węzła w tym samym czasie.

Aby naprawdę powiedzieć coś o wydajności, należy podać więcej szczegółów na temat struktury danych.