Originally published on melvinkoh.me : Dictionary changed size during iteration”, Python slaps you in your face when you try to add/remove entries in object during iteration. “RuntimeError dict In this post, I will walk us through how we can filter a collection. First, let us try to understand the problem by running this snippet in your interpreter: dict typing Dict { : { : , : , : , }, : { : , : , : , }, : { : , : , : , }, : { : , : , : , } } coffees = get_menu() code, details coffees.items(): details.get( ) : coffees[code] from import -> Dict[str, dict]: def get_menu () return "TIMMY_BLACK" "item" "Timmy's Coffee Barista's Black" "sugar_free" True "with_milk" False "TIMMY_LATTE" "item" "Timmy's Coffee Latte" "sugar_free" True "with_milk" False "TIMMY_SWEETENED_LATTE" "item" "Timmy's Coffee Latte - Sweetened" "sugar_free" True "with_milk" True "TIMMY_SIGNATURE_CARAMEL" "item" "Timmy's Signature - Caramel Latte" "sugar_free" None # Unknown "with_milk" True # Filter unsweetened coffees -> RuntimeError for in if "sugar_free" is True del > Try to run this snippet! ☝️ You will get a RuntimeError, as expected. > “RuntimeError: dictionary changed size during iteration”, Python interpreter The error message is self-explanatory and this makes perfect sense, you shouldn’t be able to expand/shrink the collection while you are looping through it. Imagine if you are allowed to do so, and you keep expanding the collection in your loop body: random data = { : , : , : } k data: rand = random.randint( , ^ ) data[rand] = rand import 1 1 2 2 3 3 # This will raise an Error for in 4 2 31 If the above snippet is valid in Python, we will slump into infinite loop until memory is run out. So, in any event we want to filter a object in Python, can we circumvent away from the RuntimeError? Of course! dict Possible Solutions Solution #1: Use A Shallow Copy This is the least favorable solution, given that we have to create a new copy of the dictionary. coffees = get_menu() coffee_copy = {**coffees} code, details coffee_copy.items(): details.get( ) : coffees[code] """ Solution #1: Create a shallow copy of dict """ # I use this function to generate my dict object # Create a shallow copy for in if "sugar_free" is True del The above code will work, but it’s less hygienic to me. Solution #2: Use A Copy Of Dictionary Keys Another solution is instead, create a copy of dictionary keys as our iterator: coffees = get_menu() key_copy = tuple(coffees.keys()) k key_copy: coffees[k].get( ) : coffees[k] """ Solution #2: Create a copy of keys """ # Feel free to use any iterable collection for in if "sugar_free" is True del Solution #3: Deferred Update If you are against of create any copy of either the source dictionary or the keys, we can also use the “deferred update” strategy. Deferred update, as the name tells, is to defer any mutation to the dictionary until the iteration is over. coffees = get_menu() keys_to_be_removed = [] code, details coffees.items(): details.get( ) : keys_to_be_removed.append(code) k keys_to_be_removed: coffees[k] """ Solution #3: Deferred Update Risk: What if an Exception is raised half way? """ for in if "sugar_free" is True for in del However, a caveat here. Imagine an uncaught exception in between line 9 and 10, the iteration will break, all pending updates will be void and your object will be left intact. dict I personally in favor of using copy of dictionary keys and deferred update. In the subsequent part of this post, I will use the former to illustrate how we can make our filter logic reusable. Making The Logic Reusable At this point, I decided to use a copy of dictionary keys to mitigate the problem when attempting to delete entries during iteration. Let’s see how we can make the logic reusable. In my case, I created — a subclass of the built-in class to add method: FilterableDict dict filter() dict.__init__(self, *args, **kwargs) key_copy = tuple(self.keys()) k key_copy: predicate(k, self.get(k)): self[k] self .format(super().__repr__()) : class FilterableDict (dict) : def __init__ (self, *args, **kwargs) : def filter (self, predicate) # use Tuple to further reduce memory footprint for in if del return : def __repr__ (self) return "FilterableDict({})" > FilterableDict, subclass of built-in dict class To further reduce the memory footprint of our key copy, I use a instead of a collection to store them. tuple list Let’s make use of our and observe the output: FilterableDict > Using our FilterableDict Here we go, a reusable class to support filtering for a dictionary in Python. Full Source Code: typing Dict { : { : , : , : , }, : { : , : , : , }, : { : , : , : , }, : { : , : , : , } } dict.__init__(self, *args, **kwargs) key_copy = tuple(self.keys()) k key_copy: predicate(k, self.get(k)): self[k] self .format(super().__repr__()) coffees = FilterableDict(get_menu()) coffees len(coffees) sugar_free_filter = _, v: v[ ] coffees.filter(sugar_free_filter) len(coffees) from import # Helper function to generate dict object -> Dict[str, dict]: def get_menu () return "TIMMY_BLACK" "item" "Timmy's Coffee Barista's Black" "sugar_free" True "with_milk" False "TIMMY_LATTE" "item" "Timmy's Coffee Latte" "sugar_free" True "with_milk" False "TIMMY_SWEETENED_LATTE" "item" "Timmy's Coffee Latte - Sweetened" "sugar_free" True "with_milk" True "TIMMY_SIGNATURE_CARAMEL" "item" "Timmy's Signature - Caramel Latte" "sugar_free" None # Unknown "with_milk" True # Our dict subclass : class FilterableDict (dict) : def __init__ (self, *args, **kwargs) : def filter (self, predicate) for in if del return : def __repr__ (self) return "FilterableDict({})" # FilterableDict({...}) # 4 lambda not "sugar_free" # 3 Final Words A different way to achieve the same purpose? Leave me a comment :)
