使用分隔符序列拆分一个ICollection<T>。

Question

这是针对C# 3.5的。

我有一个ICollection，我试图将其拆分成不同的ICollections，其中分隔符是一个序列。

例如

ICollection<byte> input = new byte[] { 234, 12, 12, 23, 11, 32, 23, 11 123, 32 };
ICollection<byte> delimiter = new byte[] {23, 11};
List<IICollection<byte>> result = input.splitBy(delimiter);

会导致

result.item(0) = {234, 12, 12};
result.item(1) = {32};
result.item(2) = {123, 32};

- Corey S

---

@Ben：可能，但不一定。我在现实世界中也不得不做类似的事情。 - AllenG

这里有一个新颖的想法。至少对于byte的情况，您可以将其转换为ASCII字符串并使用Split()进行拆分。不确定是否适用于所有情况，但在理论上听起来不错。 - Jeff Mercado

@ba__friend：当然。但我想我已经掉了一两个这样的“这是我的问题。背景是什么？”所以我愿意给一些宽限。 - AllenG

让我们等一下，也许他会添加一些内容 ;) - ba__friend

@Ben @AllenG @ba_friend 这不是作业，而是我正在进行的一个项目。字节信息是编码字符串与文件的字节数据连接在一起。@Jeff 我考虑过这样做，但我不想转换成字符串再转回来。 - Corey S

Answer 1

private static IEnumerable<IEnumerable<T>> Split<T>
    (IEnumerable<T> source, ICollection<T> delimiter)
{
    // window represents the last [delimeter length] elements in the sequence,
    // buffer is the elements waiting to be output when delimiter is hit

    var window = new Queue<T>();
    var buffer = new List<T>();

    foreach (T element in source)
    {
        buffer.Add(element);
        window.Enqueue(element);
        if (window.Count > delimiter.Count)
            window.Dequeue();

        if (window.SequenceEqual(delimiter))
        {
            // number of non-delimiter elements in the buffer
            int nElements = buffer.Count - window.Count;
            if (nElements > 0)
                yield return buffer.Take(nElements).ToArray();

            window.Clear();
            buffer.Clear();
        }
    }

    if (buffer.Any())
        yield return buffer;
}

- mqp

---

“Queue<T>”比“LinkedList<T>”更好，为什么不使用“foreach”？ - svick

这将为所有序列产生相同的缓冲区，因此Split(source, delimiter).ToList()将返回相同序列的列表，即解析的最后一个序列。 - Rick Sladkey

@Magnus：我认为可能没有任何问题，我认为我的评论准确地代表了性能。@Rob：我个人不这么认为——我希望返回一个空的序列。我同意在编写此代码之前，应该考虑好边缘情况下想要什么。 - mqp

"e".Split('e') 会返回两个空字符串。同样地，我期望在 source 等于 delimiter 的情况下也会返回两个空序列。我猜测（没有验证）你可以移除最后的 if (buffer.Any()) 条件，并且总是返回缓冲区，无论它是否为空。 - Rob

@Rob：这将产生一个空序列，而不是两个。我喜欢这种方式，因为我认为它对应于string.Split的最有用的行为（即RemoveEmptyEntries），但我也认为将其扩展为完全像string.Split一样的行为将有很多优点，就像Jeff Mercado在他的回答中所做的那样。 - mqp

Answer 2

一个最优解不会使用SequenceEqual()来检查每个子范围，否则你可能会为序列中的每个项目迭代分隔符的长度，这可能会损害性能，特别是对于大的分隔符序列。可以在枚举源序列时进行检查。

这是我写的代码，但总有改进的空间。我旨在具有类似于String.Split()的语义。

