#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2008
    Posts
    17
    Rep 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. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2007
    Location
    Joensuu, Finland
    Posts
    428
    Rep Power
    66
    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)

    Comments on this post

    • b49P23TIvg disagrees : [code]>>> l3 = [] >>> for x, y in zip([1,2,3], [4,5,6]): ... l3.append(x if x < y else y) ... l3.append(y if x < y else x) ... >>> l3 [1, 4, 2, 5, 3, 6][/code]
    My armada: openSUSE 13.1 (home desktop, home laptop), Crunchbang Linux 11 (mini laptop, work laptop), Android 4.2.1 (tablet)
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,711
    Rep Power
    480
    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 and Makefiles!
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,711
    Rep Power
    480
    (Point was to use SuperOscar's second code with the lists
    [1,2,3] and [4,5,6])

    (answering jepot's question,

    the != len tests should be < len

    and then jepot must account for remainder of list, that's what my extend business handles.
    )
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo