Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
October 3rd, 2012, 05:28 AM
 jepot
Registered User

Join Date: Dec 2008
Posts: 17
Time spent in forums: 5 h 17 m 23 sec
Reputation Power: 0
Stitching two lists together

say i have two sorted lists, list1 and list2. i would like to stitch these two lists together to another list, list3. This list would have all items on list1 and list2 sorted in order. How would i go about doing it? I think the way i approached this problem is wrong, below is my trial:

Code:
```    a, b, result = 0, 0, []

while a != len(list1) or b != len(list2):
if list1[a] <= list2[b]:
result.append(list1[a])
a += 1
else:
result.append(list2[b])
b += 1```

I would like to see a correct implementation so I can see which assumption is wrong in my approach

#2
October 3rd, 2012, 07:44 AM
 SuperOscar
Contributing User

Join Date: Jul 2007
Location: Joensuu, Finland
Posts: 420
Time spent in forums: 1 Week 18 h 52 m 16 sec
Reputation Power: 66
Quote:
 Originally Posted by jepot say i have two sorted lists, list1 and list2. i would like to stitch these two lists together to another list, list3.

Is it really necessary to “stitch” them together? If the lists aren’t inordinately long, the easiest way would be to combine them and then sort.

Code:
```>>> l1 = ['a', 'd', 'q']
>>> l2 = ['b', 'c', 'f']
>>> l1 + l2
['a', 'd', 'q', 'b', 'c', 'f']
>>> sorted(l1 + l2)
['a', 'b', 'c', 'd', 'f', 'q']```

Otherwise, at least if the lists are of equal length, you might do:

Code:
```l3 = []
for x, y in zip(l1, l2):
l3.append(x if x < y else y)
l3.append(y if x < y else x)```
b49P23TIvg disagrees:
Code:
```&gt;&gt;&gt; l3 = [] &gt;&gt;&gt; for x, y in zip([1,2,3], [4,5,6]): ...     l3.append(x if x
&lt; y else y) ...     l3.append(y if x &lt; y else x) ...   &gt;&gt;&gt; l3 [1, 4, 2, 5, 3,
6]```
__________________
My armada: openSUSE 13.1 (home desktop, home laptop), Ubuntu 13.04 (work laptop), FreeBSD 9.2 (server), Mythbuntu 12.04 LTS (HTPC), Bodhi Linux 2.0 & Windows 7 Ultimate (test desktop), Android 4.1.2 (tablet)

#3
October 3rd, 2012, 10:06 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,216
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 31 m 29 sec
Reputation Power: 455
I'm astounded that my merge function performs almost as well as combining the lists, then using lists's sort method. p.py uses list.sort(), q.py uses merge. Timings and tests are shown.

p.py
Code:
```#\$ time python /tmp/p.py
#
#real	0m0.532s
#user	0m0.504s
#sys	0m0.020s

import random

N = 100000

def IsSorted(L):
'''
\$ python -m doctest p.py
>>> IsSorted(list('acx'))
True
>>> IsSorted(list('cax'))
False
'''
return all(x<=y for (x,y,) in zip(L[:-1],L[1:]))

a = list(random.random() for i in range(N))
b = list(random.random() for i in range(N))
a.sort()
b.sort()
c = a+b
c.sort()
assert IsSorted(c)```

q.py
Code:
```#\$ time python /tmp/q.py
#
#real	0m0.589s
#user	0m0.540s
#sys	0m0.040s

import random

N = 100000

def IsSorted(L):
'''
\$ python -m doctest p.py
>>> IsSorted(list('acx'))
True
>>> IsSorted(list('cax'))
False
'''
return all(x<=y for (x,y,) in zip(L[:-1],L[1:]))

a = list(random.random() for i in range(N))
b = list(random.random() for i in range(N))
a.sort()
b.sort()

def merge(a,b):
'''
>>> ''.join(merge(list('Abf'),list('CDEfnp')))
'ACDEbffnp'
'''
c = []
i = j = 0
La = len(a)
Lb = len(b)
while (i < La) and (j < Lb):
if a[i] < b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
if i < La:
c.extend(a[i:])
elif j < Lb:
c.extend(b[j:])
return c

c = merge(a,b)
c.sort()
assert IsSorted(c)```
__________________
[code]Code tags[/code] are essential for python code!

#4
October 3rd, 2012, 10:15 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,216
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 31 m 29 sec
Reputation Power: 455
(Point was to use SuperOscar's second code with the lists
[1,2,3] and [4,5,6])

the != len tests should be < len

and then jepot must account for remainder of list, that's what my extend business handles.
)

 Viewing: Dev Shed Forums > Programming Languages > Python Programming > Stitching two lists together