ディクテーションでツリーの最初のノードを見つける方法は？

Question

私は、大きな問題を抱えている作業を開始するための機能で、私は、ツリーの最初のノードを見つける必要があり、ここでは例：

   "hi" 
      / \ 
     /  \ 
      "ok"  "no" 
     /
     /
     "lol" 

問題は、私はAからそれを取る方法を知らないということです入力は、このようなものですので、辞書は、：誰も（「こんにちは」dict.values中を持っていないので、この場合はそう

{ "ok":["lol"] , "no":[] , "hi": ["ok","no"] , "lol" : [] } 

は「こんにちは」）最初に問題はdictのことを言う方法で、最も重要な50,000ノードありますので、1つ1つチェックすると残業になります。 「「hellow」にあるがない

d = { "ok":["lol"] , "no":[] , "hi": ["ok","no"] , "lol" : [] } 
    x = d.values() 
    x = str(x) 
    for y in d.keys(): 
     if not y in x : 
      first_node = y 
      break 

が、問題はそれが「こんにちは」などの言葉と「地獄」ので「地獄」のような「キー」することができます：

は、私はこれを書きましたhellow」:(あなたはリストの内包表記を使用することができます

Answer 1

set.differenceを使用してこれを行う方法があります。

from itertools import chain 

d = { "ok":["lol"] , "no":[] , "hi": ["ok","no"] , "lol" : [] } 
roots = set(d).difference(chain.from_iterable(d.values())) 

あなたはランダムなノードを選択し、トップにそれに従うことができ、私たちに

{'hi'} 

Answer 2

：

d = { "ok":["lol"] , "no":[] , "hi":["ok","no"] , "lol" : [] } 
root = [a for a, b in d.items() if all(a not in d for c, d in d.items())][0] 

出力：

'hi' 

Answer 3

を与えます。 私は、イムのはtimeitとレポート結果を何かを書いた：

d = { "ok":["lol"] , "no":[] , "hi": ["ok","no"] , "lol" : []} 

node = list(d.keys())[0] 
found = False 
while not found: 
    found = True 
    for key, value in d.items(): 
     if node in value: 
      node = key 
      found = False 

print(node) 

---

は、私の解決策は、テスト環境で最善を行っていることが判明：

**10 nodes** 
0.0000020000017 s - my solution 
0.0000043555594 s - using set.diffrence by Patrick Haugh 
0.0001111112098 s - list comprehension by Ajax1234 

**1000 nodes** 
0.0007560006720 s - my solution 
0.0015977791980 s - using set.diffrence by Patrick Haugh 
0.3337478522203 s - list comprehension by Ajax1234 

**10000 nodes** 
0.0077213401967 s - my solution 
0.0138804567826 s - using set.diffrence by Patrick Haugh 
35.264710457520 s - list comprehension by Ajax1234