发信人: Fluorina(惊现 Bug·我爱东北), 信区: Algorithm
标 题: Finding in list with small "holes"?
发信站: 饮水思源 (2014年04月05日13:27:16 星期六), 站内信件
Data stored like this:
stored index 0 1 2 3 4 5 6 7 8 ...
logic index 13 14 15 19 20 21 22 23 24 ...
data .......................................
stored index is the natural number sequence. logic index is also natural
number, starts at any number, is mostly continuous but with some small
"holes" in it. Hole length is expected to be less than 10. Total number
of holes is roughly one in 0.1 million items.
Random access to data by stored index is O(1) but slow.
Now I want random access by logic index.
I used an offset that updates with each finding operation, but it does not
handle errors, e.g. find 17 in the above list.
Any ideas besides binary searching?
--
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 202.120.55.140]
标 题: Finding in list with small "holes"?
发信站: 饮水思源 (2014年04月05日13:27:16 星期六), 站内信件
Data stored like this:
stored index 0 1 2 3 4 5 6 7 8 ...
logic index 13 14 15 19 20 21 22 23 24 ...
data .......................................
stored index is the natural number sequence. logic index is also natural
number, starts at any number, is mostly continuous but with some small
"holes" in it. Hole length is expected to be less than 10. Total number
of holes is roughly one in 0.1 million items.
Random access to data by stored index is O(1) but slow.
Now I want random access by logic index.
I used an offset that updates with each finding operation, but it does not
handle errors, e.g. find 17 in the above list.
Any ideas besides binary searching?
--
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 202.120.55.140]
No comments:
Post a Comment