2012-02-12 15 views
14

से मेल खाने वाला पहला तत्व कुशलतापूर्वक प्राप्त करें मेरे पास एन 64-बिट पूर्णांक की सूची है जिनके बिट छोटे सेट का प्रतिनिधित्व करते हैं। प्रत्येक पूर्णांक में k बिट्स 1 पर सेट होते हैं। थोड़ा मास्क देखते हुए, मैं मास्क से मेल खाने वाली सूची में पहला तत्व ढूंढना चाहता हूं, यानी element & mask == elementकुशलता से थोड़ा सा मुखौटा

उदाहरण:

अगर मेरे सूची है:

index abcdef 
    0 001100 
    1 001010 
    2 001000 
    3 000100 
    4 000010 
    5 000001 
    6 010000 
    7 100000 
    8 000000 

और मेरे मुखौटा 111000 है, मुखौटा मिलान पहला तत्व सूचकांक 2. पर है

विधि 1:

संपूर्ण सूची के माध्यम से रैखिक खोज। यह ओ (एन) समय और ओ (1) अंतरिक्ष लेता है।

विधि 2:

precompute सभी संभव मास्क का एक पेड़ है, और प्रत्येक नोड पर कि मुखौटा के लिए जवाब रहते हैं। यह क्वेरी के लिए ओ (1) समय लेता है, लेकिन ओ (2^64) स्थान लेता है।

प्रश्न:

मैं कैसे जबकि अभी भी अंतरिक्ष के लिए उचित समय का उपयोग कर, तेजी से ओ (एन) की तुलना में मुखौटा मिलान पहला तत्व मिल सकती है? मैं प्रीकंप्यूशन में बहुपद समय बिताने का जोखिम उठा सकता हूं, क्योंकि बहुत सारे प्रश्न होंगे। कुंजी यह है कि के छोटा है। मेरे आवेदन में, के < = 5 और एन हजारों में है। मास्क में कई 1 एस हैं; आप मान सकते हैं कि यह 64-बिट पूर्णांक की जगह से समान रूप से खींचा गया है।

अद्यतन: http://up.thirld.com/binmask.tar.gz:

यहाँ सेट एक उदाहरण डेटा और एक सरल बेंचमार्क कार्यक्रम है कि लिनक्स पर चलता है। large.in, एन = 3779 और के = 3 के लिए। पहली पंक्ति एन है, इसके बाद एन तत्वों का प्रतिनिधित्व करने वाले 64-बिट इन्स को हस्ताक्षरित किया गया है। make के साथ संकलित करें। सही आउटपुट बनाने के लिए ./benchmark.e >large.out के साथ चलाएं, जिसे आप इसके बाद अलग कर सकते हैं। (मास्क यादृच्छिक रूप से उत्पन्न होते हैं, लेकिन यादृच्छिक बीज तय किया जाता है।) फिर अपने कार्यान्वयन के साथ find_first() फ़ंक्शन को प्रतिस्थापित करें।

सरल रैखिक खोज मेरी अपेक्षा से बहुत तेज है। ऐसा इसलिए है क्योंकि k छोटा है, और इसलिए यादृच्छिक मुखौटा के लिए, औसत पर औसत बहुत जल्दी मिलता है।

  1. हर स्तर डेटाबेस में हर नंबर डालने इस तरह एक सा
  2. यह होने वाली संबंधित बिट पर ठीक है, नहीं तो छोड़ दिया जाना है

से मेल खाती है:

+0

क्या तत्वों की सूची (मूल सूचकांक रिकॉर्डिंग) को सॉर्ट करना संभव होगा? यदि वे क्रमबद्ध हैं तो यह * अधिक * आसान है। इस मुद्दे के बारे में सोचने के लिए यहां कुछ स्थान दिए गए हैं: 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" अनुभाग देखें)। –

+1

निश्चित रूप से, हम सूची को सॉर्ट कर सकते हैं और मूल इंडेक्स स्टोर कर सकते हैं। फिर सवाल बन जाता है: मास्क से मेल खाने वाले तत्व को ढूंढें और सबसे छोटी अनुक्रमणिका है। मैं अभी भी यह नहीं देखता कि किसी पारंपरिक खोज एल्गोरिदम के साथ इसे कैसे किया जाए, क्योंकि हम एक विशेष तत्व की तलाश करने के बजाय मास्क से मेल खाने वाले तत्वों की तलाश में हैं। – cberzan

+3

विधि 2 'ओ (2^64) 'स्पेस लेता है, जो निरंतर लेकिन अव्यवहारिक है। –

उत्तर

1

इस प्रकार आ द्विआधारी पेड़ का निर्माण ।

अब, खोज के लिए: यदि मास्क में संबंधित बिट 1 है, तो दोनों बच्चों को पार करें। यदि यह 0 है, तो केवल बाएं नोड को पार करें। अनिवार्य रूप से पेड़ को घुमाने तक रखें जब तक आप पत्ता नोड (बीटीडब्ल्यू, 0 हर मुखौटा के लिए हिट हो)!

इस पेड़ में ओ (एन) अंतरिक्ष आवश्यकताएं होंगी।

1 के लिए पेड़ के उदाहरण के लिए (001), 2 (010) और 5 (101)

  root 
     / \ 
     0  1 
    /\  | 
    0 1 0 
    | | | 
    1 0 1 
    (1) (2) (5) 
+0

यह रैखिक खोज से वास्तव में बेहतर है? सूची में * पहले * तत्व को खोजने की आवश्यकता के बारे में क्या? –

+0

@maxtaldykin यह रैखिक खोज से काफी बेहतर है। हालांकि मैं पहले तत्व आवश्यकता के बारे में निश्चित रूप से सुनिश्चित हूं। मैंने सोचा कि उन नंबरों को क्रमबद्ध किया गया था (जिस स्थिति में मेरा एल्गोरिदम काम करता है)। – ElKamina

+2

@ElKamina, पत्ते में इंडेक्स को स्टोर करने के लिए आपको सबसे छोटी अनुक्रमणिका के साथ मिलान खोजने के लिए। पहले मैच खोजने के बाद आपको न्यूनतम सूचकांक खोजने के लिए ट्रैवर्सिंग पेड़ रखने की आवश्यकता है। ऐसा लगता है कि ओ (एन) से बहुत तेज़ नहीं है। –

3

प्रत्यय पेड़ (बिट्स) पर पत्र-गांठ पर मूल प्राथमिकता के साथ, चाल करना होगा:

000000 -> 8 
    1 -> 5 
    10 -> 4 
    100 -> 3 
    1000 -> 2 
    10 -> 1 
    100 -> 0 
10000 -> 6 
100000 -> 7 

जहां अगर बिट नकाब में सेट कर दिया जाता है, तो आप दोनों हाथों खोज, और यदि नहीं, आप खोज केवल 0 हाथ; आपका उत्तर एक पत्ता नोड पर आपको मिलने वाली न्यूनतम संख्या है।

आप बिट्स को ट्रैवर्स करके क्रमशः (मामूली) सुधार सकते हैं लेकिन अधिकतम भेदभाव से; अपने उदाहरण में, ध्यान दें 3 तत्वों है कि बिट 2 सेट, ताकि आप अपने उदाहरण में

2:0 0:0 1:0 3:0 4:0 5:0 -> 8 
        5:1 -> 5 
       4:1 5:0 -> 4 
      3:1 4:0 5:0 -> 3 
     1:1 3:0 4:0 5:0 -> 6 
    0:1 1:0 3:0 4:0 5:0 -> 7 
2:1 0:0 1:0 3:0 4:0 5:0 -> 2 
       4:1 5:0 -> 1 
      3:1 4:0 5:0 -> 0 

बनाना होगा मुखौटा इससे सहायता नहीं मिलती (जब से तुम दोनों bit2 == 0 और bit2 पार करने के लिए है == 1 पक्षों के बाद से आपका मुखौटा बिट 2 में सेट है), लेकिन औसतन यह परिणाम में सुधार करेगा (लेकिन सेटअप की लागत और अधिक जटिल डेटा संरचना)। अगर कुछ बिट्स दूसरों की तुलना में अधिक सेट होने की संभावना है, तो यह एक बड़ी जीत हो सकती है। यदि वे तत्व सूची में यादृच्छिक के बहुत करीब हैं, तो यह बिल्कुल मदद नहीं करता है।

