优化的通用列表拆分

这是我能做的最好的事情,以尽可能减少函数的分配时间(应该只在超过容量时进行分配,这应该不超过在结果中创建最大子列表所需的时间)。我已经测试了这个实现,它的工作方式和您描述的一样。

请注意,当访问组中的下一个列表时,前一个子列表的结果将被销毁。

public static IEnumerable<IEnumerable> Split(this  IEnumerable tokens, TokenType type)
{
    ArrayList currentT = new ArrayList();
    foreach (object list in tokens)
    {
        Token token = list as Token;
        if ((token != null) && token.TokenType == type)
        {
            yield return currentT;
            currentT.Clear();
            //currentT = new ArrayList(); <-- Use this instead of 'currentT.Clear();' if you want the returned lists to be a different instance
        }
        else if ((list is TokenType) && ((TokenType)list) == type)
        {
            yield return currentT;
            currentT.Clear();
            //currentT = new ArrayList(); <-- Use this instead of 'currentT.Clear();' if you want the returned lists to be a different instance
        }
        else
        {
            currentT.Add(list);
        }
    }
}

编辑 这是另一个版本,它根本不使用另一个列表(不应该进行任何分配)。不知道这会有多好的比较,但它确实按要求工作(我也不知道如果您尝试缓存子“数组”,这个会如何)。

另外,这两个都需要一个“using system.collections”语句(除了泛型命名空间之外)。

private static IEnumerable SplitInnerLoop(IEnumerator iter, TokenType type)
{
    do
    {
        Token token = iter.Current as Token;
        if ((token != null) && token.TokenType == type)
        {
            break;
        }
        else if ((iter.Current is TokenType) && ((TokenType)iter.Current) == type)
        {
            break;
        }
        else
        {
            yield return iter.Current;
        }
    } while (iter.MoveNext());
}

public static IEnumerable<IEnumerable> Split(this  IEnumerable tokens, TokenType type)
{
    IEnumerator iter = tokens.GetEnumerator();
    while (iter.MoveNext())
    {
        yield return SplitInnerLoop(iter, type);
    }
}

你的代码看起来不错。

我唯一的建议是 IEnumerable<object> 使用非泛型 IEnumerable . 中 System.Collections )

编辑 :

在进一步的检查中,你的施法次数超过了必要的次数。

替换 if 使用以下代码:

var token = list as Token;
if (token != null && token.TokenType == type) {

而且,你可以把你的 currentT 写入变量 t[t.Count - 1] 或 t.Last() . 这将使代码更清晰,但可能会对性能产生微小的负面影响。
或者,可以将对内部列表的引用存储在变量中并直接使用它。(这将稍微提高性能)

最后,如果您可以将返回类型更改为 List<List<Object>> ,您可以返回 t 直接;这将避免数组复制,并且对于大型列表将明显更快。

顺便说一下,您的变量名很混乱;您应该交换 T 和 list .

类型测试和类型转换可能是性能杀手。如果可能的话,令牌类型应该实现一个公共接口或抽象类。而不是进来 object ,您应该传入一个 IToken 把你的东西包起来。

以下是一些概念代码,您可以使用它们开始:

using System;
using System.Collections.Generic;

namespace Juliet
{
    interface IToken<T>
    {
        bool IsDelimeter { get; }
        T Data { get; }
    }

    class DelimeterToken<T> : IToken<T>
    {
        public bool IsDelimeter { get { return true; } }
        public T Data { get { throw new Exception("No data"); } }
    }

    class DataToken<T> : IToken<T>
    {
        public DataToken(T data)
        {
            this.Data = data;
        }

        public bool IsDelimeter { get { return false; } }
        public T Data { get; private set; }
    }

    class TokenFactory<T>
    {
        public IToken<T> Make()
        {
            return new DelimeterToken<T>();
        }

        public IToken<T> Make(T data)
        {
            return new DataToken<T>(data);
        }
    }

    class Program
    {

        static List<List<T>> SplitTokens<T>(IEnumerable<IToken<T>> tokens)
        {
            List<List<T>> res = new List<List<T>>();
            foreach (IToken<T> token in tokens)
            {
                if (token.IsDelimeter)
                {
                    res.Add(new List<T>());
                }
                else
                {
                    if (res.Count == 0)
                    {
                        res.Add(new List<T>());
                    }

                    res[res.Count - 1].Add(token.Data);
                }
            }

            return res;
        }

        static void Main(string[] args)
        {
            TokenFactory<string> factory = new TokenFactory<string>();
            IToken<string>[] tokens = new IToken<string>[]
                {
                    factory.Make("a"), factory.Make("b"), factory.Make("c"), factory.Make(),
                    factory.Make("d"), factory.Make("e"), factory.Make(),
                    factory.Make("f"), factory.Make("g"), factory.Make("h"), factory.Make(),
                    factory.Make("i"), factory.Make("j"), factory.Make("k"), factory.Make("l"), factory.Make(),
                    factory.Make("m")
                };

            List<List<string>> splitTokens = SplitTokens(tokens);
            for (int i = 0; i < splitTokens.Count; i++)
            {
                Console.Write("{");
                for (int j = 0; j < splitTokens[i].Count; j++)
                {
                    Console.Write("{0}, ", splitTokens[i][j]);
                }
                Console.Write("}");
            }

            Console.ReadKey(true);
        }
    }
}

原则上,您可以创建 IToken<object> 把它推广到多个类的标记。

A:如果您只是在嵌套foreach中迭代结果,那么全延迟实现就足够了:

using System;
using System.Collections.Generic;

public static class Splitter
{
    public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> source, Predicate<T> match)
    {
        using (IEnumerator<T> enumerator = source.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                yield return Split(enumerator, match);
            }
        }
    }

    static IEnumerable<T> Split<T>(IEnumerator<T> enumerator, Predicate<T> match)
    {
        do
        {
            if (match(enumerator.Current))
            {
                yield break;
            }
            else
            {
                yield return enumerator.Current;
            }
        } while (enumerator.MoveNext());
    }
}

