Python 3 从子列表末尾删除 None 值，或者如果子列表完全是 None 值则排除

Question

我有一个列表列表，其中一些子列表完全由 None 组成，有些子列表的末尾和字符串之间有 None。我需要做三件事:

1. 如果有的话，从子列表的末尾移除None，将中间由字符串分隔的替换为空字符串。

2. 排除完全None

的子列表

3. 用结果创建一个新的列表列表

我的尝试得到了预期的结果，但我想知道是否有更快的方法:

from itertools import islice

rows = [["row 1 index 0",None,"row 1 index 2",None,None],
        [None,"row 2 index 1",None,None,None],
        [None,None,None,None,None]]
data = []

for r in rows:
    for i,c in enumerate(reversed(r)):
        if c is not None:
            data.append(["" if x is None else
                         str(x) for x in islice(r,0,len(r)-i)])
            break
print (data)

期望的结果/输出:

[['row 1 index 0', '', 'row 1 index 2'], ['', 'row 2 index 1']]

基准(据我所知):

from itertools import islice
import time

q = ["string",None,"string",None,"string"] + [None] * 95
rows = [q.copy() for i in range(500000)]

for z in range(1,6):
    st = time.time()
    data = []
    for r in rows:
        for i,c in enumerate(reversed(r)):
            if c is not None:
                data.append(["" if x is None else
                             str(x) for x in islice(r,0,len(r)-i)])
                break
    end = time.time()
    print ("Run: " + str(z) + "| time: " + str(end-st))

结果(i5 ivybridge windows 10):

Run: 1| time: 5.787390232086182
Run: 2| time: 5.802111387252808
Run: 3| time: 5.697156190872192
Run: 4| time: 5.38789963722229
Run: 5| time: 5.739344596862793

Answer 1

长话短说

性能取决于数据的性质!请参阅以下时间安排，并倾向于您认为对您期望遇到的数据集更有效的时间安排。我提出了一个部分就地的解决方案，它现在似乎在我的测试中具有最佳性能，但希望很明显基准测试需要更多地充实以真正了解您的权衡。

首先我做了一个测试集。

In [60]: rows = [["row 1 index 0",None,"row 1 index 2",None,None],
    ...:         [None,"row 2 index 1",None,None,None],
    ...:         [None,None,None,None,None]]

In [61]: rowsbig = [r*1000 for r in rows]

In [62]: rowsbig = [list(r) for _ in range(1000) for r in rowsbig]

In [63]: sum(len(r) for r in rowsbig)
Out[63]: 15000000

现在，一个保持卫生的小 helper :

In [65]: def test_set(source=rowsbig):
     ...:     return [list(r) for r in source]
     ...:

因此，让我们将建议的三种方法包装在函数中:

In [86]: def new_to_coding(rows):
    ...:     data = []
    ...:     for r in rows:
    ...:         for i,c in enumerate(reversed(r)):
    ...:             if c is not None:
    ...:                 data.append(["" if x is None else
    ...:                          str(x) for x in islice(r,0,len(r)-i)])
    ...:                 break
    ...:     return data
    ...:

In [87]: def Bit(rows):
    ...:     data = [list(map(lambda x: '' if x is None else x, row)) for row in rows]
    ...:     data = [row[:max(i for i, e in enumerate(row, 1) if e is not '')] for row in data if set(row) != {''}]
    ...:     return data
    ...:

In [88]: def taras(rows):
    ...:     # remove lists with all Nones
    ...:     rows1 = [row for row in rows if set(row) != {None}]
    ...:     # remove trailing Nones
    ...:     rows2 = [dropwhile(lambda x: x is None, reversed(row)) for row in rows1]
    ...:     # replace None with ''
    ...:     rows3 = [list(reversed([x if x is not None else '' for x in row])) for row in rows2]
    ...:     return rows3
    ...:

并进行快速完整性检查:

In [89]: taras(test_set()) == new_to_coding(test_set())
Out[89]: True

In [90]: Bit(test_set()) == new_to_coding(test_set())
Out[90]: True

现在，一些计时设置。注意 @new_to_coding 始终使用 timeit 模块来创建基准。天真的 time.time() 方法忽略了很多微妙之处，而且更加方便!

In [91]: from timeit import timeit

In [92]: setup = "from __main__ import new_to_coding, Bit, taras, test_set; testrows = test_set()"

现在，结果:

In [93]: # using OP's method
    ...: timeit('new_to_coding(testrows)', setup, number=5)
Out[93]: 5.416837869910523

In [94]: # using `Bit`
    ...: timeit('Bit(testrows)', setup, number=5)
Out[94]: 14.52187539380975

In [95]: # using `taras`
    ...: timeit('taras(testrows)', setup, number=5)
Out[95]: 3.7361009169835597

所以，看来渐进式方法赢了!当然，数据的确切性质可能会改变这些相对时间。我怀疑“所有 None”行的比例会影响这些方法的相对性能。 警告!事实证明这是真的!查看编辑

我已经采用微优化的@taras 方法，确保所有名称都是函数的本地名称，因此没有全局查找，将 list(reversed(alist)) 替换为 alist[::-1]，并对生成器表达式进行中间转换，以便只具体化一个列表:

In [111]: def is_None(x): return x is None
     ...:
     ...: def taras_micro_op(rows, dropwhile=dropwhile, reversed=reversed, set=set, is_None=is_None):
     ...:     # remove lists with all Nones
     ...:     rows1 = (row for row in rows if set(row) != {None})
     ...:     # remove trailing Nones
     ...:     rows2 = (dropwhile(is_None, reversed(row)) for row in rows1)
     ...:     # replace None with ''
     ...:     rows3 = [[x if x is not None else '' for x in row][::-1] for row in rows2]
     ...:     return rows3
     ...:

In [112]: taras_micro_op(test_set()) == taras(test_set())
Out[112]: True

In [113]: setup = "from __main__ import taras, taras_micro_op, test_set; testrows = test_set()"

In [114]: # using `taras`
     ...: timeit('taras(testrows)', setup, number=50)
Out[114]: 35.11660181987099

In [115]: # using `taras_micro_op`
     ...: timeit('taras_micro_op(testrows)', setup, number=50)
Out[115]: 33.70030225184746

In [116]: 33.70030225184746 / 35.11660181987099
Out[116]: 0.9596686611281929

不到 5% 的改进。事实上，如果只是为了提高内存效率，我会放弃“使用默认参数内联”而只使用中间生成器表达式。

换句话说，我建议使用以下内容:

In [117]: def taras_memory_op(rows):
     ...:     # remove lists with all Nones
     ...:     rows1 = (row for row in rows if set(row) != {None})
     ...:     # remove trailing Nones
     ...:     rows2 = (dropwhile(lambda x: x is None, reversed(row)) for row in rows1)
     ...:     # replace None with ''
     ...:     rows3 = [[x if x is not None else '' for x in row][::-1] for row in rows2]
     ...:     return rows3
     ...:

In [118]: setup = "from __main__ import taras, taras_memory_op, test_set; testrows = test_set()"

In [119]: # using `taras`
     ...: timeit('taras(testrows)', setup, number=50)
Out[119]: 35.10479677491821

In [120]: # using `taras`
     ...: timeit('taras_memory_op(testrows)', setup, number=50)
Out[120]: 34.00812040804885

In [121]: 34.00812040804885/35.10479677491821
Out[121]: 0.9687599283396816

因为大多数已经很小的改进实际上都来自于使用生成器表达式!

编辑

所以，我用op提供的测试集试了一下:

In [3]: q = ["string",None,"string",None,"string"] + [None] * 95
   ...: rows = [q.copy() for i in range(500000)]
   ...:

In [4]: sum(len(r) for r in rows)
Out[4]: 50000000

请注意，在我最初的测试集中，大约有 33% 的行是“所有 None”。但是，在上面，没有行都是 None。这肯定会影响性能。

In [7]: def test_set(source=rows):
   ...:     return [list(r) for r in source]
   ...:

In [8]: setup = "from __main__ import new_to_coding, taras_memory_op, test_set; testrows = test_set()"

In [9]: # using OP's method
   ...: timeit('new_to_coding(testrows)', setup, number=5)
Out[9]: 14.014577565016225

In [10]: # using `taras`
    ...: timeit('taras_memory_op(testrows)', setup, number=5)
Out[10]: 33.28037207596935

因此，我提出了另一种解决方案。警告!以下解决方案就地改变内部列表:

In [14]: def sanitize(rows):
    ...:     result = []
    ...:     for row in rows:
    ...:         tail = True
    ...:         maxidx = len(row) - 1
    ...:         for i, item in enumerate(reversed(row)):
    ...:             if item is None:
    ...:                 if tail:
    ...:                     row.pop()
    ...:                 else:
    ...:                     row[maxidx - i] = ''
    ...:             else:
    ...:                 tail = False
    ...:         if row:
    ...:             result.append(row)
    ...:     return result
    ...:

In [15]: setup = "from __main__ import new_to_coding, taras_memory_op, sanitize, test_set; testrows = test_set()"

In [16]: # using `sanitize`
    ...: timeit('sanitize(testrows)', setup, number=5)
Out[16]: 8.261458976892754

In [17]: sanitize(test_set()) == new_to_coding(test_set())
Out[17]: True

因此，使用我最初制作的测试集:

In [18]: rows = [["row 1 index 0",None,"row 1 index 2",None,None],
    ...:         [None,"row 2 index 1",None,None,None],
    ...:         [None,None,None,None,None]]

In [19]:

In [19]: rows = [r*1000 for r in rows]

In [20]: rowsbig = [list(r) for _ in range(1000) for r in rows]

In [21]: rows = rowsbig

In [22]: del rowsbig

In [23]: def test_set(source=rows):
    ...:     return [list(r) for r in source]
    ...:

In [24]: setup = "from __main__ import new_to_coding, taras_memory_op, sanitize, test_set; testrows = test_set()"

In [25]: # using `taras`
    ...: timeit('taras_memory_op(testrows)', setup, number=10)
Out[25]: 6.563127358909696

In [26]: # using OP's method
    ...: timeit('new_to_coding(testrows)', setup, number=10)
Out[26]: 10.173962660133839

In [27]: # using `sanitize`
    ...: timeit('sanitize(testrows)', setup, number=10)
Out[27]: 6.3629974271170795