4

好的，这是我的情况：

  • 我有一个函数——比如说U64 calc (U64 x)——它接受一个 64 位整数参数，执行一些 CPU 密集型操作，并返回一个 64 位值
  • 现在，鉴于我x事先知道该函数的所有可能输入（s）（尽管有大约 16000 个），我认为预先计算它们然后按需获取它们（从类似数组的结构）可能会更好.
  • 理想的情况是将它们全部存储在某个数组中并通过索引（再次）U64 CALC[]检索它们x
  • 这就是问题所在：我可能知道我的 calc 函数的可能输入是什么，但它们绝对不是连续的（例如，不是从 1 到 16000，而是可能低至 0 和高达数万亿的值 - 总是具有 64 位范围）

例如

  X        CALC[X]
-----------------------
  123123   123123123
  12312    12312312
  897523   986123

  etc.

我的问题来了：

  • 你会如何储存它们？
  • 您更喜欢哪种解决方法？
  • 现在，鉴于这些值 (from CALC)必须每秒访问数千到数百万次，这将是性能方面的最佳解决方案？

注意：我没有提及我想到或尝试过的任何事情，以免将答案变成关于 A 与 B 类型事物的辩论，并且大多数情况下不会影响任何人......

4

6 回答 6

4

我会使用某种散列函数来创建指向 u64 对的索引，其中一个是创建键的值，另一个是替换值。从技术上讲，如果您需要节省空间但我会使用 u32s，则索引可能是三个字节长（假设 1600 万-“1600 万”-对）。如果存储的值与（哈希冲突）计算的值不匹配，您将输入溢出处理程序。

  • 您需要确定自定义散列算法以适合您的数据
  • 由于您知道数据的大小，因此您不需要允许数据增长的算法。
  • 我会警惕使用一些标准算法，因为它们很少适合特定数据
  • 除非您确定代码是所见即所得（不会产生很多不可见的调用），否则我会警惕使用 C++ 方法
  • 您的索引应该比对数大 25%

遍历所有可能的输入并确定碰撞次数的最小值、最大值、平均值和标准偏差，并使用这些来确定可接受的性能水平。然后配置文件以实现最佳代码。

所需的内存空间（使用 u32 索引）为 (4*1.25)+8+8 = 每对 21 个字节或 336 MeB，在典型的 PC 上没有问题。

________ 编辑________

我受到“RocketRoy”的挑战，要把钱放在嘴边。开始：

该问题与（固定大小）哈希索引中的冲突处理有关。设置舞台：

  • 我有一个 n 条目的列表，其中条目中的一个字段包含计算哈希值的 v
  • 我有一个 n*1.25（大约）indeces 的向量，使得 indeces 的数量 x 是一个素数
  • 计算一个素数 y，它是 x 的一部分
  • 向量初始化为 -1 表示未占用

很标准的东西，我想你会同意的。

列表中的条目被处理，哈希值 h 被计算和取模并用作向量的索引，条目的索引被放置在那里。

最终我遇到了索引指向的向量条目被占用（不包含-1）的情况——瞧，碰撞。

那我该怎么办？我将原始 h 保留为 ho，将 y 添加到 h 并取模 x 并在向量中获得一个新索引。如果条目未被占用，我使用它，否则我继续添加 y 模 x 直到我到达 ho。理论上，这会发生，因为 x 和 y 都是素数。在实践中 x 大于 n 所以它不会。

因此，RocketRoy 声称的“重新散列”成本很高，这不是这样的事情。

这种方法的棘手部分 - 与所有散列方法一样 - 是：

  • 为 x 确定一个合适的值（最终使用的 x 越大，难度就越大）
  • 为 h=a(v)%x 确定算法 a 使得 h 的索引合理均匀（“随机”）进入索引向量，并尽可能少地发生冲突
  • 为 y 确定一个合适的值，以使碰撞合理地均匀（“随机”）索引到索引向量中

________ 编辑________

很抱歉，我花了这么长时间来编写这段代码……其他事情有更高的优先级。

无论如何，这是证明散列比二叉树具有更好的快速查找前景的代码。它通过一堆散列索引大小和算法来帮助找到最适合特定数据的组合。对于每种算法，代码将打印第一个索引大小，这样查找所需的时间不会超过 14 次搜索（二进制搜索的最坏情况），平均查找需要少于 1.5 次搜索。

如果您没有注意到，我喜欢在这些类型的应用程序中使用素数。

有许多方法可以创建具有强制溢出处理的散列算法。我选择了简单，假设它会转化为速度……确实如此。在我的带有 i5 M 480 @ 2.67 GHz 的笔记本电脑上，平均查找需要 55 到 60 个时钟周期（大约每秒 4500 万次查找）。我实现了一个特殊的 get 操作，具有恒定数量的 indeces 和同上的 rehash 值，循环计数下降到 40（每秒 6500 万次查找）。如果您查看调用 getOpSpec 的行，则索引 i 与 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 列用于计算 rehash 值和索引大小之间的粗略关系。接下来的两个是第一个索引大小/重新散列因子组合，平均不到 1.5 次搜索，最坏的情况是 14 次搜索。然后是平均和最坏情况。最后，最后一列是每次查找的平均时钟周期数。它没有考虑读取时间戳寄存器所需的时间。