像这样使用:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MyTokenizer
{
    class Program
    {
        enum TokenTypes { SimpleToken, UberToken }

        class Token { public TokenTypes TokenType = TokenTypes.SimpleToken;    }

        class MyUberToken : Token { public MyUberToken() { TokenType = TokenTypes.UberToken; } }

        static void Main(string[] args)
        {
            List<object> objects = new List<object>(new object[] { "A", Guid.NewGuid(), "C", new MyUberToken(), "D", new MyUberToken(), "E", new MyUberToken() });
            var splitOn = TokenTypes.UberToken;
            foreach (var list in objects.Split(x => x is Token && ((Token)x).TokenType == splitOn))
            {
                foreach (var item in list)
                {
                    Console.WriteLine(item);
                }
                Console.WriteLine("==============");
            }
            Console.ReadKey();
        }

    }
}

B:如果您需要在一段时间后处理结果,并且您希望处理得不正常,或者您在一个线程上进行分区,然后可能将这些段分派给多个线程,那么这可能会提供一个很好的起点:

using System;
using System.Collections.Generic;
using System.Linq;

public static class Splitter2
{
    public static IEnumerable<IEnumerable<T>> SplitToSegments<T>(this IEnumerable<T> source, Predicate<T> match)
    {
        T[] items = source.ToArray();
        for (int startIndex = 0; startIndex < items.Length; startIndex++)
        {
            int endIndex = startIndex;
            for (; endIndex < items.Length; endIndex++)
            {
                if (match(items[endIndex])) break;
            }
            yield return EnumerateArraySegment(items, startIndex, endIndex - 1);
            startIndex = endIndex;
        }
    }

    static IEnumerable<T> EnumerateArraySegment<T>(T[] array, int startIndex, int endIndex)
    {
        for (; startIndex <= endIndex; startIndex++)
        {
            yield return array[startIndex];
        }
    }
}

C:如果您真的必须返回一个list<t>-s的集合,我对此表示怀疑,除非您稍后明确希望对其进行变异,否则请在复制之前尝试将其初始化为给定的容量:

public static List<List<T>> SplitToLists<T>(this IEnumerable<T> source, Predicate<T> match)
{
    List<List<T>> lists = new List<List<T>>();
    T[] items = source.ToArray();
    for (int startIndex = 0; startIndex < items.Length; startIndex++)
    {
        int endIndex = startIndex;
        for (; endIndex < items.Length; endIndex++)
        {
            if (match(items[endIndex])) break;
        }
        List<T> list = new List<T>(endIndex - startIndex);
        list.AddRange(EnumerateArraySegment(items, startIndex, endIndex - 1));
        lists.Add(list);
        startIndex = endIndex;
    }
    return lists;
}

