Hello World
Spiga

为List<T>内部添加一个“删除多个元素”的方法

2012-11-03 00:06 by 老赵, 8726 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

假如我用这道题目来进行面试,以上便是我会考察的一些思路。正像我一开始说的那样,这题没有标准答案,更关键的是对于思路的考察,考察一个程序员考虑问题是否全面。我虽然列举了那么多,但肯定也有我没有想到的地方。

但是,光有思路是不够的,也一定要写出代码来。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

12 条回复

  1. 躺着读书
    183.12.137.*
    链接

    躺着读书 2012-11-03 09:20:49

    假如我们使用最传统的foreach配合现成的Remove方法来实现RemoveMultiple方法,其时间复杂度是O(M * N),其中N是目前List中的元素个数,M是itemsToRemove中的元素数量。这种是最差的时间复杂度,原因是每删除itemsToRemove中的一个元素,就需要从整个列表的起始位置找起。于是,有些同学想到把被删除的元素放在一个HashSet中,这样确定单个元素是否需要删除的时间复杂度是O(1),而构建这个HashSet的时间复杂度是O(M),于是总共是O(M + N),这显然比O(M * N)要好太多。

    这段话错了。前一个方法只是遍历,不需要对每一个元素进行哈希运算。后一个对每一个元素进行了哈希运行。 不是O(M+N)和O(M*N)这么简单.进行哈希运算的开销不能忽略不计,尤其是元素很多的时候。

    事实上这个类似于数据库的查询优化器对于Join的三种执行计划的选择。如果你只是要删除很少的元素,你可以用第一种方法,嵌套循环(Nest Loop)。如果删除的元素数量接近被删除元素数量,则可以走Hash Join或者Merge Join。

    哈希也不是没有缺点的。如果元素数量十分大。你需要占用一个很大的存储空间,如果空间过大则需要占用硬盘空间。速度呼呼地下来了。此外Merge的方法也能考虑,如果元素是已经排序好了的,用merge的方法优于哈希。

  2. 老赵
    admin
    链接

    老赵 2012-11-03 11:08:37

    @躺着读书

    计算哈希不也是O(1)么,这种O(1)什么的是作为近似时间复杂度来考虑,在规模不定的的时候比较保险,当然空间开销自然也是需要考虑的。假如可以保证数量很小,或者排序,自然也可以利用这些条件。

  3. 晴天猪
    117.33.164.*
    链接

    晴天猪 2012-11-03 17:34:05

    光有思路是不够的,一定要写出代码来。

  4. tokiemki
    203.69.196.*
    链接

    tokiemki 2012-11-05 16:22:25

    我的假設跟你有一些不同,我不會假設我是 .NET 的 BCL 實現者,因為這個假設對大部分的程式設計師不適用。

    我還沒聽說 .NET 的 BCL 有用開源的方式來把外部貢獻者的程式碼放進去 (有些開源專案例外,我這裡談的是 .NET 的核心類庫)

    我的假設則是把我當成某個擴充方法類庫的實現者來看這個問題。

    像這類的實現,對於效率我並不是很追求,我追求的是能不能少寫程式碼,所以通常我不會針對 List< T> 來寫,而會是針對 IList< T> 來寫這些方法。

    另外一個我會考慮的重點則是需不需要保證多線程安全。

    P.S. 我的信箱換了

  5. 老赵
    admin
    链接

    老赵 2012-11-05 18:23:42

    @tokiemki

    当然你可以有不同假设,不同的假设可能做法会有所不同。不过,这个问题也不是只有BCL的实现者才会遇到,你没有遇到过需要自己实现一个List的基本功能但有所扩充的情况吗?再不过话说回来,这个问题9成5也不需要是BCL实现者能做到。

    线程安全是另一个很大的话题了,而且改造成线程安全的百分百会降低单线程的性能,而且对于实现线程安全的数据结构难度太大了,所以一般我就会另外出一些额外的简单些的关于线程安全的题目,不跟数据结构问题放一起问。

    打个比方,最新的那个事件支持逆变的题目,我就要求线程安全了。

  6. stackoverflow
    119.255.7.*
    链接

    stackoverflow 2012-11-06 13:32:11

    这个方法的设计就比较落后吧,集合大的话内存就会多占不少,应该是两个集合做subtract比较合理。还是Java社区比较严谨

  7. tokimeki
    61.57.134.*
    链接

    tokimeki 2012-11-07 03:18:17

    我當然有自己實現過 List 的功能,而且當時我希望用一些 bool 屬性 (例如:IsFixedSize、IsReadOnly、IsSynchronized) 來控制這個 List 的行為,並使其容易被繼承、擴展。

    就像你講的,一旦你實作上考慮太多,那麼性能就不好。

    另外一個不要自己實作的關鍵點是,你實做了又如何,其他的 BCL 的物件及其成員函數不會用你的實作品呀,你只能用在自己寫的東西上。

    我不認為在微軟寫這些 BCL 的程式設計師是笨蛋,他們不把這個 List 設計成我們自己寫的這個樣子一定有他們的取捨。

    畢竟他們面對的用戶群比我更多更廣,考慮的事情一定比我更多。

  8. tokimeki
    61.57.134.*
    链接

    tokimeki 2012-11-07 03:29:41

    為了避免有人說我沒碼沒真相,我把當初的實作品貼在下面。

    實做的東西很多缺漏,不過這篇文章不是在討論我的實作如何,只是希望大家不要誤解我上面講的不要自己實作的意思。

    我指的是非到必要不要自己從頭實作,盡量利用擴充方法來擴充原本 BCL 已有的東西。

    [Serializable]
    public class ListBase<T> : IList<T>, IList {
        public int Capacity {
            get {
                if (IsSynchronized) {
                    lock (SyncRoot) {
                        return ((List<T>)_items).Capacity;
                    }
                }
    
                return ((List<T>)_items).Capacity;
            }
            set {
                if (IsFixedSize || IsReadOnly) {
                    return;
                }
    
                if (IsSynchronized) {
                    lock (SyncRoot) {
                        ((List<T>)_items).Capacity = value;
                    }
                }
    
                ((List<T>)_items).Capacity = value;
            }
        }
    
        public int Count {
            get {
                if (IsSynchronized) {
                    lock (SyncRoot) {
                        return _items.Count;
                    }
                }
    
                return _items.Count;
            }
        }
    
        #region IsFixedSize
    
        private volatile bool _isFixedSize;
    
        public bool IsFixedSize {
            get { return _isFixedSize; }
            set { _isFixedSize = value; }
        }
    
        #endregion
    
        #region IsReadOnly
    
        private volatile bool _isReadOnly;
    
        public bool IsReadOnly {
            get { return _isReadOnly; }
            set { _isReadOnly = value; }
        }
    
        #endregion
    
        #region IsSynchronized
    
        private volatile bool _isSynchronized;
    
        public bool IsSynchronized {
            get { return _isSynchronized; }
            set { _isSynchronized = value; }
        }
    
        #endregion
    
        #region Item
    
        public T this[int index] {
            get {
                if (_isSynchronized) {
                    lock (_syncRoot) {
                        return _items[index];
                    }
                }
    
                return _items[index];
            }
            set {
                if (_isFixedSize || _isReadOnly) {
                    return;
                }
    
                if (_isSynchronized) {
                    lock (_syncRoot) {
                        SetItem(index, value);
                    }
                } else {
                    SetItem(index, value);
                }
            }
        }
    
        object IList.this[int index] {
            get { return _items[index]; }
            set { this[index] = (T)value; }
        }
    
        #endregion
    
        #region Items
    
        private volatile IList<T> _items = new List<T>();
    
        public IList<T> Items {
            get { return _items; }
        }
    
        #endregion
    
        #region SyncRoot
    
        private volatile object _syncRoot;
    
        public object SyncRoot {
            get { return _syncRoot; }
            private set { _syncRoot = value; }
        }
    
        #endregion
    
        #region Constructor
    
        public ListBase(int capacity = 0, object syncRoot = null) {
            if (0 < capacity) {
                ((List<T>)_items).Capacity = capacity;
            }
    
            SyncRoot = syncRoot ?? new object();
        }
    
        public ListBase(IEnumerable<T> list, object syncRoot = null) : this(0, syncRoot) {
            if (null != list) {
                _items = new List<T>(list);
            }
        }
    
        public ListBase(IEnumerable list, object syncRoot = null) : this(0, syncRoot) {
            if (null != list) {
                _items = new List<T>((IEnumerable<T>)list);
            }
        }
    
        #endregion
    
        #region DoAction
    
        //protected void DoAction(Action action) {
        //  if (_synchronized) {
        //    lock (_syncRoot) {
        //      action();
        //    }
        //  } else {
        //    action();
        //  }
    
        //}
    
        #endregion
    
        #region Add
    
        protected virtual void AddItem(T item) {
            _items.Add(item);
        }
    
        public void Add(T item) {
            if (_isFixedSize || _isReadOnly) {
                throw new NotSupportedException();
                //return;
            }
    
            //Expression action = () => AddItem(item);
    
            if (_isSynchronized) {
                lock (_syncRoot) {
                    AddItem(item);
                }
            } else {
                AddItem(item);
            }
        }
    
        int IList.Add(object item) {
            var result = -1;
    
            if (_isFixedSize || _isReadOnly) {
                return result;
            }
    
            if (_isSynchronized) {
                lock (_syncRoot) {
                    AddItem((T)item);
                    result = _items.Count - 1;
                }
            } else {
                AddItem((T)item);
                result = _items.Count - 1;
            }
    
            return result;
        }
    
        #endregion
    
        #region Clear
    
        protected virtual void ClearItems() {
            if (_isFixedSize) {
                var value = default(T);
    
                for (var index = 0; index < _items.Count; index++) {
                    _items[index] = value;
                }
            } else {
                _items.Clear();
            }
        }
    
        public void Clear() {
            if (_isReadOnly) {
                return;
            }
    
            if (_isSynchronized) {
                lock (_syncRoot) {
                    ClearItems();
                }
            } else {
                ClearItems();
            }
        }
    
        #endregion
    
        #region Contains
    
        protected virtual bool ContainsItem(T item) {
            return _items.Contains(item);
        }
    
        public bool Contains(T item) {
            if (_isSynchronized) {
                lock (_syncRoot) {
                    return ContainsItem(item);
                }
            }
    
            return ContainsItem(item);
        }
    
        bool IList.Contains(object item) {
            return Contains((T)item);
        }
    
        #endregion
    
        #region CopyTo
    
        protected virtual void CopyToArray(T[] array, int arrayIndex) {
            _items.CopyTo(array, arrayIndex);
        }
    
        public void CopyTo(T[] array, int arrayIndex) {
            if (_isSynchronized) {
                lock (_syncRoot) {
                    CopyToArray(array, arrayIndex);
                }
            } else {
                CopyToArray(array, arrayIndex);
            }
        }
    
        void ICollection.CopyTo(Array array, int arrayIndex) {
            CopyTo((T[])array, arrayIndex);
        }
    
        #endregion
    
        #region GetEnumerator
    
        protected virtual IEnumerator<T> ItemsEnumerator() {
            return _items.GetEnumerator();
        }
    
        public IEnumerator<T> GetEnumerator() {
            if (_isSynchronized) {
                lock (_syncRoot) {
                    return ItemsEnumerator();
                }
            }
    
            return ItemsEnumerator();
        }
    
        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
    
        #endregion
    
        #region IndexOf
    
        protected virtual int IndexOfItem(T item) {
            return _items.IndexOf(item);
        }
    
        public int IndexOf(T item) {
            if (_isSynchronized) {
                lock (_syncRoot) {
                    return IndexOfItem(item);
                }
            }
    
            return IndexOfItem(item);
        }
    
        int IList.IndexOf(object item) {
            return IndexOf((T)item);
        }
    
        #endregion
    
        #region Insert
    
        protected virtual void InsertItem(int index, T item) {
            _items.Insert(index, item);
        }
    
        public void Insert(int index, T item) {
            if (_isFixedSize || _isReadOnly) {
                return;
            }
    
            if (_isSynchronized) {
                lock (_syncRoot) {
                    InsertItem(index, item);
                }
            } else {
                InsertItem(index, item);
            }
        }
    
        void IList.Insert(int index, object item) {
            Insert(index, (T)item);
        }
    
        #endregion
    
        #region Remove
    
        protected virtual bool RemoveItem(T item) {
            return _items.Remove(item);
        }
    
        public bool Remove(T item) {
            if (_isFixedSize || _isReadOnly) {
                return false;
            }
    
            if (_isSynchronized) {
                lock (_syncRoot) {
                    return RemoveItem(item);
                }
            }
    
            return RemoveItem(item);
        }
    
        void IList.Remove(object item) {
            Remove((T)item);
        }
    
        #endregion
    
        #region RemoveAt
    
        protected virtual void RemoveAtIndex(int index) {
            _items.RemoveAt(index);
        }
    
        public void RemoveAt(int index) {
            if (_isFixedSize || _isReadOnly) {
                return;
            }
    
            if (_isSynchronized) {
                lock (_syncRoot) {
                    RemoveAtIndex(index);
                }
            } else {
                RemoveAtIndex(index);
            }
        }
    
        #endregion
    
        protected virtual void SetItem(int index, T item) {
            if ((0 > index) || (_items.Count <= index)) {
                return;
            }
    
            _items[index] = item;
        }
    }
    
  9. tokimeki
    61.57.134.*
    链接

    tokimeki 2012-11-07 03:37:29

    @stackoverflow

    你提的那連結我進去看了,實際上像一些假設元素較多 (n > 100) 的容器物件,一般在底層都會用樹的結構來取代陣列。

    相關的實作品你可以找一下 CLR via C# 作者的網站,他有寫了一些很不錯的實作,刪除元素就相當於移除節點,然後再把樹平衡。

  10. 老赵
    admin
    链接

    老赵 2012-11-07 11:32:57

    @tokimeki

    PowerCollections的确是BCL的一个补充,文章里说的HashBag就可以用PowerCollections里的,还有一个不错的是C5。

    简单回应一句你说的“因为自己写的只能自己用,别人不能用,所以不建议自己写”:我不喜欢这种思路,我写不写是看这个投入对当前项目来说值不值得,值得我就写,不值得就不写。至于这段代码能不能被更多人使用,这个我基本不考虑。BCL做的List当然可以直接用,但你也说了,他要应付的是绝大部分的普通情况。假如目前的需求正好没法最好的满足我的需求,我针对自己情况自己写一个也没说就不行,我不直接用他们的不代表我当他们是傻子。

    再进一步,很显然现在这个问题是在做“练习”,你扯的有点远了。这个问题就此打住吧,其实意思都挺明白了。

  11. 老赵
    admin
    链接

    老赵 2012-11-07 11:34:41

    @stackoverflow

    好像谁不知道Set这个东西一样。

    说到底你还是“使用者”思维,不是“提供者”思维,让你在有限的条件下提供个最优解就难过了。仔细读读文章,有几句话就是为你写的。

    还有这都能扯到Java社区,故意找茬,是来讨骂的吗?

  12. 链接

    子龙 2012-11-28 23:25:55

    赵老师,把无用的元素设成default(T)那段,加静态字段的方法,想了好长时间也没想出来code该长什么样的,能稍微写一下吗? 另外我去看List RemoveAll(..)方法的代码,什么也不判断,直接用的Array.Clear(..)方法。仔细想来一下,这可能是最好的方式了

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我