看板 CSSE 關於我們 聯絡資訊
※ 引述《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