From e20e4f550ae373414d9bc106b1615a5c5896c9c4 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 18 Jul 2024 19:39:44 +0200 Subject: Added pre-computation of short h48 positions --- test/112_h48map/h48map_tests.c | 19 ++++------ test/113_gen_h48short/00_depth_1.in | 28 +++++++++++++++ test/113_gen_h48short/00_depth_1.out | 3 ++ test/113_gen_h48short/01_depth_3.in | 3 ++ test/113_gen_h48short/01_depth_3.out | 40 +++++++++++++++++++++ test/113_gen_h48short/gen_h48short.c | 70 ++++++++++++++++++++++++++++++++++++ 6 files changed, 151 insertions(+), 12 deletions(-) create mode 100644 test/113_gen_h48short/00_depth_1.in create mode 100644 test/113_gen_h48short/00_depth_1.out create mode 100644 test/113_gen_h48short/01_depth_3.in create mode 100644 test/113_gen_h48short/01_depth_3.out create mode 100644 test/113_gen_h48short/gen_h48short.c (limited to 'test') diff --git a/test/112_h48map/h48map_tests.c b/test/112_h48map/h48map_tests.c index ce8f657..d70bc3a 100644 --- a/test/112_h48map/h48map_tests.c +++ b/test/112_h48map/h48map_tests.c @@ -1,11 +1,12 @@ #include "../test.h" #define MAP_KEYSHIFT UINT64_C(40) +#define MAXPOS 1000 typedef struct { uint64_t n; uint64_t capacity; - uint64_t mod; + uint64_t randomizer; uint64_t *table; } h48map_t; @@ -15,9 +16,7 @@ typedef struct { } kvpair_t; void h48map_create(h48map_t *, uint64_t, uint64_t); -void h48map_clear(h48map_t *); void h48map_destroy(h48map_t *); -uint64_t h48map_lookup(h48map_t *, uint64_t); void h48map_insertmin(h48map_t *, uint64_t, uint64_t); uint64_t h48map_value(h48map_t *, uint64_t); kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); @@ -40,28 +39,26 @@ uint64_t readl(void) { void run(void) { h48map_t map; - uint64_t n, i, j, capacity, mod, x, y, v; - kvpair_t kv, *a, *b; + uint64_t n, i, j, capacity, randomizer, x, y, v; + kvpair_t kv, a[MAXPOS], b[MAXPOS]; capacity = readl(); - mod = readl(); + randomizer = readl(); n = readl(); - a = malloc(n * sizeof(kvpair_t)); - b = malloc(n * sizeof(kvpair_t)); for (i = 0; i < n; i++) { x = readl(); y = readl(); a[i] = (kvpair_t) { .key = x, .val = y }; } - h48map_create(&map, capacity, mod); + h48map_create(&map, capacity, randomizer); for (i = 0; i < n; i++) h48map_insertmin(&map, a[i].key, a[i].val); i = 0; for (kv = h48map_nextkvpair(&map, &i), j = 0; - i != map.capacity; + i != map.capacity && j < MAXPOS; kv = h48map_nextkvpair(&map, &i) ) { b[j++] = kv; @@ -83,6 +80,4 @@ void run(void) { } h48map_destroy(&map); - free(a); - free(b); } diff --git a/test/113_gen_h48short/00_depth_1.in b/test/113_gen_h48short/00_depth_1.in new file mode 100644 index 0000000..c86f15b --- /dev/null +++ b/test/113_gen_h48short/00_depth_1.in @@ -0,0 +1,28 @@ +73 +157 +1 + +For longer test: + +20000003 +20000023 +8 + +Short h48: generating depth 0 +found 1 +Short h48: generating depth 1 +found 1 +Short h48: generating depth 2 +found 4 +Short h48: generating depth 3 +found 34 +Short h48: generating depth 4 +found 333 +Short h48: generating depth 5 +found 3815 +Short h48: generating depth 6 +found 45382 +Short h48: generating depth 7 +found 548562 +Short h48: generating depth 8 +found 6839723 diff --git a/test/113_gen_h48short/00_depth_1.out b/test/113_gen_h48short/00_depth_1.out new file mode 100644 index 0000000..b0dba31 --- /dev/null +++ b/test/113_gen_h48short/00_depth_1.out @@ -0,0 +1,3 @@ +2 +0 0 +71075840 1 diff --git a/test/113_gen_h48short/01_depth_3.in b/test/113_gen_h48short/01_depth_3.in new file mode 100644 index 0000000..920e70a --- /dev/null +++ b/test/113_gen_h48short/01_depth_3.in @@ -0,0 +1,3 @@ +73 +157 +3 diff --git a/test/113_gen_h48short/01_depth_3.out b/test/113_gen_h48short/01_depth_3.out new file mode 100644 index 0000000..dbce376 --- /dev/null +++ b/test/113_gen_h48short/01_depth_3.out @@ -0,0 +1,40 @@ +40 +0 0 +70981632 3 +71075840 1 +71086080 3 +142067712 2 +218789888 3 +218884096 2 +283879424 2 +283899904 3 +283953152 3 +283973632 2 +360548808 3 +360835072 3 +473668032 3 +473956352 3 +499869696 3 +500011008 3 +598679552 3 +599109185 3 +662171648 3 +662601226 3 +724818316 3 +725106688 3 +790513664 3 +790607872 3 +904991108 3 +926726144 3 +928729088 3 +1009662340 3 +1088755203 3 +1171758595 3 +1206452224 3 +1206480896 3 +1277360128 3 +1277454336 3 +1403695492 3 +1403697540 3 +1403736452 3 +1403738500 3 diff --git a/test/113_gen_h48short/gen_h48short.c b/test/113_gen_h48short/gen_h48short.c new file mode 100644 index 0000000..399ef1e --- /dev/null +++ b/test/113_gen_h48short/gen_h48short.c @@ -0,0 +1,70 @@ +#include "../test.h" + +#define COCSEP_CLASSES 3393 +#define MAXPOS 200 + +typedef struct { + uint64_t n; + uint64_t capacity; + uint64_t randomizer; + uint64_t *table; +} h48map_t; + +typedef struct { + uint64_t key; + uint64_t val; +} kvpair_t; + +void h48map_create(h48map_t *, uint64_t, uint64_t); +void h48map_destroy(h48map_t *); +kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); +size_t gendata_cocsep(void *, uint64_t *, cube_t *); +uint64_t gen_h48short( + uint8_t, const uint32_t *, const cube_t *, const uint64_t *, h48map_t *); + +char str[STRLENMAX]; + +int compare(const void *x, const void *y) { + uint64_t a = ((kvpair_t *)x)->key; + uint64_t b = ((kvpair_t *)y)->key; + + if (a > b) return 1; + if (a == b) return 0; + return -1; +} + +uint64_t readl(void) { + fgets(str, STRLENMAX, stdin); + return atoll(str); +} + +void run(void) { + uint32_t cocsepdata[300000]; + h48map_t map; + uint64_t n, i, j, capacity, randomizer, selfsim[COCSEP_CLASSES]; + kvpair_t kv, b[MAXPOS]; + cube_t crep[COCSEP_CLASSES]; + + capacity = readl(); + randomizer = readl(); + n = readl(); + + h48map_create(&map, capacity, randomizer); + gendata_cocsep(cocsepdata, selfsim, crep); + gen_h48short(n, cocsepdata, crep, selfsim, &map); + + i = 0; + for (kv = h48map_nextkvpair(&map, &i), j = 0; + i != map.capacity && j < MAXPOS; + kv = h48map_nextkvpair(&map, &i) + ) { + b[j++] = kv; + } + qsort(b, j, sizeof(kvpair_t), compare); + + printf("%" PRIu64 "\n", map.n); + for (i = 0; i < j; i++) + printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val); + + h48map_destroy(&map); +} -- cgit v1.3