सार समस्या: मेरे पास लगभग 250,000 नोड्स का ग्राफ है और औसत कनेक्टिविटी लगभग 10 है। नोड के कनेक्शन ढूंढना एक लंबी प्रक्रिया है (10 सेकंड कहें)। डेटाबेस में नोड को सहेजने में लगभग 10 सेकंड लगते हैं। मैं जांच सकता हूं कि डीबी में नोड पहले से ही मौजूद है या नहीं। समेकन की अनुमति, लेकिन एक समय में 10 से अधिक लंबे अनुरोध नहीं होने पर, आप उच्चतम कवरेज को सबसे तेज़ी से प्राप्त करने के लिए ग्राफ को कैसे पार करेंगे।अच्छा ग्राफ ट्रैवर्सल एल्गोरिदम
कंक्रीट समस्या: मैं एक वेबसाइट उपयोगकर्ता पृष्ठों को स्क्रैप करने की कोशिश कर रहा हूं। नए उपयोगकर्ताओं को खोजने के लिए मैं पहले से ज्ञात उपयोगकर्ताओं से मित्र सूची ला रहा हूं। मैंने पहले ही ग्राफ के लगभग 10% आयात किया है, लेकिन मैं चक्रों में फंस रहा हूं या बहुत अधिक नोड्स को याद रखने में बहुत अधिक स्मृति का उपयोग कर रहा हूं।
मेरे वर्तमान कार्यान्वयन:
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*
वर्तमान कार्यान्वयन की समस्याएं:
- , क्लिक्स कि मैं पहले से ही आयात किया है में अटक जाती है जिससे समय बर्बाद कर और आयात धागे निष्क्रिय होते हैं।
- जितना अधिक वे इंगित करेंगे उतना अधिक जोड़ देंगे।
तो, मामूली सुधारों का स्वागत है, साथ ही पूर्ण पुनर्लेखन भी। धन्यवाद!
कई उल्लेखनीय ग्राफ-सैद्धांतिक (!) एल्गोरिदम के खोजकर्ता रॉबर्ट तारजन से कोई संबंध? –
:) अफसोस की बात है, केवल हंगरी में शहर है कि हम दोनों को अपना अंतिम नाम मिला है। लेकिन हम दोनों को कंप्यूटर और गणित का प्यार है। –
प्रश्न से संबंधित नहीं है, लेकिन ध्यान दें कि sys.stderr.write ("... \ n") को प्रिंट >> sys.stderr द्वारा प्रतिस्थापित किया जा सकता है, "..." ("\ n" की आवश्यकता नहीं है, और उपयोग अधिक सामान्य प्रिंट स्टेटमेंट के)। – EOL