Jak mogę mieć wektor, który jest ściśle zgodny z jego wartościami, jak normalny typ z grzywką (!)?

Jedną z powszechnych wartości performance advice w Haskell jest tworzenie szybkich struktur danych, tak aby struktura, ale niekoniecznie jej zawartość, była w pełni oszacowana w momencie jej utworzenia. Dzięki temu możemy wykonać więcej pracy, gdy wstawimy wartość, a struktura jest w pamięci podręcznej, a nie odkładaniu jej, dopóki nie spojrzymy na wartość.Jak mogę mieć wektor, który jest ściśle zgodny z jego wartościami, jak normalny typ z grzywką (!)?

Z normalnego typu danych, takich jak binarny trie od Data.IntMap, można to osiągnąć przez wykonanie odpowiednich pól w strukturze danych ścisłym: (. Wyciąg ze źródła Data.IntMap.Base)

data IntMap a = Bin {- ... -} !(IntMap a) !(IntMap a) 
       | {- ... -}

Jak osiągnąć to samo zachowanie, jeśli chcę przechowywać dzieci w wektorze, a nie bezpośrednio jako pola Bin?

data IntMap a = Bin {- ... -} (Vector (IntMap a)) 
       | {- ... -}

Źródło

2015-08-31 Tikhon Jelvis

Could od 'Data.Vector.Strict' Moduł zbudowany na szczycie jednej regularnej ? Nie mogłem znaleźć żadnego paczkowanego w hackage. – chi

Przeglądanie wspólnego API w ['Data.Vector.Generic.Mutable'] (https://hackage.haskell.org/package/vector-0.11.0.0/docs/Data-Vector-Generic-Mutable.html) I znajdź jedną metodę "basicClear", która wydaje się intuicyjnie niemożliwa do zaimplementowania dla ścisłych wektorów dowolnego typu elementu (nie ma polimorficznej ścisłej wartości do zresetowania). Nie wiem, jak ważne jest to ... –

Nota boczna: wewnątrz struktur danych Najprawdopodobniej użyłbym "Data.Primitive.Array" zamiast "Vector", ponieważ prawdopodobnie nie ma potrzeby krojenia, a zatem nie ma potrzeby dodatkowe dwa słowa na węzeł. –

Najpierw odpowiem prosty wariant pytanie: Jeśli typ danych jest unboxable, np chcesz surowego wektora , s, użyć Data.Vector.Unboxed. Jako bezpłatny bonus, implementacja pozwala na posiadanie "struktury tablic", (Vector a, Vector b), nawet interfejs jest mniej podatnym na błędy "układem struktur", Vector (a, b). Zobacz Wikipedia on AOS and SOA.

Jednak w pytaniu OPS, chcemy trzymać IntMap a do Vector i IntMap nie jest unboxable (lub magazynować lub prymitywne).

Różne opcje sprowadzają się do tego samego pomysłu: musisz samemu uzyskać wartości seq. Czy iść do Data.Primitive.Array lub wdrożenie własnej Data.Vector.Strict na szczycie Data.Vector (Uwaga: basicClear może być no-op jak to dla odpakowanych wektorów, lub użyć unsafeCoerce() jako wartość zastępczą), będziesz seq wartości. W ten sposób implementowana jest wersja Data.Map.Strict o tej samej leniwej strukturze co Data.Map.Lazy.

Na przykład map Data.Map.Strict jest zaimplementowany jako:

map :: (a -> b) -> Map k a -> Map k b 
map f = go 
    where 
    go Tip = Tip 
    go (Bin sx kx x l r) = let !x' = f x in Bin sx kx x' (go l) (go r)

Porównaj to do Data.Map.Lazy.map:

map :: (a -> b) -> Map k a -> Map k b 
map f = go where 
    go Tip = Tip 
    go (Bin sx kx x l r) = Bin sx kx (f x) (go l) (go r)

Źródło

2017-10-17 07:06:41 phadej

Jak mogę mieć wektor, który jest ściśle zgodny z jego wartościami, jak normalny typ z grzywką (!)?

Odpowiedz

Powiązane problemy