[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[task #15713] Make quad structure to make unique hashes of 4 objects
From: |
Sachin Kumar Singh |
Subject: |
[task #15713] Make quad structure to make unique hashes of 4 objects |
Date: |
Fri, 17 Jul 2020 19:56:31 -0400 (EDT) |
User-agent: |
Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:76.0) Gecko/20100101 Firefox/76.0 |
Follow-up Comment #19, task #15713 (project gnuastro):
For the kd-tree, I have a bit dilemma on choosing the type of implementation.
In one implementation(as given in its Wikipedia) it uses median to build the
tree. But in another, it is also possible to build a tree without median(using
only the axis to determine the next child). Also, it is mentioned in its
Wikipedia page that,
Note that it is not required to select the median point. In the case where
median points are not selected, there is no guarantee that the tree will be
balanced. To avoid coding a complex O(n) median-finding algorithm or using an
O(n log n) sort such as heapsort or mergesort to sort all n points, a popular
practice is to sort a fixed number of randomly selected points and use the
median of those points to serve as the splitting plane. In practice, this
technique often results in nicely balanced trees.
Now it is desired/recommended to use a balanced tree for proper tree heights
and skewness and hence fast operations. But if I choose the one with median,
I'll have to make the array beforehand rather than inserting the hashes as
they are made, which is a better and more modular design. What do you
suggest?
P.S- Both kinds of implementation are ready to be tested after this minor
problem is solved:-)
_______________________________________________________
Reply to this item at:
<https://savannah.gnu.org/task/?15713>
_______________________________________________
Message sent via Savannah
https://savannah.gnu.org/
- [task #15713] Make quad structure to make unique hashes of 4 objects, (continued)
- [task #15713] Make quad structure to make unique hashes of 4 objects, Mohammad Akhlaghi, 2020/07/10
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/11
- [task #15713] Make quad structure to make unique hashes of 4 objects, Raul Infante-Sainz, 2020/07/14
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/14
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/14
- [task #15713] Make quad structure to make unique hashes of 4 objects, Mohammad Akhlaghi, 2020/07/15
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/16
- [task #15713] Make quad structure to make unique hashes of 4 objects, Mohammad Akhlaghi, 2020/07/16
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/16
- [task #15713] Make quad structure to make unique hashes of 4 objects, Mohammad Akhlaghi, 2020/07/16
- [task #15713] Make quad structure to make unique hashes of 4 objects,
Sachin Kumar Singh <=
- [task #15713] Make quad structure to make unique hashes of 4 objects, Mohammad Akhlaghi, 2020/07/17
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/18
- [task #15713] Make quad structure to make unique hashes of 4 objects, Mohammad Akhlaghi, 2020/07/18
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/28
- [task #15713] Make quad structure to make unique hashes of 4 objects, Mohammad Akhlaghi, 2020/07/28
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/29
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/30
- [task #15713] Make quad structure to make unique hashes of 4 objects, Mohammad Akhlaghi, 2020/07/30
- [task #15713] Make quad structure to make unique hashes of 4 objects, Sachin Kumar Singh, 2020/07/31
- [task #15713] Make quad structure with hashes and store in kd-tree, Mohammad Akhlaghi, 2020/07/31