隨機訪問

與隨機訪問相比順序訪問

隨機訪問(更精確,更普遍地稱為直接訪問)是能夠在相等時間或從一個人群中訪問序列的任意元素可尋址元素與其他任何元素一樣容易有效,無論該集合中有多少個要素。在計算機科學通常形成對比順序訪問這需要以存儲的順序檢索數據。

例如,數據可以在概念上存儲在一個序列中,例如一行,在表面上的行和列之類的二維或多個維度。但是,鑑於所有坐標,一個程序可以像其他任何人一樣快速,輕鬆地訪問每個記錄。從這個意義上講,基準的選擇是任意的,因為無論尋找哪個項目,要找到它所需的所有內容都是其地址,即其所在的坐標,例如其行和列(或它跟踪和記錄號磁鼓)。首先,使用“隨機訪問”一詞,因為無論需要哪種順序,該過程都必須能夠查找記錄。[1]但是,很快“直接訪問”一詞獲得了青睞,因為無論其位置如何,都可以直接檢索記錄。[2]但是,操作屬性是該設備可以立即按需訪問任何必需的記錄。相反順序訪問,其中遠程元素需要更長的時間訪問。[3]

這種區別的典型例證是比較一個古老的滾動(順序;必須在所需數據之前的所有材料都必須展開)和(直接:可以立即向任何任意開放)。一個更現代的例子是盒式錄像帶(順序 - 必須通過早期的歌曲前進才能獲得後來的歌曲)和一個光盤(直接訪問 - 知道那將是檢索到的人,可以跳過想要的賽道。

數據結構,直接訪問意味著能夠訪問任何條目列表恆定時間(獨立於其在列表和列表的大小中的位置)。很少有數據結構可以提供此保證數組(以及相關的結構動態陣列)。在許多算法中,需要直接訪問或至少有價值的訪問二進制搜索整數排序,或某些版本的eRatosthenes的篩子.[4]

其他數據結構,例如鏈接列表,犧牲直接訪問以允許有效插入,刪除或重新排序數據。自平衡二進制搜索樹可以提供可接受的折衷方案,其中收集的所有成員的訪問時間不相等,但是檢索給定成員的最大時間才會增長對數與它的大小。

參考

  1. ^國家計算機會議與博覽會(1957年)。程序。檢索10月2日2013.
  2. ^國際商業機器公司。數據處理部(1966)。IBM直接訪問存儲設備和組織方法簡介。國際商業機器公司。 pp。3–。檢索10月2日2013.
  3. ^“隨機和順序數據訪問”.
  4. ^D. E. Knuth(1969)。計算機編程的藝術。卷。 3.分類和搜索。 Addison-Wesley。ISBN978-0-201-03803-3。檢索10月2日2013.

也可以看看