Looks like I found out the power of itertools in python. It is such a hack for some problems. Makes many things easier. The craziest feature of this library in python is that it has Counter which creates a hashmap of the occurrences of some iterable object. Please check it out if you want to learn!!! For me😎
I worked on the section named "Sorting". My notes for the day:
- Itertools save the day again. chain.from_iterable return a generator, not a list or an iterable. They are different. Generators don't have an access feature (no indeces)
- can use sorted on the itertools however
- Binary search gave me some problem, because I forgot that to get the middle, you must add the two ends and divide, not subtract
- There was a counting sort problem, the only real take away is that if you are shifting, move from the back end of an array to avoid using temp variables to swap.
- Moving from the right can save a lot of time and resources for the machine
- Heap sort is the most "efficient", its in place, and can imitate a min heap or a max heap within the array, but it is slow compared to quicksort.
- quicksort is great for really messy lists, but terrible for sorted or almost sorted lists. I think algorithms use a mix of quick sort and insertion sort to counter that
effect
- Bubble, insertion, selection are all ass, O(n^2), but in place
- Radix and counting are so close together as sorts, radix(base)
- quicksort, uses two pointers to sort within the pivoted section, left and right, and swaps.
- Merge, quick is divide and conquer
- Python uses timsort which is just a fancy mergesort
No comments:
Post a Comment