Самый быстрый способ получить 16k пары Key-Value?

Ответ 1

Я бы использовал какую-то хэш-функцию, которая создает индекс для пары u64, где одно - это значение, из которого был создан ключ, а другой - значение замены. Технически индекс может составлять три байта (при условии, что 16 миллионов - "16000 тысяч" - пары), если вам нужно сохранить пространство, но я бы использовал u32s. Если сохраненное значение не соответствует значению, вычисленному на (хеш-столкновение), вы должны ввести обработчик переполнения.

• Вам необходимо определить собственный алгоритм хэширования, который будет соответствовать вашим данным.
• Поскольку вы знаете размер данных, вам не нужны алгоритмы, позволяющие увеличить данные.
• Я бы с осторожностью использовал какой-то стандартный алгоритм, потому что они редко соответствовали конкретным данным.
• Я бы с осторожностью использовал метод С++, если вы не уверены, что код WYSIWYG (не генерирует много невидимых вызовов)
• Ваш индекс должен быть на 25% больше, чем количество пар.

Пропустите все возможные входы и определите минимальное, максимальное, среднее и стандартное отклонение для числа коллизий и используйте их для определения приемлемого уровня производительности. Затем профиль для достижения наилучшего возможного кода.

Требуемое пространство памяти (с использованием индекса u32) выводится на (4 * 1,25) + 8 + 8 = 21 байт на пару или 336 MeB, без проблем на обычном ПК.

________ EDIT ________

Мне "RocketRoy" бросили вызов, чтобы поместить мои деньги туда, где есть мой рот. Здесь:

Проблема связана с обработкой конфликтов в хэш-индексе (фиксированный размер). Чтобы настроить сцену:

• У меня есть список n записей, в которых поле в записи содержит значение v, которое хэш вычисляется из
• У меня есть вектор из n * 1.25 (приблизительно) индексов такой, что число индексов x является простым числом
• Вычисляется простое число y, которое является частью x
• Вектор инициализируется, чтобы сказать -1, чтобы обозначить незанятые

Довольно стандартный материал, я думаю, вы согласитесь.

Записи в списке обрабатываются, а хэш-значение h вычисляется и по модулю и используется как индекс в векторе, а индекс к записи помещается туда.

В конце концов я сталкиваюсь с ситуацией, когда векторная запись, на которую указывает индекс, занята (не содержит -1) - voilà, столкновение.

Так что мне делать? Я сохраняю исходный h как ho, добавляю y к h и беру modulo x и получаю новый индекс в вектор. Если запись не занята, я использую ее, иначе я продолжу добавлять y modulo x до тех пор, пока не достигнут ho. Теоретически это произойдет потому, что и x, и y - простые числа. На практике x больше n, поэтому он не будет.

Таким образом, "повторный хэш", который утверждает RocketRoy, очень дорогостоящий, не является такой вещью.

Сложная часть этого метода - как и для всех методов хэширования - заключается в следующем:

• Определите подходящее значение для x (становится менее сложным, чем больше используется x)
• Определите алгоритм a для h = a (v)% x такой, что a h индексирует разумно равномерно ( "случайно" ) в индексный вектор с как можно меньшим количеством коллизий
• Определите подходящее значение для y, чтобы индексы столкновений разумно равномерно ( "случайным образом" ) в индексный вектор

________ EDIT ________

Мне жаль, что я так долго занимался производством этого кода... у других вещей были более высокие приоритеты.

В любом случае, вот код, который доказывает, что хеширование имеет лучшие перспективы для быстрого поиска, чем двоичное дерево. Он проходит через кучу размеров и алгоритмов хеширования, чтобы помочь найти наиболее подходящую комбинацию для конкретных данных. Для каждого алгоритма код будет печатать первый размер индекса, так что поиск не займет больше четырнадцати поисковых запросов (наихудший случай для двоичного поиска), а средний поиск занимает менее 1,5 запросов.

У меня есть привязанность к простым числам в этих типах приложений, если вы не заметили.

Существует множество способов создания алгоритма хэширования с его обязательной обработкой переполнения. Я выбрал простоту, предполагая, что он перейдет в скорость... и это так. На моем ноутбуке с i5 M 480 @2,67 ГГц средний поиск требует от 55 до 60 тактов (отходит примерно до 45 миллионов поисковых запросов в секунду). Я реализовал специальную операцию получения с постоянным количеством индексов и то же самое значение rehash, и количество циклов упало до 40 (65 миллионов поисковых запросов в секунду). Если вы посмотрите на строку, вызывающую getOpSpec, индекс я xor'ed с 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

Cols 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 повторений) с максимумом 14 (1 + 13).

________ EDIT ________

Я удалил "goto found"; в main(), чтобы показать все комбинации, и это показывает, что гораздо более высокая производительность возможна, конечно, за счет большего размера индекса. Например, комбинация 57667 и 33797 дает и составляет в среднем 1,192 и максимальный пересмотр 6. Комбинация 44543 и 23399 дает среднюю и 10 максимальную пересылку 1.249 (она экономит (57667-44543) * 2 = 26468 байтов индексной таблицы по сравнению с 57667/33797).

Специализированные функции с жестко закодированным размером индекса хэша и коэффициентом пересохранения будут выполняться в 60-70% случаев по сравнению с переменными. Вероятно, это связано с тем, что компилятор (gcc 64-bit) заменяет модуль с помощью умножений и не должен извлекать значения из мест памяти, поскольку они будут закодированы как немедленные значения.

________ EDIT ________

В отношении кешей я вижу два вопроса.

Первое - это кеширование данных, которое, как я думаю, не будет возможным, потому что поиск будет всего лишь небольшим шагом в каком-то более крупном процессе, и вы рискуете, что строки кэша данных таблицы станут недействительными для меньшего или (возможно) в большей степени - если не полностью - другими доступом к данным на других этапах более крупного процесса. Более того, чем больше выполняется код и доступ к данным в процессе в целом, тем меньше вероятность того, что любые данные поиска будут оставаться в кэшах (это может быть или не быть уместным для ситуации OP). Чтобы найти запись с использованием (my) хэширования, вы столкнетесь с двумя промахами в кэше (один для загрузки правильной части индекса, а другой для загрузки области, связанной с самой записью) для каждого сравнения, которое необходимо выполнить. Поиск в первой попытке будет стоить две промахи, вторая попытка - четыре и т.д. В моем примере средняя стоимость цикла в 60 тактов за просмотр подразумевает, что таблица, вероятно, полностью находится в кэше L2, а L1 не должен туда идти в большинстве случаев. Мой процессор x86-64 имеет L1-3, состояния ожидания ОЗУ приблизительно 4, 10, 40 и 100, которые мне показывают, что оперативная память полностью отключена и L3 в основном.

Во-вторых, это кеширование кода, которое будет иметь более существенное влияние, если оно будет небольшим, жестким, вложенным и с небольшими контрольными передачами (переходы и вызовы). Моя хэш-программа, вероятно, полностью находится в кеше кода L1. Для более обычных случаев, чем меньше количество строк кеша кода, тем быстрее оно будет.

Ответ 2

Сделать массив структур пар ключей val.

Сортируйте массив по ключу, поместите его в свою программу как статический массив, будет только 128 кбайт.

Тогда в вашей программе простой двоичный поиск по ключевому слову потребует в среднем только 14 ключевых сравнений, чтобы найти правильное значение. Должен быть способен приближаться к скорости 300 миллионов поисковых запросов в секунду на современном ПК.

Вы можете сортировать с помощью qsort и искать с помощью bsearch, обе функции std lib.

Ответ 3

Я бы не слишком беспокоился о производительности. Этот простой пример, используя массив и двоичный поиск 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-летнем ПК.

Ответ 4

Вам нужно хранить 16 тысяч значений эффективно, желательно в памяти. Мы предполагаем, что вычисление этих значений занимает больше времени, чем доступ к ним из хранилища.

У вас есть много разных структур данных для выполнения работы, включая базы данных. Если вы получите доступ к этим значениям в запрошенных кусках, то накладные расходы БД вполне могут быть поглощены и распределены по вашей обработке.

Вы упомянули карту и хэш-таблицу (или хеш-таблицу) уже в своих тегах вопроса, но это, вероятно, не самые лучшие ответы на ваши проблемы, хотя они могут выполнять справедливую работу, при условии, что функция хеширования не дороже, чем прямое вычисление целевого значения UINT64, которое должно быть вашим эталонным эталоном.

• Ван Эмд Боас Деревья
• Много вариантов B-Trees (широко используется в системах баз данных, высокопроизводительных файловых системах),
• Зарабатывает

Скорее всего, они намного лучше подходят. Имея некоторый опыт работы с ним, я, вероятно, поеду на B-дерево: они поддерживают довольно хорошую сериализацию. Это должно позволить вам заранее подготовить ваш набор данных в другой программе. Деревья VEB имеют очень хорошее время доступа (O (log log (n)), но я не знаю, насколько легко они могут быть сериализованы.

Позже, если вам нужна еще большая производительность, было бы также интересно узнать шаблоны использования вашей "базы данных", чтобы выяснить, что методы кеширования вы можете реализовать поверх магазина.

Ответ 5

Выполните мемонирование или, проще говоря, кешируйте уже вычисленные значения и вычислите новые. Вы должны ввести хэш и проверить кеш для этого результата. Вы даже можете начать с набора значений кеша, которые, по вашему мнению, будут чаще вызываться функцией. Кроме того, я не думаю, что вам нужно идти в крайнем случае, как предлагает другой ответ. Делайте все просто, и когда вы закончите с вашим приложением, вы можете использовать инструмент для профилирования, чтобы найти шейки бутылки.

EDIT: код

#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;
}    

Ответ 6

Использование std:: pair лучше любого из карт для скорости.

но если бы я был вами, я сначала использовал std:: list для хранения данных, после того как я их получил, я переместил их в простой вектор, а затем извлечение происходит очень быстро, если вы реализуете простой поиск двоичного дерева по сами.