Skip to content

Instantly share code, notes, and snippets.

@benhoyt benhoyt/join.awk
Created Nov 20, 2018

Embed
What would you like to do?
AWK program to compare time complexity of joining strings
# AWK program to compare time complexity of joining strings using a
# simple O(N^2) algorithm and a slightly more complex O(N log N) one.
# Join array elements, separated by sep: O(N^2) version
function join1(a, sep, i, s) {
for (i = 1; i+1 in a; i++) {
s = s a[i] sep
}
if (i in a) {
s = s a[i]
}
return s
}
# Join array elements, separated by sep: O(N log N) version
function join2(a, sep, b, i, j, n) {
# Copy a into local array "b" and find length "n"
for (i in a) {
b[i] = a[i]
n++
}
# Make log(n) passes, joining two strings at a time
while (n > 1) {
j = 0
for (i = 1; i+1 <= n; i += 2) {
b[++j] = b[i] sep b[i+1]
}
if (i <= n) {
b[++j] = b[i]
}
n = j
}
# Return final joined string
return b[1]
}
BEGIN {
if (ARGC < 3) {
print "usage: join.awk join1|join2 n"
exit 1
}
s = "The quick brown fox jumps over the lazy dog. "
for (i=0; i<int(ARGV[2]); i++) {
s = s s
}
print length(s)
split(s, a)
if (ARGV[1] == "join1") {
s = join1(a, " ")
} else {
s = join2(a, " ")
}
print length(s)+1
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.