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, <agruet...@gmail.com> 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 golang-nuts+unsubscr...@googlegroups.com.
> 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 golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
