使用十进制表示法引用多维数组

Question

性能方面（C ++），使用小数位前引用第一行的数字以及引用该列的小数位后面的数字来访问数组会更快（和/或接受）吗？

例如：

map<float,int> myarray;
myarray[1.0001]=4;
myarray[1.0002]=5;
myarray[1.0003]=2;
myarray[2.0001]=7;
myarray[2.0002]=6;
myarray[2.0003]=3;

VS：

int myarray[100][1000];
myarray[1][1]=4;
myarray[1][2]=5;
myarray[1][3]=2;
myarray[2][1]=7;
myarray[2][2]=6;
myarray[2][3]=3;

Answer 1

首先，除了可以完全表示为floats的特定十进制数的子集之外，您的方法不起作用。例如，1.0001实际上表示为1.00010001659393310546875，所以如果你计算你的索引，你可能得到一个不相符的略有不同的表示;这将导致访问map的假阴性。

就性能而言，你的map将是O（log2 n），而访问2D数组将是O（1）。此外，它也将占用更多内存，因为树为树节点占用空间，而数组则无需开销。