将一个列表拆分成大小为N的较小列表

327

我正试图将一个列表分成一系列更小的列表。

我的问题: 我的分割列表函数没有将它们分成正确大小的列表。它应该将它们分成大小为30的列表,但实际上它将它们分成了大小为114的列表?

我如何使我的函数将一个列表分成X个大小为 30或更少 的列表?

public static List<List<float[]>> splitList(List <float[]> locations, int nSize=30) 
{       
    List<List<float[]>> list = new List<List<float[]>>();

    for (int i=(int)(Math.Ceiling((decimal)(locations.Count/nSize))); i>=0; i--) {
        List <float[]> subLocat = new List <float[]>(locations); 

        if (subLocat.Count >= ((i*nSize)+nSize))
            subLocat.RemoveRange(i*nSize, nSize);
        else subLocat.RemoveRange(i*nSize, subLocat.Count-(i*nSize));

        Debug.Log ("Index: "+i.ToString()+", Size: "+subLocat.Count.ToString());
        list.Add (subLocat);
    }

    return list;
}

如果我在一个大小为144的列表上使用该函数,则输出结果为:

索引:4,大小:120
索引:3,大小:114
索引:2,大小:114
索引:1,大小:114
索引:0,大小:114


1
如果LINQ解决方案可行,这个问题可能会有所帮助 - user1479055
具体来说,参考之前那个问题中Sam Saffron的回答。除非这是为了学校作业,否则我建议直接使用他的代码并停止继续寻找。 - jcolebrand
21个回答

552

我建议使用这个扩展方法按指定的块大小将源列表分成子列表:

/// <summary>
/// Helper methods for the lists.
/// </summary>
public static class ListExtensions
{
    public static List<List<T>> ChunkBy<T>(this List<T> source, int chunkSize) 
    {
        return source
            .Select((x, i) => new { Index = i, Value = x })
            .GroupBy(x => x.Index / chunkSize)
            .Select(x => x.Select(v => v.Value).ToList())
            .ToList();
    }
}
例如,如果您将包含18个项目的列表按照每个块5个项目进行分块,它将为您提供4个子列表,其中包含以下项目:5-5-5-3。 注意:在即将推出的.NET 6中,LINQ的改进将使分块变得更加容易,就像下面这样:upcoming improvements to LINQ in .NET 6
const int PAGE_SIZE = 5;

IEnumerable<Movie[]> chunks = movies.Chunk(PAGE_SIZE);

38
在将此用于生产之前,请确保您了解内存和性能的运行时影响。仅仅因为LINQ可以简洁,这并不意味着它是一个好主意。 - Nick
6
@Nick,我建议通常在做任何事情之前先考虑一下。使用LINQ进行分块操作不应该经常重复执行数千次。通常,您需要对列表进行分块以便按批和/或并行处理项目。 - Dmitry Pavlov
14
我认为内存和性能在这里不应该是一个大问题。我碰巧有一个将超过 200,000 条记录的列表拆分成每个约 3000 条的较小列表的要求,这使我来到了这个帖子,并且我测试了两种方法,发现运行时间几乎相同。之后,我测试了将该列表拆分为每个列表仅包含3条记录,仍然性能良好。尽管如此,我认为Serj-Tm的解决方案更加直观易懂,并且具有更好的可维护性。 - Silent Sojourner
3
@IarekKovtunenko 嗯,由于有海量的记录,你肯定需要调整算法以满足你的具体需求。我建议使用流处理逻辑和缓冲区来实现,将记录分成两个步骤:1) 获取第一个部分 - 任意合理数量的记录(例如10K),2) 对每个部分内的记录再进行分块。不要用显微镜去钉钉子 - 要使用适合这项任务的正确工具 ;) - Dmitry Pavlov
7
@DmitryPavlov 在这整段时间里,我从未知道在 select 语句中可以像这样投射索引!直到我注意到你在2014年发帖时才意识到,真的让我很惊讶!感谢你的分享。另外,将此扩展方法应用于 IEnumerable 并返回 IEnumerable 是否更好呢? - Aydin
显示剩余6条评论

385
public static List<List<float[]>> SplitList(List<float[]> locations, int nSize=30)  
{        
    var list = new List<List<float[]>>(); 

    for (int i = 0; i < locations.Count; i += nSize) 
    { 
        list.Add(locations.GetRange(i, Math.Min(nSize, locations.Count - i))); 
    } 

    return list; 
} 

通用版本:

public static IEnumerable<List<T>> SplitList<T>(List<T> locations, int nSize=30)  
{        
    for (int i = 0; i < locations.Count; i += nSize) 
    { 
        yield return locations.GetRange(i, Math.Min(nSize, locations.Count - i)); 
    }  
} 

2
@MatthewPigram测试过并且有效。Math.Min函数取最小值,因此如果最后一个块的大小小于nSize(2 < 3),它会创建一个包含剩余项的列表。 - Phate01
1
@HaraldCoppoolse,OP并没有要求选择,只是要拆分列表。 - Phate01
我在想,是否最好将 locations.count 赋值给一个变量,这样就不需要一遍又一遍地重新计算了。还是说这对你来说已经优化了? - Jorn.Beyers
2
@Jorn.Beyers 这可能属于微优化的范畴。只有当它成为问题时才是问题。Microsoft表示.Count是一个O(1)操作,因此我怀疑通过将其存储在变量中来获得任何改进:https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.count?view=netcore-3.1 - user1666620
我认为应该是 "i <= locations.Count",否则它会跳过最后一个数字/对象。 - user2404597
显示剩余5条评论

67

.NET 6更新

var originalList = new List<int>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

// split into arrays of no more than three
IEnumerable<int[]> chunks = originalList.Chunk(3);

在 .NET 6 之前

public static IEnumerable<IEnumerable<T>> SplitIntoSets<T>
    (this IEnumerable<T> source, int itemsPerSet) 
{
    var sourceList = source as List<T> ?? source.ToList();
    for (var index = 0; index < sourceList.Count; index += itemsPerSet)
    {
        yield return sourceList.Skip(index).Take(itemsPerSet);
    }
}

1
这是一个时间复杂度为O(n)的绝佳答案。 - Lee Z

57

这样怎么样:

while(locations.Any())
{    
    list.Add(locations.Take(nSize).ToList());
    locations= locations.Skip(nSize).ToList();
}

这会消耗大量的内存吗?每次发生 locations.Skip.ToList,我都会想知道是否分配了更多的内存,并且未跳过的项目被新列表引用。 - Zasz
3
每次循环都会创建一个新的列表,这确实会消耗内存。但是,如果您遇到了内存问题,这不是优化的地方,因为在下一次循环中,这些列表的实例已经准备好被收集了。您可以通过跳过 ToList 来在性能和内存之间进行权衡,但我不会费心尝试优化它——它非常微不足道,并且不太可能成为瓶颈。此实现的主要优点在于其简单易懂。如果您愿意,可以使用已接受的答案,它不会创建这些列表,但会更加复杂一些。 - Rafal
2
.Skip(n) 每次被调用时都会遍历 n 个元素,虽然这可能没问题,但在对性能至关重要的代码中考虑这一点很重要。https://dev59.com/qWIj5IYBdhLWcg3wrG4q - Chakrava
@Chakrava 当然,我的解决方案不适用于性能关键代码,但根据我的经验,你首先编写可工作的代码,然后确定什么是性能关键点,很少会在我的对象操作中使用50个对象。这应该根据具体情况进行评估。 - Rafal
@Rafal 我同意,我在公司的代码库中发现了许多.Skip(),虽然它们可能不是“最优”的,但它们完全可以胜任。像数据库操作这样的事情本来就需要更长时间。但我认为重要的是要注意.Skip()在其路径上“触及”每个小于n的元素,而不是直接跳转到第n个元素(就像你可能期望的那样)。如果您的迭代器从触摸元素中具有副作用,.Skip()可能会导致难以找到的错误。 - Chakrava

51

MoreLinq 有一个叫做Batch的方法

List<int> ids = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; // 10 elements
int counter = 1;
foreach(var batch in ids.Batch(2))
{
    foreach(var eachId in batch)
    {
        Console.WriteLine("Batch: {0}, Id: {1}", counter, eachId);
    }
    counter++;
}

结果是

Batch: 1, Id: 1
Batch: 1, Id: 2
Batch: 2, Id: 3
Batch: 2, Id: 4
Batch: 3, Id: 5
Batch: 3, Id: 6
Batch: 4, Id: 7
Batch: 4, Id: 8
Batch: 5, Id: 9
Batch: 5, Id: 0

ids 被拆分成 5 个块,每个块有 2 个元素。


2
这应该成为被采纳的答案。或者至少在这个页面上排名更高。 - Zar Shardan
同意,我来这里就是因为我知道会有一个 MoreLinq 的答案。 - Marc Bernier
这实际上是最好的答案。 - Ayo Adesina

15

Serj-Tm的解决方案很好,同时这是针对列表的通用版本作为扩展方法(将其放入静态类中):

public static List<List<T>> Split<T>(this List<T> items, int sliceSize = 30)
{
    List<List<T>> list = new List<List<T>>();
    for (int i = 0; i < items.Count; i += sliceSize)
        list.Add(items.GetRange(i, Math.Min(sliceSize, items.Count - i)));
    return list;
} 

13

我认为被采纳的答案(Serj-Tm)最为稳健,但我想提供一个通用版本。

public static List<List<T>> splitList<T>(List<T> locations, int nSize = 30)
{
    var list = new List<List<T>>();

    for (int i = 0; i < locations.Count; i += nSize)
    {
        list.Add(locations.GetRange(i, Math.Min(nSize, locations.Count - i)));
    }

    return list;
}

10

在mhand非常有用的评论后添加

原始回答

虽然大多数解决方案可能都能工作,但我认为它们并不是非常有效。假设您只想要前几个块中的前几个项。那么您就不希望遍历您序列中的所有(很多)项。

以下代码最多会枚举两次:一次是取值时,一次是跳过时。它不会枚举超过您将使用的任何元素:

public static IEnumerable<IEnumerable<TSource>> ChunkBy<TSource>
    (this IEnumerable<TSource> source, int chunkSize)
{
    while (source.Any())                     // while there are elements left
    {   // still something to chunk:
        yield return source.Take(chunkSize); // return a chunk of chunkSize
        source = source.Skip(chunkSize);     // skip the returned chunk
    }
}

这个枚举器将枚举序列多少次?

假设你将源代码分成chunkSize大小的块。你只会枚举前N个块。从每个被枚举的块中,你只会枚举前M个元素。

While(source.Any())
{
     ...
}

Any会获取Enumerator,执行1次MoveNext()并在释放Enumerator后返回返回值。这将重复进行N次

yield return source.Take(chunkSize);

根据参考源代码,这将执行类似以下的操作:
public static IEnumerable<TSource> Take<TSource>(this IEnumerable<TSource> source, int count)
{
    return TakeIterator<TSource>(source, count);
}

static IEnumerable<TSource> TakeIterator<TSource>(IEnumerable<TSource> source, int count)
{
    foreach (TSource element in source)
    {
        yield return element;
        if (--count == 0) break;
    }
}

在开始枚举获取的块之前,这并没有太大作用。如果您获取了多个块,但决定不枚举第一个块,则foreach不会执行,正如您的调试器将向您显示的那样。

如果您决定取第一个块的前M个元素,那么yield return 就会被执行恰好M次。这意味着:

  • 获取枚举器
  • 调用 MoveNext() 和 Current M 次。
  • 释放枚举器。

在第一个块已经被 yield 返回后,我们跳过这个第一个块:

source = source.Skip(chunkSize);

再次查看参考源代码,找出skipiterator

static IEnumerable<TSource> SkipIterator<TSource>(IEnumerable<TSource> source, int count)
{
    using (IEnumerator<TSource> e = source.GetEnumerator()) 
    {
        while (count > 0 && e.MoveNext()) count--;
        if (count <= 0) 
        {
            while (e.MoveNext()) yield return e.Current;
        }
    }
}

正如您所看到的,SkipIterator 对于 Chunk 中的每个元素都调用了一次 MoveNext() ,但没有调用 Current
因此对于每个 Chunk,我们可以看到以下操作:
- Any(): GetEnumerator;1 次 MoveNext();Dispose Enumerator - Take(): - 如果 Chunk 的内容未被枚举,则不执行任何操作。 - 如果 Chunk 内容被枚举:GetEnumerator(),针对每个枚举项执行一次 MoveNext 和一次 Current,然后 Dispose enumerator。 - Skip():对于每个已枚举的 Chunk(而不是每个 Chunk 的内容): - GetEnumerator(); - MoveNext() chunkSize 次,没有 Current! - Dispose enumerator 如果您查看枚举器运行的情况,就会发现有很多次调用 MoveNext(),而只有在您要访问 TSource 项时才会调用 Current
如果您取 N 个大小为 chunkSize 的 Chunk,则需要调用 MoveNext() 次数如下:
- 对于 Any(),需要调用 N 次; - 对于 Take(),只要您不枚举 Chunk,就不需要调用任何次数; - 对于 Skip(),需要调用 N × chunkSize 次。
如果您决定只枚举每个获取的 Chunk 的前 M 个元素,则需要针对每个枚举的 Chunk 调用 M 次 MoveNext。
总的来说,
MoveNext calls: N + N*M + N*chunkSize
Current calls: N*M; (only the items you really access)

所以,如果您决定枚举所有块的所有元素:

MoveNext: numberOfChunks + all elements + all elements = about twice the sequence
Current: every item is accessed exactly once

MoveNext的工作量与源序列的类型有关。对于列表和数组,只需简单的索引增加,可能需要检查是否超出范围。

但是,如果你的IEnumerable是数据库查询的结果,请确保数据真正实现在你的电脑上,否则数据将被多次获取。DbContext和Dapper会在访问之前正确传输数据到本地进程。如果你多次枚举相同的序列,则不会多次获取数据。Dapper返回的对象是List,DbContext记住了数据已经被获取。

在开始分割项目之前,调用AsEnumerable()或ToLists()是否明智取决于您的存储库。


这样不会每个批次都枚举两次吗?所以我们实际上要枚举源 2*chunkSize 次?这对于可枚举对象的来源来说是致命的(例如基于数据库或其他非记忆化的来源)。想象一下,将这个可枚举对象作为输入 Enumerable.Range(0, 10000).Select(i => DateTime.UtcNow) -- 每次枚举可枚举对象时,你会得到不同的时间,因为它没有被记忆化。 - mhand
考虑以下代码:Enumerable.Range(0, 10).Select(i => DateTime.UtcNow)。如果每次调用Any,都会重新计算当前时间。对于DateTime.UtcNow来说还好,但是考虑一个由数据库连接/SQL游标或类似设施支持的可枚举对象。我曾经看到过这样的情况,因为开发人员没有理解“可枚举对象的多次枚举”可能带来的影响而导致发出了成千上万个数据库调用 - ReSharper也为此提供了提示。 - mhand

9

虽然上面的答案很好,但是它们在处理无限序列(或非常长的序列)时都失败了。下面是一种完全在线实现,它保证了最佳的时间和内存复杂度。我们仅对源枚举进行一次迭代,并使用yield return 进行惰性评估。消费者可以在每次迭代中丢弃列表,从而使内存占用量等于具有 batchSize 元素的列表。

public static IEnumerable<List<T>> BatchBy<T>(this IEnumerable<T> enumerable, int batchSize)
{
    using (var enumerator = enumerable.GetEnumerator())
    {
        List<T> list = null;
        while (enumerator.MoveNext())
        {
            if (list == null)
            {
                list = new List<T> {enumerator.Current};
            }
            else if (list.Count < batchSize)
            {
                list.Add(enumerator.Current);
            }
            else
            {
                yield return list;
                list = new List<T> {enumerator.Current};
            }
        }

        if (list?.Count > 0)
        {
            yield return list;
        }
    }
}

编辑:刚刚意识到OP问的是如何将List<T>分成更小的List<T>,所以我的评论关于无限枚举对OP不适用,但可能有助于其他人。 这些评论是针对其他已发布的解决方案而言的,它们使用IEnumerable<T>作为其函数的输入,但多次枚举源枚举。


我认为 IEnumerable<IEnumerable<T>> 版本更好,因为它不涉及太多的 List 构造。 - NetMage
@NetMage - IEnumerable<IEnumerable<T>> 的一个问题是其实现可能依赖于完全枚举每个内部可枚举项。我相信可以以避免该问题的方式表达解决方案,但我认为生成的代码很快就会变得复杂。此外,由于它是惰性的,我们一次只生成一个列表,并且由于我们提前知道大小,因此仅在每个列表上进行一次内存分配。 - mhand
你说得对 - 我的实现使用了一种新类型的枚举器(位置枚举器),它跟踪你当前的位置,包装了一个标准枚举器并允许你移动到一个新的位置。 - NetMage

8

我有一个通用的方法,可以接受包括浮点型在内的任何类型,并且已经通过了单元测试,希望它能够帮到你:

    /// <summary>
    /// Breaks the list into groups with each group containing no more than the specified group size
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="values">The values.</param>
    /// <param name="groupSize">Size of the group.</param>
    /// <returns></returns>
    public static List<List<T>> SplitList<T>(IEnumerable<T> values, int groupSize, int? maxCount = null)
    {
        List<List<T>> result = new List<List<T>>();
        // Quick and special scenario
        if (values.Count() <= groupSize)
        {
            result.Add(values.ToList());
        }
        else
        {
            List<T> valueList = values.ToList();
            int startIndex = 0;
            int count = valueList.Count;
            int elementCount = 0;

            while (startIndex < count && (!maxCount.HasValue || (maxCount.HasValue && startIndex < maxCount)))
            {
                elementCount = (startIndex + groupSize > count) ? count - startIndex : groupSize;
                result.Add(valueList.GetRange(startIndex, elementCount));
                startIndex += elementCount;
            }
        }


        return result;
    }

谢谢。不知道您是否可以更新注释,加入maxCount参数的定义?这是一种安全措施吗? - Andrew Jens
2
在枚举可枚举对象时要小心。values.Count() 会导致完整的枚举,然后 values.ToList() 又会再次枚举。更安全的做法是使用 values = values.ToList(),这样它就已经被实例化了。 - mhand

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接