Pixar, Adobe, Apple, Autodesk, and Nvidia Form Alliance for OpenUSD

Re:Pixar, Adobe, Apple, Autodesk, and Nvidia Form Alliance f... by panzi on Tuesday August 01, 2023 @11:38PM (#36966697)

Interesting. Since the list is sorted, is the insertion still a linear search (O(N)) or now a binary search (O(log(N))? Or did I misunderstand something? Also, why is it not a hash table (almost O(1))?

[ Parent | on HN ]

Re:Pixar, Adobe, Apple, Autodesk, and Nvidia Form Alliance f... by bssrdf on Wednesday August 02, 2023 @11:37AM (#36972364)

Good point, I have the same doubt. Even if it is sorted, you still cannot do binary search on it unless using some skip list ideas. In fact, the code right now is doing linear search to find the ID given a name.

TBH, I don't fully understand how the ID linked list is utilized in Blender and why it needs to sorted by names. It seems some other data structure could also work, unless I missed something.

[ Parent | on HN ]

Re:Pixar, Adobe, Apple, Autodesk, and Nvidia Form Alliance f... by panzi on Thursday August 03, 2023 @05:41PM (#36992369)

Oh is it an actual linked list and not an array?

[ Parent | on HN ]

Re:Pixar, Adobe, Apple, Autodesk, and Nvidia Form Alliance f... by bssrdf on Thursday August 03, 2023 @06:41PM (#36993068)

Yes, actually it is a doubly linked list.

[ Parent | on HN ]