将一个IEnumerable<IEnumerable<T>>“旋转”90度

Question

我需要的是一种基本操作（我相信这个操作有一个名字，但我目前还不知道）。我有一个矩阵，例如：

{1,2,3}

{A,N,F}

{7,8,9}

我希望将其转换为

{1,A,7}

{2,N,8}

{3,F,9}

（上述仅为对象标识符，而非实际值。实际对象类型相同且无序）

我更喜欢声明性的解决方案，但速度也很重要。我将需要处理相当多的表格（每分钟处理10万个单元格），如果速度过慢就会成为关键路径。

然而，我更感兴趣的是可读性较强的解决方案。 我正在寻找以下方法的替代方案。（“替代”并不意味着变体，而是不同的方法）

var  arrays = rows.Select(row => row.ToArray());
var cellCount = arrays.First().Length;
for(var i = 0;i<cellCount;i++){
  yield return GetRow(i,arrays);
}

IEnumerable<T> GetRow(int i,IEnumerable<T[]> rows){
  foreach(var row in rows}{
     yield return row[i]; 
  }
}

在两个几乎同样易读的解决方案中，我会选择更快的一个，但是可读性要比速度重要。

编辑 它将始终是一个方阵。

- Rune FS

---

这被称为转置（http://zh.wikipedia.org/wiki/转置） - Frank

我认为这已经非常易读了！ - logicnp

这仅适用于方阵，还是适用于非方阵？ - Ken Wayne VanderLinde

@Novox 谢谢，我知道我的代数里有些东西我忘了。 - Rune FS

顺时针旋转90度实际上会得到 {7,A,1} {8,N,2} {9,F,3}。 - MSalters

@MSalters 你是对的，我相信我实际上需要什么还是很明显的，虽然“旋转90度”不准确。 - Rune FS

Answer 1

我对这个实现有些犹豫。它在迭代器局部具有副作用，但在逻辑上看起来很清晰。这假定每个序列的长度相同，但应该适用于任何长度。您可以将其视为可变长度的 Zip() 方法。它应该比其他答案中找到的链接的LINQ解决方案执行得更好，因为它只使用了必要的最小操作才能工作。即使没有使用LINQ，它的表现也可能更好。甚至可以被认为是最优的。

public static IEnumerable<IEnumerable<T>> Transpose<T>(this IEnumerable<IEnumerable<T>> source)
{
    if (source == null) throw new ArgumentNullException("source");
    var enumerators = source.Select(x => x.GetEnumerator()).ToArray();
    try
    {
        while (enumerators.All(x => x.MoveNext()))
        {
            yield return enumerators.Select(x => x.Current).ToArray();
        }
    }
    finally
    {
        foreach (var enumerator in enumerators)
            enumerator.Dispose();
    }
}

- Jeff Mercado

---

在我看来，这似乎很干净。据我所知，它将会被急切地执行。在我的情况下不是问题，因为我总是需要迭代所有内容。方法的实现可能难以阅读，但调用方很容易。 - Rune FS

@Rune：这个实现有什么难以阅读的地方吗？在我看来，这是一个相当简单的实现。 - Jeff Mercado

顺便提一下，第二次调用 ToArray() 可能可以被移除。如果你有许多序列需要压缩，那就更好了。 - Jeff Mercado

enumerators.All(x => x.MoveNext()) 不太符合“最少惊讶原则”，因为通常的 Linq 语句是无副作用的。 - Rune FS

实际上，您不需要任何ToArray，它可以在没有ToArray的情况下工作，如果您将除第一行之外的所有内容移动到另一个方法中，它也会像大多数Linq方法一样进行惰性评估。如果您还没有获得积分，至少记得Dispose :) - Rune FS

Answer 2

看一下这个扩展方法，在这里找到。

/// <summary>
/// Swaps the rows and columns of a nested sequence.
/// </summary>
/// <typeparam name="T">The type of elements in the sequence.</typeparam>
/// <param name="source">The source sequence.</param>
/// <returns>A sequence whose rows and columns are swapped.</returns>
public static IEnumerable<IEnumerable<T>> Transpose<T>(
         this IEnumerable<IEnumerable<T>> source)
{
    return from row in source
           from col in row.Select(
               (x, i) => new KeyValuePair<int, T>(i, x))
           group col.Value by col.Key into c
           select c as IEnumerable<T>;
}

我不确定性能如何，但代码看起来很优雅。

- Yury Tarabanko

Answer 3

根据您的问题，似乎您想要修改原始矩阵。

如果是这种情况，并且您能够将矩阵存储为 IList<IList<T>> matrix，那么这将起作用，但仅适用于方阵的情况。

for(int i = 0; i < matrix.Count; ++i)
{
    for(int j = 0; j < i; ++j)
    {
        T temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp
    }
}

- Ken Wayne VanderLinde

---

这是问题中依赖于IList<IList<T>>的特定方法版本。我正在寻找一种依赖于IEnumerable<IEnumerable<T>>的不同方法。 - Rune FS

Answer 4

这是我的基于枚举器的解决方案，试图使用 for 来提高速度，而不是使用 foreach / LINQ：

public static IEnumerable<IEnumerable<T>> Pivot<T>(this IEnumerable<IEnumerable<T>> src) {
    var enums = src.Select(ie => ie.GetEnumerator()).ToList();
    var initialMoveNext = Enumerable.Repeat(true, enums.Count).ToList();

    for (; ; ) {
        var moveNext = initialMoveNext.ToArray(); // initialize to all true
        var hasMore = false;

        for (int j1 = 0; j1 < enums.Count; ++j1)
            if (moveNext[j1]) {
                moveNext[j1] = enums[j1].MoveNext();
                hasMore = hasMore || moveNext[j1];
            }

        if (!hasMore)
            break;

        IEnumerable<T> subEnum() {
            for (int j1 = 0; j1 < enums.Count; ++j1) {
                if (moveNext[j1])
                    yield return enums[j1].Current;
            }
        }

        yield return subEnum();
    }
    
    for (int j1 = 0; j1 < enums.Count; ++j1)
        enums[j1].Dispose();
}

- NetMage

Answer 5

这是我的代码，如果有人感兴趣的话。它的执行方式与Jeff的类似，但似乎稍微快一些（假设那些ToArrays()是必要的）。没有可见的循环或临时变量，而且更加紧凑。

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    return source
        .Select(a => a.Select(b => Enumerable.Repeat(b, 1)))
        .Aggregate((a, b) => a.Zip(b, Enumerable.Concat));
}

如果你需要它也能处理空列表，那么代码就变成了这样：

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    return source
        .Select(a => a.Select(b => Enumerable.Repeat(b, 1)))
        .DefaultIfEmpty(Enumerable.Empty<IEnumerable<T>>())
        .Aggregate((a, b) => a.Zip(b, Enumerable.Concat));
}

我注意到提问者写道矩阵总是正方形的。这个实现（和Jeff的实现）将一次评估整行，但如果我们知道矩阵是正方形的，我们可以以更合适的方式重写zip函数：

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    return source
        .Select(a => a.Select(b => Enumerable.Repeat(b, 1)))
        .DefaultIfEmpty(Enumerable.Empty<IEnumerable<T>>())
        .Aggregate(Zip);
}

public static IEnumerable<IEnumerable<T>> Zip<T>(
    IEnumerable<IEnumerable<T>> first, 
    IEnumerable<IEnumerable<T>> second)
{
    var firstEnum = first.GetEnumerator();
    var secondEnum = second.GetEnumerator();

    while (firstEnum.MoveNext())
        yield return ZipHelper(firstEnum.Current, secondEnum);
}

private static IEnumerable<T> ZipHelper<T>(
    IEnumerable<T> firstEnumValue, 
    IEnumerator<IEnumerable<T>> secondEnum)
{
    foreach (var item in firstEnumValue)
        yield return item;

    secondEnum.MoveNext();

    foreach (var item in secondEnum.Current)
        yield return item;
}

这样，每个元素在返回之前都不会被评估。

- YellPika

Answer 6

嗯，你在这里寻找的是一个转换 T[][] -> T[][]。有很多IEnumerabe<IEnumerable<T>>.Transpose()的解决方案，但它们都归结为使用临时查找/键循环枚举，当处理大量数据时性能表现不佳。你的示例实际上运行得更快（虽然你也可以去掉第二个foreach）。

首先问一下“我是否需要LINQ”。你没有描述转置矩阵的目的，如果速度确实是你关心的问题，你最好远离LINQ/foreach，用老式的方式（内部for循环）来完成。

- mmix

---

不，我不“需要”Linq，这就是为什么我要求声明性解决方案而不是Linq解决方案的原因 :)。在不损害性能的情况下，有改善可读性的空间，但盲目地提高可读性可能会影响我们的性能。它处于关键路径上。 - Rune FS