Ответ 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. Для более обычных случаев, чем меньше количество строк кеша кода, тем быстрее оно будет.