Оптимизированный общий список Сплит

Question

Прочтите приведенное ниже для получения дополнительной информации.

У меня есть код ниже, который я использую для разделения общего списка объектов, когда элемент имеет определенный тип.

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, если кто-то заинтересован, возможно, мы сможем отслеживать последние изменения.

Обновление: Я пытаюсь разобрать конкретные жетоны. Его список некоторых классов классов и токенов. Токен имеет свойство (enum) 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} 

EDIT UPDATE: Похоже, все мои проблемы скорости приходят в постоянное создание и дополнение родовых списков. Кто-нибудь знает, как я могу обойти это без этого? Это профиль того, что происходит, если он кому-то помогает.

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

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

EDIT Вот еще одна версия, которая не использует другого списка на всех (не следует делать каких-либо ассигнований). Не уверен, насколько хорошо это будет сравнивать, но он работает по запросу (также я понятия не имею, как это произойдет, если вы попытаетесь кэшировать вспомогательный массив).

Кроме того, для обоих из них требуется выражение «using System.Collections» (в дополнение к пространству имен Generic).

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

Answer 2

Ваш код выглядит нормально.

Мое единственное предложение будет заменять IEnumerable<object> с не общим IEnumerable. (В System.Collections)

EDIT:

О дальнейшей проверки, вы литье больше раз, чем это необходимо.

Заменить 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.

Answer 3

Нужно ли преобразовать его в массив? Вы можете использовать LINQ и отложенное выполнение для возврата результатов.

EDIT:
С осветленной вопрос было бы трудно согнуть 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 
} 

Answer 4

Моя первая мысль была бы вместо того, чтобы искать t[currentT] все время, просто хранить currentList и добавить непосредственно к этому.

Answer 5

Я думаю, что сломаны случаи для этих сценариев, в которых предполагающих, что элементы списка являются строчными буквами, а элемент с совпадающим типом маркеров Т:

1. {T а б ...};
2. {... x y z T};
3. {... j k l T T m n o ...};
4. {T}; и
5. {}

Который приведет:

1. {{} {а б ...}};
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. {}

Answer 6

Типовые испытания и слепки могут быть убийцей производительности.Если это вообще возможно, ваши типы токенов должны реализовывать общий интерфейс или абстрактный класс. Вместо того чтобы проходить через и 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>, чтобы он обобщается знаками нескольких классов.

Answer 7

Использование 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; 
    } 
}