再谈谈列表元素的删除

之前(以及更早之前)都提到了列表元素的删除,也提到过几种方法,有兴趣的朋友可以去看看,其中一种个人比较倾向的写法大概是这个样子(C++):

auto iter = vec.begin();
while (iter != vec.end()) {
	if (isEven(*iter)) {
		iter = vec.erase(iter);
	}
	else {
		++iter;
	}
} 

  近几日恰巧看到了C#系统库中List<T>的RemoveAll实现,觉的实现的更好,所以想到可以就这个问题再随便写写,算做笔记吧~

  基本思路大概是这样的:由于列表元素都是顺序存放的,导致的一个常见问题就是插入或者删除元素的代价较高,列表在插入元素或者删除元素之后需要移动相关列表数据以保证数据存放的顺序性,遇到容量(Capacity)不足时,列表还需要重新申请内存,甚至于移动整个列表元素~

  所以一般情况下,如果你的业务场景需要频繁的插入或者删除元素,那么建议你使用链表等数据结构来代替列表,拿C++来说就是使用list来代替vector,不过鉴于list的访问效率不高,C++中还有一个结合了list和vector的deque,有兴趣的朋友可以看看~

  有点扯远了,我们继续来说RemoveAll的实现:对于列表结构,顺序存放这个特点是固有的,我们无法规避,但是对于删除操作,如果我们能先将需要删除的元素移动至列表尾部,然后再执行删除操作,那么就可以规避掉多余的列表元素移动!

  想法是挺好的,但是新的问题又来了:如何移动元素至列表尾部呢?对于不要求元素间顺序的列表来说,这一点是挺容易实现的,一个Swap操作即可,但是在多数情况下,我们还是希望保持列表元素间的相对顺序的,这时如果要实现移动元素至尾部的操作,那么就需要将元素后的所有列表数据统一前置,这在本质上跟直接删除元素,然后由列表自行完成数据迁移没有区别~(大多数情况下,由于列表的内部实现往往经过了很多优化,其“内部”移动数据的效率往往比“外部”来移动要高,但这是属于实现层面或者说工程层面的问题,在此我们就简单假定只要是移动数据,那么效率就是一致的,没有内部和外部之分)

  对于删除单个元素来说,上述做法确实与传统的直接删除法没有区别,但是考虑一下同时删除多个元素的情景,如果仍然沿用之前的直接删除法,那么就可能会触发多次列表元素的移动,但是如果我们首先将需要删除的多个元素统一移动至列表尾部,然后再执行清理操作,那么就可以大幅度降低列表元素的移动次数!

  OK,废话完毕,上代码~

public int RemoveAll(Predicate<T> match)
{
	// 首先检查参数合法性
	if (match == null) {
		ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
	}
	int num = 0;
	// 尝试找到第一个需要删除的元素的位置(num)
	while (num < this._size && !match(this._items[num])) {
		num++;
	}
	// 已到达列表末尾,说明不存在符合条件的元素,直接返回
	if (num >= this._size) {
		return 0;
	}
	int i = num + 1;
	while (i < this._size) {
		// 寻找下一个不需要删除的元素的位置
		while (i < this._size && match(this._items[i])) {
			i++;
		}
		// 将不需要删除的元素直接移动至目前num的位置,并递增位置索引
		if (i < this._size) {
			this._items[num++] = this._items[i++];
		}
	}
	// 清除列表末尾的数据(大小为列表大小减去当前num)
	Array.Clear(this._items, num, this._size - num);
	// 更新列表内部数据并返回
	int result = this._size - num;
	this._size = num;
	this._version++;
	return result;
}

  还是不懂?那就再看下这张示意图:

  简单分析一下时间复杂度:

  假设列表中每个元素被删除的概率为P(1/n <= P <=1)(其中n为列表大小),那么对于之前提到过的直接删除法,其平均情况下的时间复杂度为:

  T(n) = P * (n -1) + P * (n - 2) + P * (n - 3) + ... + P * 1 = P * (n^2 - n) / 2 = O(P*n^2)

  对于目前所分析的这种方法,其平均情况下的时间复杂度为:

  T(n) = O(n)

  并且在最坏情况下的复杂度依然如此~Cool!

  (PS:如果取P为1/n,即只删除一个元素的情况,那么这两种方法的时间复杂度便都是O(n),没有区别,这与我们之前的分析一致~)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

跟我学 Java 8 新特性之 Stream 流基础体验

Java8新增的功能中,要数lambda表达式和流API最为重要了.这篇文章主要介绍流API的基础,也是流API系列的第一篇文章,话不多说,直奔主题.

1263
来自专栏北京马哥教育

Python 开发者不得不知的魔术方法(Magic Method)

来源:j_hao104 my.oschina.net/jhao104/blog/779743 介绍 在Python中,所有以“__”双下划线包起来的方法,都统...

2987
来自专栏web前端教室

积累下素材,明天要讲:javascript的变量和作用域

咱们的零基础前端课程,明天就要讲到js的作用域了,今晚先提前写一写,积累下素材。 说到作用域其实就是“非全局变量”能够工作的范围了,你定义这个变量时的区域有多大...

2455
来自专栏C语言及其他语言

实例说明

上一节,我们大致总揽了一个简单C程序的框架,程序如下: #include<stdio.h> /*引入头文件*/ int main(void) /*一个简单的C程...

2868
来自专栏我的技术专栏

细说new与malloc的10点区别

1654
来自专栏开发与安全

从零开始学C++之boost库(一):详解 boost 库智能指针(scoped_ptr<T> 、shared_ptr<T> 、weak_ptr<T> 源码分析)

一、boost 智能指针 智能指针是利用RAII(Resource Acquisition Is Initialization:资源获取即初始化)来管理资源。关...

3170
来自专栏web前端教室

大白话-prototype属性

今天来聊聊javascript的prototype, ==========先说结论========= --它是什么呢? 它是一个属性。 --谁的属性? 函数的...

2189
来自专栏blackheart的专栏

[C#6] 2-nameof 运算符

0. 目录 C#6 新增特性目录 1. 老版本的代码 1 using System; 2 namespace csharp6 3 { 4 in...

2145
来自专栏小樱的经验随笔

COGS 1299. bplusa【听说比a+b还要水的大水题???】

1299. bplusa ☆   输入文件:bplusa.in   输出文件:bplusa.out 评测插件 时间限制:1 s   内存限制:128 MB ...

2828
来自专栏软件测试经验与教训

Python学习笔记(二)

2897

扫码关注云+社区

领取腾讯云代金券