Lecture 1

[pevnak]

Tim Holy in the video I posted somewhere on slack has absolutely great example of two language problem. It goes as follows. Imagine you are supposed to compute number of occurences of an integer in a seqeunce. A naive version would be

function occurrences!(counts, x)
  for i in 1:counts
    x[i] = count(==(i), x)
  end
end

where he assume that you will initiate counts well. This is obviously a shitty algorithm, because it has complexity o(length(counts)length(x). A sane programmer would code it as

function occurrences!(counts, x)
  fill!(counts, 0)
  for j in x
    x[j] += 1
  end
end

is obviously right with complexity O(length(counts) + length(x)). Funny enough, in Python, the second is super slow and first is fast, because numpy implements count function. Tim shows the scaling with respect to counts and x in 3d graphs and rotate them to show scaling according to individual dimensions. I have not seen a better sell of two language problem.

[nmheim]

Oh, nice one!

[natema]

I haven't seen the video that is mentioned in the OP, but the code of the two examples looks broken to me. My guess is that the first should be

function occurrences!(counts, x)
  for i in eachindex(counts)
    counts[i] = count(==(i), x)
  end
end

and the second should be

function occurrences!(counts, x)
  fill!(counts, 0)
  for j in x
    counts[j] += 1
  end
end