Re: [Tutor] lists+sort

[Steven D'Aprano]

On Mon, Jan 04, 2016 at 12:34:57PM -0500, Pooja Bhalode wrote:
> Hi, I wanted to check if this program can be used to merge the lists
> together and sort them. This seems to work, but i wanted to check if there
> are drawbacks in writing it in this manner.
> 
> My solution:
> 
> def linear_merge(list1, list2):
> for num in list2:
> list1.append(num)
> list1.sort()
> return list1

One small change:

def linear_merge(list1, list2):
list1.extend(list2)
list1.sort()
return list1

is easier to write and faster. For use in an actual program, this method 
is perfectly acceptible, although this version modifies the first list 
in place rather than make a copy. If you want a copy:

def linear_merge(list1, list2):
result = list1[:]
result.extend(list2)
result.sort()
return result


Or more compact, but not quite as efficient:

def linear_merge(list1, list2):
return sorted(list1 + list2)

You should play around with these and see if you can understand how they 
differ.

For a practice exercise, none of the above might be acceptible. Usually, 
when people talk about "merging" lists, they mean to avoid calling sort. 
Sorting, on average, takes time proportional to N*log N, where N is the 
number of items. So if you have 1000 items, sorting will take time 
proportional to 1000*(log 1000), or 3000. But "merging" should take time 
proportional to just N, or 1000. So in theory, merging may be faster.

So for practice exercises, it is often expected that you do not just 
add the two lists together and sort as we did above.

Let's look at their code:

> def linear_merge(list1, list2):
>   result = []
>   # Look at the two lists so long as both are non-empty.
>   # Take whichever element [0] is smaller.
>   while len(list1) and len(list2):
> if list1[0] < list2[0]:
>   result.append(list1.pop(0))
> else:
>   result.append(list2.pop(0))
>   # Now tack on what's left
>   result.extend(list1)
>   result.extend(list2)
>   return result

As you can see, there is no call to sort. (This does assume that each 
list is itself sorted, but that is normal for this type of question.) So 
the function starts with a new, empty, list and then it keeps looking at 
the two lists. It looks at the first item from each list, picks the 
smaller, and moves it to the new list. When one or the other list has 
run out of items, the function then does a quick copy of the rest of the 
items from the other.


However, while this might technically be a merge, it is actually *very* 
inefficient. It will actually take time proportional to N**2, due to the 
list.pop calls. Each time you pop an item from the *beginning* of a 
list, all the other items have to be moved back one space. So if you 
have 10 items in the list, and remove the first one, the remaining 9 
have to move; then you remove the first, now the remaining 8 have to 
move; and so on. If you don't understand this, don't worry about it too 
much, the important thing is that the answer given will perform very 
slowly for large lists with millions of items. Here's a better version:


def merge(lista, listb):
# Assumes that both lista and listb are already sorted.
new = []
i = 0  # Index of an item in lista
j = 0  # Index of an item in listb
while i < len(lista) and j < len(listb):
if lista[i] < listb[j]:
new.append(lista[i])
i += 1
else:
new.append(listb[j])
j += 1
new.extend(lista[i:])
new.extend(listb[j:])
return new



-- 
Steve
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] lists+sort

[Peter Otten]

Pooja Bhalode wrote:

> Hi, I wanted to check if this program can be used to merge the lists
> together and sort them. This seems to work, but i wanted to check if there
> are drawbacks in writing it in this manner.

When you start out lists are the natural datatype to use, but as you get 
more experienced you'll often switch to generators and iterators. These 
allow you to defer calculations until they are actually necessary and to 
reduce memory footprint. For example:

>>> import heapq
>>> a = range(0, 10**100, 2)
>>> b = range(0, 10**100, 7)
>>> for item in heapq.merge(a, b):
... print(item)
... if item > 20:
... break
... 
0
0
2
4
6
7
8
10
12
14
14
16
18
20
21

A list-based implementation would try to build a list with 

>>> 10**100//2 + 10**100//7
6428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428

items. CPython can't even determine the length of such a list:

>>> len(range(0, 10**100, 2))
Traceback (most recent call last):
  File "", line 1, in 
OverflowError: Python int too large to convert to C ssize_t