आप अनिवार्य रूप से यादृच्छिक बिट्स सेट के साथ फंस रहे हैं, तो आप पर औसत (13x speedup) प्रत्यय पेड़ दृष्टिकोण है, जो दक्षता में अंतर की तुलना में बेहतर हो सकता है से (1-5/64)^32 के बारे में लाभ की वजह से और अधिक जटिल आपरेशनों का उपयोग कर मिलना चाहिए (लेकिन इस पर भरोसा न करें - बिट मास्क तेज़ हैं)। यदि आपके पास अपनी सूची में बिट्स का एक गैर-यादृच्छिक वितरण है, तो आप लगभग मनमाने ढंग से अच्छी तरह से कर सकते हैं।

1

प्रीकंप्यूटेड बिटमास्क के साथ। औपचारिक रूप से अभी भी ओ (एन) है, क्योंकि मास्क ऑपरेशंस ओ (एन) हैं। अंतिम पास भी ओ (एन) है, क्योंकि इसे सबसे कम बिट सेट खोजने की ज़रूरत है, लेकिन इसे भी बढ़ाया जा सकता है।

#include <limits.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 

    /* For demonstration purposes. 
    ** In reality, this should be an unsigned long long */ 
typedef unsigned char Thing; 

#define BITSPERTHING (CHAR_BIT*sizeof (Thing)) 
#define COUNTOF(a) (sizeof a/sizeof a[0]) 

Thing data[] = 
/****** index abcdef */ 
{ 0x0c /* 0 001100 */ 
, 0x0a /* 1 001010 */ 
, 0x08 /* 2 001000 */ 
, 0x04 /* 3 000100 */ 
, 0x02 /* 4 000010 */ 
, 0x01 /* 5 000001 */ 
, 0x10 /* 6 010000 */ 
, 0x20 /* 7 100000 */ 
, 0x00 /* 8 000000 */ 
}; 

     /* Note: this is for demonstration purposes. 
     ** Normally, one should choose a machine wide unsigned int 
     ** for bitmask arrays. 
     */ 
struct bitmap { 
     char data[ 1+COUNTOF (data)/ CHAR_BIT ]; 
     } nulmaps [ BITSPERTHING ]; 

#define BITSET(a,i) (a)[(i)/CHAR_BIT ] |= (1u << ((i)%CHAR_BIT)) 
#define BITTEST(a,i) ((a)[(i)/CHAR_BIT ] & (1u << ((i)%CHAR_BIT))) 

void init_tabs(void); 
void map_empty(struct bitmap *dst); 
void map_full(struct bitmap *dst); 
void map_and2(struct bitmap *dst, struct bitmap *src); 

int main (void) 
{ 
Thing mask; 
struct bitmap result; 
unsigned ibit; 

mask = 0x38; 
init_tabs(); 
map_full(&result); 

for (ibit = 0; ibit < BITSPERTHING; ibit++) { 
     /* bit in mask is 1, so bit at this position is in fact a don't care */ 
     if (mask & (1u <<ibit)) continue; 
     /* bit in mask is 0, so we can only select items with a 0 at this bitpos */ 
     map_and2(&result, &nulmaps[ibit]); 
     } 

     /* This is not the fastest way to find the lowest 1 bit */ 
for (ibit = 0; ibit < COUNTOF (data); ibit++) { 
     if (!BITTEST(result.data, ibit)) continue; 
     fprintf(stdout, " %u", ibit); 
     } 
fprintf(stdout, "\n"); 
return 0; 
} 

void init_tabs(void) 
{ 
unsigned ibit, ithing; 

     /* 1 bits in data that dont overlap with 1 bits in the searchmask are showstoppers. 
     ** So, for each bitpos, we precompute a bitmask of all *entrynumbers* from data[], that contain 0 in bitpos. 
     */ 
memset(nulmaps, 0 , sizeof nulmaps); 
for (ithing=0; ithing < COUNTOF(data); ithing++) { 
     for (ibit=0; ibit < BITSPERTHING; ibit++) { 
       if (data[ithing] & (1u << ibit)) continue; 
       BITSET(nulmaps[ibit].data, ithing); 
       } 
     } 
} 

     /* Logical And of two bitmask arrays; simular to dst &= src */ 
void map_and2(struct bitmap *dst, struct bitmap *src) 
{ 
unsigned idx; 
for (idx = 0; idx < COUNTOF(dst->data); idx++) { 
     dst->data[idx] &= src->data[idx] ; 
     } 
} 

