4 ms·
Note that you're copying one half of the list into a new list at each recursive call, making the algorithm O(n). Better to pass the original list and use indice
by blackbear_ 6y ago
Note that you're copying one half of the list into a new list at each recursive call, making the algorithm O(n). Better to pass the original list and use indices to indicate which portion you're working on
- nomy99 6y agogreat suggestion
- tzs 6y agoSuppose he changed the type of numbers from List[int] to Tuple[int]. Would that get rid of the copying? Tuples are immutable in Python, so in theory it should be able to but I have no idea if Python actually makes that optimization. Even if it does, this is probably not a good approach in Python because Python does not optimize away tail recursion.
- zbentley 6y agoPython will reclaim/reuse tuples sometimes, but I'm unsure if it will fully "intern" them the way it does for ints (and java does for some strings). Regardless, even if that optimization is present, the overhead of checking and deduping the tuples against the intern cache as they are constructed after the split operations would likely be considerable. Indexes would likely remain the very fastest strategy. An optimization theoretically exists which could make tuple splitting as fast as index accounting (representing split results as slices/views into the original tuple), but I do not believe python does that, as it would cause unexpected memory growth in some situations, unless accompanied by a very specialized garbage collection scheme.
- deleted 6y ago[deleted]