Python – Data Structures to represent logical expressions

If you wan to use a LRU eviction cache (Least Recently Used eviction), then probably a good combination of data structures to use is:

• Circular linked list (as a priority queue)
• Dictionary

This is why:

• The linked list has a O(1) insertion and removal time
• List nodes can be reused when the list is full and no extra allocations need to be performed.

This is how the basic algorithm should work:

The data structures

LinkedList<Node<KeyValuePair<Input,Double>>> list; Dictionary<Input,Node<KeyValuePair<Input,Double>>> dict;

1. Input is received
2. If the dictionary contains the key
   • return the value stored in the node and move the node to the beginning of the list
3. If the dictionary does not contain the key
   • compute the value
   • store the value in the last node of the list
   • if the last not has a value, remove the previous key from the dictionary
   • move the last node to first position.
   • store in the dictionary the (input, node) key value pair.

Some benefits of this approach are, reading and setting a dictionary value approaches O(1), inserting and removing a node in a linked list is O(1), which means the algorithm is approaching O(1) for reading and writing of values to the cache, and avoids memory allocations and block memory copying operations, making it stable from a memory point of view.

I would be very loath to call a data structure "immutable" unless, once it was exposed to the outside world, unless all changes that are made to its internal state continue at all times to leave the object in the same observable state, and unless the state of the object would be valid with any arbitrary combination of those changes either happening or not happening.

An example of a reasonably-good "immutable" object which obeys this principle is the Java string type. It includes a hash-code field which is initially zero, but which is used to memoize the result of querying the hash code. The state of a string with a zero hash-code field is semantically the same as that of a string where the hash-code field is filled in. If two threads simultaneously attempt to query the hash code, it's possible that both may end up performing the computation and storing the result, but it doesn't matter because neither store will affect the observable state of the object. If a third thread comes along and queries the hash code, it might or might not see the stores from the first two, but the returned hash code will be the same regardless.

(BTW, my one quibble with Java's string-hashing method is that it's possible for the hash function to return zero for a non-null string. I would have thought it better to have the hash function test for zero and substitute something else. For example, if the hashing step is such that adding a single character to a string whose hash is zero will always yield a non-zero hash, simply return the hash of the string minus the last character. Otherwise the worst-case time to hash a long string thousands of times may be much worse than the normal-case time.)

The big things to beware of are (1) sequences of operations which change the state of an object and then change it back, or (2) substitution of objects that appear to have the same state, but don't. Ironically, Microsoft's fixing of what it regarded as bug in its default Struct.Equals method makes #2 harder to protect against. If one has a number of immutable objects which hold references to what appear to be identical immutable objects, replacing all those references with references to one of those immutable objects should be safe. Unfortunately, the Equals overrides for system types Decimal, Double, and Float will sometimes report true even when comparing slightly-different values. It used to be that wrapping one of those types in a struct and calling Equals on that struct would test for true equivalence, but Microsoft changed things so a struct will report Equals if its members do, even if those members hold non-equivalent values of the aforementioned types.