如何有效比较两个地图

Question

我需要比较2个地图，我正在寻找最好的方法。特别是，给定两个输入中的地图，我需要确定至少80％的条目是否相同。当前的方法是：

-data以键 ->的形式存储在两个文件中。

例如：

1.1.1.0/24 |178 188 198

1.1.2.0/24 |199 2212 2999 212....

在此文件中存储约60万个条目。

- 输入在地图上上传，然后进行比较。

由于大量数据，执行非常慢。（我需要多次进行这种比较）。我什至不知道地图是否是使用的最佳数据结构。考虑到2个文件中的条目数可能有所不同（第一个文件中存在的一些可能不存在于第二AMD VICE，反之亦然），文件中的条目按字母顺序排列。我正在使用python。

两种不同的方法：

1）在包含元素的集合中上传后，进行比较如下：

def checkSame(bgpt1, bgpt2):
    size1 = len(bgpt1)
    size2 = len(bgpt2)
    num_shared_ip = float(len(bgpt1 & bgpt2))
    ratio = num_shared_ip / max(size1, size2)
    return ratio

2）使用地图通过迭代进行比较：

def compareMaps(map1,map2):
    counter=0
    for keyM1 in map1:
         if keyM1 in map2:
            if map2[keyM1]==map1[keyM1]:
                counter+=1
    ...

Answer 1

由于您的文件进行排序，因此您不必将它们存储，甚至不必在线之外解析它们。您可以通过较小的当前元素来继续前进：

def count_equal(a, b):
    """
    Counts the number of values that are equal in two sorted iterables.
    >>> odds = [1, 3, 5, 7, 9, 11, 13, 15]
    >>> primes = [2, 3, 5, 7, 11, 13]
    >>> count_equal(odds, primes)
    5
    """
    return _count_equal(iter(a), iter(b))

def _count_equal(a, b):
    c = 0
    x = next(a)
    y = next(b)
    try:
        while True:
            while x < y:
                x = next(a)
            while y < x:
                y = next(b)
            if x == y:
                c += 1
                x = next(a)
                y = next(b)
    except StopIteration:
        return c

您可以在同一读取中分别跟踪每个文件中有多少行：

from __future__ import division

class CountingIterable:
    def __init__(self, iterable):
        self.iterable = iterable
    def __iter__(self):
        count = 0
        for x in self.iterable:
            yield x
            count += 1
        self.count = count

with open('file1.txt', 'r') as a, open('file2.txt', 'r') as b:
    a_counter = CountingIterable(a)
    b_counter = CountingIterable(b)
    a_iterator = iter(a_counter)
    b_iterator = iter(b_counter)
    n = count_equal(a_iterator, b_iterator)
    # consume any remaining elements to acquire count
    for _ in a_iterator: pass
    for _ in b_iterator: pass
    result = n / max(a_counter.count, b_counter.count)

Answer 2

由于您发布没有代码，所以我可以尝试提出一些想法。

也许您可以尝试合并两个文件，然后将每行与下一行进行比较（每个文件都有一个唯一的密钥）。对于每次命中，您都可以按一个更新计数器，当您最终到达文件末端时，您可以用线进行分配以获得相似性。

另一个想法是计算jaccard的相似性，但这要求每个文件具有唯一的值，并且您的数据符合内存。从两个文件中读取所有值，并创建（键：值）字符串集。（集合表示每个值的基数是一个）。然后，您可以使用此功能：

def compute_jaccard_index(set_1, set_2):
    n = len(set_1.intersection(set_2))    
    return n / float(len(set_1) + len(set_2) - n)

返回两个集合的归一化索引[0-1]。

编辑：刚刚看到了您已发布的代码。按照我建议，请尝试在元组中的jaccard索引。您也可以将jaccard索引的现成实现之一