Преобразование списка позиций в двумерный массив позиций с использованием функционального программирования (F #) - PullRequest
Новая
       10

Преобразование списка позиций в двумерный массив позиций с использованием функционального программирования (F #)

3 голосов
/ 26 марта 2010

Как бы вы сделали следующий код работающим с той же скоростью? В общем, в качестве входных данных у меня есть список объектов, содержащих координаты положения и другие вещи, и мне нужно создать 2D-массив, состоящий из этих объектов. 

let m = Matrix.Generic.create 6 6 []
let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]  
pos |> List.iter (fun (pz,py) ->
  let z, y = int pz, int py
  m.[z,y] <- (pz,py) :: m.[z,y]
)

Вероятно, это можно сделать следующим образом: 

let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]
Matrix.generic.init 6 6 (fun z y ->
  pos |> List.fold (fun state (pz,py) ->
    let iz, iy = int pz, int py
    if iz = z && iy = y then (pz,py) :: state else state
  ) []
)

Но я полагаю, что это будет намного медленнее, потому что он перебирает всю матрицу, умноженную на список по сравнению с предыдущей итерацией списка ...

PS: код может быть неправильным, поскольку у меня нет F # на этом компьютере, чтобы проверить его.

Ответы [ 3 ]

3 голосов
/ 26 марта 2010

Зависит от определения «функционал». Я бы сказал, что «функциональная» функция означает, что она всегда возвращает один и тот же результат для одних и тех же параметров и что она не изменяет какое-либо глобальное состояние (или значение параметров, если они изменчивы). Я думаю, что это разумное определение для F #, но это также означает, что нет ничего «не функционального» при использовании мутации локально.

На мой взгляд, следующая функция является "функциональной", потому что она создает и возвращает новую матрицу вместо изменения существующей, но, конечно, реализация функции использует мутацию. 

let performStep m =
  let res = Matrix.Generic.create 6 6 [] 
  let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]   
  for pz, py in pos do
    let z, y = int pz, int py 
    res.[z,y] <- (pz,py) :: m.[z,y] 
  res

Версия без мутаций: Теперь, если вы хотите сделать реализацию полностью функциональной, я бы начал с создания матрицы, содержащей Some(pz, py) в тех местах, где вы хотите добавить новый элемент списка к элементу матрицы, и None во всех остальных. мест. Я думаю, это можно сделать, инициализировав разреженную матрицу. Примерно так: 

let sp = pos |> List.map (fun (pz, py) -> int pz, int py, (pz, py)) 
let elementsToAdd = Matrix.Generic.initSparse 6 6 sp

Тогда вы сможете объединить исходную матрицу m с вновь созданной elementsToAdd. Это, безусловно, можно сделать с помощью init (однако, что-то вроде map2 может быть лучше): 

let res = Matrix.init 6 6 (fun i j -> 
  match elementsToAdd.[i, j], m.[i, j] with
  | Some(n), res -> n::res
  | _, res -> res )

Вполне вероятно, что некоторые мутации скрыты в функциях библиотеки F # (например, init и initSparse), но по крайней мере это показывает один из способов реализации операции с использованием более простых операций.

EDIT: Это будет работать, только если вам нужно добавить не более одного элемента в каждую ячейку матрицы. Если вы хотите добавить несколько элементов, вам сначала нужно сгруппировать их (например, используя Seq.groupBy)

1 голос
/ 08 августа 2010

Вы можете сделать что-то вроде этого: 

[1.3, 4.3; 5.6, 5.4; 1.5, 4.8]
|> Seq.groupBy (fun (pz, py) -> int pz, int py)
|> Seq.map (fun ((pz, py), ps) -> pz, py, ps)
|> Matrix.Generic.initSparse 6 6

Но в своем вопросе вы сказали:

Как бы вы сделали следующий код работающим с такой же скоростью?

И в последующем комментарии вы сказали:

Хорошо, я стараюсь избегать изменчивости, чтобы в будущем код можно было просто парализовать.

Боюсь, это торжество надежды над реальностью. Функциональный код обычно имеет низкую абсолютную производительность и плохо масштабируется при распараллеливании. Учитывая огромное количество ресурсов, выделяемых этим кодом, вы вряд ли увидите какой-либо выигрыш в производительности от параллелизма.

0 голосов
/ 26 марта 2010

Почему вы хотите сделать это функционально? Тип Matrix спроектирован так, чтобы его можно было мутировать, поэтому то, как вы это делаете, теперь выглядит хорошо для меня.

Если вы действительно хотите сделать это функционально, вот что я бы сделал: 

let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]  
let addValue m k v = 
  if Map.containsKey k m then
    Map.add k (v::m.[k]) m
  else
    Map.add k [v] m
let map = 
  pos 
  |> List.map (fun (x,y) -> (int x, int y),(x,y)) 
  |> List.fold (fun m (p,q) -> addValue m p q) Map.empty
let m = Matrix.Generic.init 6 6 (fun x y -> if (Map.containsKey (x,y) map) then map.[x,y] else [])

Он проходит по списку один раз, создавая неизменную карту от индексов до списков точек. Затем мы инициализируем каждую запись в матрице, выполняя поиск по одной карте для каждой записи. Это должно занять общее время O(M + N log N), где M и N - количество записей в вашей матрице и списке соответственно. Я считаю, что ваше оригинальное решение с использованием мутации занимает O(M+N) времени, а ваше исправленное решение - O(M*N) времени.

...