作者semop (semop)
看板CSSE
標題Re: [問題] 陣列的替代品
時間Sat Mar 21 16:48:35 2009
※ 引述《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
→ xam:這個好像是正解耶... 03/21 21:49
推 ledia:那 C 不花空間嗎? 03/23 17:02
推 demintree:這樣子不對吧...沒有塞進B的數字不就永遠都查不到了? 04/04 01:27
→ demintree:cache的機制建立在上層查不到會跑到下一層去找資料 04/04 01:28
→ demintree:所以A的空間依然是O(n)+B的空間O(m)+C的空間? 04/04 01:29
→ semop:文內已經說了要把原始資料丟棄 這種應用本來就存在 04/04 09:54
→ semop:等於是資料重整 例如全文檢索的索引就可能會用到這樣的做法 04/04 10:00
→ semop:而陣列 C 需要的資料空間相對較少 所以才說足夠小的 m 值 04/04 10:03
→ semop:例如陣列 A 用 int, 陣列 C 用 short int, m 值為 32768 04/04 10:06
→ semop:當陣列 A 的資料數大於 65536 時 B+C 的空間就會減少 04/04 10:08
推 ledia:C 也用 O(n) 吧.... 04/06 10:41