-1

I don't understand what's unclear in this question. From what I can tell, it's a yes or no. Comments have asked "why", perhaps suggesting I don't need to do what I'm trying to do, but that doesn't invalidate the question. I'm not asking if it is the best way of solving a particular problem, I'm asking if it's a way at all.

If bools stored a boolean literal instead of an array, the answer is a simple "yes", and if additionally x isn't an array, then the answer is "yes in Python with functools.lru_cache".

What's missing?


Update: thanks for everyone's feedback.

While I understand the mentioned flaws, I don't understand StackOverflow's handling of it. I wouldn't make this post if the question was closed with 3 downvotes. It was 18 downvotes, closed, deleted.

I have seen complete garbage questions not treated worse. I've also seen worse questions per closure's cited reasons treated better. Nothing in what anyone has said warrants such a response, and if this is disagreeable, then StackOverflow still has a problem.

9
  • 4
    If you really think the answer is just a yes or a no, then here, it's a yes. Does that really answer your question? You clearly have a problem in your mind that's more than that, and there's no way to tell what it is.
    – Passer By
    Jul 7, 2022 at 19:04
  • 2
    @PasserBy "You clearly have a problem in your mind that's more than that, and there's no way to tell what it is" - Spot on.
    – Ted Lyngmo
    Jul 7, 2022 at 20:40
  • 1
    You already show you think it's possible, you outline an "approach I can imagine". Also you are not clear about just what the requirements are. Including, "caching" is not only not clear, it isn't the right word, that is for data not code. Moreover "optimized" (let alone "extremely") has no specific meaning outside detailed context (and tends to be chaotically dependent on details) let alone across languages. Also the post is disorganized.
    – philipxy
    Jul 7, 2022 at 20:56
  • @philipxy "caching" [...] isn't the right word, that is for data not code. - So codecache doesn't exist? Jul 7, 2022 at 21:16
  • 1
    @KellyBundy One can find many words used in some context, that doesn't mean they work like that in any context. Caching in the context of the language used in the question and even the utility alluded to refers to caching concrete results. Can one construct a situation where code/instructions are that result? Yes. Does the question do so? Not as far as I can tell. And even if we were to say it does, as the comments on your answer indicate that is apparently still not what is wanted. Jul 8, 2022 at 5:04
  • 1
    @MisterMiyagi "Does the question do so?" - I think it does. It asks "can [the sequence of paths] be cached?". In my understanding, that means it wants to execute the modifying instructions on the path without re-evaluating over and over again which ones to use (which way the path goes). Which is what my solutions do. For each key, they evaluate once which modifying instructions to use, and cache the resulting "path". But yes, that's apparently still not what they want, and I'll leave it at what it is. For me it was interesting to do, and maybe it's interesting for someone else as well. Jul 8, 2022 at 5:19
  • @KellyBundy Don't get me wrong, I fully agree that what you guessed the question to be is very interesting and quite fun to play with. Jul 8, 2022 at 5:21
  • 1
    "I wouldn't make this post if the question was closed with 3 downvotes." - Isn't that exactly what you did? - "It was 18 downvotes, closed, deleted" - Wasn't that after you made this post, as a result of making this post? Jul 9, 2022 at 1:12
  • Stack Overflow does not have a problem. It has many problems. It is up to the individual to keep an open mind and try to understand why those problems are persistent. When you use Stack Overflow as intended, which is to search for answers, you will have little to no problem with it. It might take a while to find an answer among many answers, but in general what you need is there. It is only when asking questions that things get dicy as then you have to really do quadruple the effort - which is exactly what is expected of you. So better to not ask, search instead. Much better experience.
    – Gimby
    Jul 12, 2022 at 14:04

2 Answers 2

15

If your goal is really just to get a yes/no answer - yes, a pure function* can always be memoized safely (whether doing so is practical or not does not seem to be something you care about)... but such yes/no questions are frowned upon in general.

The question does not look practical - so it is not expected to receive a warm welcome. Based on comments ("the actual objective is to speed up out[i] = 2*x[i] + y[i]/2") you actually need to compute something different and the question looks like an optimization request of a random middle step in an attempt to optimize some algorithm. The only hope for such a question is to be very interesting and have clear scoring for the answer - unfortunately it looks like many "provide some code that I would like" questions where OP's sense of taste is the only criteria.

Should it be closed? Probably - to me, it is quite unclear what would make a particular piece of code an actual answer, especially since you are willing to accept multiple languages as the solution.

