1

我需要一个带有两个参数的扩展方法：一个目标IList<T>和一个自定义比较器。

public static void CustomSort<T>( IList<T> target, IComparer<T> comparer )
{
    ...
}

扩展方法的工作是按照自定义比较器指示的顺序排列目标元素。

以下是一些不起作用的解决方案：

  • 就地排序，这List<T>.Sort基本上是我所追求的。但我不能假设目标的具体类型是List<T>.
  • LINQ 提供了一些解决方案，但不幸的是，它们将结果作为新的枚举输出，而不是修改目标列表。

相反，我需要调用目标Remove和Insert方法以将其元素放入正确的顺序。目标列表可能是可观察的，因此重要的是解决方案不会执行比获得所需顺序所需的更多的删除和插入。

4

3 回答 3

2

我认为这样的事情会做你。

我们对偏移数组进行排序，然后确定需要应用的增量集，最后应用它们来生成新排序的 IList。

public static void CustomSort<T>( IList<T> list , IComparer<T> comparer )
{
  int[] unsorted = Enumerable.Range(0,list.Count).ToArray() ;
  int[] sorted   = Enumerable.Range(0,list.Count).OrderBy( x => list[x] , comparer ).ToArray() ;
  var   moves    = sorted.Zip( unsorted , (x,y) => new{ Src = x , Dest = y , } ).Where( x => x.Src != x.Dest ).OrderBy( x => x.Src ).ToArray() ;

  // at this point, moves is a list of moves, from a source position to destination position.
  // We enumerate over this and apply the moves in order.
  // To do this we need a scratch pad to save incomplete moves, where an existing item has
  // been over-written, but it has not yet been moved into its final destination.

  Dictionary<int,T> scratchPad = new Dictionary<int, T>() ; // a parking lot for incomplete moves
  foreach ( var move in moves )
  {
    T value ;

    // see if the source value is on the scratchpad.
    // if it is, use it and remove it from the scratch pad.
    // otherwise, get it from the indicated slot in the list.
    if ( scratchPad.TryGetValue( move.Src , out value ) )
    {
      scratchPad.Remove( move.Src );
    }
    else
    {
      value = list[ move.Src ] ;
    }

    // if the destination is after the source position, we need to put
    // it on the scratch pad, since we haven't yet used it as a source.
    if ( move.Dest > move.Src )
    {
      scratchPad.Add( move.Dest , list[ move.Dest ]);
    }

    // finally, move the source value into its destination slot.
    list[ move.Dest ] = value ;

  }

  return ;
}
于 2013-09-24T20:59:27.370 回答
1

  1. 使用LINQ扩展方法排序，ToList()最后隐式调用得到一个新的List；

  2. 然后告诉你的可观察列表暂停自己（不关心变化）

  3. 清除您的可观察列表

  4. 从 linq-ordered 列表中将项目添加到 observable 列表中。

  5. 告诉你的可观察列表继续观察变化

关于 observables 观察的变化次数是有效的；从算法效率的角度来看，我会尝试这个解决方案。您可能永远不需要进一步优化。记住：过早优化是万恶之源

于 2013-09-24T23:08:27.017 回答
1

评论表明，如前所述，这实际上可能是一个难题。那么如果我们从不同的角度来看待这个问题呢：

  1. 为什么这个集合的观察者需要这么长时间？他们应该只对个人变化做出快速反应。例如，如果是为了 UI 更改，它可以等到下一次 UI 重绘后才关心更改。这应该让整个重新排序一次完成。或者
  2. 使用类似的东西，ObservableRangeCollection<T>这样你就有了一个AddRange可观察的集合。如果可能，一些简单的代码可以确定该集合是否可用List<T>或ObservableRangeCollection<T>使用AddRange。

例如

public static void SmartSort<T>(IList<T> source)
{
    var sortedList = source.OrderBy(x => x).ToList();
    if (source.SequenceEqual(sortedList))
        return;
    var list = source as List<T>;
    var collection = source as ObservableRangeCollection<T>;
    if (list != null)
    {
        list.Clear();
        list.AddRange(sortedList);
    }
    else if (collection != null)
        collection.ReplaceRange(sortedList);
    else
    {
        for (int i = 0; i < source.Count; i++)
            source[i] = sortedList[i];
    }
}
于 2013-09-24T19:27:12.670 回答