D:如果这还不够,我建议您滚动自己的轻量级列表实现,该实现可以从另一个实例将范围直接复制到其内部数组。

我的第一个想法是不要抬头 t[currentT] 一直以来,只要储存一个 currentList 直接加进去。

我认为在这些场景中,假设列表项是小写字母,并且具有匹配标记类型的项是t:

1. {T A B C…};
2. {…XY-Z T};
3. {…我不知道…};
4. { };及
5. {}

这将导致:

1. {{}{a b c…};
2. {…x y z}{};
3. {…我不知道…};
4. {{}};
5. {}

直接重构:

public static IEnumerable<object>[] Split(this IEnumerable<object> tokens,
                                          TokenType type) {
    var outer = new List<List<object>>();
    var inner = new List<object>();
    foreach (var item in tokens) {
        Token token = item as token;
        if (token != null && token.TokenType == type) {
            outer.Add(inner);
            inner = new List<object>();
            continue;
        }
        inner.Add(item);
    }
    outer.Add(inner);
    return outer.ToArray();
}

要修复损坏的案例(假设这些案例确实已损坏),我建议:

public static IEnumerable<object>[] Split(this IEnumerable<object> tokens,
                                          TokenType type) {
    var outer = new List<List<object>>();
    var inner = new List<object>();
    var enumerator = tokens.GetEnumerator();
    while (enumerator.MoveNext()) {
        Token token = enumerator.Current as token;
        if (token == null || token.TokenType != type) {
            inner.Add(enumerator.Current);
        }
        else if (inner.Count > 0) {
            outer.Add(inner);
            inner = new List<object>();
        }
    }
    return outer.ToArray();
}

这将导致:

1. {{a b c…};
2. {…x y z };
3. {…我不知道…};
4. {};
5. {}

使用linq你可以试试这个:(我没有测试它…)

    public static IEnumerable<object>[] Split(this  IEnumerable<object> tokens, TokenType type)
    {
        List<List<object>> l = new List<List<object>>();
        l.Add(new List<object>());
        return tokens.Aggregate(l, (c, n) => 
        {
            var t = n as Token;
            if (t != null && t.TokenType == type)
            {
                t.Add(new List<object>());
            }
            else
            {
                l.Last().Add(n);
            }
            return t;
        }).ToArray();
    }

第二次尝试:

public static IEnumerable<object>[] Split(this  IEnumerable<object> tokens, TokenType type)
{
    var indexes = tokens.Select((t, index) => new { token = t, index = index }).OfType<Token>().Where(t => t.token.TokenType == type).Select(t => t.index);
    int prevIndex = 0;
    foreach (int item in indexes)
    {
        yield return tokens.Where((t, index) => (index > prevIndex && index < item));
        prevIndex = item;
    }
}

有一种可能性

令牌类(可能是任何类)

public class Token
{
    public string Name { get; set; }
    public TokenType TokenType { get; set; }
}

现在是类型枚举(这可能是任何其他分组因素)

public enum  TokenType
{
    Type1,
    Type2,
    Type3,
    Type4,
    Type5,
}

扩展方法(不管您选择什么都声明这个)

public static class TokenExtension
{
    public static IEnumerable<Token>[] Split(this IEnumerable<Token> tokens)
    {
        return tokens.GroupBy(token => ((Token)token).TokenType).ToArray();
    }
}

使用示例(我使用了一个web项目来旋转这个)

List<Token> tokens = new List<Token>();
        tokens.Add(new Token { Name = "a", TokenType = TokenType.Type1 });
        tokens.Add(new Token { Name = "b", TokenType = TokenType.Type1 });
        tokens.Add(new Token { Name = "c", TokenType = TokenType.Type1 });

        tokens.Add(new Token { Name = "d", TokenType = TokenType.Type2 });
        tokens.Add(new Token { Name = "e", TokenType = TokenType.Type2  });

        tokens.Add(new Token { Name = "f", TokenType = TokenType.Type3 });
        tokens.Add(new Token { Name = "g", TokenType = TokenType.Type3 });
        tokens.Add(new Token { Name = "h", TokenType = TokenType.Type3 });

        tokens.Add(new Token { Name = "i", TokenType = TokenType.Type4 });
        tokens.Add(new Token { Name = "j", TokenType = TokenType.Type4 });
        tokens.Add(new Token { Name = "k", TokenType = TokenType.Type4 });
        tokens.Add(new Token { Name = "l", TokenType = TokenType.Type4 });

        tokens.Add(new Token { Name = "m", TokenType = TokenType.Type5 });

        StringBuilder stringed = new StringBuilder();

        foreach (Token token in tokens)
        {
            stringed.Append(token.Name);
            stringed.Append(", ");
        }

        Response.Write(stringed.ToString());
        Response.Write("</br>");


        var q = tokens.Split();
        foreach (var list in tokens.Split())
        {
            stringed = new StringBuilder();
            foreach (Token token in list)
            {
                stringed.Append(token.Name);
                stringed.Append(", ");
            }
            Response.Write(stringed.ToString());
            Response.Write("</br>");
        }

所以我所要做的就是使用linq,可以随意添加或删除,你可以在这个上疯狂,在许多不同的属性上分组。

是否需要将其转换为数组?您可以使用linq和延迟执行来返回结果。

编辑:
随着问题的澄清,将很难弯曲linq,使其返回您想要的结果。如果您仍然希望延迟每个周期的执行,可以编写自己的枚举器。

我建议将此选项与其他选项进行性能测试,以查看如果尝试此方法,您的场景是否有性能提升。它可能会导致管理迭代器的更多开销,这对于数据很少的情况是不利的。

我希望这能有帮助。

// This is the easy way to make your own iterator using the C# syntax
// It will return sets of separated tokens in a lazy fashion
// This sample is based on the version provided by @Ants
public static IEnumerable<IEnumerable<object>> Split(this IEnumerable<object> tokens,
                                          TokenType type) {        
    var current = new List<object>();

    foreach (var item in tokens) 
    {
        Token token = item as Token;
        if (token != null && token.TokenType == type) 
        {
            if( current.Count > 0)
            {
                yield return current;
                current = new List<object>();
            }
        }
        else 
        {
            current.Add(item);
        }
    }

    if( current.Count > 0)
        yield return current;
}

警告:这将编译,但仍可能有隐藏的错误。这里越来越晚了。

// This is doing the same thing but doing it all by hand. 
// You could use this method as well to lazily iterate through the 'current' list as well
// This is probably overkill and substantially more complex
public class TokenSplitter : IEnumerable<IEnumerable<object>>, IEnumerator<IEnumerable<object>>
{
    IEnumerator<object> _enumerator;
    IEnumerable<object> _tokens;
    TokenType _target;

    List<object> _current;
    bool _isDone = false;

    public TokenSplitter(IEnumerable<object> tokens, TokenType target)
    {
        _tokens = tokens;
        _target = target;
        Reset();
    }        

    // Cruft from the IEnumerable and generic IEnumerator
    public IEnumerator<IEnumerable<object>> GetEnumerator() { return this; }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    {
        return GetEnumerator();
    }

    public IEnumerable<object> Current { get { return _current; } }                
    public void Dispose() { }        

    #region IEnumerator Members

    object System.Collections.IEnumerator.Current { get { return Current; } }

    // See if there is anything left to get
    public bool MoveNext()
    {
        if (_isDone) return false;

        FillCurrent();

        return !_isDone;            
    }

    // Reset the enumerators so that you could reuse this structure if you wanted
    public void Reset()
    {
        _isDone = false; 
        _enumerator = _tokens.GetEnumerator();
        _current = new List<object>();
        FillCurrent();
    }

    // Fills the current set of token and then begins the next set
    private void FillCurrent()
    {
        // Try to accumulate as many tokens as possible, this too could be an enumerator to delay the process more
        bool hasNext = _enumerator.MoveNext();
        for( ; hasNext; hasNext = _enumerator.MoveNext())
        {            
            Token token = _enumerator.Current as Token;
            if (token == null || token.TokenType != _target)
            {
                _current.Add(_enumerator.Current);
            }
            else
            {
                _current = new List<object>();
            }
        }

        // Continue removing matching tokens and begin creating the next set
        for( ; hasNext; hasNext = _enumerator.MoveNext())
        {
            Token token = _enumerator.Current as Token;
            if (token == null || token.TokenType != _target)
            {
                _current.Add(_enumerator.Current);
                break;
            }
        }

        _isDone = !hasNext;
    }

    #endregion
}