python - 删除基于 python 列表中的索引的列时避免一对一错误

Question

我有一个名为 TARGFILE 的目标文件，格式为:

10001000020002002001100100200000111
10201001020000120210101100110010011
02010010200000011100012021001012021
00102000012001202100101202100111010

我的想法是将其保留为字符串，并在 python 中使用切片来删除索引。

删除将基于名为 INDICES 的整数列表进行，如下所示:

[1, 115654, 115655, 115656, 2, 4, 134765, 134766, 18, 20, 21, 23, 24, 17659, 92573, 30, 32, 88932, 33, 35, 37, 110463, 38, 18282, 46, 18458, 48, 51, 54]

我想删除 TARGFILE 中与 INDICES 匹配的 every 行的每个位置。例如，INDICES 中的第一个数字是 1，因此包含 1,1,0,0 的 TARGFILE 的第一列将被删除。但是，如果没有同时删除所有内容，我厌倦了由于差一错误和更改索引位置而错误地执行此操作。

因此，同时从每一行中删除每一列的解决方案可能比使用嵌套循环更快更安全，但我不确定如何对此进行编码。

到目前为止我的代码在这里:

#!/usr/bin/env python
import fileinput
SRC_FILES=open('YCP.txt', 'r')

for line in SRC_FILES:
    EUR_YRI_ADM=line.strip('\n')
    EUR,YRI,ADM=EUR_YRI_ADM.split(' ')
    ADMFO=open(ADM, 'r')
    lines=ADMFO.readlines()
    INDICES=[int(val) for val in lines[0].split()]
    TARGFILE=open(EUR, 'r')

在我看来，使用 enumerate 的解决方案可能是可行的，但我还没有找到它，而且这可能首先不是最优的...

编辑:为了回应对内存的担忧:最长的行大约有 180,000 个项目，但我应该能够毫无问题地将其存入内存，我可以访问一个集群。

Answer 1

我喜欢 Peter 的简单回答，尽管目前还差一个。我的想法是，您可以通过对 INDICES 进行排序并从后到前执行该过程来摆脱索引移位问题。这导致了 remove_indices1，这是非常低效的。我认为 2 更好，但最简单的是 3，这是 Peter 的答案。

我可能会为一些大数做一些计时，但我的直觉告诉我，如果 INDICES 非常稀疏，我的 remove_indices2 将比 Peter 的 remove_indices3 更快。 (因为您不必遍历每个字符，而只需遍历要删除的索引。)

顺便说一句 - 如果您可以对 INDICES 进行一次排序，那么您就不需要制作本地副本来进行排序/反转，但我不知道您是否可以这样做。

rows = [
    '0000000001111111111222222222233333333334444444444555555555566666666667',
    '1234567890123456789012345678901234567890123456789012345678901234567890',
    ]

def remove_nth_character(row,n):
    return row[:n-1] + row[n:]

def remove_indices1(row,indices):
    local_indices = indices[:]
    retval = row
    local_indices.sort()
    local_indices.reverse()
    for i in local_indices:
        retval = remove_nth_character(retval,i)
    return retval

def remove_indices2(row,indices):
    local_indices = indices[:]
    local_indices.sort()
    local_indices.reverse()
    front = row
    chunks = []
    for i in local_indices:
        chunks.insert(0,front[i:])
        front = front[:i-1]
    chunks.insert(0,front)
    return "".join(chunks)

def remove_indices3(row,indices):
    return ''.join(c for i,c in enumerate(row) if i+1 not in indices)

indices = [1,11,4,54,33,20,7]

for row in rows:
    print remove_indices1(row,indices)
print ""
for row in rows:
    print remove_indices2(row,indices)
print ""
for row in rows: 
    print remove_indices3(row,indices)

编辑:添加时间信息，以及新的获胜者!

正如我所怀疑的，当没有太多要删除的索引时，我的算法 (remove_indices2) 获胜。然而，事实证明，基于枚举的索引变得更糟甚至更快，因为要删除的索引更多。这是时间代码(bigrows 行有 210000 个字符):

bigrows = []
for row in rows:
    bigrows.append(row * 30000)

for indices_len in [10,100,1000,10000,100000]:
    print "indices len: %s" % indices_len
    indices = range(indices_len)
    #for func in [remove_indices1,remove_indices2,remove_indices3,remove_indices4]:
    for func in [remove_indices2,remove_indices4]:
        start = time.time()
        for row in bigrows:
            func(row,indices)
        print "%s: %s" % (func.__name__,(time.time() - start))

结果如下:

indices len: 10
remove_indices1: 0.0187089443207
remove_indices2: 0.00184297561646
remove_indices3: 1.40601491928
remove_indices4: 0.692481040955
indices len: 100
remove_indices1: 0.0974130630493
remove_indices2: 0.00125503540039
remove_indices3: 7.92742991447
remove_indices4: 0.679095029831
indices len: 1000
remove_indices1: 0.841033935547
remove_indices2: 0.00370812416077
remove_indices3: 73.0718669891
remove_indices4: 0.680690050125

那么，为什么 3 的表现要差这么多？好吧，事实证明 in 运算符在列表上效率不高。它必须遍历所有要检查的列表项。 remove_indices4 只是 3，但首先将索引转换为集合，因此内部循环可以进行快速哈希查找，而不是遍历列表:

def remove_indices4(row,indices):
    indices_set = set(indices)
    return ''.join(c for i,c in enumerate(row) if i+1 not in indices_set)

而且，正如我最初预期的那样，这比我的高密度算法要好:

indices len: 10
remove_indices2: 0.00230097770691
remove_indices4: 0.686790943146
indices len: 100
remove_indices2: 0.00113391876221
remove_indices4: 0.665997982025
indices len: 1000
remove_indices2: 0.00296902656555
remove_indices4: 0.700706005096
indices len: 10000
remove_indices2: 0.074893951416
remove_indices4: 0.679219007492
indices len: 100000
remove_indices2: 6.65899395943
remove_indices4: 0.701599836349

如果您要删除的索引少于 10000 个，则 2 是最快的(如果您在函数外对索引进行排序/反转，速度会更快)。但是，如果您想要时间非常稳定的东西，无论有多少索引，都使用 4。