Elm中的数组与列表对比

Question

我惊讶地发现Array和List是Elm中的两种不同类型：

• Array

• List

在我的情况下，我有一个长度为2,000,000的List Int，我需要其中的大约10,000个，但我事先不知道哪个是哪个。这将由另一个列表提供。伪代码如下：

x = [ 1,1,0,30,...,255,0,1 ]
y = [ 1,4,7,18,36,..., 1334823 , ... 1899876 ]
z = [ y[x[0]], y[x[1]], ... ]

我使用伪代码，因为显然这不是Elm语法（可能是合法的JavaScript）。

这些数组选择可以在List或Array中完成吗？

- john mangual

---

List 是一个链表结构，因此表达式 y[x[i]] 是对 x 中第 i 个元素的 O(n) 查找加上对 y 中元素的另一个 O(n) 查找。换句话说，对于在 200 万个元素中进行的 10000 次查找，这将变得非常缓慢。请使用数组。 - Alex Reinking

除非“y”已经被保证为排序，否则另一个算法将起作用。 - Alex Reinking

只是出于好奇，您通过从200万个元素列表中选择10,000个元素来解决的更广泛的问题是什么？ - Søren Debois

这200万个元素是图像中的像素。我有10000个点，需要找到它们的RGB颜色。如果您愿意，我可以提出一个新问题。 - john mangual

Answer 1

List 是一个链表，可以根据索引提供 O(n) 的查找时间。通过索引获取元素需要遍历列表中的 n 个节点。在核心库中没有为 List 提供索引查找函数，但是你可以使用 elm-community/list-extra 包，该包提供了两个查找函数（根据参数顺序不同而有所不同）：!! 和 getAt。

Array 允许进行 O(log n) 索引查找。可以使用Array.get进行数组的索引查找。数组以Relaxed Radix Balanced Trees表示。

两者都是不可变的（Elm 中所有值都是不可变的），因此取决于你的情况而有不同的权衡。如果你需要频繁进行修改，则 List 很好，因为你只需要更新链表指针，而 Array 对于修改的性能较差但查找速度快，如果你需要频繁进行查找，则应考虑使用它。

- Chad Gilbert

---

我没有检查过，但我认为Array应该是一种具有O(lg n)查找的红黑树形式？ - Søren Debois

@SørenDebois 你说得完全正确，Elm的Array查找是O(lg n)。 - halfzebra

看起来Array在内部使用了Relaxed Radix Balanced Trees。我已经更新了我的答案。 - Chad Gilbert

在折叠或映射方面，Array和List哪个更好？ - fiatjaf

一般来说，List 在折叠和映射方面的性能更好，因为它是“一步”到达下一个项目。Array 对于索引查找来说更好，但在折叠和映射方面的性能略差，因为它们需要更多的步骤才能到达下一个元素。 - Chad Gilbert

Answer 2

像这样的代码应该可以工作：

import Array
import Debug

fromJust : Maybe a -> a
fromJust x = case x of
    Just y -> y
    Nothing -> Debug.crash "error: fromJust Nothing"

selectFromList : List a -> List Int -> List a
selectFromList els idxs = 
  let arr = Array.fromList els
   in List.map (\i -> fromJust (Array.get i arr)) idxs

它将输入列表转换为数组以进行快速索引，然后将索引列表映射到数组中对应的值。我从 this StackOverflow question 中使用了 fromJust 函数。

- Alex Reinking

Answer 3

只有在需要使用Array.get时才使用Array。

在大多数情况下，应该使用List，因为通常您可以使用foldl、map等完成所需的所有操作，而无需从索引获取项，并且List在这些函数中具有更好的性能。

- Dull Bananas