好吧，这里是我的情况：
- 我有一个功能-比方说
U64 calc (U64 x) -这需要一个64位的整数的参数，执行某些CPU密集型操作，并返回一个64位的值 - 现在，因为我知道所有可能的输入（
x s）表示函数事先的（也有一些16000虽然），我想这可能是更好的预先计算它们，然后取他们的需求（从阵列状结构）。 - 理想的情况是它们都存储在一些阵列
U64 CALC[]和索引（检索这些x再次） - 而这里的问题：我可以知道我的计算功能可能的输入是什么，但他们绝对不是连续的 （例如，不从1到16000，但可能会低至0和高一些万亿价值观-总是withing 64位范围）
EG
X CALC[X]
-----------------------
123123 123123123
12312 12312312
897523 986123
etc.
在这里，我的问题是：
- 你将如何保存呢？
- 你喜欢什么解决方法吗？
- 现在，因为这些值（从
CALC ） 将要访问几千到几百万次，每秒 ，这将是最好的解决方案的性能代价？
注 ：我没有提任何东西，我想还是尝试，以免转成答案对B型的，事情的一些争论，而且大多不会影响任何人...
我会用某种散列函数创建一个索引到U64对，其中一个关键是从创造的价值和其他替代值。 从技术上讲，指数可能是三个字节长（假设1600万 - “16000000” - 对）如果你需要节省空间，但我会用u32s。 如果存储的值不匹配计算上（哈希冲突）的值，您需要输入溢出处理程序。
- 您需要确定一个自定义的哈希算法，以适应您的数据
- 既然你知道数据的大小，你并不需要的算法，让数据增长。
- 我会警惕使用一些标准算法，因为他们很少满足特定数据
- 除非你是确保代码是所见即所得（不产生很多无形的电话），我会谨慎使用C ++的方法
- 你的指数应该比对的数量大25％
通过所有可能的输入运行，并确定最小值，最大值，对于冲突的数量平均值和标准偏差，并使用这些来确定可接受的性能水平。 然后文件，以达到最佳的代码。
所需的存储器空间（使用U32指数）出来到（4 * 1.25）每对或336 MEB，典型的PC机上没有问题+ 8 + 8 = 21个字节。
________ EDIT________
我一直在质疑的“RocketRoy”把我的钱用在我的嘴。 开始：
这个问题有一个（固定大小）哈希索引冲突处理的事情。 要设置阶段：
- 我有n个条目的列表，其中的条目中的字段包含散列计算，从V值
- 我有N * 1.25（大约）的indeces的载体中，使得的indeces x的数量是素数
- 素数y计算，其是x的分数
- 矢量被初始化为-1说表示没人住
非常标准的东西，我想你会同意。
在列表中的条目进行处理和计算并modulo'd和用作索引到载体和索引条目的散列值h被放在那里。
最后，我遇到这样的向量入口指向索引被占用的情况（不包含-1） - 瞧，碰撞。
所以，我该怎么办？ 我保持原来的H作为浩，Y添加到小时，取模x，并得到一个新的索引到载体中。 如果该项未占用我使用它，否则我继续加上y模x直到我到达豪。 从理论上讲，这不会发生，因为x和y是质数。 在实践中，x是大于n所以它不会。
因此，“重新哈希”那RocketRoy声称是非常昂贵的是没有这样的事情。
与所有哈希方法 - - 用这种方法最棘手的部分是：
- 确定对于x的适当值（变小棘手X越大最终使用）
- 确定的算法的为H = A（V）％×使得合理均匀（“随机地”）转换成具有少碰撞尽可能索引向量的H的指数
- 确定用于Y，使得碰撞索引一个合适的值相当均匀（“随机地”）插入索引向量
________ EDIT________
对不起，我已经采取了这么久才产生这个代码...其他的东西有较高的优先级。
总之，这里是证明散列具有快速查找比一个二叉树前景更好的代码。 它贯穿一堆散列索引大小和算法寻找该特定数据的最合适的组合，以帮助的。 对于每一个算法的代码将打印所述第一索引大小应使得不查找时间比14次的搜索（最坏的情况下为二进制搜索）和平均查找时间小于1.5的搜索。
我对这些类型的应用程序素数的喜爱，如果你还没有注意到。
有创造，其强制性溢出处理哈希算法的许多方面。 我选择了简单假设它会转化为速度......它确实。 在我的笔记本电脑与酷睿i5 480中号2.67 @千兆赫的平均查找需要55到60个时钟周期（出来以每秒约4500万的查询）。 我实现了一个特殊的get操作具有恒定数量的indeces和同上翻版值和周期计数下降到40（每秒65000000个查询）。 如果你看看行调用getOpSpec我相异或0x444到索引行使缓存，实现更“真实世界”般的结果。
我必须再次指出，该方案提出了具体的数据适当组合。 其他数据可能需要不同的组合。
的源代码包含两个用于产生16000无符号长长对和用于测试不同的常数（索引的大小和翻版值）的代码：
#include <windows.h>
#define i8 signed char
#define i16 short
#define i32 long
#define i64 long long
#define id i64
#define u8 char
#define u16 unsigned short
#define u32 unsigned long
#define u64 unsigned long long
#define ud u64
#include <string.h>
#include <stdio.h>
u64 prime_find_next (const u64 value);
u64 prime_find_previous (const u64 value);
static inline volatile unsigned long long rdtsc_to_rax (void)
{
unsigned long long lower,upper;
asm volatile( "rdtsc\n"
: "=a"(lower), "=d"(upper));
return lower|(upper<<32);
}
static u16 index[65536];
static u64 nindeces,rehshFactor;
static struct PAIRS {u64 oval,rval;} pairs[16000] = {
#include "pairs.h"
};
struct HASH_STATS
{
u64 ninvocs,nrhshs,nworst;
} getOpStats,putOpStats;
i8 putOp (u16 index[], const struct PAIRS data[], const u64 oval, const u64 ci)
{
u64 nworst=1,ho,h,i;
i8 success=1;
++putOpStats.ninvocs;
ho=oval%nindeces;
h=ho;
do
{
i=index[h];
if (i==0xffff) /* unused position */
{
index[h]=(u16)ci;
goto added;
}
if (oval==data[i].oval) goto duplicate;
++putOpStats.nrhshs;
++nworst;
h+=rehshFactor;
if (h>=nindeces) h-=nindeces;
} while (h!=ho);
exhausted: /* should not happen */
duplicate:
success=0;
added:
if (nworst>putOpStats.nworst) putOpStats.nworst=nworst;
return success;
}
i8 getOp (u16 index[], const struct PAIRS data[], const u64 oval, u64 *rval)
{
u64 ho,h,i;
i8 success=1;
ho=oval%nindeces;
h=ho;
do
{
i=index[h];
if (i==0xffffu) goto not_found; /* unused position */
if (oval==data[i].oval)
{
*rval=data[i].rval; /* fetch the replacement value */
goto found;
}
h+=rehshFactor;
if (h>=nindeces) h-=nindeces;
} while (h!=ho);
exhausted:
not_found: /* should not happen */
success=0;
found:
return success;
}
volatile i8 stop = 0;
int main (int argc, char *argv[])
{
u64 i,rval,mulup,divdown,start;
double ave;
SetThreadAffinityMask (GetCurrentThread(), 0x00000004ull);
divdown=5; //5
while (divdown<=100)
{
mulup=3; // 3
while (mulup<divdown)
{
nindeces=16000;
while (nindeces<65500)
{
nindeces= prime_find_next (nindeces);
rehshFactor=nindeces*mulup/divdown;
rehshFactor=prime_find_previous (rehshFactor);
memset (index, 0xff, sizeof(index));
memset (&putOpStats, 0, sizeof(struct HASH_STATS));
i=0;
while (i<16000)
{
if (!putOp (index, pairs, pairs[i].oval, (u16) i)) stop=1;
++i;
}
ave=(double)(putOpStats.ninvocs+putOpStats.nrhshs)/(double)putOpStats.ninvocs;
if (ave<1.5 && putOpStats.nworst<15)
{
start=rdtsc_to_rax ();
i=0;
while (i<16000)
{
if (!getOp (index, pairs, pairs[i^0x0444]. oval, &rval)) stop=1;
++i;
}
start=rdtsc_to_rax ()-start+8000; /* 8000 is half of 16000 (pairs), for rounding */
printf ("%u;%u;%u;%u;%1.3f;%u;%u\n", (u32)mulup, (u32)divdown, (u32)nindeces, (u32)rehshFactor, ave, (u32) putOpStats.nworst, (u32) (start/16000ull));
goto found;
}
nindeces+=2;
}
printf ("%u;%u\n", (u32)mulup, (u32)divdown);
found:
mulup=prime_find_next (mulup);
}
divdown=prime_find_next (divdown);
}
SetThreadAffinityMask (GetCurrentThread(), 0x0000000fu);
return 0;
}
这是不可能包括所产生的对文件（一个答案明确限定为30000个字符）。 但是，将消息发送到我的收件箱，我会寄出。
而这些结果如下：
3;5;35569;21323;1.390;14;73
3;7;33577;14389;1.435;14;60
5;7;32069;22901;1.474;14;61
3;11;35107;9551;1.412;14;59
5;11;33967;15427;1.446;14;61
7;11;34583;22003;1.422;14;59
3;13;34253;7901;1.439;14;61
5;13;34039;13063;1.443;14;60
7;13;32801;17659;1.456;14;60
11;13;33791;28591;1.436;14;59
3;17;34337;6053;1.413;14;59
5;17;32341;9511;1.470;14;61
7;17;32507;13381;1.474;14;62
11;17;33301;21529;1.454;14;60
13;17;34981;26737;1.403;13;59
3;19;33791;5333;1.437;14;60
5;19;35149;9241;1.403;14;59
7;19;33377;12289;1.439;14;97
11;19;34337;19867;1.417;14;59
13;19;34403;23537;1.430;14;61
17;19;33923;30347;1.467;14;61
3;23;33857;4409;1.425;14;60
5;23;34729;7547;1.429;14;60
7;23;32801;9973;1.456;14;61
11;23;33911;16127;1.445;14;60
13;23;33637;19009;1.435;13;60
17;23;34439;25453;1.426;13;60
19;23;33329;27529;1.468;14;62
3;29;32939;3391;1.474;14;62
5;29;34543;5953;1.437;13;60
7;29;34259;8263;1.414;13;59
11;29;34367;13033;1.409;14;60
13;29;33049;14813;1.444;14;60
17;29;34511;20219;1.422;14;60
19;29;33893;22193;1.445;13;61
23;29;34693;27509;1.412;13;92
3;31;34019;3271;1.441;14;60
5;31;33923;5449;1.460;14;61
7;31;33049;7459;1.442;14;60
11;31;35897;12721;1.389;14;59
13;31;35393;14831;1.397;14;59
17;31;33773;18517;1.425;14;60
19;31;33997;20809;1.442;14;60
23;31;34841;25847;1.417;14;59
29;31;33857;31667;1.426;14;60
3;37;32569;2633;1.476;14;61
5;37;34729;4691;1.419;14;59
7;37;34141;6451;1.439;14;60
11;37;34549;10267;1.410;13;60
13;37;35117;12329;1.423;14;60
17;37;34631;15907;1.429;14;63
19;37;34253;17581;1.435;14;60
23;37;32909;20443;1.453;14;61
29;37;33403;26177;1.445;14;60
31;37;34361;28771;1.413;14;59
3;41;34297;2503;1.424;14;60
5;41;33587;4093;1.430;14;60
7;41;34583;5903;1.404;13;59
11;41;32687;8761;1.440;14;60
13;41;34457;10909;1.439;14;60
17;41;34337;14221;1.425;14;59
19;41;32843;15217;1.476;14;62
23;41;35339;19819;1.423;14;59
29;41;34273;24239;1.436;14;60
31;41;34703;26237;1.414;14;60
37;41;33343;30089;1.456;14;61
3;43;34807;2423;1.417;14;59
5;43;35527;4129;1.413;14;60
7;43;33287;5417;1.467;14;61
11;43;33863;8647;1.436;14;60
13;43;34499;10427;1.418;14;78
17;43;34549;13649;1.431;14;60
19;43;33749;14897;1.429;13;60
23;43;34361;18371;1.409;14;59
29;43;33149;22349;1.452;14;61
31;43;34457;24821;1.428;14;60
37;43;32377;27851;1.482;14;81
41;43;33623;32057;1.424;13;59
3;47;33757;2153;1.459;14;61
5;47;33353;3547;1.445;14;61
7;47;34687;5153;1.414;13;59
11;47;34519;8069;1.417;14;60
13;47;34549;9551;1.412;13;59
17;47;33613;12149;1.461;14;61
19;47;33863;13687;1.443;14;60
23;47;35393;17317;1.402;14;59
29;47;34747;21433;1.432;13;60
31;47;34871;22993;1.409;14;59
37;47;34729;27337;1.425;14;59
41;47;33773;29453;1.438;14;60
43;47;31253;28591;1.487;14;62
3;53;33623;1901;1.430;14;59
5;53;34469;3229;1.430;13;60
7;53;34883;4603;1.408;14;59
11;53;34511;7159;1.412;13;59
13;53;32587;7963;1.453;14;60
17;53;34297;10993;1.432;13;80
19;53;33599;12043;1.443;14;64
23;53;34337;14897;1.415;14;59
29;53;34877;19081;1.424;14;61
31;53;34913;20411;1.406;13;59
37;53;34429;24029;1.417;13;60
41;53;34499;26683;1.418;14;59
43;53;32261;26171;1.488;14;62
47;53;34253;30367;1.437;14;79
3;59;33503;1699;1.432;14;61
5;59;34781;2939;1.424;14;60
7;59;35531;4211;1.403;14;59
11;59;34487;6427;1.420;14;59
13;59;33563;7393;1.453;14;61
17;59;34019;9791;1.440;14;60
19;59;33967;10937;1.447;14;60
23;59;33637;13109;1.438;14;60
29;59;34487;16943;1.424;14;59
31;59;32687;17167;1.480;14;61
37;59;35353;22159;1.404;14;59
41;59;34499;23971;1.431;14;60
43;59;34039;24799;1.445;14;60
47;59;32027;25471;1.499;14;62
53;59;34019;30557;1.449;14;61
3;61;35059;1723;1.418;14;60
5;61;34351;2803;1.416;13;60
7;61;35099;4021;1.412;14;59
11;61;34019;6133;1.442;14;60
13;61;35023;7459;1.406;14;88
17;61;35201;9803;1.414;14;61
19;61;34679;10799;1.425;14;101
23;61;34039;12829;1.441;13;60
29;61;33871;16097;1.446;14;60
31;61;34147;17351;1.427;14;61
37;61;34583;20963;1.412;14;59
41;61;32999;22171;1.452;14;62
43;61;33857;23857;1.431;14;98
47;61;34897;26881;1.431;14;60
53;61;33647;29231;1.434;14;60
59;61;32999;31907;1.454;14;60
3;67;32999;1471;1.455;14;61
5;67;35171;2621;1.403;14;59
7;67;33851;3533;1.463;14;61
11;67;34607;5669;1.437;14;60
13;67;35081;6803;1.416;14;61
17;67;33941;8609;1.417;14;60
19;67;34673;9829;1.427;14;60
23;67;35099;12043;1.415;14;60
29;67;33679;14563;1.452;14;61
31;67;34283;15859;1.437;14;60
37;67;32917;18169;1.460;13;61
41;67;33461;20443;1.441;14;61
43;67;34313;22013;1.426;14;60
47;67;33347;23371;1.452;14;61
53;67;33773;26713;1.434;14;60
59;67;35911;31607;1.395;14;58
61;67;34157;31091;1.431;14;63
3;71;34483;1453;1.423;14;59
5;71;34537;2423;1.428;14;59
7;71;33637;3313;1.428;13;60
11;71;32507;5023;1.465;14;79
13;71;35753;6529;1.403;14;59
17;71;33347;7963;1.444;14;61
19;71;35141;9397;1.410;14;59
23;71;32621;10559;1.475;14;61
29;71;33637;13729;1.429;14;60
31;71;33599;14657;1.443;14;60
37;71;34361;17903;1.396;14;59
41;71;33757;19489;1.435;14;61
43;71;34583;20939;1.413;14;59
47;71;34589;22877;1.441;14;60
53;71;35353;26387;1.418;14;59
59;71;35323;29347;1.406;14;59
61;71;35597;30577;1.401;14;59
67;71;34537;32587;1.425;14;59
3;73;34613;1409;1.418;14;59
5;73;32969;2251;1.453;14;62
7;73;33049;3167;1.448;14;61
11;73;33863;5101;1.435;14;60
13;73;34439;6131;1.456;14;60
17;73;33629;7829;1.455;14;61
19;73;34739;9029;1.421;14;60
23;73;33071;10399;1.469;14;61
29;73;33359;13249;1.460;14;61
31;73;33767;14327;1.422;14;59
37;73;32939;16693;1.490;14;62
41;73;33739;18947;1.438;14;60
43;73;33937;19979;1.432;14;61
47;73;33767;21739;1.422;14;59
53;73;33359;24203;1.435;14;60
59;73;34361;27767;1.401;13;59
61;73;33827;28229;1.443;14;60
67;73;34421;31583;1.423;14;71
71;73;33053;32143;1.447;14;60
3;79;35027;1327;1.410;14;60
5;79;34283;2161;1.432;14;60
7;79;34439;3049;1.432;14;60
11;79;34679;4817;1.416;14;59
13;79;34667;5701;1.405;14;59
17;79;33637;7237;1.428;14;60
19;79;34469;8287;1.417;14;60
23;79;34439;10009;1.433;14;60
29;79;33427;12269;1.448;13;61
31;79;33893;13297;1.445;14;61
37;79;33863;15823;1.439;14;60
41;79;32983;17107;1.450;14;60
43;79;34613;18803;1.431;14;60
47;79;33457;19891;1.457;14;61
53;79;33961;22777;1.435;14;61
59;79;32983;24631;1.465;14;60
61;79;34337;26501;1.428;14;60
67;79;33547;28447;1.458;14;61
71;79;32653;29339;1.473;14;61
73;79;34679;32029;1.429;14;64
3;83;35407;1277;1.405;14;59
5;83;32797;1973;1.451;14;60
7;83;33049;2777;1.443;14;61
11;83;33889;4483;1.431;14;60
13;83;35159;5503;1.409;14;59
17;83;34949;7151;1.412;14;59
19;83;32957;7541;1.467;14;61
23;83;32569;9013;1.470;14;61
29;83;33287;11621;1.474;14;61
31;83;33911;12659;1.448;13;60
37;83;33487;14923;1.456;14;62
41;83;33587;16573;1.438;13;60
43;83;34019;17623;1.435;14;60
47;83;31769;17987;1.483;14;62
53;83;33049;21101;1.451;14;61
59;83;32369;23003;1.465;14;61
61;83;32653;23993;1.469;14;61
67;83;33599;27109;1.437;14;61
71;83;33713;28837;1.452;14;61
73;83;33703;29641;1.454;14;61
79;83;34583;32911;1.417;14;59
3;89;34147;1129;1.415;13;60
5;89;32797;1831;1.461;14;61
7;89;33679;2647;1.443;14;73
11;89;34543;4261;1.427;13;60
13;89;34603;5051;1.419;14;60
17;89;34061;6491;1.444;14;60
19;89;34457;7351;1.422;14;79
23;89;33529;8663;1.450;14;61
29;89;34283;11161;1.431;14;60
31;89;35027;12197;1.411;13;59
37;89;34259;14221;1.403;14;59
41;89;33997;15649;1.434;14;60
43;89;33911;16127;1.445;14;60
47;89;34949;18451;1.419;14;59
53;89;34367;20443;1.434;14;60
59;89;33791;22397;1.430;14;59
61;89;34961;23957;1.404;14;59
67;89;33863;25471;1.433;13;60
71;89;35149;28031;1.414;14;79
73;89;33113;27143;1.447;14;60
79;89;32909;29209;1.458;14;61
83;89;33617;31337;1.400;14;59
3;97;34211;1051;1.448;14;60
5;97;34807;1789;1.430;14;60
7;97;33547;2417;1.446;14;60
11;97;35171;3967;1.407;14;89
13;97;32479;4349;1.474;14;61
17;97;34319;6011;1.444;14;60
19;97;32381;6337;1.491;14;64
23;97;33617;7963;1.421;14;59
29;97;33767;10093;1.423;14;59
31;97;33641;10739;1.447;14;60
37;97;34589;13187;1.425;13;60
41;97;34171;14437;1.451;14;60
43;97;31973;14159;1.484;14;62
47;97;33911;16127;1.445;14;61
53;97;34031;18593;1.448;14;80
59;97;32579;19813;1.457;14;61
61;97;34421;21617;1.417;13;60
67;97;33739;23297;1.448;14;60
71;97;33739;24691;1.435;14;60
73;97;33863;25471;1.433;13;60
79;97;34381;27997;1.419;14;59
83;97;33967;29063;1.446;14;60
89;97;33521;30727;1.441;14;60
列数1和2被用于计算翻版值和索引尺寸之间的关系粗糙。 接下来的两个是第一索引大小/翻版因子组合，其具有14次的搜索的最坏情况平均要查找小于1.5的搜索。 然后平均和最坏的情况。 最后，最后一列是每查找时钟周期的平均数目。 它没有考虑到阅读时间戳寄存器所需要的时间。
最佳常数的实际存储器空间（的indeces的＃= 31253和翻版因子= 28591）出来超过我最初指示（16000 * 2 * 8 + 1,25 * 16000 * 2 => 296000个字节）。 实际大小是16000 * 2 * 8 + 31253 * 2 => 318506。
最快的组合是11/31具有35897的索引的大小和12721.该翻版值的近似比将平均1.389（1个初始散列+ 0.389老调重弹）具有最大的14（1 + 13）。
________ EDIT________
我删除了“发现跳转;” 在main（）来显示所有的组合，它显示了更好的性能，可以在一个更大的索引大小为代价的，当然。 例如，该组合57667和33797的产率和的1.192平均和6的组合的最大翻版44543 23399和产生一个1.249平均和最大10个老调重弹（它保存（57667-44543）×2 = 26468字节的索引表中的相比33797分之57667）。
通过硬编码的哈希索引大小和翻版因素专业功能将在比较变量的时间60％-70％执行。 这可能是由于这样的编译器（gcc 64位）取代与乘法模和不具有以从存储位置取回的值，因为他们将被编码为立即值。
________ EDIT________
在高速缓存的问题，我看到两个问题。
首先是数据cacheing我不认为将是可能的，因为查询也只是在一些较大的进程的一小步，你运行表数据的缓存行的风险开始失效较轻或（可能）更大程度 - 如果不是完全 - 通过其他数据访问在较大的过程的其它步骤。 我的e更多的代码执行，并且在这个过程中数据访问整体上不太可能这将是任何有关查找数据将保留在缓存（这可能是也可能不是相关的业务方案的情况）。 为了找到使用（我的）散列，你会遇到两个高速缓存未命中的条目（加载索引的正确部分，而其他加载区方含入口本身）为每个需要进行比较。 发现在第一次尝试的项目将耗资2次失误，第二次尝试4等。在我的例子查找每60个时钟周期平均成本意味着该表可能完全在二级高速缓存与L1不必去那里居住大多数的情况下。 我X86-64 CPU具有L1-3，RAM等待大约4，10，40和100这对我表明RAM完全被拒之门外和L3大多状态。
第二个是代码cacheing这将有更显著影响，如果它小，紧张，内衬和少数控制转移（跳转和调用）。 我的哈希程序可能完全驻留在L1代码缓存。 对于比较正常的情况下，较少的代码缓存行的数量加载它会更快。
制作关键VAL对结构的数组。
排序数组由键，把它放进你的程序作为静态数组，就只能是128K字节。
然后在你的程序中简单的二进制查找由关键需要平均只有14个重点比较，以找到合适的值。 应该能够接近现代PC的每秒3个亿的样子UPS速度。
你可以用快速排序进行排序，并与bsearch搜索，无论是标准库函数。
执行memonization，或者简单地说，缓存你已经计算出的值，并计算出新的问题。 你应该哈希输入和检查缓存，此结果。 你甚至可以用一组，你认为该函数将被调用更经常的缓存值的开始。 除此之外，我不认为你需要去任何极端的其他答案建议。 做事情简单，当你与你的应用程序做，你可以使用一个分析工具找到瓶颈。
编辑：一些代码
#include <iostream>
#include <ctime>
using namespace std;
const int MAX_SIZE = 16000;
int preCalcData[MAX_SIZE] = {};
int getPrecalculatedResult(int x){
return preCalcData[x];
}
void setupPreCalcDataCache(){
for(int i = 0; i < MAX_SIZE; ++i){
preCalcData[i] = i*i; //or whatever calculation
}
}
int main(){
setupPreCalcDataCache();
cout << getPrecalculatedResult(0) << endl;
cout << getPrecalculatedResult(15999) << endl;
return 0;
}
我不会担心太多性能。 这个简单的例子，使用数组和二进制搜索lower_bound
#include <stdint.h>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <memory>
const int N = 16000;
typedef std::pair<uint64_t, uint64_t> CALC;
CALC calc[N];
static inline bool cmp_calcs(const CALC &c1, const CALC &c2)
{
return c1.first < c2.first;
}
int main(int argc, char **argv)
{
std::iostream::sync_with_stdio(false);
for (int i = 0; i < N; ++i)
calc[i] = std::make_pair(i, i);
std::sort(&calc[0], &calc[N], cmp_calcs);
for (long i = 0; i < 10000000; ++i) {
int r = rand() % 16000;
CALC *p = std::lower_bound(&calc[0], &calc[N], std::make_pair(r, 0), cmp_calcs);
if (p->first == r)
std::cout << "found\n";
}
return 0;
}
和编译
g++ -O2 example.cpp
的确，包括设置，10,000,000搜索在约2秒，我5岁的电脑上。
你需要有效地，储存最好在内存16000个值。 我们假设这些值的计算更加耗时比从存储访问它们。
您在您的处置许多不同的数据结构来完成这项工作，其中包括数据库。 如果您在可查询的数据块访问这些值，那么DB开销很可能被吸收并扩散翻过你的处理。
你在你的问题中提到的标签地图和HashMap（或哈希表）了，但这些可能不是问题的最佳可能的答案，但他们可以做一个公平的工作，前提是哈希函数并不比直接计算更贵目标UINT64值，它必须是你的参考基准。
- 范·昂德博阿斯树
- B-树的许多变体 （在数据库引擎，高性能文件系统广泛使用），
- 尝试
可能是更适合。 有与它的一些经验，我可能会去一个B-tree：他们支持相当不错系列化。 这应该让您准备的数据集事先在不同的程序。 VEB树有一个非常好的访问时间（O（日志的log（n）），但我不知道他们是如何轻易可序列化。
后来，如果需要更高的性能，这也将是有趣的知道你的“数据库”的使用模式，以找出缓存技术 ，你可以在商店之上实现。
使用std ::对，比任何地图的速度更好。
但如果我是你，我先用std ::列表来存储数据，之后我得到了他们的一切，我将它们移动到一个简单的载体，然后检索如果实现自己简单的二进制树搜索去非常快。
