0

我有一个大文件，表格的每一行

a b c

我想删除所有不存在另一行的行，例如

b d e

或者d a e

与abs(c - e) < 10.

a, b, c, d,e都是整数。

例如，如果输入是：

0 1 10 
1 2 20
2 3 25
0 1 15 
1 4 40

那么输出应该是

1 2 20
2 3 25
0 1 15

是否有可能在线性时间内做到这一点？

一种想法是创建两个排序列表的字典。一个用于与第一列值关联的第三列值。另一个用于与第二列值关联的第三列值。然后，当您看到 abc 时，使用第二个字典中的键 a 在排序列表中查找 c，然后使用第一个字典中的键 b 在排序列表中查找 c。

4

3 回答 3

3

我不知道这是否可以在线性时间内完成。如果输入中有 n 个三元组，那么在 O(n·log n) 时间内完成是很简单的。这是一种方法的草图，采用非必要的实现形式：

  1. 制作一组标记 M，最初全部清除。

  2. 创建一个数组并复制输入，首先按中间元素排序，然后在中间元素相等时按第三个元素排序。（到目前为止，时间是 O(n·log n)。）

  3. 对于每个不同的中间值，使用 key = 第三个元素创建一个 BST（二叉搜索树）。（时间又是 O(n·log n)。）

  4. 制作一个以中间值为键的哈希表，数据指向适当的 BST。也就是说，给定一个中间值 y 和第三个元素 z，我们可以在 O(1) 时间内得到中间值为 y 的三元组的 BST；由此，在 O(log n) 时间内可以找到第三个元素值最接近 z 的三元组。

  5. 对于每个三元组 t = (x,y,z)，如果尚未设置标记，则使用哈希表查找对应于 x 的 BST（如果有）。在那个 BST 中，找到第三个元素最接近 z 的三元组 u。如果差值小于 10，则设置 t 和 u 的标记。（时间又是 O(n·log n)。）

  6. 重复步骤 2-5，但 BST 基于第一个元素值而不是中间值，步骤 5 中的查找基于 y 而不是 x。（虽然匹配关系是对称的，所以我们可以在步骤 5 中的每个循环设置两个标记，但一些合格的三元组最终可能没有标记；即，它们在公差范围内，但比找到的最近匹配更远。可以在步骤 5 中标记所有符合条件的三元组，但这会将最坏情况的时间从 O(n·log n) 增加到 O(n²·log n)。）

  7. 对于设置的每个标记，输出相应的三元组。

总时间：O(n·log n)。无需构建 BST 而是在已排序数组的子范围内使用二进制搜索即可实现相同的时间。

编辑：在 python 中，可以构建可用于bisect的结构，如下图所示，摘自 ipython 解释器会话。（可能有更有效的方法来执行这些步骤。）字典h中的每个数据项都是一个适合使用搜索的数组bisect。

In [1]: from itertools import groupby

In [2]: a=[(0,1,10), (1,2,20), (2,3,25), (0,1,15), (1,4,40), (1,4,33), (3,3,17), (2,1,19)]

In [3]: b=sorted((e[1],e[2],i) for i,e in enumerate(a)); print b
[(1, 10, 0), (1, 15, 3), (1, 19, 7), (2, 20, 1), (3, 17, 6), (3, 25, 2), (4, 33, 5), (4, 40, 4)]

In [4]: h={k:list(g) for k,g in groupby(b,lambda x: x[0])}; h
Out[4]: 
{1: [(1, 10, 0), (1, 15, 3), (1, 19, 7)],
 2: [(2, 20, 1)],
 3: [(3, 17, 6), (3, 25, 2)],
 4: [(4, 33, 5), (4, 40, 4)]}
于 2013-07-23T16:39:35.213 回答
1

正如其他人所说，线性时间可能是不可能的。这是一个简单的 O(n^2) 实现。如果您对字典中的列表进行排序，您应该能够改进运行时。

lines = """0 1 10 
1 2 20
2 3 25
0 1 15 
1 4 40"""
Adata = {}
Bdata = {}
for line in lines.split('\n'):
    a,b,c = line.split(' ')[:3]
    vals = map(int,[a,b,c])
    if b in Adata:
        Adata[b].append(vals)
    else:
        Adata[b] = [vals]
    if a in Bdata:
        Bdata[a].append(vals)
    else:
        Bdata[a] = [vals]

def case1(a,b,c):
    if a in Adata:
        for val in Adata[a]:
            if abs(int(c)-val[2]) < 10:
                return True
    return False

def case2(a,b,c):
    if b in Bdata:
        for val in Bdata[b]:
            if abs(int(c)-val[2]) < 10:
                return True
    return False


out = []
for line in lines.split('\n'):
    a,b,c = line.split(' ')[:3]
    if case1(a,b,c) or case2(a,b,c):
        out.append(line)

for line in out:
    print line
于 2013-07-23T16:56:07.430 回答
0

我认为您正在寻找的是类似的东西

set lines
for line in infile:
  if line not in lines:
    lines.add(line)
    outfile.write(line)
于 2013-07-23T16:02:14.457 回答