为IEnumerable<T>添加RemoveAll<IEnumerable&

作者:编程技术

小编先把装有的代码贴出来,然后一点一点的教师,不至于片面包车型大巴头晕

分分快三计划 1

         3卡塔 尔(阿拉伯语:قطر‎,尽管该key值和输入的"a"字符不均等况兼对应的next值为-1,则申明Set<T>不带有字符“a”。

到此为至,大家并不曾找到真正的急速的方法。‘办法’嘛,总是想靠人想的,不能够说,就那样算了吧?

和率先种方式相比,消耗的时光并不曾太大巩固,差不离等同,唉,真是令人悲从当中来。

 

下边我们商讨过 IEnumerable<T>.RemoveAll<IEnumerable<T>>(IEnumerable<T> Items)方法

为了在进更一步的压实下质量,大名鼎鼎,hashcode为标志贰个数码的'目的',若是大家能够看清hashcode是还是不是等于,可能能够压实一点属性,如若看见字典的源码,很四人会火速想起,是何等协会了三个像样Set<T>的'数据组'。

     d,在bucket[2]存储0。

 DateTime now = DateTime.Now;

            /**注册这里ToList()主要是让查询真正的执行,不然,只是生成语句
            var r = (from item in source
                     where !remove.Contains(item)
                     select item).ToList();
            **/
            var r = source.Where(item => !remove.Contains(item)).ToList();

            Console.WriteLine("RemoveAll Running time:"   (DateTime.Now - now).TotalSeconds);
            Console.ReadKey();

Add(20,”20″)

想来想去,仍然把它改成扩充格局吗,不然有人会问作者,怎样改?

透过下边包车型大巴解析,产生了众多项NULL的盈余项,假如只要能够自动扩大大小,那就更加好但是了。

分分快三计划 2

咱们删除成分时,通过叁回碰上,并且沿着链表寻觅3次,找到key为4的因素所在的职分,删除当前元素。而且把FreeList的职位指向当前剔除成分之处

    b,早先化Set<T>内部数组容器:buckets int[]和slots<TElement>[],分别分配长度7;

 

Add(11,”11″)

 

 

地方是四个暗指图,A B C D E 作为Key 此中Value值匀为1。

 当数组相当不够时进行扩大体量(在时下的底子上*2的矮小质数( 1卡塔 尔(英语:State of Qatar)卡塔尔,然后开展重新hashcode碰撞产生链表关系:

 for (int index = 0; index < source.Count; index  )
            {
                var item = source.ElementAt(i);
                if (remove.Contains(item))
                {
                    source.Remove(item);
                }
            }

3.Result IEnumerable Items:F  G  H

 public Set(IEqualityComparer<TElement> comparer)
        {
            if (comparer == null)
            {
                comparer = EqualityComparer<TElement>.Default;
            }
            this.comparer = comparer;
            this.slots = new Slot<TElement>[7];
            this.buckets = new int[7];
            this.freeList = -1;
        }

 

 

 

     b,然后与bucket数主管度(7卡塔 尔(英语:State of Qatar)进行取模总计,假诺结果为:2

大家看出,Dictionary在构造的时候做了以下几件事:

 

Add(19,”19″)

此次,哈哈,既然仅仅只用了0.016001...s,上边多少个例子用了16s 相差太大了,足足加强了1000倍之多,果然接纳字典格局,品质上来了,那样的代码,放在项目工夫备实际意义!

     c,因为a是首先次写入,则自动将a的值赋值到slots[0]的key,同理将"abc"赋值给slots[0].value,将方面b步骤的哈希值赋值给slots[0].hashCode,

作者们抬高18,让HashCode再一次冲击到巴克ets中下标为4的槽上,此时新成分加多到count 1的职分,而且巴克et槽指向新因素,新成分的Next指向slots中下标为1的因素。当时您会发觉持有hashcode相近的要素都形成了一个链表,纵然成分碰撞次数越来越多,链表越长。所开支的年华也相对很多。

var r = source.Iterator(remove, null);

一些图纸仿效自网络,哈哈,然后重画,写小说真心不易于,太耗费时间间,那时四个钟头已过去。

 

View Code

所耗时Running time:0.0112076..s 

可能本人说的有一点点抽像,就像下边那样

分分快三计划 3

1.Source IEnumerable Items:A  B  C  D  A  E  F  G  H

要驾驭字典是通过Key找寻键值的,速度远远超越foreach 遍历List强的多。

这时候,想起了链表情势的东西。

 

 private void Resize()
        {
            int num = (this.count * 2)   1;
            int[] numArray = new int[num];
            Slot<TElement>[] destinationArray = new Slot<TElement>[num];
            Array.Copy(this.slots, 0, destinationArray, 0, this.count);
            for (int i = 0; i < this.count; i  )
            {
                int index = destinationArray[i].hashCode % num;
                destinationArray[i].next = numArray[index] - 1;
                numArray[index] = i   1;
            }
            this.buckets = numArray;
            this.slots = destinationArray;
        }

 

上边的代码,大家为了让调用方便,故去增加IEnumerable<T>,上边我们来测验下看看时间有未有增高多少?

下边大家一步一步讲讲笔者遇到的涉世分享给我们。

 

    DateTime now = DateTime.Now;
            Set<string> iteratorVariable = new Set<string>(null);
            foreach (var local in remove)
            {
                iteratorVariable.Add(local);
            }
            foreach (var local in source)
            {
                if (!iteratorVariable.Add(local))
                {
                    continue;
                }
            }
            Console.WriteLine("Running time:"   (DateTime.Now - now).TotalSeconds);
            Console.ReadKey();

参照他事他说加以考查资料

 

  1. MSDN, IEquatable<T>, ;

  2. MSDN IEqualityComparer, ;

3.MSDN IEqualityComparer,

4.Enumerable.Except<TSource> Method(IEnumerable<TSource>, IEnumerable<TSource>),

 

作者:谷歌's(谷歌's博客园)
出处: 款待转发,但别的转发必得保留完好文章,在首要地点显得签名以致原著链接。如您有任何疑问依旧授权方面的说道,请给自个儿留言。

其实留心分析下边代码依然有毛病的

从时间耗费来讲,二种办法时间消耗大致千篇生机勃勃律 O(M*N);

当然,我们摸拟的多寡也许太过火庞大,但必须要承叁个从客观事实,那几个办法成效不是太好!

最终自个儿想说的大器晚成件事,在个方式别的等同于Except<IEnumerable<T>>(),在Linq .net 3.5 微软已经给大家兑现。

2.Remove IEnumerable Items:A  B  C  D  A  E

    a,调用Set暗中同意无参构造函数。

View Code

好吧,那样做,指标是达到规定的标准了,然而,接下去的测量检验,令人纠心。

第3行是最后删除结果的数目

分分快三计划 4

分分快三计划 5

 

测量试验结果所消耗时间是 RemoveAll Running time:16.1175443s

 

先是,我们协会一个:

 

试想下,假使大家以后有五个‘特殊字典’,特殊在,我们增多相通的key的时候,重回的是false,而只有不重复的项才方可成功的丰硕跻身,那样大家所得的‘数组’正是大家想要的。

新建三个Source IEnumerable 随机爆发10万条数据 和Remove IEnumerable 随机产生1万条数据

第1行是原来的IEnumerable数据

 

 

Remove(4)

分分快三计划 6分分快三计划 7

Set<TSource> iteratorVariable = new Set<TSource>(NULL);

那儿您会意识FreeList指向了三个链表,链表里面不包括其余因素,FreeCount表示不带有成分的链表的尺寸。

价值评估见到上边的代码,能晕倒一大片,哈哈~晕倒笔者不肩负哦。

 

         1卡塔 尔(阿拉伯语:قطر‎,若是该key值和输入的的“a”字符相通,则附和的value值正是急需找出的值。

明显,字典Key 是天下第一的,如若大家把Remove IEnumverable Items 放入字典Dictionary<Remove Items>里,用一个Foreach遍历所用场,在时刻上反对上理应是O(N),然后再对Source IEnumberable Items遍历比较Dictionary<Remove Items>IEnumverable Items ,假诺两岸是均等的项那么continue for遍历,不然,把遍历到的Source IEnumberable Items 项存入三个数组里,那么那个数组里,就是大家供给的Result IEnumberable items结果项了。这一个措施有一些像‘装脑袋’。哈哈~,不要喜欢的太早,由于Remove IEnumverable Items 是允许有再度的项,那么放在字典里,不是有一点扯了吗?不用怕,看来,大家一向玩字典得换个法子,把字典的Key放入Remove Item,把Value存入多个流速计值作为标计,以此借使存在多项重复的重置value=1,不另行现身的项一向赋值1。仔仔思考,方法有效。

3.Result IEnumerable Items:F  G  H

   b,依据上一步骤结果,找到buckets数组索引为2上的值,若是该值为0.

       slots[0].next 赋值为-1,hashCode赋值b步骤总括出来的哈希值。

 

     IEnumerable<string> dd = source.RemoveAll(remove);

   c, 找到到slots数组上索引为0的key,

通过以上,我们得以窥见Set<T>在累积,删除成分遵照如下方法进行:

大器晚成,实例化二个Set<string> iteratorVariable = new Set<string>(null);

 

独自依然一句话,达成了上述同样的点子!

这时,大家来会见linq to object 看看。

三,通过key获取相应的value,  var v=Set["a"];

 

若是如下的数额:

实则咱们稳重的解析下代码 m => remove.Contains(m) 本来依旧生龙活虎种遍历,外层又生龙活虎层遍历。再重临过看看Linq To Object 实际上也是变相的双层遍历

1.Source IEnumerable Items:A  B  C  D  A  E  F  G  H

Add(18,”18″)

请不要骂小编,刚先河作者也不驾驭那一个办法,写着写着想起来了。微软的上进,正悄悄的把大家省了广大事。然后,依附微软的主意开展校勘而来。

View Code

 List<string> source = new List<string>();
            List<string> remove = new List<string>();

            int i = 0;
            Random rad = new Random();

            while (i < 100000)
            {
                source.Add(rad.Next(Int32.MaxValue).ToString());
                i  ;
            }

            i = 0;

            while (i < 10000)
            {
                remove.Add(rad.Next(Int32.MaxValue).ToString());
                i  ;
            }

            DateTime now = DateTime.Now;
            source.RemoveAll(m => remove.Contains(m));
            Console.WriteLine("RemoveAll Running time:"   (DateTime.Now - now).TotalSeconds);

2.Remove IEnumerable Items:A  B  C  D  A  E

分分快三计划 8

下边大家来分析部分法规,然后再回眸上面的代码,就很清淅了,必竟写代码是创建在风流罗曼蒂克种思虑幼功上而来的嘛!

费话非常的少说,直接上来测量试验下,看看哪些。

到现在结束,大家再回过头来,看看代码,作者想一触即溃!不清楚的请多多思虑,不要老问!

里头yield iteratorVariable1 发生的便是大家想要的‘数组’,这里只所以那么威猛,归功于Set<TSource>

分分快三计划 9分分快三计划 10

准确,非常多技师想必和自家同样,大相当多会这么做

从下边数据,我们解析下怎么样急速的得到第3行数据吧?记得,一定要‘高效’,失去高效的主意,我觉着不是本节斟酌的内容,因为还未有其余意义,当然,高效是绝没有错,不是说,前几日讲的措施是最便捷的,最少很便捷,恩~ 请不要骂本身,确实是费话!

  1. 起初化贰个this.buckets = new int[7]
  2. 开头化四个this.slots= new slots<T>[7]
  3. count=0和freeList=-1
  4. comparer = EqualityComparer<TElement>.Default 作为比较三个T是还是不是等于的相比较器
    public static IEnumerable<TSource> Iterator<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
        {
            Set<TSource> iteratorVariable = new Set<TSource>(comparer);
            foreach (TSource local in second)
            {
                iteratorVariable.Add(local);
            }
            foreach (TSource iteratorVariable1 in first)
            {
                if (!iteratorVariable.Add(iteratorVariable1))//这儿是过滤性添加,如果添加失败,说明此项已添加 return false
                {
                    continue;
                }
                yield return iteratorVariable1;//yield语句为我们有机会创造枚举数组
            }
        }

 

增加项时候的改造

         2) ,假诺该key值和输入的"a"字符不平等,表明爆发了碰撞,这个时候获取相应的next值,依据next值定位buckets数组(buckets[next]卡塔尔,然后拿走对应buckets上囤积的值在一向到slots数组上,......,一向到找到截止。

剔除项时的浮动:

分分快三计划 11

笔者们看出,A重复了两遍,那么在字典里value 标计匀重新苏醒设置为1,B现身了二次,标计为1,那样做不是为蛇画足吗?

Remove(18)

Set<T>构造器:Slots

  1. 通过Hash算法来冲击到指定的Bucket上,碰撞到同一个Bucket槽上有着数据变成叁个单链表
  2. 暗中同意情形slots槽中的数据依照加多顺序排列
  3. 除去的数额会产生一个FreeList的链表,增加数码的时候,优先向FreeList链表中添增添少,FreeList为空则根据count依次排列
  4. 字典查询及其的频率决意于碰撞的次数,那也疏解了怎么Set<T>的查找会非常的慢。

措施十分轻巧吗,其实我们第豆蔻梢头想使用字典的Key 快捷合营,至于值就没那么重大了。

上述代码消耗的光阴是 Remove Running time:16.6678431s

于是遭受这种情景,测量检验结果证明,消耗的时候太长,大家一贯等不起,而且放在程序里正是叁个炸弹。

多年来写代码,境遇三个难题,微软基于List<T>自带的不二等秘书籍是public bool Remove(T item);,但是一时候我们或然会用到诸如RemoveAll<IEnumerable<T>>的方式,坦白的说,正是传播的参数是三个IEnumerable<T>,并非八个T,这种情状是随即可能用到的。当然大家会自由的意识List<T>里作者就封装了一个方法public int RemoveAll(Predicate<T> match),不过前面大家的测查验质量量上的话,真不敢恭维。被逼无耐,只好想方法封装贰个IEnumerable<T>扩充方法。可是此时毫不要忘了写那篇文章的主题,封装的目标,正是‘质量’必定要好!

测量检验结果所消耗费时间间是 RemoveAll Running time:16.1112403s

 

去除Key为18的要素,仍旧通过一次碰上,而且沿着链表寻觅2次,找到当前因素,删除当前因素,并且让FreeList指向当前元素,当前成分的Next指向上三个FreeList成分。

 

代码如下:相当粗略,仅需风流倜傥行:

分分快三计划 12

到那边,一声不响的你早就学会了后生可畏种‘算法’。即使微软提供了小编们现有的方法,也不足为奇!必竟理念的提练是大家最终的指标!

依据Hash算法: 4.GetHashCode()%7= 4,因此碰撞到buckets中下标为4的槽上,那个时候出于Count为0,因而成分放在slots中第0个元素上,加多后Count变为1

   a, 先总计"a"的哈希值,要是结果为2,

 

好了,大家依据地点的思路写出方法:

分分快三计划 13分分快三计划 14

简轻巧单来说正是此中间有八个数组:buckets数组和slots数组,slots有一个next用来效仿链表,该字段存款和储蓄八个int值,指向下三个存款和储蓄地点(实际正是bukets数组的目录卡塔尔,当未有爆发冲击时,该字段为-1,发生了磕碰则存款和储蓄二个int值,该值指向bukets数组.

再度测验下看下结果(那么些措施自己用扩充方法,没事的相爱的人能够自已写下,代码在上边已经贴出,这里关键看的比较直观些卡塔 尔(阿拉伯语:قطر‎

看见没,与地点的例子品质上偏离十分小。不过也远远超过了前方多少个例子。何况也是自行扩大容积的,引进了hashcode碰撞,这是大器晚成种沉凝,相当多.net字典也是基于这种规律完成的。没事的校友能够看看.net 相关源码。

 

二,向Set<T>增加一个值,Set.add("a","abc");

Add(4,”4″)后:

字典的目录时间上是O(1),遍历source时间是O(M) 总结时间理论上应该上O(M N)并非O(M*N)。

  internal class Set<TElement>
    {

        private IEqualityComparer<TElement> comparer;
        private int count;
        private int freeList;
        private Slot<TElement>[] slots;
        private int[] buckets;

        public Set()
            : this(null)
        { }

        public Set(IEqualityComparer<TElement> comparer)
        {
            if (comparer == null)
            {
                comparer = EqualityComparer<TElement>.Default;
            }
            this.comparer = comparer;
            this.slots = new Slot<TElement>[7];
            this.buckets = new int[7];
            this.freeList = -1;
        }


        private bool Find(TElement value, bool add)
        {
            int hashCode = this.InternalGetHashCode(value);
            for (int i = this.buckets[hashCode % this.buckets.Length] - 1; i >= 0; i = this.slots[i].next)
            {
                if ((this.slots[i].hashCode == hashCode) && this.comparer.Equals(this.slots[i].value, value))
                {
                    return true;
                }
            }
            if (add)
            {
                int freeList;
                if (this.freeList >= 0)
                {
                    freeList = this.freeList;
                    this.freeList = this.slots[freeList].next;
                }
                else
                {
                    if (this.count == this.slots.Length)
                    {
                        this.Resize();
                    }
                    freeList = this.count;
                    this.count  ;
                }
                int index = hashCode % this.buckets.Length;
                this.slots[freeList].hashCode = hashCode;
                this.slots[freeList].value = value;
                this.slots[freeList].next = this.buckets[index] - 1;
                this.buckets[index] = freeList   1;
            }
            return false;
        }

        private void Resize()
        {
            int num = (this.count * 2)   1;
            int[] numArray = new int[num];
            Slot<TElement>[] destinationArray = new Slot<TElement>[num];
            Array.Copy(this.slots, 0, destinationArray, 0, this.count);
            for (int i = 0; i < this.count; i  )
            {
                int index = destinationArray[i].hashCode % num;
                destinationArray[i].next = numArray[index] - 1;
                numArray[index] = i   1;
            }
            this.buckets = numArray;
            this.slots = destinationArray;
        }

        public bool Add(TElement value)
        {
            return !this.Find(value, true);
        }

        internal int InternalGetHashCode(TElement value)
        {
            if (value != null)
            {
                return (this.comparer.GetHashCode(value));
            }
            return 0;
        }
    }

    internal struct Slot<TElement>
    {
        internal int hashCode;
        internal TElement value;
        internal int next;
    }

T[] _items = new T[_count]; //此间只是回顾的叁次性定义了三个_count大小的数组,这样的多寡远远大于真正使用的数组

     a,总结"a"的哈希值,

再增加一个要素,此时出于FreeList链表不为空,因而字典会预先增添到FreeList链表所指向之处,增加后,FreeList链表长度变为1

 

基于Hash算法 11.GetHashCode()%7=4,由此再一次冲击到Buckets中下标为4的槽上,由于此槽上的值已经不为-1,这个时候Count=1,因而把那些新加的成分放到slots中下标为1的数组中,而且让Buckets槽指向下标为1的slots中,下标为1的slots之下下标为0的slots。

再也添法郎素19,当时Hash碰撞到此外叁个槽上,不过成分照旧增进到count 1的地点。

分分快三计划 15

  public static IEnumerable<T> RemoveAll<T>(this IEnumerable<T> source, IEnumerable<T> items)
        {
            var removingItemsDictionary = new Dictionary<T, int>();
            var _count = source.Count();
            T[] _items = new T[_count];
            int j = 0;
            foreach (var item in items)
            {
                if (!removingItemsDictionary.ContainsKey(item))
                {
                    removingItemsDictionary[item] = 1;
                }
            }
            for (var i = 0; i < _count; i  )
            {
                var current = source.ElementAt(i);
                if (!removingItemsDictionary.ContainsKey(current))
                {
                    _items[j  ] = current;
                }
            }
            return _items;
        }

第2行是要刨除(remove)的多寡

 

笔者们来摸拟下数据

  List<string> source = new List<string>();
            List<string> remove = new List<string>();

            int i = 0;
            Random rad = new Random();

            while (i < 100000)
            {
                source.Add(rad.Next(Int32.MaxValue).ToString());
                i  ;
            }

            i = 0;

            while (i < 10000)
            {
                remove.Add(rad.Next(Int32.MaxValue).ToString());
                i  ;
            }

            DateTime now = DateTime.Now;
            for (int index = 0; index < source.Count; index  )
            {
                var item = source.ElementAt(i);
                if (remove.Contains(item))
                {
                    source.Remove(item);
                }
            }

            Console.WriteLine("Remove Running time:"   (DateTime.Now - now).TotalSeconds);
            Console.ReadKey();

仔仔思考,List<T> 在遍历上,是超慢的,而利用诸如字典Dictionary<T> 查找有个别键(Key)值(Value),品质是十分迅猛的,因为它是根据'索引'(上边会详细的认证卡塔 尔(英语:State of Qatar)的,理论上讲在时间花销是O(1)。即然那样,大家回过头来再看看我们的事例

View Code

分分快三计划 16分分快三计划 17

 

本文由分分快三计划发布,转载请注明来源

关键词: 分分快三计划