CODEWITHSUNDEEP
haskell
Ignat Insarov
Ignat Insarov

Reputation: 4832

Efficiently replace a portion of a binary object

My goal is to efficiently overwrite several sections of a blob, while leaving its overall content and structure pristine. To this end, I have written the following functions:

replace :: ByteString -> Int -> ByteString -> ByteString
replace source offset replacement = prefix <> replacement <> suffix
  where
    prefix = ByteString.take offset source 
    suffix = ByteString.drop (offset + ByteString.length replacement) source

fix :: Int -> ByteString -> ByteString -> ByteString
fix offset replacement source = replace source offset replacement

And this is how they work:

λ replace "I have a cat." 0x09 "dog"
"I have a dog."
λ fix 0x0A "fat" . fix 0x03 "dog" $ "My cat is red."
"My dog is fat."

Unfortunately, <> = append is linear time, and therefore these functions too. Having the knowledge that the replacement is just as long as the section being replaced, surely we can do better?

I would be especially joyful if it happens that we can replace multiple sections in time less than linear over the number of replacements.

Upvotes: 2

Views: 115

Answers (1)

Regis Kuckaertz
Regis Kuckaertz

Reputation: 991

Given concat is linear in the size of the list and both take and drop are O(1), this may be as good as it gets:

replace source offset replacement = 
  concat [ take offset source
         , replacement
         , drop n source
         ] 
  where n = offset + length replacement

For an arbitrary number of replacements:

replacemany :: [(Int, ByteString)] -> ByteString -> ByteString
replacemany wss bs = foldr f bs wss where
  f (l, ws) bs = replace bs l ws

Upvotes: 2

Related Questions