最佳常量的实际内存空间（# of indeces = 31253 和 rehash factor = 28591）比我最初指出的要多（16000*2*8 + 1,25*16000*2 => 296000 字节）。实际大小为 16000*2*8+31253*2 => 318506。

最快的组合是 11/31 的近似比率，索引大小为 35897，rehash 值为 12721。这将平均为 1.389（1 个初始散列 + 0.389 个 rehash），最大值为 14（1+13）。

________ 编辑________

我删除了“goto found;” 在 main() 中显示所有组合，它表明可以有更好的性能，当然是以更大的索引大小为代价的。例如，57667 和 33797 的组合产生 1.192 的平均值和 6 的最大重新哈希。44543 和 23399 的组合产生 1.249 的平均值和 10 最大的重新哈希（与索引表相比，它节省了 (57667-44543)*2=26468 字节57667/33797）。

与变量相比，具有硬编码哈希索引大小和重新哈希因子的专用函数将在 60-70% 的时间内执行。这可能是由于编译器（gcc 64 位）用乘法代替了模，而不必从内存位置获取值，因为它们将被编码为立即值。

________ 编辑________

关于缓存的主题，我看到了两个问题。

第一个是数据缓存，我认为这是不可能的，因为查找只是某个较大过程中的一小步，并且您冒着表数据的缓存行开始在较小或（可能）较大程度上失效的风险-如果不是完全 - 通过更大过程的其他步骤中的其他数据访问。即，整个过程中执行的代码和访问的数据越多，任何相关的查找数据将保留在缓存中的可能性就越小（这可能与 OP 的情况有关，也可能不相关）。要使用（我的）散列查找条目，每次需要执行的比较都会遇到两次缓存未命中（一个加载索引的正确部分，另一个加载包含条目本身的区域）。在第一次尝试中找到一个条目将导致两次未命中，第二次尝试四次，以此类推。在我的示例中，每次查找 60 个时钟周期的平均成本意味着该表可能完全驻留在 L2 缓存中，并且在大多数情况下 L1 不必去那里。我的 x86-64 CPU 具有 L1-3，RAM 等待状态大约为 4、10、40 和 100，这对我来说表明 RAM 完全被排除在外，而大部分是 L3。

第二个是代码缓存，如果它很小、紧凑、内联并且控制传输（跳转和调用）很少，它将产生更显着的影响。我的哈希例程可能完全驻留在 L1 代码缓存中。对于更正常的情况，代码缓存行加载的数量越少，加载速度就越快。

于 2012-12-16T06:30:44.330 回答
1

执行记忆，或者简单地说，缓存你已经计算的值并计算新的值。您应该对输入进行哈希处理并检查该结果的缓存。您甚至可以从一组您认为该函数会被更频繁地调用的缓存值开始。除此之外，我认为您不需要像其他答案所建议的那样走极端。做一些简单的事情，当您完成应用程序后，您可以使用分析工具来查找瓶颈。

编辑：一些代码

#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;
}
于 2012-12-16T05:39:31.637 回答
1

制作一个键值对结构数组。

按键排序数组，把它作为静态数组放在你的程序中，只有128kbyte。

然后在您的程序中，通过键进行简单的二进制查找平均只需要 14 次键比较即可找到正确的值。在现代 PC 上应该能够达到每秒 3 亿次查找的速度。

您可以使用 qsort 排序和使用 bsearch 搜索，这两个标准库函数。

于 2012-12-16T05:47:59.430 回答
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

在我 5 年的旧电脑上，包括设置在内，在大约 2 秒内完成了 10,000,000 次搜索。

于 2012-12-16T05:09:24.857 回答
0

您需要有效地存储 16,000 个值，最好是在内存中。我们假设这些值的计算比从存储中访问它们更耗时。

您可以使用许多不同的数据结构来完成工作，包括数据库。如果您以可查询的块访问这些值，那么 DB 开销很可能会被吸收并分散在您的处理中。

您已经在问题标签中提到了 map 和 hashmap（或 hashtable），但这些可能不是您问题的最佳答案，尽管它们可以做得很好，前提是散列函数不比直接计算更昂贵目标 UINT64 值，它必须是您的参考基准。

可能更适合。有了一些经验，我可能会选择 B-tree：它们支持相当好的序列化。这应该可以让您提前在不同的程序中准备数据集。VEB 树的访问时间非常好（O（log log（n）），但我不知道它们序列化的难易程度。

稍后，如果您需要更高的性能，了解您的“数据库”的使用模式以弄清楚您可以在存储之上实现哪些缓存技术也会很有趣。

于 2012-12-16T05:28:45.193 回答
-2

使用 std::pair 比任何 map 的速度都要好。

但是如果我是你，我首先使用一个 std::list 来存储数据，在我得到它们之后，我将它们移动到一个简单的向量中，然后如果你自己实现一个简单的二叉树搜索，那么检索会非常快。

于 2012-12-16T05:16:42.123 回答