यह थोड़ा सा केडी-पेड़ है। इसे प्रति लुकअप ऑपरेशन के लिए 64 से कम विज़िट की आवश्यकता होती है। वर्तमान में, बिट (आयाम) का चयन पिवोट पर यादृच्छिक है।
#include <limits.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef unsigned long long Thing;
typedef unsigned long Number;
unsigned thing_ffs(Thing mask);
Thing rand_mask(unsigned bitcnt);
#define WANT_RANDOM 31
#define WANT_BITS 3
#define BITSPERTHING (CHAR_BIT*sizeof(Thing))
#define NONUMBER ((Number)-1)
struct node {
Thing value;
Number num;
Number nul;
Number one;
char pivot;
} *nodes = NULL;
unsigned nodecount=0;
unsigned itercount=0;
struct node * nodes_read(unsigned *sizp, char *filename);
Number *find_ptr_to_insert(Number *ptr, Thing value, Thing mask);
unsigned grab_matches(Number *result, Number num, Thing mask);
void initialise_stuff(void);
int main (int argc, char **argv)
{
Thing mask;
Number num;
unsigned idx;
srand (time(NULL));
nodes = nodes_read(&nodecount, argv[1]);
fprintf(stdout, "Nodecount=%u\n", nodecount);
initialise_stuff();
#if WANT_RANDOM
mask = nodes[nodecount/2].value | nodes[nodecount/3].value ;
#else
mask = 0x38;
#endif
fprintf(stdout, "\n#### Search mask=%llx\n", (unsigned long long) mask);
itercount = 0;
num = NONUMBER;
idx = grab_matches(&num,0, mask);
fprintf(stdout, "Itercount=%u\n", itercount);
fprintf(stdout, "KdTree search %16llx\n", (unsigned long long) mask);
fprintf(stdout, "Count=%u Result:\n", idx);
idx = num;
if (idx >= nodecount) idx = nodecount-1;
fprintf(stdout, "num=%4u Value=%16llx\n"
,(unsigned) nodes[idx].num
,(unsigned long long) nodes[idx].value
);
fprintf(stdout, "\nLinear search %16llx\n", (unsigned long long) mask);
for (idx = 0; idx < nodecount; idx++) {
if ((nodes[idx].value & mask) == nodes[idx].value) break;
}
fprintf(stdout, "Cnt=%u\n", idx);
if (idx >= nodecount) idx = nodecount-1;
fprintf(stdout, "Num=%4u Value=%16llx\n"
, (unsigned) nodes[idx].num
, (unsigned long long) nodes[idx].value);
return 0;
}
void initialise_stuff(void)
{
unsigned num;
Number root, *ptr;
root = 0;
for (num=0; num < nodecount; num++) {
nodes[num].num = num;
nodes[num].one = NONUMBER;
nodes[num].nul = NONUMBER;
nodes[num].pivot = -1;
}
nodes[num-1].value = 0; /* last node is guaranteed to match anything */
root = 0;
for (num=1; num < nodecount; num++) {
ptr = find_ptr_to_insert (&root, nodes[num].value, 0ull);
if (*ptr == NONUMBER) *ptr = num;
else fprintf(stderr, "Found %u for %u\n"
, (unsigned)*ptr, (unsigned) num);
}
}
Thing rand_mask(unsigned bitcnt)
{struct node * nodes_read(unsigned *sizp, char *filename)
{
struct node *ptr;
unsigned size,used;
FILE *fp;
if (!filename) {
size = (WANT_RANDOM+0) ? WANT_RANDOM : 9;
ptr = malloc (size * sizeof *ptr);
#if (!WANT_RANDOM)
ptr[0].value = 0x0c;
ptr[1].value = 0x0a;
ptr[2].value = 0x08;
ptr[3].value = 0x04;
ptr[4].value = 0x02;
ptr[5].value = 0x01;
ptr[6].value = 0x10;
ptr[7].value = 0x20;
ptr[8].value = 0x00;
#else
for (used=0; used < size; used++) {
ptr[used].value = rand_mask(WANT_BITS);
}
#endif /* WANT_RANDOM */
*sizp = size;
return ptr;
}
fp = fopen(filename, "r");
if (!fp) return NULL;
fscanf(fp,"%u\n", &size);
fprintf(stderr, "Size=%u\n", size);
ptr = malloc (size * sizeof *ptr);
for (used = 0; used < size; used++) {
fscanf(fp,"%llu\n", &ptr[used].value);
}
fclose(fp);
*sizp = used;
return ptr;
}
Thing value = 0;
unsigned bit, cnt;
for (cnt=0; cnt < bitcnt; cnt++) {
bit = 54321*rand();
bit %= BITSPERTHING;
value |= 1ull << bit;
}
return value;
}
Number *find_ptr_to_insert(Number *ptr, Thing value, Thing done)
{
Number num=NONUMBER;
while (*ptr != NONUMBER) {
Thing wrong;
num = *ptr;
wrong = (nodes[num].value^value) & ~done;
if (nodes[num].pivot < 0) { /* This node is terminal */
/* choose one of the wrong bits for a pivot .
** For this bit (nodevalue==1 && searchmask==0)
*/
if (!wrong) wrong = ~done ;
nodes[num].pivot = thing_ffs(wrong);
}
ptr = (wrong & 1ull << nodes[num].pivot) ? &nodes[num].nul : &nodes[num].one;
/* Once this bit has been tested, it can be masked off. */
done |= 1ull << nodes[num].pivot ;
}
return ptr;
}
unsigned grab_matches(Number *result, Number num, Thing mask)
{
Thing wrong;
unsigned count;
for (count=0; num < *result;) {
itercount++;
wrong = nodes[num].value & ~mask;
if (!wrong) { /* we have a match */
if (num < *result) { *result = num; count++; }
/* This is cheap pruning: the break will omit both subtrees from the results.
** But because we already have a result, and the subtrees have higher numbers
** than our current num, we can ignore them. */
break;
}
if (nodes[num].pivot < 0) { /* This node is terminal */
break;
}
if (mask & 1ull << nodes[num].pivot) {
/* avoid recursion if there is only one non-empty subtree */
if (nodes[num].nul >= *result) { num = nodes[num].one; continue; }
if (nodes[num].one >= *result) { num = nodes[num].nul; continue; }
count += grab_matches(result, nodes[num].nul, mask);
count += grab_matches(result, nodes[num].one, mask);
break;
}
mask |= 1ull << nodes[num].pivot;
num = (wrong & 1ull << nodes[num].pivot) ? nodes[num].nul : nodes[num].one;
}
return count;
}
unsigned thing_ffs(Thing mask)
{
unsigned bit;
#if 1
if (!mask) return (unsigned)-1;
for (bit=random() % BITSPERTHING; 1 ; bit += 5, bit %= BITSPERTHING) {
if (mask & 1ull << bit) return bit;
}
#elif 0
for (bit =0; bit < BITSPERTHING; bit++) {
if (mask & 1ull <<bit) return bit;
}
#else
mask &= (mask-1); // Kernighan-trick
for (bit =0; bit < BITSPERTHING; bit++) {
mask >>=1;
if (!mask) return bit;
}
#endif
return 0xffffffff;
}
struct node * nodes_read(unsigned *sizp, char *filename)
{
struct node *ptr;
unsigned size,used;
FILE *fp;
if (!filename) {
size = (WANT_RANDOM+0) ? WANT_RANDOM : 9;
ptr = malloc (size * sizeof *ptr);
#if (!WANT_RANDOM)
ptr[0].value = 0x0c;
ptr[1].value = 0x0a;
ptr[2].value = 0x08;
ptr[3].value = 0x04;
ptr[4].value = 0x02;
ptr[5].value = 0x01;
ptr[6].value = 0x10;
ptr[7].value = 0x20;
ptr[8].value = 0x00;
#else
for (used=0; used < size; used++) {
ptr[used].value = rand_mask(WANT_BITS);
}
#endif /* WANT_RANDOM */
*sizp = size;
return ptr;
}
fp = fopen(filename, "r");
if (!fp) return NULL;
fscanf(fp,"%u\n", &size);
fprintf(stderr, "Size=%u\n", size);
ptr = malloc (size * sizeof *ptr);
for (used = 0; used < size; used++) {
fscanf(fp,"%llu\n", &ptr[used].value);
}
fclose(fp);
*sizp = used;
return ptr;
}
अद्यतन:
मैं धुरी-चयन के साथ एक सा प्रयोग किया, उच्चतम भेदभावपूर्ण मूल्य ("जानकारी सामग्री") के साथ बिट्स के पक्ष में।यह शामिल है:
- पेड़ के निर्माण, जबकि बिट्स के उपयोग के एक हिस्टोग्राम (जबकि initialising किया जा सकता है)
- बनाने: शेष subtrees में आवृत्ति 1/2 के सबसे करीब के साथ एक को चुनने।
परिणाम: यादृच्छिक पिवट चयन बेहतर प्रदर्शन किया।
क्या तत्वों की सूची (मूल सूचकांक रिकॉर्डिंग) को सॉर्ट करना संभव होगा? यदि वे क्रमबद्ध हैं तो यह * अधिक * आसान है। इस मुद्दे के बारे में सोचने के लिए यहां कुछ स्थान दिए गए हैं: http://en.wikipedia.org/wiki/List_of_algorithms#Item_search और http://en.wikipedia.org/wiki/Selection_algorithm ("Use_data_structures_to_select_in_sublinear_time" अनुभाग देखें)। –
निश्चित रूप से, हम सूची को सॉर्ट कर सकते हैं और मूल इंडेक्स स्टोर कर सकते हैं। फिर सवाल बन जाता है: मास्क से मेल खाने वाले तत्व को ढूंढें और सबसे छोटी अनुक्रमणिका है। मैं अभी भी यह नहीं देखता कि किसी पारंपरिक खोज एल्गोरिदम के साथ इसे कैसे किया जाए, क्योंकि हम एक विशेष तत्व की तलाश करने के बजाय मास्क से मेल खाने वाले तत्वों की तलाश में हैं। – cberzan
विधि 2 'ओ (2^64) 'स्पेस लेता है, जो निरंतर लेकिन अव्यवहारिक है। –