我聽說當數據限制存儲在磁盤而不是主內存時,嘗試比散列表效率低。爲什麼會這樣呢?爲什麼在存儲在磁盤上時嘗試比散列表慢?
2
A
回答
3
在磁盤上,隨機存取速度很慢,因爲要讀取特定位置的字節,硬盤驅動器必須物理旋轉才能將這些字節放在讀取頭下。磁盤上隨機訪問的成本可能比同等訪問RAM慢數百萬倍。
最重要的是,無論何時從磁盤讀取數據,都會從磁盤中讀取稱爲頁的內存塊,而不僅僅是要求的字節。這意味着如果您從磁盤讀取一些數據,訪問該字節附近的字節可能會非常快,因爲該數據將從同一頁面讀取並加載到RAM中。這意味着磁盤陣列中的順序存取速度會很快,因爲在第一次(緩慢)讀取以獲取讀取第一個數組元素的字節後,下一個數組元素的字節可能已經被加載並可用。
想想這對於嘗試與線性探測哈希表意味着什麼。一個trie是一個樹結構,在這個結構中,查找需要很多指向內存中沒有特定順序的節點的指針。這意味着查詢字典查找的成本可能是字符串的每個字符讀取的一個磁盤,這非常低效。另一方面,如果你有一個使用線性探測的散列表,查找的代價將(大致)成爲一個磁盤讀取的成本,因爲在查找表中的初始位置後,數組應該是數組讀取的位置不需要將來的磁盤讀取。
請注意,並非所有嘗試和所有散列表都具有此屬性。緩存遺忘嘗試是特別構建的嘗試,以最大限度地減少磁盤讀取,並且在外部存儲器中可以非常快速。許多散列表(如鏈式散列表或雙散列表)具有更分散的查找模式,因此會導致更多的磁盤讀取。
希望這會有所幫助!
+0
它幾乎消除了懷疑! – rocker
相關問題
- 1. 爲什麼不能在散列表中存儲散列表?
- 2. Spark shuffle爲什麼在磁盤上存儲中間數據?
- 3. 存儲在磁盤上的HashMap從磁盤迴讀非常緩慢
- 4. Java Script對象存儲在磁盤上的位置是什麼?
- 5. InnoDB沒有在磁盤上存儲什麼值?
- 6. 將會話存儲在磁盤上
- 7. Django:在磁盤上存儲InMemoryUploadedFile
- 8. 在磁盤或MongoDB上存儲文件
- 9. 爲什麼在散列表鍵上存在空白?
- 10. 什麼時候在iOS上清除磁盤緩存?
- 11. 爲什麼在連接列表時Enum.concat比++慢得多?
- 12. 爲什麼Redis Hash Bucket保存磁盤?
- 13. RDFlib'磁盤'存儲
- 14. RavenDB磁盤存儲
- 15. 在Java中將對象存儲在磁盤上的最佳方式是什麼?
- 16. 列表保存到磁盤上
- 17. Sesame 2.7在磁盤上存儲本地存儲庫?
- 18. 爲什麼jvm重啓後ehcache磁盤存儲失效?
- 19. 如何在磁盤上存儲長文本列?
- 20. Flash - 關閉IE時爲什麼我的SharedObject不能保存在磁盤上?
- 21. 在Azure Linux VM中,什麼存在?什麼磁盤收費?
- 22. 什麼是可以存儲在使用inode和磁盤塊的磁盤上的最大文件大小
- 23. 爲什麼Android中的磁盤上的位圖大小比內存大?
- 24. 爲什麼在嘗試將QSslSocket存儲在QScopedPointer中時發生bps_remove_fd失敗?
- 25. 保存與列表列的磁盤到磁盤
- 26. 磁盤存儲的陣列等
- 27. WebClient的緩存駐留在磁盤上的什麼位置?
- 28. 爲什麼內存沒有在C#在磁盤上寫入文件後釋放
- 29. 在磁盤中存儲圖像
- 30. NSURLCache在iOS 5中的磁盤存儲?
據說在哪裏? –
閱讀嘗試在維基頁面嘗試的應用程序。我不認爲從硬盤訪問也會有太大的區別 – rocker
這部分是由* can *限定的,並且有引用。 – delnan