کے ڈی ٹری (C ++ عمل درآمد)

Kd Tree



حوالہ مواد:

https://blog.csdn.net/dymodi/article/details/46830071



https://github.com/ बुद्धिमानDoge/libkdtree



اعلی جہتی اعداد و شمار تک رسائی حاصل کرنے کے لئے اعداد و شمار کے ڈھانچے کے طور پر ، جامد سوالات اور اضافے کے لحاظ سے کے ڈی ڈریچ اب بھی بہت موثر ہے۔ اس آرٹیکل میں یہاں کے ڈی کے درخت کے مندرجات کا تعارف کیا گیا ہے ، اور کے ڈی ڈی درخت کو استعمال کرنے کے کچھ تجربات کے ساتھ مل کر کچھ تبصرے بھی کرسکتا ہے۔ در حقیقت ، کے-ڈی درخت کی تجویز اسٹینفورڈ کے بینٹلی نے 1975 میں کی تھی۔ اس مضمون کا مواد بھی اس کے دو انتہائی مضامین [بین 75] اور [ایف بی ایف 77] سے آتا ہے۔



K-d درخت کا جائزہ اور داخل عمل (اندراج)
سب سے پہلے ، کے ڈی ٹری ایک قسم کا بائنری سرچ ٹریٹ بھی ہے۔ عام متوازن بائنری سرچ ٹری (BST) کے برخلاف ، کے ڈی درخت میں ، ہر نوڈ اسٹورز ایک ریکارڈ ہے ، یا ایک کثیر جہتی جگہ میں ایک نقطہ ، جس کی نمائندگی ویکٹر کے ذریعہ کی جاتی ہے۔ اور کے ڈی کے درخت میں ، یہ نکتہ خلا میں بھی ایک علاقے کی نمائندگی کرتا ہے۔ ہر نوڈ میں دو بچوں کے نوڈ ہوتے ہیں ، اور یہ علاقہ والدین کے نوڈس میں سے ہر ایک کے حصے کی ایک تقسیم ہے۔

ایک جہتی کیس میں ، ہر ریکارڈ کی نمائندگی ایک ایک کلید کے ذریعہ کی جاتی ہے۔ لہذا ، K-d درخت کے ہر نوڈ کے لئے ، اس نقطہ کی جس کی کلید قیمت موجودہ نوڈ کی کلیدی قدر سے کم یا اس کے برابر ہے ، کا تعلق بائیں subtree سے ہے ، اور موجودہ نوڈ کلیدی قدر سے بڑی قیمت کا تعلق دائیں سب ٹری سے ہے۔ لہذا ، یہاں کی اہم قدر امتیازی سلوک بن جاتی ہے۔ K جہت کے معاملے میں ، ریکارڈ کو k اہم اقدار کے ذریعہ پیش کیا جاتا ہے ، جہاں ہر جہت کی کلیدی قدر کو کسی نوڈ کے بائیں اور دائیں سب ٹریج کی طرف نقطہ کی درجہ بندی کرنے کے لئے امتیازی سلوک کے طور پر استعمال کیا جاسکتا ہے۔ کے ڈی درخت میں ، امتیازی سلوک کرنے والے کا انتخاب تہوں کی تعداد سے متعلق ہے جس میں نوڈ واقع ہے ، یعنی جڑ نوڈ پر ، یعنی پرت 0 ، پہلی جہت کی کلیدی قیمت کے مطابق ، پہلی جہت کی کلیدی قیمت جڑ نوڈ کے پہلے جہت کی کلیدی قدر کے کلیدی قدر کے جڑ کے نوڈ سے تعلق رکھنے والے بائیں ذیلی نقطہ سے کم یا اس کے برابر ہے ، اور دائیں ذیلی جگہ جس کی جڑ نوڈ سے متعلق ہے پہلے کی کلیدی قیمت سے زیادہ ہے۔ جڑ نوڈ کے طول و عرض. پھر ، جڑ نوڈ کے بائیں اور دائیں بچوں کے نوڈس کی پوزیشن پر ، یعنی پہلی پرت کی پوزیشن پر ، یہ دوسرے جہت کی کلیدی قدر کے مطابق ممتاز ہے ، وغیرہ۔ یعنی ، کیتھ پرت میں موازنہ کی جانے والی کلیدی قیمت کا طول و عرض D = L Mod k + 1D = L Mod k + 1 ہے۔ جہاں ایل پرتوں کی تعداد ہے جس میں موجودہ نوڈ واقع ہے ، جہاں جڑ نوڈ 0 ویں پرت ہے۔

