良好的圖遍歷算法

抽象的問題：我有一個約250,000個節點的圖形，平均連接約爲10個。查找一個節點的連接是一個漫長的過程（10秒可以說）。將節點保存到數據庫也需要大約10秒。我可以很快檢查一個節點是否已經存在於db中。如果允許併發，但一次不會有超過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*

目前執行的問題：

卡在我已導入拉幫結派，從而浪費時間和進口線程是空閒的。
隨着他們指出，會增加更多。

所以，邊際的改進是值得歡迎的，以及完整的重寫。謝謝！

來源

2009-08-24 Paul Tarjan

與Robert Tarjan，幾個着名的圖論（！）算法的發現者有何關係？ – 2009-08-24 07:34:54

:)不幸的是，只有匈牙利的這個城市，我們都得到了我們的姓氏。但我們都喜歡電腦和數學。 – 2009-08-24 08:23:38

與這個問題無關，但請注意sys.stderr.write（「... \ n」）可以替換爲print >> sys.stderr，「...」（不需要「\ n」，並且使用更平常的印刷說明）。 – EOL 2009-08-24 09:59:12

要記住訪問過的用戶ID，您需要地圖250,000整數的長度。這遠非「太多」。只需維護這樣的地圖，並只遍歷通向已經發現的用戶的邊緣，並在找到這樣的邊緣時將它們添加到該地圖。

據我所知，你已經接近實現廣度優先搜索（BFS）了。檢查谷歌關於這個算法的細節。當然，不要忘記互斥體 - 你需要它們。

來源

2009-08-24 06:15:54

用戶實際上是平均長度爲15的字符串。我嘗試了{username1：True，username2：True}的字典，但很快就達到100％memeory並鎖定了機器。也許這只是在Python中使用字典效率低下？ – 2009-08-24 07:04:35

一種可能的解決方案是僅存儲用戶名 – cobbal 2009-08-24 07:07:54

的散列，一組更適合於該類型的存儲比字典 – cobbal 2009-08-24 07:08:37

我真的很困惑，爲什麼需要10秒鐘將節點添加到數據庫。這聽起來像是一個問題。你使用的是哪個數據庫？你有嚴格的平臺限制嗎？

隨着現代系統，以及他們的記憶，我會推薦一個很好的簡單緩存的某種。你應該能夠創建一個非常快速的用戶信息緩存，這將允許你避免重複的工作。當您遇到節點時，請停止處理。這將避免在派系中永遠循環。

如果您需要允許在一段時間後重新調整現有節點，則可以使用last_visit_number，它將是dB中的全局值。如果節點具有該編號，則該爬網是遇到它的那個。如果你想自動重新訪問任何節點，你只需要在開始抓取之前碰撞last_visit_number。

通過您的描述，我不太清楚您是如何陷入困境的。

編輯------ 我剛剛注意到你有一個具體的問題。爲了增加吸引新數據的速度，我會跟蹤給定用戶在數據中鏈接的次數（導入或未導入）。選擇用戶進行抓取時，我會選擇鏈接數量較少的用戶。我會特別選擇鏈接數量最少的鏈接，或者鏈接數量最少的用戶隨機選擇。

雅各

來源

2009-08-24 06:15:06 TheJacobTaylor

10秒來自於不得不刮掉用戶的幾頁信息，然後將其轉換爲我的數據庫格式。大部分是網絡時間。 – 2009-08-24 07:06:56

至於新用戶的選擇，很有意思。我會嘗試計算用戶的鏈接，並且只能從低鏈接的用戶身上搜索。 – 2009-08-24 07:07:40

爲什麼這麼少的線程？你擔心他們會阻止你嗎？我將爲每個節點（a.la Pavel）建議一個散列。你可以做的一件事是創建一個遞增的id並使用一個簡單的映射表來交叉引用它們。 – TheJacobTaylor 2009-08-24 17:44:31

沒有特定的算法可以幫助您從頭開始優化圖形的構建。無論如何，你將不得不每次訪問每個節點一次。無論你做這個depth first還是breadth first從速度角度來看都是無關緊要的。 Theran在下面的評論中正確指出了廣度優先搜索，通過先探索更接近的節點，可以在整個圖完成之前立即爲您提供更有用的圖;這可能會或可能不會成爲您的擔憂。他還指出，深度優先搜索的最新版本是使用遞歸實現的，這可能會成爲您的問題。請注意，遞歸不是必需的，但是;您可以將不完整探索的節點添加到堆棧，並根據需要線性處理它們。

如果您對新節點進行簡單的存在檢查（如果您使用散列進行查找，則爲O（1）），那麼週期不會成爲問題。如果你不存儲完整的圖表，循環只是一個問題。您可以通過圖表優化搜索，但構建步驟本身總是需要線性時間。

我同意其他海報，你的圖的大小不應該是一個問題。 250,000不是很大！

關於併發執行;該圖由所有線程更新，因此它需要是一個同步的數據結構。由於這是Python，因此您可以使用Queue模塊來存儲仍然由線程處理的新鏈接。

來源

2009-08-24 06:30:09

BFS可能會更好，因爲它會首先查看最初的節點，這很可能會在早期給出一個有用的子集。 BFS還避免了遞歸250,000級深度的風險，並且可以將其隊列保留在與最終圖（假設RDBMS）相同的DB中。 – Theran 2009-08-24 06:36:34

您當然可以在不存在深堆棧跟蹤問題的情況下製作DFS：DFS和BFS之間唯一真正的區別是在BFS中將節點添加到隊列;在DFS中，一個堆棧。相同的算法，不同的數據結構 - 因此，不同的語義。 – 2009-08-24 06:49:14

@Theran，Michael：+1謝謝 - 答案調整後作出澄清。 – 2009-08-24 06:56:07

雖然你說，讓好友列表需要花費大量的時間（10秒以上），良好的老Dijkstra算法的一種變體可能只是工作：

得到任何節點。
從您已經加載的任何節點獲取連接。
如果另一端尚未加載，則將該節點添加到圖中。
轉到步驟2.

訣竅是選擇在加載第二步中，通過智能的方式連接。關於此的一些簡短的評論：

您應該以某種方式防止相同的連接被加載兩次或更多。如果你已經連接好了，選擇一個隨機連接並丟棄它，如果它已經被加載，那麼效率是非常低的。
如果要最終加載所有連接，請同時加載節點的所有連接。

爲了真正說一下效率，請提供關於數據結構的更多細節。

來源

2009-08-24 07:04:43 Martijn

良好的圖遍歷算法

回答

相關問題