5 ms·

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 *

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...

tyingq 6y ago
"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-with-pointers-structures-and-arrays 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/ https://discodb.readthedocs.io/en/latest/
brundolf 6y ago
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.
- nicoburns 6y ago
  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.
  - brundolf 6y ago
    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
    - nicoburns 6y ago
      I believe C++ has "Runtime Type Information" (RTTI) that allows you to do this. Although I also hear that it's not great.
      - MaxBarraclough 6y ago
        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-or-exceptions https://llvm.org/docs/CodingStandards.html#do-not-use-rtti-o... [1] https://google.github.io/styleguide/cppguide.html#Run-Time_Type_Information__RTTI_ https://google.github.io/styleguide/cppguide.html#Run-Time_T...
ectopod 6y ago
Use an object?
whateveracct 6y ago
if the fields are different types, how do you know the type of key access's return?
- daneelsan 6y ago
  I guess that can be solved by creating an Expression type
daneelsan 6y ago
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...
sgtnoodle 6y ago
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.
- daneelsan 6y ago
  Yes. At some point i encountered this trie with payloads (which would act as t he field values).
ben509 6y ago
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#collections.namedtuple https://docs.python.org/3/library/collections.html#collectio... [2]: https://docs.python.org/3/reference/datamodel.html#object.__slots__ https://docs.python.org/3/reference/datamodel.html#object.__...
- daneelsan 6y ago
  That seems like the thing I'm looking for! Thanks for the info
mywittyname 6y ago
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.

tyingq 6y ago

"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-with-pointers-structures-and-arrays 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/ https://discodb.readthedocs.io/en/latest/

brundolf 6y ago

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.

nicoburns 6y ago
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.
- brundolf 6y ago
  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
  - nicoburns 6y ago
    I believe C++ has "Runtime Type Information" (RTTI) that allows you to do this. Although I also hear that it's not great.
    - MaxBarraclough 6y ago
      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-or-exceptions https://llvm.org/docs/CodingStandards.html#do-not-use-rtti-o... [1] https://google.github.io/styleguide/cppguide.html#Run-Time_Type_Information__RTTI_ https://google.github.io/styleguide/cppguide.html#Run-Time_T...

ectopod 6y ago

Use an object?

whateveracct 6y ago

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

daneelsan 6y ago
I guess that can be solved by creating an Expression type

daneelsan 6y ago

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...

sgtnoodle 6y ago

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.

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

ben509 6y ago

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#collections.namedtuple https://docs.python.org/3/library/collections.html#collectio... [2]: https://docs.python.org/3/reference/datamodel.html#object.__slots__ https://docs.python.org/3/reference/datamodel.html#object.__...

daneelsan 6y ago
That seems like the thing I'm looking for! Thanks for the info

mywittyname 6y ago

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.