کے ڈی درخت کے قواعد کے مطابق (0،0) ، (-10، 10)، (10، -10)، (-40، -20)، (-20، 11)، (20، 0) داخل کریں۔ نقطہ ، ہم ذیل میں بائیں تصویر میں دکھائے گئے کے ڈی کے درخت کو حاصل کرسکتے ہیں ، دائیں تصویر ہوائی جہاز میں ان نکات کا ایک اسکیمٹک آریگرام ہے۔ نیلی لائن اشارہ کرتی ہے کہ نقطہ پہلی جہت کی کلیدی قدر سے ممتاز ہے ، اور سرخ لکیر اس بات کی نشاندہی کرتی ہے کہ نقطہ دوسرے جہت کی اہم قدر سے ممتاز ہے۔




ایک ہی وقت میں ، ہم دیکھ سکتے ہیں کہ کے ڈی کے درخت میں موجود ہر نوڈ دراصل کے جہتی خلا میں ایک خطے کی نمائندگی کرتا ہے۔ آئیے مذکورہ بالا دو جہتی خلا میں نکات کو ایک مثال کے طور پر لیں۔ جڑ نوڈ (0،0) پورے ہوائی جہاز کی نمائندگی کرتا ہے ، یعنی (-50، -50، 50، 50) ایسے علاقے کی ، جہاں ہم استعمال کرتے ہیں (xmin، ymin، xmax، ymax) (xmin، ymin، xmax، ymax) اس بات کی نشاندہی کرنے کی وجہ یہ ہے کہ جڑ نوڈ (0،0) پہلے جہت میں ممتاز ہے ، یعنی ، ایکس ایکس محور ، اس کا بائیں بچہ کا نوڈ بائیں آدھے طیارے کی نمائندگی کرتا ہے ، اور دائیں بچہ نوڈ دائیں نصف طیارے کی نمائندگی کرتا ہے۔ نقطہ (-10، 10) (-50، -50، 0، 50) کے ایک علاقے کی نمائندگی کرتا ہے ، اور نقطہ (10، -10) (0، -50، 50، 50) کے علاقے کی نمائندگی کرتا ہے ). اور اسی طرح ، نقطہ پر (-10 ، 10) ، کیونکہ یہ پہلی پرت ہے ، یہ دوسرے جہت سے ممتاز ہے ، لہذا نقطہ کی دوسری جہت (-40 ، -20) نقطہ سے چھوٹا ہے (- 10 ، 10)۔ ، صرف بائیں طرف نقطہ کی دوسری جہت (-20 ، 11) صرف دائیں طرف ، نقطہ (-10 ، 10) سے بڑا ہے۔ مزید یہ کہ ، بائیں نقطہ (-40 ، -20) اپنے پیرنڈ نوڈ کے نچلے نصف کی نمائندگی کرتا ہے ، یعنی (-50، -50، 0، 10) اس طرح کا علاقہ دائیں نقطہ (-20، 11) کی نمائندگی کرتا ہے یہ اوپری ہے اس کے آدھے پیرنٹ نوڈ ، جو (-50 ، 10 ، 0 ، 50) کا ایک علاقہ ہے۔

سرچ آپریشن
اوپر ہم نے K-d درخت کا اصول اور نوڈس داخل کرنے کا عمل متعارف کرایا۔ اب ہم نوڈس کی تلاش کے عمل کو متعارف کراتے ہیں۔ K-d درخت میں پوائنٹس تلاش کرنے کے بہت سے طریقے ہیں۔ ان میں شامل ہیں: (1) مخصوص نکات کے سوالات جو تمام جہتوں سے مطابقت رکھتے ہیں (عین مطابق میچ) (2) کسی خاص علاقے میں پوائنٹس کے جزوی طول و عرض (3) سے ملنے والے سوالات (4) کچھ نکات ملتے ہیں جو کسی خاص نقطہ کے قریب ہوتے ہیں۔

مذکورہ بالا متعدد سرچ الگورتھم کو [بین 75] اور [ایف بی ایف 77] میں تفصیل سے بیان کیا گیا ہے۔ یہاں ہم بنیادی طور پر متعارف کراتے ہیں (3) ، جو میں نے خود استعمال کیا وہ علاقہ کوئری ہے۔ علاقے کے استفسار کا ہدف یہ ہے کہ کے ڈی درخت کی نمائندگی کی جگہ میں مذکورہ بالا مثال کے طور پر بیان کردہ دو جہتی طیارے میں ایک آئتاکار علاقہ (یعنی ایک جگہ (-50، -50، 50، 50) دینا ہے۔ ہر جہت میں اس خطے کی بالائی اور نچلی حدود کو دیکھتے ہوئے ، جیسا کہ اوپر کی مثال کے طور پر ہم اس خطے میں آنے والے تمام نکات کو تلاش کرنے کے لئے ایک علاقہ (-45، -30، -30، -10) دے سکتے ہیں۔

علاقے کی تلاش کا بنیادی طریقہ اس طرح ہے: جڑ نوڈ سے شروع کرتے ہوئے ، اس بات کی تفتیش کی جاتی ہے کہ نوڈ کی کلیدی قیمت کے ذریعہ جس مقام کی نمائش کی جارہی ہے وہ اس علاقے میں ہے جہاں تلاش کیا جاسکتا ہے ، اور اگر یہ اس علاقے میں ہے جس کی جانچ پڑتال کی جائے تو ، نوڈ کو عالمی فہرست میں رکھا جاتا ہے ، اس کے بعد ، یہ جانچ پڑتال کی جاتی ہے کہ آیا نوڈ کے بائیں اور دائیں بچوں کے نوڈس کے ذریعہ نمائندگی والے حصے کو پوچھ گچھ کے علاقے کے ساتھ ایک چوراہا ہے یا نہیں ، اور اگر ایسا ہے تو ، تکرار کے ساتھ بچے کے نوڈ کو جڑ کے نوڈ کے طور پر استعمال کرتا ہے۔ مندرجہ بالا آپریشن انجام دینے کے ل and ، اور اگر نہیں ، تو لوٹ آتا ہے۔ تمام بار بار چلنے والی افعال کے ختم ہونے کے بعد ، ہم ان نکات کی ایک عالمی فہرست حاصل کرسکتے ہیں جو علاقے میں محفوظ ہیں۔ جیسا کہ مذکورہ بالا تفصیل سے دیکھا جاسکتا ہے ، سرچ الگورتھم کی پیچیدگی کا معائنہ کرنے والے علاقے کی جسامت کے ساتھ بڑا رشتہ ہے۔ اگرچہ [ایل ڈبلیو] to] کے مطابق ، بدترین صورتحال والے خطے کی تلاش کی پیچیدگی O (kN1−1k) O (kN1−1k) تک پہنچ جائے گی ، جہاں کے ڈی ڈیٹا پوائنٹ کی جہت ہے اور NN کے ڈی میں نوڈس کی کل تعداد ہے درخت تاہم ، [بین 75 ، ایف بی 74] کی ایک بڑی تعداد نے انضمام دکھایا ہے کہ جب ہائپر آئتاکار خطوں کی تلاش کی جارہی ہے تو کے ڈی ٹری پر ایریا سرچ کافی اچھی (معقول حد تک) اچھی کارکردگی کا مظاہرہ کرتا ہے۔

آپریشن حذف کریں (حذف)
در حقیقت ، کے ڈی ڈریٹ ڈیلیٹ آپریشنز کو اچھی طرح سے سپورٹ نہیں کرتا ہے ، کیوں کہ کے ڈی d درخت میں خود توازن نہیں ہوتا ہے ، اور متحرک اضافے اور حذف کرنے کے عمل K-d درخت کو لکیری ٹیبل میں ہٹا سکتے ہیں۔ اصل میں K-d درختوں کو متوازن کرنے کے بارے میں مطالعات ہیں ، جیسے [Rob81]۔ لیکن شاید نفاذ کی پیچیدگی کی وجہ سے ، کے ڈی D-B درخت کو بہت زیادہ درخواستیں مل رہی ہیں۔

ذیل میں ہم بنیادی طور پر حذف کرنے کے آپریشن کے بارے میں بات کرتے ہیں ، کے ڈی درخت میں نوڈس کو حذف کرنے کا اصول یہ ہے کہ بغیر کسی جانشین نوڈ کے بیرونی نوڈ کے ل the ، ڈیلیٹمنٹ آپریشن براہ راست اندرونی نوڈ پی پی کے لئے انجام دیا جاسکتا ہے جس کے بعد نوڈ ہوتا ہے ، کیا ہے اس کو نوڈ کی جگہ پر رکھنے کے ل its اپنے چائلڈ نوڈس سے ایک مناسب نوڈ کیو کیو تلاش کریں۔ نام نہاد موزوں نوڈ ، یعنی ، اگر پی پی نوڈ کو جے جے طول و عرض میں حد سے تجاوز کیا گیا ہے ، تو پی کیو کے بائیں سب ٹری کے JJ جہت کا سب سے بڑا نوڈ ، یا پی پی کے دائیں سب سبری میں سب سے چھوٹی جے جے جہت ہے۔ نوڈ ، دونوں کر سکتے ہیں۔ کیو کیوڈ کو پی پی نوڈ کے مقام کے ساتھ تبدیل کرنے کے ل the ، کیو کیو نوڈ کو اپنے اصل مقام سے ہٹانے کی ضرورت ہے ، لہذا مذکورہ ڈیلیٹ آپریشن بھی ایک تکرار عمل درآمد عمل ہے۔

میں نے خود کو حذف کرنے کا عمل بہت زبانی بتایا تھا کیونکہ مجھے اسے دوسرے اطلاق کے ساتھ جوڑنا تھا ، لہذا میں نے اسے یہاں جاری نہیں کیا۔

آپریشن کو بہتر بنائیں (اصلاح کریں)
آپٹمائزیشن آپریشن k-d درخت کا ایک آف لائن آپریشن ہے۔ ہم سب جانتے ہیں کہ جب ثنائی درخت اندراج کے عمل کے ساتھ ترقی کرتا ہے ، اگر درخت کے توازن کی ضمانت نہیں دی جاسکتی ہے تو ، بائنری درخت پر آپریشن کی پیچیدگی آہستہ آہستہ خراب ہوجائے گی۔ انتہائی صورت میں ، بائنری ٹری ایک لکیری ٹیبل میں انحطاط پذیر ہوگا۔ متوازن K-d درخت کے ل lookup ، اس کے بعد کے آپریشنز کی کارکردگی کو یقینی بنانے کے ل optim آپٹمائزڈ آپریشنز کے ذریعہ متوازن کیا جاسکتا ہے۔

نام نہاد اصلاح کا آپریشن حقیقت میں طول و عرض کے ترتیب کے مطابق نوڈس کو چھانٹ رہا ہے۔ مثال کے طور پر ، کے ڈی درخت کے لئے جس کو بہتر بنانے کی ضرورت ہے ، اس کے تمام نوڈس کو پہلے طول و عرض کے عنصر کے مطابق چڑھتے ترتیب میں ترتیب دیا جاتا ہے ، پھر درمیانہ والا ایک جڑ نوڈ کے طور پر استعمال ہوتا ہے ، پھر نوڈ کے بائیں نصف حصے کے طور پر استعمال ہوتا ہے اہم سب ٹری کا نوڈ ، اور نوڈس کے نصف ہیں۔ سب ٹری کے نوڈ کے طور پر۔ پھر ، مذکورہ بالا پروسیسنگ بالترتیب بائیں اور دائیں سب ٹریجس کے نوڈس پر انجام دی جاتی ہے ، لیکن ریفرنس کے طول و عرض بالترتیب دوسری جہت ، تیسری جہت ...

مندرجہ بالا پروسیسنگ کے بعد ، ایک صوابدیدی K-d درخت کو متوازن K-d درخت بنایا جاسکتا ہے۔

یہاں ہم کے ڈی درخت کے مندرجات کا خلاصہ بناتے ہیں۔ موجودہ N ڈیٹا پوائنٹس کے ل each ، ہر ایک نقطہ کی نمائندگی کے جہتی اعداد و شمار کے ذریعہ کی جاتی ہے۔ کے ڈی درخت کی تعمیر کی پیچیدگی O (NlogN) O (Nlog⁡N) ہے۔ موجودہ کے ڈی ٹری کو بہتر بنانے کی پیچیدگی O (NlogN) O (NlogN) ہے ، نوڈ ڈالنے کی پیچیدگی O (logN) O (log⁡N) ہے ، اور نوڈ کو حذف کرنے کی پیچیدگی O (logN)) O ہے (log⁡N) ، عین مطابق میچ کرنے کی پیچیدگی O (logN) O (log⁡N) ہے ، اور کسی خاص خطے کی تلاش کے ل the بدترین معاملت کی پیچیدگی O (kN1−1k) O (kN1− 1k) ہے ، لیکن خطے کی تلاش کی پیچیدگی کا تعلق خطے کے سائز سے ہے اور اوسط لحاظ سے اس کا اثر اچھا ہے۔

کوڈ شو نیچے کے طور پر:

kdtree.h

#ifndef KDTREE_H #define KDTREE_H // set dynamic link library #if defined(_MSC_VER) #define DLLExport __declspec(dllexport) #else #define DLLExport #endif // set c++ #ifdef __cplusplus extern 'C' { #endif #include struct DLLExport tree_node { size_t id size_t split tree_node *left, *right } struct DLLExport tree_model { tree_node *root const float *datas const float *labels size_t n_samples size_t n_features float p } DLLExport void free_tree_memory(tree_node *root) DLLExport tree_model* build_kdtree(const float *datas, const float *labels, size_t rows, size_t cols, float p) DLLExport float* k_nearests_neighbor(const tree_model *model, const float *X_test, size_t len, size_t k, bool clf) DLLExport void find_k_nearests(const tree_model *model, const float *coor, size_t k, size_t *args, float *dists) #ifdef __cplusplus } #endif #endif

kdtree.cpp

