代表二進制數據的集合

我正在處理樣本由Float s組成的信號。我寫的一些算法只需要知道信號何時穿過x軸（即正值爲負值，反之亦然）。當我進行這些操作時，我意識到我不需要知道每個樣本的實際值Float。我只需要知道樣本的價值是否正面。代表二進制數據的集合

我原先所表示的信號作爲Float的Vector一個第我發現後，我開始將其表示爲Vector的Boolean值（即False爲負值，True爲正值）。事實證明，這樣做效率更高，我在運行時和內存消耗方面都提高了程序的性能。

我一直在想，如果沒有表示該「二進制數據的收集」的更有效的方式。類似於Bit Vector或Bit Array。我在Hackage上發現了一個BitArray，但它似乎不支持與Vector相同的功能。

是否有更有效的方式來表示我的用例數據，還是應該堅持Vector的Boolean值？

來源

2017-06-12 Thomas Vanhelden

你需要什麼'Vector'的功能？ –

@WillemVanOnsem標準的Haskell List原語（即map，fold，filter等）我也使用'V.generate'來讀取文件中的所有樣本。 –

C++標準庫包含[bool的模板專門化]（http://en.cppreference.com/w/cpp/container/vector_bool），它使用字節的全部內容來提高空間效率......但是， [現在被廣泛認爲是一個壞主意]（https://isocpp.org/blog/2012/11/on-vectorbool）。對於這樣的向量，性能往往會受到很大的影響，因爲元素訪問不能直接用指針算術來執行。 - 如果只想有效地表示連續信號的符號，則應考慮只存儲符號變化處的_點。 – leftaroundabout

分別可以從vector和array包得到one-bool-per-byte和one-bool-per-bit選項。

首先，Data.Vector.Unboxed的Vector Bool使用一個字節數組，每Bool一個字節。

newtype instance Vector Bool = V_Bool (P.Vector Word8)

以及獲取和設置通過功能介導的：這可以從在模塊Data.Vector.Unboxed.Base源其中Vector Bool被定義爲覈實

fromBool :: Bool -> Word8 
toBool :: Word8 -> Bool

可替代地，它可以直接由仿形的驗證程序：

import Data.Vector.Unboxed as V 
main = let v = V.replicate 1000000000 True 
    in print (v ! 5)

並觀察到它分配的只是超過1,000,000,000字節。

其次，的UArray Int Bool被實現爲位向量，每位有一個Bool。該有關人士是在Data.Array.Base，在那裏你可以看到在實例中使用的位操作：

instance IArray UArray Bool where 
    ... 
    unsafeAt (UArray _ _ _ arr#) (I# i#) = isTrue# 
     ((indexWordArray# arr# (bOOL_INDEX i#) `and#` bOOL_BIT i#) 
     `neWord#` int2Word# 0#)

同樣，這可以直接通過分析證實：

import Data.Array.Unboxed as A 
main = let v = A.listArray (1,1000000000) (repeat True) :: UArray Int Bool 
    in print (v ! 5)

，並驗證其分配大約125,000,000字節。

來源

2017-06-13 21:57:21

感謝您的回答！我覺得它很有趣！糾正我，如果我錯了，但'矢量'更快，'陣列'是我的問題更有記憶效率？ –

好吧，'Array'確實比'Vector'更有記憶效率，但是對於速度來說，這可能取決於特定的算法。我認爲基準測試是解決這個問題的唯一方法。 –

代表二進制數據的集合

回答

相關問題