F #: Эффективно получить последнее состояние из List.scan

Question

Я запускаю List.scan по очень большому списку, чтобы вычислить текущую сумму. Когда я закончил, мне понадобится сумма в дополнение к выводу сканирования, чтобы разбить список неравномерно. Общее количество в последнем состоянии выводится путем сканирования, и мне бы очень хотелось избежать дополнительного обхода списка, чтобы получить конечное состояние. Единственный способ, с помощью которого я могу это сделать, - передать изменчивую ссылку, чтобы скопить итог. Есть ли лучший способ приблизиться к этому?

let l = <very large list of int64> 
let runningTotal=List.scan (fun s x -> x+s) 0L l 
let total= <last element of runningTotal- very inefficient> 
doSomething total runningTotal 

Answer 1

В F # 4.0, List.mapFold в настоящее время added, что позволяет это красиво.

[1;2;3;4] |> List.mapFold (fun state elem -> let nxt = state + elem in (nxt,nxt)) 0 

// > val it : int list * int = ([1; 3; 6; 10], 10) 

List.last также добавляется в 4.0, хотя его перфорация еще О (п). Если вы хотите вырезать последний элемент из списка в F # 3.1 и ранее, вы можете сделать это с помощью fold, но опять же, это O (n).

let last lst = 
    lst |> List.fold (fun _ x -> x) Unchecked.defaultof<_> 

@ Решение Джона, вероятно, является самым быстрым и простейшим.

Answer 2

Я думаю, что фактически доступ к последнему элементу в списке действительно невозможен. Вы сказали, что ваш список очень велик. Когда речь заходит о очень больших входах, список может не быть оптимальной структурой данных для начала. То, что приходит на ум, будет заключаться в том, что вы, конечно, могли бы использовать массив вместо списка в этом случае. Массивы также более эффективны с точки зрения памяти, чем списки, потому что список создаст ссылку для каждого элемента, которая составляет около 12 байт на элемент. В то время как массив имеет только ссылку на первый элемент.

Если массив работает для вас, то это будет решение, так как вы можете получить доступ к последнему элементу массива без служебных данных O (n).

Answer 3

Это один из способов. Поскольку мы можем определить лямбда, чтобы что-либо сделать, просто сделайте так, чтобы он всегда сохранял результат в ячейке ref. Поскольку сканирование работает от начала до конца, результатом будет последнее значение.

let last = ref 0L 
let l = <very large list of int64> 
let runningTotal=List.scan (fun s x ->let t = x+s;last=:t;t) 0L l 
let total= !last 
doSomething total runningTotal