Python from scratch – lists
My journey into Python from scratch got into the list phase.
But it started with a crazy week
Crazy week
Well, I had a crazy week.
My first post- Python from scratch was a huge hit.
I got all this attention and even now a few days later I still get visits and comments and being followed by Email and RSS.
I have read each comment and each referral to a site which led me to many python sites that come to help and found myself in heaven for a newbie like me.
Also, I met this guy from Costa-Rica who is going through the same journey more or less like me and we are exchanging ideas by email.
The success of the first post
My post was published on some great sites and if you search in Google “python from scratch” I am on top5.
All the above made me lose focus and on top of it my young son got sick (still) so I had some sleepless night lately.
Last night I decided that no matter what I will continue on my journey and I have started to read the next page in Google python class-lists.
Python from scratch – learning lists
So I read the entire chapter which teaches how lists work in Python, a bit tricky in some points yet easy to follow.
Then the chapter teaches how to use the FOR var IN list which is different from C++
It took me some time to get used to it but once you get it- wow!
Towards the end, you get familiar with some lists method which will come handy later on and voila- the exercise.
First problem
So here I am solving the tests and the first 2 problems I was doing fine only to bump into the third problem which took me around an hour, here it is:
“Given a list of non-empty tuples, return a list sorted in increasing order by the last element in each tuple.” example- (1, 3), (3, 2), (2, 1) should return- (2, 1), (3, 2), (1, 3).
Easy to see the obstacle over here is how to sort using the last elementץ
I really tried to make my code as simple as possible (KISS).
But no matter what I did I was writing more and more rows and more and more taking care of corner cases
Until I decide that I am doing something wrong and surely there is a faster solution hidden in the learning subject.
Does Google have a bug?
So I read the lists page course again until I discovered the problem- Google has a Doc BUG in this page- an important method is mentioned but not explained.
It says:
list.sort() — sorts the list in place (does not return it).
(The sorted() function shown below is preferred.)
But there is no sorted() below and this method was the method to solve the issue easily.
in fact, also list.sort() can handle this case but I couldn’t understand it from reading over here.
After spending too much time on this and being so late at night I went to sleep.
Easy to solve
The night follows I spent another 30 minutes to solve the advanced exercise and again I met into a strange situation.
The second exercise was very easy to do and took me only 3 rows to complete.
Yet Google solution was about 10 rows (not making sense, haha)
Ask the experts
So I decided to show it to you and ask you where am I wrong with my solution:
The question is-
“Given two lists sorted in increasing order, create and return a merged list of all the elements in sorted order.” example- [‘aa’, ‘xx’, ‘zz’], [‘bb’, ‘cc’]) should return- [‘aa’, ‘bb’, ‘cc’, ‘xx’, ‘zz’])
My 3 rows solution was-
Google 10 rows solution is-
I was running several lists to test my code and it works just fine.
This also goes fine with The Zen of Python “Simple is better than complex”.
So I am asking you the Python people, do you see the reason why my code is only three rows of code while Google’s is much bigger?
Do I have a bug?
Can you do it better?
Anyway, that’s it for this subject python from scratch – lists
I am all fired up for the next one as I am continuing in my journey into python from scratch.
## Press here for part 3- The journey continues
Thanks, I didn't know its possible to return with a code (Now i know).
So you agree with my solution? and do you understand why Google's answer is so long?
lambda is a bit advanced for me. I just read about it and it sounds cool. Anyway yeah you are right and that was my understanding eventually.
As for your second answer, i will re-exam again your point and see if i get it right. Thanks Man.
I got you.
Do you think this code is better?
def linear_merge(list1, list2):
list1.extend (list2)
list1.sort ()
return list1
There's a one-liner:
def linear_merge (list1, list2): return list (sorted (list1.extend (list2)))
🙂
The solution for the first problem you mention is to use the key parameter which allows you to map each item of the list to a key value which is then used for sorting. The following sorts a list xs of tuples by the last item in each pair as required:
def sort_by_last(xs):
return sorted(xs, key=lambda x: x[-1])
As far as the Google sort method given they're implementing a version of merge sort in python. Your version is a little bit dodgy as you're passing in the result of list.extend as the cmp parameter to list.sort. Fortunately the result of list.extend is None so you get away with it, but I wouldn't encourage that kind of code in general.
I believe Google's solution is right.
Your solution has an O(nlogn) complexity while Google's solution has an O(n) time complexity limit (also known as "linear time"). If you work with large lists yours will run considerably slower.
The exercise calls for it: "Ideally, the solution should work in "linear" time, making a single pass of both lists" – and the name of the function hints at it.
— Arik
One of the reasons one would chose Python is for the tendency of the code to be clearer to read (compared to other languages).
Your form, however valid, will render the code less readable.
Thanks Arik for your answer.
At this point of my studies- complexity is not something i should deal with.
Still of course you are right, Thanks for your answer.
def linear_merge(list1, list2): return sorted(list1 + list2)
can do the job also.
It did.
Good advise.