mvanaltvorst
Joined 7 years ago
Joined 7 years ago
[1]: https://github.com/google/jax/issues/16321 [2]: https://github.com/google/jax/issues/17490
I really like PyMC's API, but as soon as you move towards bigger datasets JAGS or Stan seem to be the only practical options.
This seems to be another variant that claims to find the global minimum quicker than other existing methods. I am not experienced enough to verify this claim. I am also not sure how this new algorithm performs in practice; in theory, ellipsoid methods are a lot more efficient than simplex methods for optimising convex functions, while in practice simplex methods are usually an order of magnitude faster. So take this result with a grain of salt.
An example is the fact that `for_each` is not supported on providers [1], an issue with 230 likes which has not been solved since January 2019. This had me resort to a Python script which generates a `.tf.json` file, definitely not ideal. Infrastructure as code sounds great, but in practice it's closer to "infrastructure as a non-standard markup language".
You could also construct a graph, where every price is a node. Start at 0.00, and do a BFS until you find the desired price. Worst case scenario O(n) where n is the desired price. Could be optimised by using a path finding algorithm like A*, its heuristic would make it try a greedy algorithm at first and then do a more complex solve at the end.
Another possibility is by memoization (dynamic programming). Strictly worse than the graph algorithm in complexity terms, but in practice your computer is very good at working sequentially on a very big array of booleans.
Really many different approaches to solve this problem. In this specific case greedy worked as well.