2010-02-16 49 views
4

阅读下面的编辑以获取更多信息。优化泛型列表拆分

下面我有,我用当产品某一类型的分割对象的泛型列表一些代码。

public static IEnumerable<object>[] Split(this IEnumerable<object> tokens, TokenType type) { 

     List<List<object>> t = new List<List<object>>(); 
     int currentT = 0; 
     t.Add(new List<object>()); 
     foreach (object list in tokens) { 
      if ((list is Token) && (list as Token).TokenType == type) { 
       currentT++; 
       t.Add(new List<object>()); 

      } 
      else if ((list is TokenType) && ((TokenType)list)== type) { 
       currentT++; 
       t.Add(new List<object>()); 

      } 
      else { 
       t[currentT].Add(list); 
      } 
     } 

     return t.ToArray(); 
    } 

我没有一个明确的问题,因为我很好奇,如果有人知道任何方式,我可以优化此代码。我多次称它为“时钟周期”,它似乎是相当的野兽。有任何想法吗?如果有人感兴趣,我也可以将其制作成Wiki,也许我们可以跟踪最新的变化。

更新:我试着去分析出具体的令牌。它是一些其他类和令牌类的列表。令牌具有TokenType的属性(枚举)。我需要找到所有的令牌类,并在每个类中分割。

{a b c T d e T f g h T i j k l T m} 

会分裂样

{a b c}{d e}{f g h}{i j k l}{m} 

编辑更新: 好像所有我的速度问题进入不断建立和另外泛型列表中。有没有人知道我怎么能没有这个呢? 这是如果它可以帮助任何人的情况下所发生的情况。

alt text http://i49.tinypic.com/1zvpcmq.png

+2

原谅我的无知,但这段代码解决了什么问题? – 2010-02-16 01:42:51

+0

哇......你是从Python中移植这段代码的吗?必须有更好的方法来做到这一点。 – Randolpho 2010-02-16 01:49:17

+0

@Randolpho:不是。 – SLaks 2010-02-16 01:51:12

回答

1

这是我可以做的最好的事情,以尽可能多地为函数分配时间(应该只在分配容量时进行分配,这应该不会超过创建最大子分区所需的分配时间在结果中)。我已经测试过这个实现,它的工作原理与你所描述的一样

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

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); 
     } 
    } 
} 

编辑 这里的另一个版本,不会使所有使用另一个名单(不应该做任何分配)。不知道这会比较好,但它确实按要求工作(我也不知道如果你试图缓存一个子数组,它将如何去)。

此外,这两个要求“使用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); 
    } 
} 
+1

我也建议如果这个函数看起来是你的瓶颈,那么你可能会通过尝试为你正在尝试执行的整体任务找到一个更好的算法,或者你应该缓存结果每个操作(我的实现不适用于缓存,但如果需要的话,请使用原始实现) – 2010-02-22 03:46:15

4

您的代码看起来不错。

我的唯一建议是用非泛型IEnumerable代替IEnumerable<object>。 (在System.Collections

编辑

在进一步的检查,你超过必要铸造多次。

用下面的代码替换if

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

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

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

顺便说一句,你的变量名是混乱的;您应该更换tlist的名称。

0

你需要将其转换为一个数组?你可以使用LINQ和延迟执行来返回结果。

编辑:
随着澄清疑问这将是难以弯曲LINQ,使其返回结果你想要的方式。如果你仍然想延迟每个周期的执行,你可以编写自己的枚举器。

我建议使用perf测试,与其他选项进行比较,以确定如果尝试使用此方法,您的方案是否会有性能提升。这可能会导致更多的管理迭代器的开销,这对于数据量很小的情况会很糟糕。

我希望这会有所帮助。

// 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 
} 
+0

的例子我可能会使用这种方法,你能详细说明它将如何完成吗? – Dested 2010-02-16 06:33:19

2

我首先想到的是,而不是仰视t[currentT]所有的时间,只是存储currentList,直接补充。

+0

这将使代码更简单,更具可读性。 – SLaks 2010-02-16 01:52:51

1

我认为有被打破的情况下,这些场景中假定列表项是小写字母,以及相匹配的令牌类型的产品T:

  1. 【T A B C ...};
  2. {... x y z T};
  3. {... j k l T T m n o ...};
  4. {T};和
  5. {}

这将导致:

  1. {{} {A B C ...}};
  2. {{... x y z} {}};
  3. {{... j k l} {} {} {m n o ...}};
  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. {{... j k l} {m n o ...}};
  4. {};和
  5. {}
3

类型测试和类型转换可以是性能杀手。如果可能的话,你的令牌类型应该实现一个通用接口或抽象类。而不是通过和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>情况下把它推广到多个类的标记。

1

使用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; 
    } 
} 
+0

有趣的做法!速度问题似乎来自通用列表的创建和列举。我真正需要的是一种解决方案,它能够以某种方式向我返回我想要的数组中的Ienumerable ,而不是不断添加到列表。 – Dested 2010-02-19 20:51:53

+0

@Dested:好吧,看来我错过了你的评论。如果你想做数组,只需用'Array.Copy()'替换我的最后一段代码中的列表创建和'list.AddRange(EnumerateArraySegment(items,startIndex,endIndex - 1));'部分。 我希望这可以帮助。 – 2010-02-22 00:20:43

3

答:一个全懒实施,就足够了您只需遍历嵌套的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()); 
    } 
} 

使用它l IKE在此:

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:如果你真的必须返回列表的集合<牛逼> -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:如果这仍然是不够的,我建议你滚你自己的轻量级目录实现可以将范围直接复制到另一个实例的内部数组。

+0

我喜欢它!这是超级干净。做得好。 – smaclell 2010-02-20 07:16:27

+0

@Dested:如果你需要数组,只需要用'创建一个新数组并替代'Array.Copy'来替换'list.Addrange'周围的部分。 – 2010-02-22 18:58:59

1

这是一个可能性

的令牌类(可能是什么都类)

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 soing,随意添加或删除,你可以actualy发疯就这个问题和群体在许多不同的性质。

+0

如果你想要,你可以声明一个对象列表,并在尝试读取属性之前改变方法以使用“as”运算符进行测试。 或者你也可以坚持使用反射,甚至可以使用MSIL来达到非常低的水平。 – Oakcool 2010-02-19 23:31:00