public enum SequenceSplitOptions { None, RemoveEmptyEntries }
public static IEnumerable<IList<T>> SequenceSplit<T>(
    this IEnumerable<T> source,
    IEnumerable<T> separator)
{
    return SequenceSplit(source, separator, SequenceSplitOptions.None);
}
public static IEnumerable<IList<T>> SequenceSplit<T>(
    this IEnumerable<T> source,
    IEnumerable<T> separator,
    SequenceSplitOptions options)
{
    if (source == null)
        throw new ArgumentNullException("source");
    if (options != SequenceSplitOptions.None
     && options != SequenceSplitOptions.RemoveEmptyEntries)
        throw new ArgumentException("Illegal option: " + (int)option);
    if (separator == null)
    {
        yield return source.ToList();
        yield break;
    }

    var sep = separator as IList<T> ?? separator.ToList();
    if (sep.Count == 0)
    {
        yield return source.ToList();
        yield break;
    }

    var buffer = new List<T>();
    var candidate = new List<T>(sep.Count);
    var sindex = 0;
    foreach (var item in source)
    {
        candidate.Add(item);
        if (!item.Equals(sep[sindex]))
        {   // item is not part of the delimiter
            buffer.AddRange(candidate);
            candidate.Clear();
            sindex = 0;
        }
        else if (++sindex >= sep.Count)
        {   // candidate is the delimiter
            if (options == SequenceSplitOptions.None || buffer.Count > 0)
                yield return buffer.ToList();
            buffer.Clear();
            candidate.Clear();
            sindex = 0;
        }
    }
    if (candidate.Count > 0)
        buffer.AddRange(candidate);
    if (options == SequenceSplitOptions.None || buffer.Count > 0)
        yield return buffer;
}

- Jeff Mercado

Answer 3

public IEnumerable<IEnumerable<T>> SplitByCollection<T>(IEnumerable<T> source, 
                                                        IEnumerable<T> delimiter)
{
    var sourceArray = source.ToArray();
    var delimiterCount = delimiter.Count();

    int lastIndex = 0;

    for (int i = 0; i < sourceArray.Length; i++)
    {
        if (delimiter.SequenceEqual(sourceArray.Skip(i).Take(delimiterCount)))
        {
            yield return sourceArray.Skip(lastIndex).Take(i - lastIndex);

            i += delimiterCount;
            lastIndex = i;
        }
    }

    if (lastIndex < sourceArray.Length)
        yield return sourceArray.Skip(lastIndex);
}

调用它...

var result = SplitByCollection(input, delimiter);

foreach (var element in result)
{
    Console.WriteLine (string.Join(", ", element));
}

返回

234，12，12
32
123，32

- ulrichb

---

这肯定是正确的想法，但我真的希望你不要认真建议这种实现方式。反复枚举源序列是不合理的，而且由于此原因算法的复杂度非常糟糕。 - mqp

.Count() 是一个 O(n) 操作。 - Magnus

Answer 4

这是我的看法：

public static IEnumerable<IList<byte>> Split(IEnumerable<byte> input, IEnumerable<byte> delimiter)
{
    var l = new List<byte>();
    var set = new HashSet<byte>(delimiter);
    foreach (var item in input)
    {
        if(!set.Contains(item))
            l.Add(item);
        else if(l.Count > 0)
        {
            yield return l;
            l = new List<byte>();
        }
    }
    if(l.Count > 0)
        yield return l;
}

- Magnus

Answer 5

可能有更好的方法，但这是我以前使用过的一种方法：对于相对较小的集合来说很好：

byte startDelimit = 23;
byte endDelimit = 11;
List<ICollection<byte>> result = new List<ICollection<byte>>();
int lastMatchingPosition = 0;
var inputAsList = input.ToList();

for(int i = 0; i <= inputAsList.Count; i++)
{
    if(inputAsList[i] == startDelimit && inputAsList[i + 1] == endDelimit)
    {
        ICollection<byte> temp = new ICollection<byte>();
        for(int j = lastInputPosition; j <= i ; j++)
        {
            temp.Add(inputAsList[j]);
        }
        result.Add(temp);
        lastMatchingPosition = i + 2;
    }
}

我现在没有打开我的集成开发环境，所以这可能无法编译，或者可能有一些你需要填补的漏洞。但这是我遇到这个问题时的起点。同样，就像我之前说过的那样，如果这是针对大型集合的，它会很慢 - 因此可能存在更好的解决方案。

- AllenG

---

如果分隔符是三个字节长呢？或者十个字节呢？ - svick

你需要适当地更改逻辑。使用字节集作为分隔符，每次 inputAsList[i] == 你的第一个分隔符时，你可以枚举它而不是枚举主列表，但这会使其变得更慢。 - AllenG

我想我说过了。它假设有一个小集合。 - AllenG

我不会仅将分隔符的大小定义为 2，因为如果你需要 3、4、5 的话，那么它们也同样小。 - Jeff Mercado

啊，那个部分。我在评论中解决了这个问题。由于他在问题中只寻找两个，所以这是我在答案中使用的假设。如果他需要更多，那么我可能会稍微改变一下。但是，目前它并不是很可扩展。因此我的免责声明。 - AllenG

不用说，你不能构造一个类型为ICollection<byte>的对象。 - mqp