为List<T>内部添加一个“删除多个元素”的方法
2012-11-03 00:06 by 老赵, 9148 visits不久前我在微博上提出一个问题:众所周知,.NET中自带的List<T>
集合类型没有“删除多个元素”的方法,那么假如我们是.NET类库中List<T>
的实现者,我们该如何添加这么一个方法?例如:
namespace System.Collections.Generic { public class List<T> { private T[] _items; private int _count; public void RemoveMultiple(IEnumerable<T> itemsToRemove) { // Replace the implementation here foreach (var item in itemsToRemove) { this.Remove(item); } } } }
其中元素保存在_items
数组中,而_count
则保存当前元素的个数。我这里给出了一个实现来体现这个方法的含义,但很显然这并不是一个合适的做法。原因有几个,一会儿会提到,但最重要的自然就是效率很低。请注意这里我们是“内部实现者”,因此肯定就是要提供一个高效的,并且尽可能通用的实现。
有些同学表示如果要高效,则不应该用List<T>
这种数据结构。这个思路似乎考虑周到,但实际上很让人捉急,因为这还是种代码“消费者”的习惯,而不是代码的“提供者”。记得以前我也提出过一些简单的题目,写明“抛出异常”,但大部分答案依旧在try...catch
,我认为这是同样的原因。在我看来,假如要提高技术水平,一定要把思维观念从技术的“消费者”切换为“提供者”,因为提供者能影响更多人,会让自己对自己编写的代码要求更高。
其实这道题目没有标准答案,但是很容易判断出某一个实现好不好,对不对,有哪些缺陷等等。这题的确十分简单,但是会有不少细节方面值得考虑,所以我反复强调,光有思路是不够的,一定要写出代码来。
首先,我想代码判断了参数的合法性,也就是null
与否。其次,您觉得该如何使用itemsToRemove
比较合适?一定要从头枚举吗?这里举一个.NET中自带的例子:
namespace System.Linq { public static class Enumerable { public static int Count<TSource>(this IEnumerable<TSource> source) { checked { if (source == null) { throw new ArgumentNullException("source"); } var collection = source as ICollection<TSource>; if (collection != null) return collection.Count; var collection2 = source as ICollection; if (collection2 != null) return collection2.Count; int num = 0; foreach (var item in source) num++; return num; } } } }
可见,为了提高效率,有时候我们会考虑使用下标,而不是直接foreach
来进行计算,因为如常见的数组或是List<T>
这种枚举类型,使用下标访问的速度会比使用枚举器有一定程度的提高。另外,一般来说在使用IEnumerable
的时候切忌多次遍历。
假如我们使用最传统的foreach
配合现成的Remove
方法来实现RemoveMultiple
方法,其时间复杂度是O(M * N),其中N是目前List<T>
中的元素个数,M是itemsToRemove
中的元素数量。这种是最差的时间复杂度,原因是每删除itemsToRemove
中的一个元素,就需要从整个列表的起始位置找起。于是,有些同学想到把被删除的元素放在一个HashSet
中,这样确定单个元素是否需要删除的时间复杂度是O(1),而构建这个HashSet的时间复杂度是O(M),于是总共是O(M + N),这显然比O(M * N)要好太多。
但问题在于,HashSet
是不够的,因为集合中的元素不可重复,而itemsToRemove
中显然是可能有重复元素的,这意味着要从列表中删除多个相同的元素,这个需求也很正常,因为List<T>
中本身就有可能重复。于是一个比较容易想到的做法便是建立一个字典,保存某个元素需要被删除的次数。装配脑袋的做法便是如此:
public void RemoveMultiple(IEnumerable<T> itemsToRemove) { var removingItems = new Dictionary<T, int>(); foreach (var item in itemsToRemove) { if (removingItems.ContainsKey(item)) { removingItems[item]++; } else { removingItems[item] = 1; } } var setIndex = 0; for (var getIndex = 0; getIndex < _count; getIndex++) { var current = _items[getIndex]; if (removingItems.ContainsKey(current)) { removingItems[current]--; if (removingItems[current] == 0) { removingItems.Remove(current); } continue; } _items[setIndex++] = _items[getIndex]; } _count = setIndex; }
不过从细节上说,这个做法还是有些改进空间。例如,一次removingItems[item]++
实际上就会访问两次字典,一次取值,一次是加一后设置回去,在此之前还有个ContainsKey
判断。字典的读写操作理论上是O(1),但实际上在内部会调用每个元素的GetHashCode
方法,以及一次或多次Equals
,这对于没有重载过这两个方法的引用类型,或是int
等基础类型来说比较迅速,但假如T是一个字符串,开销还是会大上好几倍。因此,我们还是希望可以尽量少地访问字典。在我目前工作中的项目里,表示一个属性的可选方式是一个数字下标,这样很多地方就可以直接使用数组来保存与属性有关的映射关系,而不需要用PropertyInfo
甚至更慢的字符串来查找字典。
为了解决这个问题,最好是编写一个特定的数据结构——但并不“特殊”,因为这就是个典型的Bag(也称为MultiSet)),顾名思义,便是允许重复元素的集合。在一个Bag中,相同元素可以被添加或删除多次。
public void RemoveMultiple(IEnumerable<T> itemsToRemove) { var removingItems = new HashBag<T>(itemsToRemove); var setIndex = 0; for (var getIndex = 0; getIndex < _count; getIndex++) { var current = _items[getIndex]; if (removingItems.Remove(current)) continue; _items[setIndex++] = _items[getIndex]; } _count = setIndex; }
在HashBag
内部,我们每次添加和删除元素只需要访问一次代码,便可以增加或删除该元素的计数器。封装一个通用的HashBag
容器之后,连代码都变的简单很多。但是,使用基于哈希容器一般会占用相对比较大的空间,为了提高效率及节省空间,在可行的情况下,我们还可以为在创建HashBag
的时候指定尺寸,或者权衡之下选用二叉树而不是基于哈希的Bag,这样时间复杂度会变成O(log(M) * N),但空间使用可以节省许多。此外,我们还可以尝试建立一个现有元素至其下标的映射,先找出需要删除的位置,最后进行一次移动。这在不同的M和N大小关系时都是可能的选择。
但问题是,这就足够了吗?以上这段实现实际上还有错误!请注意,最后我们虽然把setIndex
赋值给_count
,但是setIndex
和旧的_count
之间的元素,我们并没有设成null
(确切地说应该是default(T)
),这就会造成内存泄露。总有同学说托管程序不会出现内存泄露,这我不同意,托管程序还是程序,并不能阻止程序员犯错误嘛。不过话又说回来,我们一定需要将那些位置设为null
吗?答案是否定的,对于像int
等基础类型来说,我们就完全无需实现这点。
不过话说回来,你会如何判断一个T是否需要设为null
?是在RemoveMultiple
内部每次判断下typeof(T)
吗?答案依旧是否定的,只需要定义一个静态成员即可。要记住,List<int>
和List<string>
是两个不同的类型,它们的静态成员是分开存放的。这有时候会带来问题,但善加利用也会收到很好的效果。
这些都是细节。
其他还有一些值得考虑的有意思的地方。例如,您的实现如果遇上list.RemoveMultiple(list)
这种用法,会出现什么样的情况?例如,itemsToRemove
的数量假如远大于当前的元素数量,其代价是否过高?例如,假如itemsToRemove
是一个无限长的枚举,但到某一个阶段却可以把所有当前元素删光,那么您的实现能否直接返回?
这些都是RemoveMultiple
方法可能会遇到的状况。我这里做出的假设是可以修改List<T>
的内部实现,因此我们甚至可以开一个新的数组赋值给_items
——假如它再某个情况下有帮助的话。当然,作为一个通用的实现的来说,一个方法应对大部分的情况就够了,我们无法顾及各种环境下的最坏情况。在实际情况下,有时候我们知道更多条件,甚至选择更合适的做法,并且使用反射从外部设置_item
及_count
。
假如我用这道题目来进行面试,以上便是我会考察的一些思路。正像我一开始说的那样,这题没有标准答案,更关键的是对于思路的考察,考察一个程序员考虑问题是否全面。我虽然列举了那么多,但肯定也有我没有想到的地方。
但是,光有思路是不够的,也一定要写出代码来。
这段话错了。前一个方法只是遍历,不需要对每一个元素进行哈希运算。后一个对每一个元素进行了哈希运行。 不是O(M+N)和O(M*N)这么简单.进行哈希运算的开销不能忽略不计,尤其是元素很多的时候。
事实上这个类似于数据库的查询优化器对于Join的三种执行计划的选择。如果你只是要删除很少的元素,你可以用第一种方法,嵌套循环(Nest Loop)。如果删除的元素数量接近被删除元素数量,则可以走Hash Join或者Merge Join。
哈希也不是没有缺点的。如果元素数量十分大。你需要占用一个很大的存储空间,如果空间过大则需要占用硬盘空间。速度呼呼地下来了。此外Merge的方法也能考虑,如果元素是已经排序好了的,用merge的方法优于哈希。