作者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
1F：→ xam:这个好像是正解耶... 03/21 21:49
2F：推 ledia:那 C 不花空间吗? 03/23 17:02
3F：推 demintree:这样子不对吧...没有塞进B的数字不就永远都查不到了? 04/04 01:27
4F：→ demintree:cache的机制建立在上层查不到会跑到下一层去找资料 04/04 01:28
5F：→ demintree:所以A的空间依然是O(n)+B的空间O(m)+C的空间? 04/04 01:29
6F：→ semop:文内已经说了要把原始资料丢弃 这种应用本来就存在 04/04 09:54
7F：→ semop:等於是资料重整 例如全文检索的索引就可能会用到这样的做法 04/04 10:00
8F：→ semop:而阵列 C 需要的资料空间相对较少 所以才说足够小的 m 值 04/04 10:03
9F：→ semop:例如阵列 A 用 int, 阵列 C 用 short int, m 值为 32768 04/04 10:06
10F：→ semop:当阵列 A 的资料数大於 65536 时 B+C 的空间就会减少 04/04 10:08
11F：推 ledia:C 也用 O(n) 吧.... 04/06 10:41