Makes sense. Best I am going to get is a linear search w/ a divide and
conquer if I want to speed it up. Thanks needed the sounding board and feed
back.
Thanks,
Anthony
On Wednesday, August 29, 2018 at 8:16:44 PM UTC-7, Daniela Petruzalek wrote:
>
> Do you have an example?
>
> I'm assuming that the replacement is one character for another. (ie.: not
> one character being replaced by a group of characters).
>
> Regarding to finding the positions to replace you can't beat O(n)
> complexity as you must look at least once at every character on the source
> string.
>
> In regards to finding the replacement... the 9 characters could be stored
> in a dictionary (map in Go) with their counterparts. Since a dictionary
> lookup is O(1) in the average case you still have an O(n) algorithm. But,
> since the byte[] size will not be over 100, you may assume that n is
> constant too, so it's a constant time algorithm.
>
> You didn't mention if the replacement should be in-place or not, so I'm
> assuming it's in place.
>
> Something like this I suppose:
>
> func main() {
> dict := map[byte]byte {0:1, 1:2, 3: 5}
> arr := []byte{0,1,1,2,3,5,8,13,21}
> fmt.Printf("Before: %#v", arr)
> for i, b := range arr {
> if replacement, ok := dict[b]; ok {
> arr[i] = replacement
> }
> }
> fmt.Printf("After: %#v", arr)
> }
>
> https://play.golang.org/p/hXnBKK3pDWk
>
> O(n) time complexity (or O(1) if n == 100) and O(k) additional space for
> the dictionary.
>
> Best,
>
> Dani
>
> Em qua, 29 de ago de 2018 às 22:15, <[email protected] <javascript:>>
> escreveu:
>
>> I have approximately 9 characters that all need to be replaced with
>> different characters. I know there are a number of ways to do this but what
>> is the most efficient?
>>
>>
>> - 1) Do a []byte walk and compare each byte and replace when found?
>> - Seems expensive if you have a 100 bytes in the []byte
>> - comes out to a max of 900 operations
>> - 2) Use byte.Replace() for each one?
>> - This seems to be about the same as #1 but seems like it makes a
>> copy so might use slightly more memory
>> - 3) Regex for each one?
>> - Seems like using a nuke to kill a flee
>> - Seems expensive in processing
>> - 4) Something I have not thought of?
>> - Specific algorithm to solve this?
>>
>>
>> The []byte slice it self likely will not be over 100 bytes, however they
>> may be be 10s of thousands of them.
>>
>> Thanks,
>> Anthony Gruetzmacher
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "golang-nuts" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected] <javascript:>.
>> For more options, visit https://groups.google.com/d/optout.
>>
>
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
