問題從谷歌的Python類日

嘿，一個解決方案，我想了解一點關於Python，所以我決定效仿谷歌的tutorial。無論如何，我有一個問題關於他們的一個解決方案的練習。問題從谷歌的Python類日

我是這樣做的。

# E. Given two lists sorted in increasing order, create and return a merged 
# list of all the elements in sorted order. You may modify the passed in lists. 
# Ideally, the solution should work in "linear" time, making a single 
# pass of both lists. 
def linear_merge(list1, list2): 
    # +++your code here+++ 
    return sorted(list1 + list2)

然而他們以更復雜的方式做到了。 Google的解決方案是否更快？因爲我在註釋行中注意到解決方案應該在「線性」時間內工作，而我的解決方案可能不是？

這是他們的溶液

def linear_merge(list1, list2): 
    # +++your code here+++ 
    # LAB(begin solution) 
    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

來源

2011-04-30 starcorn

你的不是線性的，但這並不意味着它會變慢。算法的複雜性（「大哦表示法」）往往只是一個粗略的指導，總是隻講述故事的一部分。

然而，他們並非是線性的任一，儘管它可能似乎是乍一看。從列表中彈出需要移動所有後面的項目，所以從前面彈出需要移動所有剩餘的元素。

想想如何製作這個O（n）是一個很好的練習。以下是與給定的解決方案相同的精神，但避免其陷阱，同時爲了鍛鍊而推廣到2個以上的列表。對於正好2個列表，您可以刪除堆處理，並簡單地測試下一個項更小。

import heapq 

def iter_linear_merge(*args): 
    """Yield non-decreasing items from sorted a and b.""" 
    # Technically, [1, 1, 2, 2] isn't an "increasing" sequence, 
    # but it is non-decreasing. 

    nexts = [] 
    for x in args: 
    x = iter(x) 
    for n in x: 
     heapq.heappush(nexts, (n, x)) 
     break 

    while len(nexts) >= 2: 
    n, x = heapq.heappop(nexts) 
    yield n 
    for n in x: 
     heapq.heappush(nexts, (n, x)) 
     break 

    if nexts: # Degenerate case of the heap, not strictly required. 
    n, x = nexts[0] 
    yield n 
    for n in x: 
     yield n

取而代之的是最後如果換，while循環條件可改爲只「的nextS」，但它可能是值得特別處理最後剩下的迭代器。

如果你希望只返回一個列表，而不是一個迭代的：

def linear_merge(*args): 
    return list(iter_linear_merge(*args))

來源

2011-04-30 09:30:58

「從列表中彈出需要移動所有以後的項目」。這實際上取決於底層的列表實現。無論通過鏈表或數組完成實現，彈出第一個元素都可以很容易地在O（1）中實現。 – 2011-04-30 12:03:20

@IoanAlexandruCucu：當然這取決於底層的列表實現，但我們正在討論具體的實現：Python。什麼實現與我描述的不同？ – 2011-04-30 12:09:41

這個解決方案也是O（nlogn），基本上只是'sorted（list1 + list2） '的一個非常複雜的版本。不要像你那樣混合推送和彈出，你也可以將堆中的所有項目一次推送到堆上。這在時間複雜度方面沒有什麼區別，用於構建堆的是'O（nlogn）'。確實，'list.pop（0）'不需要一定的時間，但是有一個數據結構：'collections.deque'。只需將'list1，list2 = deque（list1），deque（list2）'添加到google解決方案的頂部，就可以真正實現linerar。 – 2011-04-30 13:20:30

隨着大多排序數據，timsort接近線性的。此外，您的代碼不必與列表本身搞砸。因此，你的代碼可能會快一點。

但是，這是什麼時機，爲什麼？

來源

2011-04-30 09:13:58

我覺得這裏的問題是，教程說明如何實現一個衆所周知的算法在Python稱爲「合併」。本教程不希望您在解決方案中實際使用庫分類功能。

sorted（）可能是O（nlgn）;那麼你的解決方案在最壞的情況下不能是線性的。

瞭解merge（）是如何工作是很重要的，因爲它在許多其他算法中很有用。它利用輸入列表單獨排序的事實，順序遍歷每個列表並選擇最小的選項。其餘的項目在最後附加。

的問題不是它是對於給定的輸入的情況下「更快」，但關於哪個算法更復雜。

存在落入背面上的另一個排序算法一旦輸入列表大小下降到低於某一閾值合併排序的雜化的變化。

來源

2011-04-30 09:29:26 rohannes

對於排序，您將不會遇到最糟糕的情況，因爲您將得到單獨排序的列表。 – 2011-04-30 09:31:42

托馬斯，這取決於排序算法;那裏確實存在種類（但也許他們現在實際上從未在實踐中被實際使用過）？在已經排序的輸入上表現最差。 – 2011-04-30 13:09:24

@BrandonCraigRhodes：當然，我可以構造一個排序算法，這是最糟糕的情況，但是Python的sorted（）的實現是真的嗎？ – 2011-04-30 13:13:10

這可能是另一個SOLN？＃

def linear_merge(list1, list2): 
      tmp = [] 
      while len(list1) and len(list2): 
        #print list1[-1],list2[-1] 
        if list1[-1] > list2[-1]: 
          tmp.append(list1.pop()) 
        else: 
          tmp.append(list2.pop()) 
        #print "tmp = ",tmp 

      #print list1,list2 
      tmp = tmp + list1 
      tmp = tmp + list2 
      tmp.reverse() 
      return tmp

來源

2014-08-13 16:09:45 san

問題從谷歌的Python類日

回答

相關問題