有效地合并两个列表

本文介绍了有效地合并两个列表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我目前正在学习Haskell，并且正在与List一起工作.

根据 HaskellWiki ，如果我想将两个列表合并在一起，我会写: /p>

list1 ++ list2

但是，根据此答案，在大量列表上使用++效率不高.

通过研究，我遇到了此SO页面，但是该问题需要一个List的输出的特定要求.

我尝试过的事情:

假设我有两个数字列表(对于此示例，假设两个列表都足够大，以致如SO答案所述，使用++效率不高):

oldNumbers = [1,5,14,22,37] newNumbers = [3,10,17,27,34,69] allNumbers = oldNumbers:newNumbers

正如您所看到的，我试图将oldNumbers添加到newNumbers的头部，目的是事后将其反转(忽略allNumbers现在将是无序的，这是另一天的练习).

您可能已经猜到了，它产生了一个错误

error: * Non type-variable argument in the constraint: Num [a] (Use FlexibleContexts to permit this) * When checking the inferred type allNumbers :: forall a. (Num a, Num [a]) => [[a]]

那么，正如标题中所述，我将如何有效地合并两个列表?

解决方案

根据 HaskellWiki ，如果我想将两个列表合并在一起， 我会写:

list1 ++ list2

但是，根据在大型列表上使用++的答案为 效率低下.

我认为您需要在此答案中考虑上下文.如果我们将两个列表a和b与(++)附加在一起，则它将两个列表附加在 O(m)中(列表的长度为 m ) .因此，就时间复杂度而言，这是有效的.构造这种单链表的效率最高.

@melpomene 实际上指出了Haskell刚认识的人经常犯的一个错误:他们会附加一个单个列表末尾的em>元素.同样，如果您只想将单个元素添加到列表中，那不是问题.如果您想以这种方式将 n 元素添加到列表中，那么这将是一个问题，因此，如果您每次都将单个元素添加到列表中，并且您执行 n 次，则算法为 O(n 2 ).

因此，简而言之，从时间复杂度的角度来看，将两个列表附加在一起时(++)并不慢，而将单例列表附加到其中时也不慢.但是，就渐近行为而言，通常有比将具有一个元素的列表重复添加到列表更好的方法，因为那样的话，第一个操作数通常会变大，并且每次迭代花费 O(n)仅将单个元素添加到列表的时间.通常，在这种情况下，可以在列表的tail元素上使用递归，或者例如以反向方式构建列表.

因此，

(++)并非固有"的低效率，通过以非设计的方式使用它，您可以获得低效率的行为.

++会非常慢的一个示例是执行映射"的以下函数:

badmap :: (a -> b) -> [a] -> [b] badmap f = go [] where go temp [] = temp go temp (x:xs) = go (temp ++ [f x]) xs

这里有两个问题:

这不是偷懒，它需要评估整个列表，然后才能发出第一个元素；和

它将以二次时间运行，因为对于输入列表中的每个元素，添加该元素将花费越来越多的时间.

一种更有效的地图实现方法是:

goodmap :: (a -> b) -> [a] -> [b] goodmap f = go where go (x:xs) = f x : go xs go [] = []

I'm currently learning Haskell, and working with List.

According to the HaskellWiki, if I wanted to merge two lists together, I would write:

list1 ++ list2

However, according to this answer, using ++ on a large list would be inefficient.

From researching, I came across this SO page, but that question requires a specific requirement for the output of the List.

What I tried:

Suppose if I had two lists of numbers (for this example, assume that both lists are large enough that using ++ would be inefficient as described in the SO answer):

oldNumbers = [1,5,14,22,37] newNumbers = [3,10,17,27,34,69] allNumbers = oldNumbers:newNumbers

As you can see I attempted to add oldNumbers to the head of newNumbers with the intention of reversing it afterward (disregard that allNumbers would be unorder for now, that's an exercise for another day).

As you probably guessed, it produced an error

error: * Non type-variable argument in the constraint: Num [a] (Use FlexibleContexts to permit this) * When checking the inferred type allNumbers :: forall a. (Num a, Num [a]) => [[a]]

So, as stated in the title, how would I efficiently merge two lists?

解决方案

According to the HaskellWiki, if I wanted to merge two lists together, I would write:

list1 ++ list2

However, according to this answer, using ++ on a large list would be inefficient.

I think you need to take the context into account in this answer. If we append two lists a and b with (++) then it appends the two lists in O(m) (with m the length of the list). So this is, in terms of time complexity efficient. One can not construct such singly linked list more efficient than that.

@melpomene actually points to a popular mistake people new to Haskell make: they append a single element at the end of the list. Again if you only want to append a single element to the list, that is not a problem. This is a problem if you want to append n elements that way to a list, so if you each time append a single element to the list, and you do that n times, then the algorithm will be O(n2).

So in short, from a time complexity point of view, (++) is not slow when you append two lists together, nor is it slow when you append a singleton list to it. There are however, in terms of asymptotic behavior, usually better ways than repeatedly appending a list with one element to a list, since then the first operand will typically become larger, and each iteration it takes O(n) time only to append a single element to a list. Typically one can use recursion on the tail element of a list in that case, or for example build the list in reverse.

(++) is thus not "intrinsically" inefficient, by by using it in ways for which it was not design, you can obtain inefficient behavior.

An example where ++ will be quite slow is the following function that performs a "mapping":

badmap :: (a -> b) -> [a] -> [b] badmap f = go [] where go temp [] = temp go temp (x:xs) = go (temp ++ [f x]) xs

There are two problems here:

it is not lazy, it requires to evaluate the entire list before this can emit the first element; and

it will run in quadratic time, since for each element in the input list, it will take more and more time to append this element.

A more effective way to implement a map is:

goodmap :: (a -> b) -> [a] -> [b] goodmap f = go where go (x:xs) = f x : go xs go [] = []