python - 合并列表中相同元素的列表
问题描述
我需要对列表进行合并,并且有一个可以实现的功能,但是当合并的次数很慢而且难以忍受的时候,不知道有没有更高效的方法
合并条件:子列表编号相同 谢谢
简单关联:
[7,8,9] = [7,8]+[8,9] #The same number 8
级联包含:</p>
[1,2,3] = [1,2,3]+[3,4] #The same number 3
[3,4,5,6] = [3,4],[4,5,6] #The same number 4
[1,2,3,4,5,6] = [1,2,3]+[3,4,5,6] #The same number 3
功能:</p>
a = [ [1,2,3],[4,5,6],[3,4],[7,8],[8,9],[6,12,13] ]
b = len(a)
for i in range(b):
for j in range(b):
x = list(set(a[i]+a[j]))
y = len(a[j])+len(a[i])
if i == j or a[i] == 0 or a[j] == 0:
break
elif len(x) < y:
a[i] = x
a[j] = [0]
print a
print [i for i in a if i!= [0]]
结果:</p>
[[8, 9, 7], [1, 2, 3, 4, 5, 6, 10, 11]]
上面是一个例子,实际计算中每个子列表的长度只有2,
a = [[1,3],[5,6],[3,4],[7,8],[8,9],[12,13]]
我想错过更多数据,这是一个模拟数据。
a = np.random.rand(150,150)>0.99
a[np.tril_indices(a.shape[1], -1)] = 0
a[np.diag_indices(a.shape[1])] = 0
a = [list(x) for x in np.c_[np.where(a)]]
consolidate(a)
解决方案
我认为您的算法接近最优,除了可以缩短内循环,因为交集操作是对称的,即如果您检查(A, B)
相交,则无需检查(B, A)
. 这样你就可以从O(n²)
到O(n * (n / 2))
。
但是,我会更干净地重写这段代码,并且我也会避免修改输入。另请注意,由于set
s 不保证排序,因此在进入列表之前进行一些排序是个好主意。
这是我建议的代码(已编辑以减少铸件和分类的数量):
def consolidate(items):
items = [set(item.copy()) for item in items]
for i, x in enumerate(items):
for j, y in enumerate(items[i + 1:]):
if x & y:
items[i + j + 1] = x | y
items[i] = None
return [sorted(x) for x in items if x]
将您的代码封装在一个函数中,我会得到:
def consolidate_orig(a):
a = [x.copy() for x in a]
b = len(a)
for i in range(b):
for j in range(b):
x = list(set(a[i]+a[j]))
y = len(a[j])+len(a[i])
if i == j or a[i] == 0 or a[j] == 0:
break
elif len(x) < y:
a[i] = x
a[j] = [0]
return [i for i in a if i!= [0]]
这将允许我们做一些干净的微基准测试(为了完整性,我还包括了@zipa's merge()
):
编辑:
@zipa 的代码没有正确封装,这里是一个适当封装的等效版本:
def merge(iterable, base=None):
if base is None:
base = iterable
merged = set([tuple(set(i).union(
*[j for j in base if set(i).intersection(j)])) for i in iterable])
if merged == iterable:
return merged
else:
return merge(merged, base)
和更新的时间:
in_list = [[1,2,3], [4,5,6], [3,4], [7,8], [8,9], [6,12,13]]
%timeit consolidate_orig(in_list)
# 17.9 µs ± 368 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit consolidate(in_list)
# 6.15 µs ± 30 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit merge(in_list)
# 53.6 µs ± 718 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
in_list = [[1, 3], [5, 6], [3, 4], [7, 8], [8, 9], [12, 13]]
%timeit consolidate_orig(in_list)
# 16.1 µs ± 159 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit consolidate(in_list)
# 5.87 µs ± 71.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit merge(in_list)
# 27 µs ± 701 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
表明,至少对于这个输入,建议的解决方案始终更快。由于生成大量有意义的输入并不是很简单,因此我将让您检查这是否比您对较大输入的方法更有效。
编辑
对于更大但可能毫无意义的输入,时间安排仍然有利于提议的版本:
in_list = [[1,2,3], [4,5,6], [3,4], [7,8], [8,9], [6,12,13]] * 300
%timeit consolidate_orig(in_list)
# 1.04 s ± 14.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit consolidate(in_list)
# 724 ms ± 7.51 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit merge(in_list)
# 1.04 s ± 7.94 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
in_list = [[1, 3], [5, 6], [3, 4], [7, 8], [8, 9], [12, 13]] * 300
%timeit consolidate_orig(in_list)
# 1.03 s ± 18 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit consolidate(in_list)
# 354 ms ± 3.43 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit merge(in_list)
# 967 ms ± 16.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
推荐阅读
- python - --headless 标志在升级到 chrome 76/chromedriver 76 后不再起作用
- hibernate - H2 数据库转储
- gdb - 无法在 gdb 中使用标准库调试符号
- mod-wsgi - 获取 Python.h:在 OSX 上使用 python3 编译 mod_wsgi 时没有这样的文件或目录
- python - 将 xml 文件解析为 csv 时跳过一个空元素
- vba - 如果主题行匹配,则将电子邮件保存到文件夹
- python - 断言由 @propertyname.setter 生成的异常
- buffer - 在 WebGL 中绘制多个模型
- scala - 尽管需要方法来更新图像,但图像仍被冻结
- javascript - Vanilla WebComponents 方法:“从 html 导入 js”和“从 js 获取 html”文件之间有什么真正的区别