Explaining what your actual goal is may make the question look more practical. It is quite possible that there is a well known approach that is easier to optimize (or optimized already). Or at the very least some people may see actual value in searching for the answer.

Alternatively, you can make the question more interesting (may need to re-ask the question)

  • come up with a solution where you don't understand why it is faster or slower and ask for an explanation;
  • come up with some ridiculous claim so people will try to debunk it
  • come up with some entertaining story about why you need that optimization
  • get crystal-clear rules for the winning answer. Preferably stick to one language per question.

*Note that the function as written in the question is not pure and can't be memoized, but equivalent one that returns result in a new array is. My statements should be more "function in the question can be easily converted to pure and become memoizable. Thanks Karl Knechtel for comment highlighting that.

1
  • 11
    "Preferably stick to one language per question" emphasis on that bit, it seems absurd to include "Python (likely Cython) > C > C++ > assembly" when what OP is asking for is possible in all these languages with varying degrees of difficulty/usefulness. Also say they got an answer in x86 what would they even do with that...?
    – 0x263A
    Jul 7, 2022 at 4:37
7

Some issues:

  1. Is this intended as a language-agnostic question, or are you just listing off implementation languages you're willing to use? In the first case, try to show pseudocode, and be explicit that the question is about theory - i.e. saying to use such and such a library tool isn't really appropriate; the question is about general technique. (Also consider https://cs.stackexchange.com instead.) In the second case, pick one and stick with it; otherwise you are effectively asking multiple questions in one.

  2. Is this indeed a question about whether it's possible, or a question about how to do it? (It is not possible for the setup that is shown; but it seems that you misunderstand why.) If you really just want someone to explain specifically what the requirements are to make caching possible, then that is an answerable question.

  3. What is the underlying context? How many keys are there? How many possible initial values of x are there? Why are we running this code?

  4. "The context in question is extremely optimized and can't afford things like for idx in true_indices: x[idx] += 1" is a strange thing to say when your language of preference is Python, even with Cython enhancements. The code will have to iterate to compute results for the cache, even if they can be cached. It isn't clear if you're using Numpy; you might want to look into that.

  5. I have no idea how the current title, "Cache a conditional in for loop", is supposed to prepare anyone for the question being asked. Unless there's some confusion over what caching means to you? Normally, we cache outputs of a function for given inputs. Were you perhaps hoping to, somehow, cache unrolled code for the inner loop, according to only one of the parameters? I can't make a lot of sense of it.

7
  • I'm interesting in reasoning for your 2 - to me it looks like method is pure and it is trivial (probably non-practical) to cache results for any input. Not sure why you think it is not possible in OP's case. (I can start separate SO question if you think answer in comment would not be enough) Jul 8, 2022 at 4:16
  • @ArvindKumarAvinash The function isn't pure, it modifies one of its arguments. For any usual means of caching, it cannot be cached. Not even the supposed "instruction cache" is possible at face value, because these instructions are never present in isolation. Jul 8, 2022 at 4:50
  • @MisterMiyagi What do you mean with "present in isolation"? Btw, I posted an answer in the meantime, and I consider the two solutions that compile to be a kind of instruction cache... Jul 8, 2022 at 5:07
  • @KellyBundy Python never unrolls the loop to fixed instructions like x[0] += 1 x[1] += 1 and so on. It only has the instructions for looping and dynamic access. So for what the question is working with the thing the OP wants cached * just does not exist. Can we manually write a code compiler with unrolling and const propagation and cache its output? Sure, and I think your answer shows that nicely. Does that mean caching of anything non-trivial related to the original function? No. Jul 8, 2022 at 5:14
  • 1
    I meant "unrolling the loop" in the sense of dynamically compiling code with those fixed instructions - like Kelly Bundy's answer does. "Does that mean caching of anything non-trivial related to the original function?" Well, that's the entire point of the request for clarification, right? It isn't clear what OP thinks qualifies as a cache, nor what OP's mental model is for how caching works in general. Jul 8, 2022 at 7:29
  • 2
    @AlexeiLevenkov the function looks up data from the global bools_all, and it communicates its result by mutating the passed-in x object rather than by returning a value. Neither of those is permissible for a pure function. Naively applying functools.cache to the function would result in cached calls failing to modify x and simply returning the cached None that was returned the first time. Jul 8, 2022 at 7:32
  • @KarlKnechtel fair point. I looked at that function differently - it produces exactly the same value for the same inputs and unfortunately clobbers input with output. But indeed as written it can't be memoized... Jul 8, 2022 at 7:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .