I decided to learn Go, knowing Python. My approach is by solving easy problems like this one:
You are given two strings, A and B. Find if there is a substring that appears in both A and B. Several test cases will be given to you in a single file. The first line of the input will contain a single integer T, the number of test cases.
Then there will be T descriptions of the test cases. Each description contains two lines. The first line contains the string A and the second line contains the string B. For each test case, display YES (in a newline), if there is a common substring. Otherwise, display NO.
The problem is straightforward: check if two sets intersect.
The real problem is that for the biggest testcase (20 strings of length 105 each) my Go code takes 2.6 seconds, which is unacceptable, knowing that my Python code solves the problem in 0.08 seconds. Based on the fact that Go is claimed to be near C speed, I assume that I am doing something super inefficiently.
package main
import "fmt"
func subst(s1 string, s2 string) bool {
m := map[uint8]bool{}
for i := 0; i < len(s1); i++ {
m[s1[i]] = true
}
for i := 0; i < len(s2); i++ {
if m[s2[i]] {
return true
}
}
return false
}
func main() {
var n int
var s1, s2 string
fmt.Scanf("%d", &n)
for i := 0; i < n; i++ {
fmt.Scanf("%s", &s1)
fmt.Scanf("%s", &s2)
if subst(s1, s2) {
fmt.Println("YES")
} else {
fmt.Println("NO")
}
}
}
Python implementation:
def twoStrings(a, b):
if len(set(a) & set(b)):
print 'YES'
else:
print 'NO'
for i in xrange(input()):
twoStrings(raw_input(), raw_input())
Nonetheless, two snippets look really different, they are actually doing similar things. In go
I create a hash-map and put boolean value for each character from the first string (this is how sets are implemented in a lot of languages) and then for each character from the second string I am checking whether it is in a map and if no - exiting. It's obvious in the Python code.
any(char in a and char in b for char in ascii_lowercase)
is 5x faster than using sets. \$\endgroup\$ – Veedrac May 1 '15 at 10:44