Re: [問題] 陣列的替代品
※ 引述《snobbery (egoist)》之銘言：
: 如果我有一個n items的陣列A,
: 每個item都是0 ~ q之間的數值,
: 那可以知道要存下這個陣列要花O(n)的儲存空間,
: (嚴格來說, 是log(q)*n bits)
: 然後每次我要查詢第i個位置的item的話, 我需要花的時間是O(1),
: (反正下個A[i]的指令就馬上取到i-th item的值)
: 現在, 如果我想把儲存空間降到o(n),
: 但是也許可以允許查詢item有錯誤, 或是查詢時間可以不是constant time的話,
: 不知道有沒有這樣的data structure可以完成這樣的事情?
: thx
那就做一個較小的有 m 個資料的陣列 B
按照某種排序方式（相同資料的出現數目或查詢次數等等）
將 A 的資料的依序填入
並建立陣列 C 使得 C[n] < m 時, B[C[n]] == A[n]
於是只要足夠小的 m 值，就能減少資料所需空間
簡單來說，這樣的資料結構當然存在，它的名字就叫做 cache.
你的問題就是如何製作 cache 然後把原始資料丟棄
所以請去找 cache 相關資料即可
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.137.180.66
→
03/21 21:49, , 1F
03/21 21:49, 1F
推
03/23 17:02, , 2F
03/23 17:02, 2F
推
04/04 01:27, , 3F
04/04 01:27, 3F
→
04/04 01:28, , 4F
04/04 01:28, 4F
→
04/04 01:29, , 5F
04/04 01:29, 5F
→
04/04 09:54, , 6F
04/04 09:54, 6F
→
04/04 10:00, , 7F
04/04 10:00, 7F
→
04/04 10:03, , 8F
04/04 10:03, 8F
→
04/04 10:06, , 9F
04/04 10:06, 9F
→
04/04 10:08, , 10F
04/04 10:08, 10F
推
04/06 10:41, , 11F
04/06 10:41, 11F
討論串 (同標題文章)