#include 'kdtree.h' #include #include #include #include #include #include #include #include #include #include // Example: // int x = Malloc(int, 10) // int y = (int *)malloc(10 * sizeof(int)) #define Malloc(type, n) (type *)malloc((n)*sizeof(type)) // If you need to use Intel MKL to accelerate, // you can cancel the next line comment. //#define USE_INTEL_MKL #ifdef USE_INTEL_MKL #include #endif // Clang does not support OpenMP. #ifndef __clang__ #include #endif / / Release a binary tree memory non-recursive algorithm DLLExport void free_tree_memory(tree_node *root) { std::stack node_stack tree_node *p node_stack.push(root) while (!node_stack.empty()) { p = node_stack.top() node_stack.pop() if (p->left) node_stack.push(p->left) if (p->right) node_stack.push(p->right) free(p) } } class KDTree { public: KDTree(){} KDTree(tree_node *root, const float *datas, size_t rows, size_t cols, float p) KDTree(const float *datas, const float *labels, size_t rows, size_t cols, float p, bool free_tree = true) ~KDTree() tree_node *GetRoot() { return root } std::vector FindKNearests(const float *coor, size_t k) std::tuple FindNearest(const float *coor, size_t k) { return FindKNearests(coor, k)[0] } void CFindKNearests(const float *coor, size_t k, size_t *args, float *dists) private: // The sample with the largest distance from point `coor` // is always at the top of the heap. struct neighbor_heap_cmp { bool operator()(const std::tuple &i, const std::tuple &j) { return std::get(i) neighbor_heap // Search for the heap of the K-nearest neighbor (large top heap), the top of the heap is always the farthest point of the sample point in the K-nearest neighbor neighbor_heap k_neighbor_heap_ // p when looking for distance, dist(x, y) = pow((x^p + y^p), 1/p) float p // Whether to release the memory of the tree when destructing bool free_tree_ // tree root node tree_node *root // Training set const float *datas // The number of samples in the training set size_t n_samples // the dimensions of each sample size_t n_features // The label of the training set const float *labels // The cache pool used to find the median std::tuple *get_mid_buf_ // Search for the cache pool for K nearest neighbors, if you have searched for point i, make visited_buf[i] = True bool *visited_buf_ #ifdef USE_INTEL_MKL // Cache when using the Intel MKL library float *mkl_buf_ #endif // Initialize the cache void InitBuffer() // Building a tree tree_node *BuildTree(const std::vector &points) // Find the median of a set of numbers std::tuple MidElement(const std::vector &points, size_t dim) // into the heap void HeapStackPush(std::stack &paths, tree_node *node, const float *coor, size_t k) // Get the value of the dim of the sample point in the training set float GetDimVal(size_t sample, size_t dim) { return datas[sample * n_features + dim] } // Find the distance from the coor to the i-th point of the training set float GetDist(size_t i, const float *coor) // Find the cut point size_t FindSplitDim(const std::vector &points) } // Find the K nearest neighbor of a tree. The id of Ki and the distance between Ki and coor are stored in args and dists respectively. DLLExport void find_k_nearests(const tree_model *model, const float *coor, size_t k, size_t *args, float *dists) { KDTree tree(model->root, model->datas, model->n_samples, model->n_features, model->p) std::vector k_nearest = tree.FindKNearests(coor, k) for (size_t i = 0 i datas = datas model->labels = labels model->n_features = cols model->n_samples = rows model->root = tree.GetRoot() model->p = p return model } // Find the average for regression problems float mean(const float *arr, size_t len) { float ans = 0.0 for (size_t i = 0 i = cur_max) { cur_arg_max = static_cast(i.first) cur_max = i.second } } return cur_arg_max } DLLExport float * k_nearests_neighbor(const tree_model *model, const float *X_test, size_t len, size_t k, bool clf) { float *ans = Malloc(float, len) size_t *args float *dists, *y_pred size_t arr_len int i, j #ifdef USE_INTEL_MKL int n_procs = omp_get_num_procs() assert(n_procs <100) KDTree *trees[100] for (size_t i = 0 i root, model->datas, model->n_samples, model->n_features, model->p) arr_len = k * n_procs #else arr_len = k KDTree tree(model->root, model->datas, model->n_samples, model->n_features, model->p) #endif args = Malloc(size_t, arr_len) dists = Malloc(float, arr_len) y_pred = Malloc(float, arr_len) #ifdef USE_INTEL_MKL #pragma omp parallel for for (i = 0 i CFindKNearests(X_test + i * model->n_features, k, args + k * thread_num, dists + k * thread_num) for (j = 0 j labels[args[j + k * thread_num]] if (clf) ans[i] = vote(y_pred + k * thread_num, k) else ans[i] = mean(y_pred + k * thread_num, k) } for (size_t i = 0 i n_features, k, args, dists) for (j = 0 j labels[args[j]] if (clf) ans[i] = vote(y_pred, k) else ans[i] = mean(y_pred, k) } #endif free(args) free(y_pred) free(dists) return ans } inline KDTree::KDTree(tree_node *root, const float *datas, size_t rows, size_t cols, float p) : root(root), datas(datas), n_samples(rows), n_features(cols), p(p), free_tree_(false) { InitBuffer() labels = nullptr } inline KDTree::KDTree(const float *datas, const float *labels, size_t rows, size_t cols, float p, bool free_tree) : datas(datas), labels(labels), n_samples(rows), n_features(cols), p(p), free_tree_(free_tree) { std::vector points for (size_t i = 0 i KDTree::FindKNearests(const float *coor, size_t k) { std::memset(visited_buf_, 0, sizeof(bool) * n_samples) std::stack paths tree_node *p = root while (p) { HeapStackPush(paths, p, coor, k) p = coor[p->split] id, p->split) ? p = p->left : p = p->right } while (!paths.empty()) { p = paths.top() paths.pop() if (!p->left && !p->right) continue if (k_neighbor_heap_.size() left) HeapStackPush(paths, p->left, coor, k) if (p->right) HeapStackPush(paths, p->right, coor, k) } else { float node_split_val = GetDimVal(p->id, p->split) float coor_split_val = coor[p->split] float heap_top_val = std::get(k_neighbor_heap_.top()) if (coor_split_val > node_split_val) { if (p->right) HeapStackPush(paths, p->right, coor, k) if ((coor_split_val - node_split_val) left) HeapStackPush(paths, p->left, coor, k) } else { if (p->left) HeapStackPush(paths, p->left, coor, k) if ((node_split_val - coor_split_val) right) HeapStackPush(paths, p->right, coor, k) } } } std::vector res while (!k_neighbor_heap_.empty()) { res.emplace_back(k_neighbor_heap_.top()) k_neighbor_heap_.pop() } return res } void KDTree::CFindKNearests(const float *coor, size_t k, size_t *args, float *dists) { std::vector k_nearest = FindKNearests(coor, k) for (size_t i = 0 i left = nullptr node->right = nullptr node->id = arg_mid_val node->split = dim std::vector left, right for (auto &i : points) { if (i == arg_mid_val) continue if (GetDimVal(i, dim) left = BuildTree(left) if (!right.empty()) node->right = BuildTree(right) return node } std::tuple KDTree::MidElement(const std::vector &points, size_t dim) { size_t len = points.size() for (size_t i = 0 i id if (visited_buf_[id]) return visited_buf_[id] = true float dist = GetDist(id, coor) std::tuple t(id, dist) if (k_neighbor_heap_.size()

main.cpp

#include 'kdtree.h' #include #include int main() { float datas[100] = {1.3, 1.3, 1.3, 8.3, 8.3, 8.3, 2.3, 2.3, 2.3, 1.2, 1.2, 1.2, 7.3, 7.3, 7.3, 9.3, 9.3, 9.3, 15, 15, 15, 3, 3, 3, 1.1, 1.1, 1.1, 12, 12, 12, 4, 4, 4, 5, 5, 5} float labels[100] for(size_t i = 0 i <12 ++i) labels[i] = (float)i tree_model *model = build_kdtree(datas, labels, 12, 3, 2) float test[6] = {3, 3, 3, 4, 4, 4} size_t args[100] float dists[100] Find_k_nearests(model, test, 5, args, dists) // This only searches for K neighbors of (3,3,3) printf('K-Nearest: ') for (size_t i = 0 i root free(ans) free_tree_memory(model->root) return 0 }

آپریشن کا نتیجہ