Follow

Feeling a little iffy on this function to calculate the mean edit distances of a list of words...

github.com/sts10/tidy/blob/mai

take 2 on this tricky "calculate mean edit distance of list of words"

github.com/sts10/tidy/blob/mea

Feel like there's a way to cut the time in half?

@schlink That's because I'm pretty sure it's wrong. You want for every (m, n) where m != n, get the edit distance.

for #1 should be i = 0 ... list size - 1
for #2 should be j = 0 to i - 1

No?

@schlink Oh and also m < n indexwise. Actually the additional check for same word is pretty... iffy itself. If it's a list of all the same words... the mean edit distance should be 0.

@schlink Yep. There is. More like this...
for i = 0..list.len() {
for j = 0 .. i - 1 {
let this_edit_distance = find_edit_distance(list[i], list[j]);

@schlink The trick is to make a table. The list of words on the X axis, the list of words on the Y axis. You know you don't need the diagonal in that table (comparing index i to index i). You also don't need anything past that diagonal because that'll be a double compare.

Sign in to participate in the conversation
Octodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!