c# - 使用 LINQ 计算两个字符串之间的汉明距离

Question

我需要帮助。我正在编写一个函数来比较字符串参数之间的汉明距离，这意味着您必须返回每个字符串中相同索引处的元素不相同的次数。

我已经设法用 for 循环完成该方法，但是使用这个 Linq 方法它只通过了 9 项测试中的 8 项。

我的初始循环:

public static int Distance(string firstStrand, string secondStrand)
{
    int count = 0;

    if(firstStrand.Length>secondStrand.Length || firstStrand.Length<secondStrand.Length){throw new ArgumentException();}
    else if(firstStrand.Length == 0 || secondStrand.Length == 0){count = 0;}
    else if(firstStrand == secondStrand){count = 0;}
    else
    {
        for(int i = 0; i < firstStrand.Length; i++)
        {
            if(firstStrand[i] != secondStrand[i])
            {
                count++;
            }
        }
    }


    return count;
}

我对 Linq 的尝试:

public static int Distance(string firstStrand, string secondStrand)
{
    int count = 0;

    if (firstStrand.Length > secondStrand.Length || firstStrand.Length < 
    secondStrand.Length) { throw new ArgumentException(); }
    if(firstStrand.Length == 0 && secondStrand.Length == 0) { count = 0; }
    else if (firstStrand == secondStrand) { count = 0; }
    else
    {

        var result = firstStrand.Zip(secondStrand, (c, b) => c != b);

        foreach (int value in result)
        {
            count++;
        }

    }
        return count;
}

测试文件:

[Fact]
public void Empty_strands()
{
    Assert.Equal(0, Hamming.Distance("", ""));
}

[Fact]
public void Single_letter_identical_strands()
{
    Assert.Equal(0, Hamming.Distance("A", "A"));
}

[Fact]
public void Single_letter_different_strands()
{
    Assert.Equal(1, Hamming.Distance("G", "T"));
}

[Fact]
public void Long_identical_strands()
{
    Assert.Equal(0, Hamming.Distance("GGACTGAAATCTG", "GGACTGAAATCTG"));
}

[Fact]
public void Long_different_strands()
{
    Assert.Equal(9, Hamming.Distance("GGACGGATTCTG", "AGGACGGATTCT"));
}

[Fact]
public void Disallow_first_strand_longer()
{
    Assert.Throws<ArgumentException>(() => Hamming.Distance("AATG", "AAA"));
}

[Fact]
public void Disallow_second_strand_longer()
{
    Assert.Throws<ArgumentException>(() => Hamming.Distance("ATA", "AGTG"));
}

[Fact]
public void Disallow_left_empty_strand()
{
    Assert.Throws<ArgumentException>(() => Hamming.Distance("", "G"));
}

[Fact]
public void Disallow_right_empty_strand()
{
    Assert.Throws<ArgumentException>(() => Hamming.Distance("G", ""));
}

希望大家指点一下。我对 Linq 还是很陌生。

Answer 1

您的实现存在的问题是，当您比较字符值时，您从不考虑比较的结果。您只需计算比较值的总长度，这将与输入字符串的长度相同。

您有 9 个测试用例，但即使在您的实现中存在这个严重缺陷，8 个仍然成功，因为:

• 零长度字符串通常会导致计数为零
• 相同的字符串将通过您的==优化计算字符串的长度
• 涉及不同长度字符串的测试用例会抛出异常，所以永远不要关心计算的计数

只有一个测试用例以非平凡的方式实际执行比较代码，所以当然是失败的那个。

在我看来，您的方法更有效的实现方式如下所示:

public static int Distance(string firstStrand, string secondStrand)
{
    if (firstStrand.Length != secondStrand.Length) { throw new ArgumentException(); }

    return firstStrand.Zip(secondStrand, (c, b) => c != b).Count(f => f);
}

一些注意事项:

• 多次比较 Length 属性没有意义。检查第一个长度是否小于第二个，然后检查它是否大于第二个，与检查它们是否不相等相同。一旦您满足了该要求，您就不需要检查两个长度来了解两个长度是否为零。
• 也没有必要像您一样尝试优化特殊情况。要比较字符串是否相等，您无论如何都需要扫描两者。这种“优化”实际上会损害性能，至少对于某些类型的数据而言是这样，因为它会导致字符串的过度迭代。优化零长度的情况也没有用；在进行这种比较时，零长度字符串是您最不用担心的。保持代码简单更好。