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!
Jakiś związek z Robertem Tarjanem, odkrywcą kilku znanych algorytmów graficznych (!)? –
:) Niestety, tylko miasto na Węgrzech, z którego oboje otrzymaliśmy nasze nazwisko. Ale oboje kochamy komputery i matematykę. –
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