我在C中实现了一个灵活的数组。所有的想法都是基于这个小的AA>。
我的错误是索引操作。已经很久没承认了。寻求有知识的头脑和眼睛。
概述:
数据结构由一个平面索引块组成,该块保存指向数据块的指针每个数据块的大小为2^(k/2)。其中k是前导设置位。所以当我搜索元素“i”时,k是log 2(i+1)。
index = {
[0], -> [0]
[2], -> [0,1]
[2], -> [0,1]
[3], -> [0,1,2,3]
[4], -> [0,1,2,3]
....}
每个数据块的大小由其聚集到的“超级块”决定其中超级块由具有相同大小的数据块组成。所以。索引1、2位于同一个超级块(超级块1)中。而0(超级块0)和索引3(超级块2)则不是。
最后,每个超级块都有2^(floor(k/2))个数据块,每个数据块的大小都是2^(ceil(k/2))。
问题
当r=2的幂时,索引跳过应该是什么。
就像我搜索3时,它应该是
index [2][0]
,而不是它的index[3][0]
。为什么会这样?有没有办法避免是不是有一个我看不到的“1比1”错误??
守则
这里有一个单一的主函数Paper,它清晰而简单,当试图在索引3处获取元素时失败;
定位索引i的简化代码如下:
/* Edited from the actual test case for extra clarity */
/* all vars int */
r= i+1
k = first_set_bit(r) - 1; // ex: r = 5, 5 = "00000101"b so k is (3-1) = 2
b = first_subset_of_r(floor(k/2)); // floor(k/2) bits of r immediately after first set;
e = last_subset_of_r(ceil(k/2); // last ceil(k/2) bits of r
p = (1 << k) -1 ; // 2^k -1
// Index supposed to be found with. . .
return index[p+b][e];
下面是一些实际输出,首先通过索引和数据块打印数组的内容,然后将4个trys的输出放入索引
第一部分转储2d数组,其中条前的数字是索引块的索引,后一部分是索引块指向的数组中包含的元素。所有数组都是零索引的。
[clemensm@gaia:23]> ./a.out
Index block | element number (Not it's index!)
0 | 0
1 | 1 2
2 | 3 4
3 | 5 6
4 | 7 8 9 10
5 | 11 12 13 14
6 | 15 16 17 18
7 | 19 20 21 22
8 | 23 24 25 26
9 | 27 28 29 30
10 | 31 32 33 34 35 36 37 38
11 | 39 40 41 42 43 44 45 46
12 | 47 48 49 50 51 52 53 54
13 | 55 56 57 58 59 60 61 62
14 | 63 64 65 66 67 68 69 70
15 | 71 72 73 74 75 76 77 78
16 | 79 80 81 82 83 84 85 86
17 | 87 88 89 90 91 92 93 94
18 | 95 96 97 98 99 100 101 102
19 | 103 104 105 106 107 108 109 110
Finished element dump
Trying to get 0
R: [1]b
k/2=[0], Ceil(k,2)=[0]
K: [0] is the leading 1 bit
B: [0]
E: [0]
P: [0] data blocks prior to our superblock
p+b,e : [0,0]
Trying to get 1
R: [10]b
k/2=[0], Ceil(k,2)=[1]
K: [1] is the leading 1 bit
B: [0]
E: [0]
P: [1] data blocks prior to our superblock
p+b,e : [1,0]
Trying to get 2
R: [11]b
k/2=[0], Ceil(k,2)=[1]
K: [1] is the leading 1 bit
B: [0]
E: [1]
P: [1] data blocks prior to our superblock
p+b,e : [1,1]
Trying to get 3
R: [100]b
k/2=[1], Ceil(k,2)=[1]
K: [2] is the leading 1 bit
B: [0]
E: [0]
P: [3] data blocks prior to our superblock
p+b,e : [3,0]
a.out: test_array.c:81: main: Assertion `get_index(3)==3' failed.
Abort (core dumped)
最佳答案
只是为了搜索引擎和clearity,论文名:Resizable Arrays in Optimal Time and Space
据我在报纸上看到的,你可以在这里做一个非常基本的体验即使这是一篇好看的论文,也可能有错误。
定位算法显然是错误的。声称计算SB_k
之前的数据块数的第3行不能这样工作。你已经在上面的例子中看到了这一点。
我建议你自己找出公式,然后继续阅读。
我的分析表明这个公式:
p = 2^(k/2 + 1) - 2 + (k mod 2) * 2^(k/2) # "/" indicates integer division
示例代码:
int max = 20;
for (int k = 0; k < max; k++)
System.out.println("k=" + k + " - data blocks: " + Math.pow(2, k/2) + " - data blocks size: " + Math.pow(2, Math.ceil(k/2.0)));
System.out.println();
for (int i = 0; i < max; i++) {
String r = Integer.toBinaryString(i + 1);
int k = r.length() - 1;
String b_bin = r.substring(1, 1 + k/2);
int b = Integer.parseInt("0" + b_bin, 2);
String e_bin = r.substring((int)Math.ceil(k / 2.0));
int e = Integer.parseInt("0" + e_bin, 2);
int p = (1 << (k/2 + 1)) - 2 + (k & 1) * (1 << (k/2));
int db = p + b;
System.out.println("i=" + i + ", r=" + r + ", k=" + k + ", b_bin=" + b_bin + ", b=" + b + ", e_bin=" + e_bin + ", e=" + e + ", p=" + p + ", db=" + db);
}
样本结果:
k=0 - data blocks: 1.0 - data blocks size: 1.0
k=1 - data blocks: 1.0 - data blocks size: 2.0
k=2 - data blocks: 2.0 - data blocks size: 2.0
k=3 - data blocks: 2.0 - data blocks size: 4.0
k=4 - data blocks: 4.0 - data blocks size: 4.0
k=5 - data blocks: 4.0 - data blocks size: 8.0
k=6 - data blocks: 8.0 - data blocks size: 8.0
k=7 - data blocks: 8.0 - data blocks size: 16.0
k=8 - data blocks: 16.0 - data blocks size: 16.0
k=9 - data blocks: 16.0 - data blocks size: 32.0
k=10 - data blocks: 32.0 - data blocks size: 32.0
k=11 - data blocks: 32.0 - data blocks size: 64.0
k=12 - data blocks: 64.0 - data blocks size: 64.0
k=13 - data blocks: 64.0 - data blocks size: 128.0
k=14 - data blocks: 128.0 - data blocks size: 128.0
k=15 - data blocks: 128.0 - data blocks size: 256.0
k=16 - data blocks: 256.0 - data blocks size: 256.0
k=17 - data blocks: 256.0 - data blocks size: 512.0
k=18 - data blocks: 512.0 - data blocks size: 512.0
k=19 - data blocks: 512.0 - data blocks size: 1024.0
i=0, r=1, k=0, b_bin=, b=0, e_bin=1, e=1, p=0, db=0
i=1, r=10, k=1, b_bin=, b=0, e_bin=0, e=0, p=1, db=1
i=2, r=11, k=1, b_bin=, b=0, e_bin=1, e=1, p=1, db=1
i=3, r=100, k=2, b_bin=0, b=0, e_bin=00, e=0, p=2, db=2
i=4, r=101, k=2, b_bin=0, b=0, e_bin=01, e=1, p=2, db=2
i=5, r=110, k=2, b_bin=1, b=1, e_bin=10, e=2, p=2, db=3
i=6, r=111, k=2, b_bin=1, b=1, e_bin=11, e=3, p=2, db=3
i=7, r=1000, k=3, b_bin=0, b=0, e_bin=00, e=0, p=4, db=4
i=8, r=1001, k=3, b_bin=0, b=0, e_bin=01, e=1, p=4, db=4
i=9, r=1010, k=3, b_bin=0, b=0, e_bin=10, e=2, p=4, db=4
i=10, r=1011, k=3, b_bin=0, b=0, e_bin=11, e=3, p=4, db=4
i=11, r=1100, k=3, b_bin=1, b=1, e_bin=00, e=0, p=4, db=5
i=12, r=1101, k=3, b_bin=1, b=1, e_bin=01, e=1, p=4, db=5
i=13, r=1110, k=3, b_bin=1, b=1, e_bin=10, e=2, p=4, db=5
i=14, r=1111, k=3, b_bin=1, b=1, e_bin=11, e=3, p=4, db=5
i=15, r=10000, k=4, b_bin=00, b=0, e_bin=000, e=0, p=6, db=6
i=16, r=10001, k=4, b_bin=00, b=0, e_bin=001, e=1, p=6, db=6
i=17, r=10010, k=4, b_bin=00, b=0, e_bin=010, e=2, p=6, db=6
i=18, r=10011, k=4, b_bin=00, b=0, e_bin=011, e=3, p=6, db=6
i=19, r=10100, k=4, b_bin=01, b=1, e_bin=100, e=4, p=6, db=7
编辑:有关公式的方法的详细信息
如何得到公式(我建议你读每一步,如果你能自己继续,如果不能继续走):
报纸上说:
"When superblock SB_k is fully allocated, it consists of 2^floor(k/2) data blocks"
如果我们想在sb_k之前得到数据块的数量,我们必须对所有数据块求和:
p = sum from i=0 to k-1 over 2^floor(i/2)
我们现在可以使用这个了,这是一个明确的for循环语句。但让我们做一个单一的计算。
如果你考虑一下总数,它是每2^i加两次,因为地板这对所有的k都是正确的,因为最大和是不均匀的,所以我们有
floor((k-2)/2) = floor((k-1)/2)
。对于奇数k,我们只有一个数字,我们必须分别考虑这个。
所以,我们现在:
(2 * sum from i=0 to floor((k-2)/2) over 2^i) + (k mod 2)*2^k/2
(如果需要更多详细信息,请举例说明k=6、7、8)
现在,我们可以清楚地去掉和,因为我们知道
sum from i=0 to n over 2^i = 2^(n+1) - 1
(这是一个基本的数学/cs证明。您可以从二进制表示清楚地看到正确性)我们用这个公式得到:2 * (2^(floor((k-2)/2) + 1) - 1) + (k mod 2)*2^k/2
现在,我们可以乘以2,修改指数,就完成了:
2^(floor(k/2) + 1) - 2 + (k mod 2)*2^k/2
希望能帮上忙。
关于c - 灵活的数组,最佳空间,索引错误,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13128064/