News for hackers. Stuff that matters.
Re:Binary Search Reconsidered (2018) by blackbear_ on Friday December 25, 2020 @02:02PM (#25538303)
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
Re:Binary Search Reconsidered (2018) by tzs on Friday December 25, 2020 @03:31PM (#25538816)
Suppose 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.

Re:Binary Search Reconsidered (2018) by zbentley on Friday December 25, 2020 @04:32PM (#25539200)
Python 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.

Re:Binary Search Reconsidered (2018) by nomy99 on Friday December 25, 2020 @02:05PM (#25538317)
great suggestion