Hacker News Reader

Comment by daneelsan | Hacker News Reader

This might not be the best place to ask but: I'm wondering what the best data structure is for these needs: * there are fields and values, similar to a struct * I know at initialization time what fields there are (assume a string) * at run time I want to be able to get this values accessing via the key/field * also I want to update those values * what I don't care about is inserting/deleting fields because that's now allowed,

I guess what I want is a struct like data structure, but in an interpreted language

Mightve typed to fast...

View on HN

You're looking for something similar to Python's namedtuple.[1] (Though modern python should use a dataclasses in the stdlib or the attrs package.)

Essentially, you have an array/list/vector under the hood, and a mapping of field names to array indices to govern field access.

If you're trying to implement this at a lower level, in the interpreted language itself, take a look at the slots mechanism[2] in Python.

[1]: https://docs.python.org/3/library/collections.html#collectio...

[2]: https://docs.python.org/3/reference/datamodel.html#object.__...

That seems like the thing I'm looking for! Thanks for the info

Sounds like you want a struct except you want to be able to reflect on the property keys (which you can't do normally in C/C++/Rust)?

I got thrown off by "but in an interpreted language" so I'm not sure whether you're requesting this for C or for another language. In JS, at least the V8 engine does some of this for you: if you have a group of objects that always have the same set of properties, V8 will detect this in many cases and optimize them under the hood as a struct or class (it must also store the string keys somewhere since those can be iterated in JS).

In C/C++ you'd have to store the keys as strings somehow, and also add some way to index the struct via those keys (since you can't even do that with a normal struct). You may be stuck with a hashmap one way or another.

Rust allows you to do this with a macro. The serde macros are pretty close to what you need, but a slight variant could give you a much more ergonomic API.

Right, I thought about suggesting a macro for C/C++ but I don't know enough about their macro systems to know for sure that it would work

I believe C++ has "Runtime Type Information" (RTTI) that allows you to do this. Although I also hear that it's not great.

To expand on not great: RTTI is one of the few features of C++ where you pay for it even if you don't use it, so it's not all that popular. It can be disabled with compiler flags to shrink the binary. LLVM's coding standard prohibits use of RTTI, they instead use their own 'hand-rolled' solution. [0] RTTI is also banned by the Google C++ coding standard. [1]

[0] https://llvm.org/docs/CodingStandards.html#do-not-use-rtti-o...

[1] https://google.github.io/styleguide/cppguide.html#Run-Time_T...

It depends on what you want its footprint in memory to look like. Since you don't need to mutate the structure, a densely packed structure seems optimal. For small structures, linearly searching through an array would be fast. For larger structures, a sorted array could be binary searched efficiently.

It also depends on how you can represent the string and their typical size. If the strings are small, then allocating fixed size chunks to store them inline might make sense. If the strings are long, it might make sense to go crazy and use a "trie" data structure to minimize comparisons.

I believe python uses hash maps for classes by default, but you can alternatively use "slots", which are less mutable and presumably more densely packed.

Yes. At some point i encountered this trie with payloads (which would act as t he field values).

"I guess what I want is a struct like data structure, but in an interpreted language"

Python ffi is an option: https://cffi.readthedocs.io/en/latest/using.html#working-wit...

Though I don't know what advantage that route would have over most interpreted language's already existing associative arrays / hashmaps / dicts.

There may be some module already built that serves your needs. DiscoDB is a good example..a very fast hashmap that uses mmap(). https://discodb.readthedocs.io/en/latest/

Sorry if I wasn't clear enough. Yes I want something like an object in javascript, like a struct in C but at runtime. But I want to implement this myself. At first I thought a hash table was the right choice. But I don't need the insert delete increase capacity that this data structure typically needs to implement. I want to implement this in Mathematica. The language doesn't have native objects given that the main idea is for things to be immutable. But I still can program data structures, so I'm looking for one...

A class? After all, an class is a struct with some additional features to handle functions.

You can use a static instance if you just need a single object.

if the fields are different types, how do you know the type of key access's return?

I guess that can be solved by creating an Expression type

Use an object?

Reply on news.ycombinator.com