void map_empty(struct bitmap *dst) 
{ 
memset(dst->data, 0 , sizeof dst->data); 
} 

void map_full(struct bitmap *dst) 
{ 
unsigned idx; 
     /* NOTE this loop sets too many bits to the left of COUNTOF(data) */ 
for (idx = 0; idx < COUNTOF(dst->data); idx++) { 
     dst->data[idx] = ~0; 
     } 
} 
+0

चूंकि मुखौटा को 64-बिट पूर्णांक की जगह से समान रूप से खींचा जाता है, इसलिए इस विधि को औसतन 2x गति देना चाहिए। –

+0

अधिक स्मृति की कीमत पर, एक बार में एक से अधिक बिट के लिए प्रीकंप्यूटेड बिटमास्क बनाने के द्वारा बिट ऑपरेशंस की संख्या को और कम किया जा सकता है, उदाहरण के लिए 4 बिट निबल्स: 16 * 16 बिटमास्क, प्रत्येक 64/1/16 (4 बिट) को कवर करता है बिट शब्द बिटमैस्क भी कम घना हो जाएगा, जो सेट के लिए एक अलग प्रतिनिधित्व चुनकर शोषण किया जा सकता है। यह निष्क्रिय सीक खोज से संभावित रूप से तेज़ है, लेकिन औपचारिक रूप से अभी भी ओ (एन) है। – wildplasser

+0

यह एल्गोरिदम सरल रैखिक खोज के सभी अच्छे गुणों को बरकरार रखता है। यह सरल, रैखिक, अनुमानित, वेक्टरिजेबल और कैश-अनुकूल है। आगे अनुकूलन के लिए, 4 बिट निबल्स बहुत ही आशाजनक नहीं दिखते हैं। मेरा मानना ​​है कि, सभी संभव 2-बिट क्रमपरिवर्तनों का उपयोग करके 2x गति-गति प्रदान की जाएगी, केवल 30x अधिक मेमोरी लेनी होगी (अभी भी कैश में हो सकती है)। सभी 3,4-बिट क्रमपरिवर्तन सैद्धांतिक रूप से 4x अधिक गति देते हैं, लेकिन सीमित मेमोरी बैंडविड्थ इसे खराब कर देता है। मुझे आश्चर्य है कि बेहतर बिट संयोजनों का आविष्कार करना संभव है ... –

2

यह थोड़ा सा केडी-पेड़ है। इसे प्रति लुकअप ऑपरेशन के लिए 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 के सबसे करीब के साथ एक को चुनने।

परिणाम: यादृच्छिक पिवट चयन बेहतर प्रदर्शन किया।

+0

क्या आप कुछ स्पष्टीकरण दे सकते हैं कि यह एल्गोरिदम कैसे काम करने का इरादा रखता है? मुझे यकीन नहीं है कि यह कोड पढ़ने के अनुमान लगाना संभव है। इस कोड में कई प्रिंट डालने पर, मैंने देखा कि "पेड़" वास्तव में एक रैखिक श्रृंखला है। और 'grab_matches' को कभी भी पुनरावर्ती नहीं कहा जाता है ... –

+0

यह रिकर्सन से बचने का प्रयास करता है। क्या आपने वास्तविक परीक्षण डेटा का उपयोग किया था? बीटीडब्लू, पोस्ट करने से पहले, मैंने सभी डीबगिंग-एफप्रिंटफ() एस ;-) को हटा दिया एल्गोरिदम ऊपर, एल्कामिना के समान है। लेकिन यह अपने पिवट बिट को बिट्स के सेट से चुनता है जो नोड और mask_at_test (जो एक्सओआर और मास्क बिट है) के बीच भिन्न होता है। वास्तव में एक केडी-पेड़, एक-बिट चौड़े आयामों के साथ। बीटीडब्ल्यू: क्या आपने फ़ाइल से वास्तविक परीक्षण डेटा का उपयोग किया था, या केवल अंतर्निर्मित? – wildplasser

+0

ओपी ने कुछ परीक्षण डेटा पोस्ट किए। लिंक ओपी के तहत टिप्पणियों में है। संपादित करें: टिप्पणियों में नहीं, लेकिन ** ** ओपी में। – wildplasser