我試圖在這裏和Python文檔中找到答案，但我唯一得到的問題是有關散列列表對象和細節的問題，以及dicts如何工作。Python中是否存在任何類型的散列表

背景

我開發瞭解析一個龐大的圖形程序（大氣壓44K節點，其中14K是任何利益，他們是由15K邊連接），並具有性能雖然我媒體鏈接問題只要我能，現在最後一招是優化數據結構優化我的算法：

def single_pass_build(nodes): 
    for node in nodes: 
     if node.__class__ in listOfRequiredClasses: 
      children = get_children(node) 
      for child in children: 
       if child__class__ in listOfRequiredClasses: 
        add_edge(node, child) 

def get_children(node): 
    return [attr for attr in node.__dict__.values() if attr.__class__ in listOfRequiredClasses]

我還是要關心我add_connection功能，但即使沒有它我的程序需要略微超過10分鐘，不過這個迭代。爲了比較：我得到數據的模塊在不超過5秒的時間內從xml文檔生成數據。我總共有44K對象，每個對象代表一個關係圖中的一個節點。我得到的對象有很多屬性，所以我可以嘗試優化get_children以瞭解每個類的所有相關屬性，或者只是加快查找速度。列表取O（n）（所以如果a是數字的屬性，並且k是我列表中的類的數量，則我得到總數爲O（n = a k + m a k））。我的許多屬性類不在該列表中，因此我接近最壞的情況而不是平均值。我想從O（k）的加速查找，以O（1）或至少爲O（log（k））的

問題

明知字典的鍵查找應該是O（日誌（n））對於許多散列衝突並且（很少）沒有散列衝突，它變成（幾乎）靜態的。在我不關心任何值的情況下，我想知道是否存在針對x in list優化的（哈希）列表？
我可以使用帶有None值的字典，但將來可以使用總共70000個查找和更大的圖表，而每個毫秒的數字都可以。這裏的空間並不是什麼大問題，因爲我預計總共有50班，絕不超過上百班。在其他情況下，空間也可能是一個問題。

我不認爲答案是在標準的Python，但maby有人知道一個共同的框架，可以幫助或可以讓我相信，沒有任何理由，爲什麼我不能使用字典的工作。

來源

2017-05-31 hajef

你需要['set']（https://docs.python.org/2/library/ stdtypes.html＃set） –

你想要的內置set類型：https://docs.python.org/2/library/stdtypes.html#set

而且是其採用的是標準的Python）

來源

2017-05-31 10:54:05

回答了我的問題，但沒有解決我的問題。好像我低估了未使用屬性的數量，同時高估了班級名單。在我改變'get_children'來學習每個類的有用屬性之後（當然，希望它們每次都是相同的 - 必須測試它！）我需要不到一秒鐘的時間。引入該集合沒有相關的影響（看起來像班級名單畢竟是微小的），但我會保持該集合的可擴展性的原因，並在程序的其他地方使用它，我存儲了一些K的entrys，它會* * 做出改變。謝謝 – hajef

似乎空字典和空集之間沒有區別，這讓我懷疑字典是否是其他字符集。現在我想知道如果我不打算成爲字典，我是否仍然可以使用一套存儲對。 ......可能會更好，但事實並非如此。 – hajef

在語義上，一個'dict'實際上是一個無序的鍵值對 - 實際上甚至是官方定義的一部分（https://docs.python.org/2/tutorial/datastructures.html#dictionaries） - 與（這也是正式定義的一部分）。實際上他們都是基於哈希表，所以你也可以把集合看作「無價值」的字典。 –

Python中是否存在任何類型的散列表

背景

回答

相關問題