Python Dictionary ported to LabVIEW

[crabstew]

I missed having proper hash map dictionaries in LabVIEW and was not happy with the implementation from Bloomy so I implemented a proper dictionary in LabVIEW. Based mostly off of this wonderful talk from one of the core Python developers, it uses 4 arrays to track the keys, values, hashes and index map and 2 ints to keep track of how many elements there are and how many buckets are used in the index map.

On average, inserts and gets are much faster than variant attributes, relabels are orders of magnitude faster and deletes are a tad slower.

Try it out and see if you can squeeze any more performance out of it. I'm not super familiar with the intricacies of the LabVIEW compiler so I'm sure there is something I've overlooked performance-wise but it was pretty fun nonetheless and I'm quite happy with the results.

[OneOfTheDans]

I'd really like to see how you did this, and perhaps use it in our application. Would you mind posting a 2013 port? Thanks!

[crabstew]

---

@OneOfTheDans wrote:

I'd really like to see how you did this, and perhaps use it in our application. Would you mind posting a 2013 port? Thanks!

---

Attached.

[OneOfTheDans]

Thanks for the port, this looks neat! Did you build this exactly following Python's algorithm, or just was that just the source of inspiration? And this handles key collisions by re-modulating the hash inside _lookup? I'm looking forward to using this in one of our projects soon. I'll touch base here if there are any issues, or further optimizations.

[Yamaeda]

I can't open your code right now, but i'll assume you have 1 variant, right? You could do an array of variants, similar to buckets and then use attributes as the list. I wonder how that'll compare. 🙂

/Y

[crabstew]

@OneOfTheDans wrote:

Thanks for the port, this looks neat! Did you build this exactly following Python's algorithm, or just was that just the source of inspiration? And this handles key collisions by re-modulating the hash inside _lookup? I'm looking forward to using this in one of our projects soon. I'll touch base here if there are any issues, or further optimizations.

---

I pulled the majority of the algorithm straight from Python. Only thing that's a bit different is the resizing strategy and that's mostly because LabVIEW makes an array copy whenever you append or delete from the end of an array.

The hashing scheme uses a linear probe with perturbation on hash collision. Sounds complicated but the source code is really well commented.

---

@Yamaeda wrote:

I can't open your code right now, but i'll assume you have 1 variant, right? You could do an array of variants, similar to buckets and then use attributes as the list. I wonder how that'll compare. 🙂

/Y

---

What you're suggesting sounds very similar to Bloomy's implementation. The problem with using Variant Attributes is that they use a binary search tree (O(log n)) to store values rather than a hash map (O(1)).