比较环形缓冲区的内容

Question

我需要检查特定数字序列的接收情况，例如3,3,3,2,2,3，但此重复序列可以从不同的位置开始，例如3,3,3,3,2,2

我已经创建了一个环形缓冲区，用于存储接收到的数字并与所有可能的序列进行比较

class MFMSequence {
    int _index = 0;
    int[] _buffer = new int[6];
    public void add(int value) {
        _buffer[_index] = value;
        _index = (_index + 1) % 6;
    }
    public bool is4e() {
        return (_buffer.SequenceEqual(new int[] { 3, 3, 3, 2, 2, 3 }) ||
                _buffer.SequenceEqual(new int[] { 3, 3, 3, 3, 2, 2 }) ||
                _buffer.SequenceEqual(new int[] { 2, 3, 3, 3, 3, 2 }) ||
                _buffer.SequenceEqual(new int[] { 2, 2, 3, 3, 3, 3 }) ||
                _buffer.SequenceEqual(new int[] { 3, 2, 2, 3, 3, 3 }) ||
                _buffer.SequenceEqual(new int[] { 3, 3, 2, 2, 3, 3 }));
    }
    public bool is00() {
        return (_buffer.SequenceEqual(new int[] { 2, 2, 2, 2, 2, 2 }));
    }
}

这是工作，但我觉得它丑陋！有没有关于如何更优雅地编写代码的想法？

Answer 1

您可以尝试这样做：

private bool CheckIt(int[] checkFor, int[] have)
{
    return Enumerable.Range(0, checkFor.Length).Any(i =>
        checkFor.Concat(checkFor).Skip(i).Take(have.Length).SequenceEqual(have)
    );
}

不完全“漂亮”，但它是一个快速的模型，我相信有很多改进。也适用于任意数量的项目。用法：

var checkFor = new int[] { 3,3,3,2,2,3 };
var have = new int[] { 3,2,2,3,3,3 };
var result = CheckIt(checkFor, have);

Answer 2

您可以编写一个循环来比较所有可能的序列，然后至少可以将其扩展到任意数量的项，而不必更改代码：

public static bool RingBufferContains(int[] buffer, int[] target)
{
    if (buffer == null || target == null || buffer.Length != target.Length)
        throw new InvalidOperationException("buffer and target must be non-null and the same length.");

    int n = buffer.Length;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (buffer[(i+j)%n] != target[j])
                break;

            if (j == n - 1)
                return true;
        }
    }

    return false;
}

这是一个O(N^2)解决方案，就像您的解决方案一样。

测试代码：

int[] buffer = { 3, 2, 2, 3, 3, 3 };
int[] target = { 3, 3, 3, 2, 2, 3 };
Console.WriteLine(RingBufferContains(buffer, target));

Answer 3

我认为Rob和Matthew Watson的解决方案比硬编码所有的可能性要好得多。Matthew的代码更优化，但Rob的代码看起来更漂亮。如果你的序列很小，这两个就足够好了。但是，如果你有更多更大的序列，或者如果你想开发一些通用的解决方案，你应该优化它。

我的想法是将序列的起始位置设置为最小或最大元素，并且只比较序列一次。

如果我们有几个min或max元素，我们就有几个可能的起始位置，我们需要比较几次。在最坏的情况下，它将是N/2次(序列{ min，max，max，max })。