Anyway, heapq.merge() is written in Python, so you can easily take a look:

https://hg.python.org/cpython/file/737efcadf5a6/Lib/heapq.py#l349




___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] lists+sort

[Joel Goldstick]

On Mon, Jan 4, 2016 at 12:34 PM, Pooja Bhalode 
wrote:

> Hi, I wanted to check if this program can be used to merge the lists
> together and sort them. This seems to work, but i wanted to check if there
> are drawbacks in writing it in this manner.
>
>
> My solution:
>
>
> def linear_merge(list1, list2):
>
> for num in list2:
>
> list1.append(num)
>
>
>
> list1.sort()
>
> This could be more easily done with
list1.extend(list2)
list1.sort()

>
>
>   # +++your code here+++
>
> return list1
>
>
>
> Whereas, their code is a bit different, I have posted it here.
>
>
> def linear_merge(list1, list2):
>
>
>
>   result = []
>
>   # Look at the two lists so long as both are non-empty.
>
>   # Take whichever element [0] is smaller.
>
>   while len(list1) and len(list2):
>
> if list1[0] < list2[0]:
>
>   result.append(list1.pop(0))
>
> else:
>
>   result.append(list2.pop(0))
>
>
>   # Now tack on what's left
>
>   result.extend(list1)
>
>   result.extend(list2)
>
>   return result
>
>
> I don't think this code will work if the original lists are unsorted to
begin with.  You should give some sample data and your results for both
methods

>
> Can you please tell me if there is a problem in the first code?
>
> Thank you.
> ___
> Tutor maillist  -  Tutor@python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>



-- 
Joel Goldstick
http://joelgoldstick.com/stats/birthdays
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] lists+sort

[Joel Goldstick]

On Mon, Jan 4, 2016 at 5:35 PM, Danny Yoo  wrote:

> On Jan 4, 2016 11:00 AM, "Pooja Bhalode"  wrote:
> >
> > Hi, I wanted to check if this program can be used to merge the lists
> > together and sort them. This seems to work, but i wanted to check if
> there
> > are drawbacks in writing it in this manner.
>
> You may be missing some important details or misunderstanding a crucial
> detail.
>
> For example, the term "merge" in this context usually had a very specific
> technical meaning.
>
> Are your two input lists already sorted?
>
> The use of the term "linear" in the function definition:
>
> > def linear_merge(list1, list2):
>
> has a particular meaning in terms of algorithmic complexity, and the first
> implementation does not satisfy it: it does not perform linearly due to the
> internal use of the sort().
>
> If you have questions, please feel free to ask.
> ___
> Tutor maillist  -  Tutor@python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>

You may also take a look at this link:
http://stackoverflow.com/questions/7237875/linear-merging-for-lists-in-python

It appears that the poster was going through Googles python tutorials

-- 
Joel Goldstick
http://joelgoldstick.com/stats/birthdays
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] lists+sort

[Danny Yoo]

On Jan 4, 2016 11:00 AM, "Pooja Bhalode"  wrote:
>
> Hi, I wanted to check if this program can be used to merge the lists
> together and sort them. This seems to work, but i wanted to check if there
> are drawbacks in writing it in this manner.

You may be missing some important details or misunderstanding a crucial
detail.

For example, the term "merge" in this context usually had a very specific
technical meaning.

Are your two input lists already sorted?

The use of the term "linear" in the function definition:

> def linear_merge(list1, list2):

has a particular meaning in terms of algorithmic complexity, and the first
implementation does not satisfy it: it does not perform linearly due to the
internal use of the sort().

If you have questions, please feel free to ask.
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] lists+sort

[Danny Yoo]

>
> You may also take a look at this link:
> http://stackoverflow.com/questions/7237875/linear-merging-for-lists-in-python
>
> It appears that the poster was going through Googles python tutorials

Hi Joel,

Ah.  Nice catch!  Yes, that looks like it.  It looks like this comes
from the material at https://developers.google.com/edu/python/, as
part of the list2.py exercises referenced by the
google-python-exercises.zip file in
https://developers.google.com/edu/python/set-up

Just as a warning: those materials assume that the participant already
knows programming and computer science theory, and so they probably
won't work too well for complete beginners.
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor