我的python代码花了8个多小时来迭代大数据

Question

更新:已经超过24小时了,代码还没有完成:)

我在下面有这个python代码.基本上,此代码目前仅使用1%的数据集(这就是它被称为样本的原因).它有32968行名称.我清理了标点符号并将其全部用小写字母表示.

我的问题是这段代码到目前为止已经运行了8个小时,还没有完成.因为,如上所述,我只使用1%的数据,我将需要稍后在整个数据集上再次运行此代码,这将花费100倍的时间.我不认为等待800小时是个好主意.所以对于我的问题:

有什么办法可以让它更快吗？应该了解spark或mapreduce,并尝试将这些用于此代码？

编辑:好的,我将尝试添加有关代码实际执行的更多信息.清理之前的名称示例:

import pandas as pd
import numpy as np

data = {'clean_name': ['Abbott Laboratories','Apple Computers', 'Apple, Inc.', 'Abercrombie & Fitch Co.', 'ABM Industries Incorporated', 'Ace Hardware Corporation'], 'name_group': np.zeros(6, dtype=int)}

sample = pd.DataFrame(data)
sample

Out[2]: 
                    clean_name  name_group
0          Abbott Laboratories           0
1              Apple Computers           0
2                  Apple, Inc.           0
3      Abercrombie & Fitch Co.           0
4  ABM Industries Incorporated           0
5     Ace Hardware Corporation           0

然后,我清理标点符号并将其全部用小写字母表示.基本上,我想将每个名称与下一个名称进行比较,如果相似,我会给它相同的组号.像这样的东西:

sample
Out[28]: 
                    clean_name  name_group
0          abbott laboratories           0
1              apple computers           1
2                  apple  inc            1
3      abercrombie   fitch co            0
4  abm industries incorporated           0
5     ace hardware corporation           0

下面的代码是我提出的:

i = 1
for alpha,beta in itertools.combinations(sample.clean_name, 2):
    score = fuzz.token_sort_ratio(alpha, beta)
    A = sample.loc[sample.clean_name==alpha, 'name_group'].values[0]
    B = sample.loc[sample.clean_name==beta, 'name_group'].values[0]
    if score > 60:
        if ((B != 0) & (A !=0)): continue
        if ((A == 0) & (B !=0)): A = B
        elif ((B == 0) & (A !=0)): B = A
        elif ((B == 0) & (A ==0)):
            A, B = i, i
            i += 1
        sample.loc[sample.clean_name==alpha, 'name_group'] = A
        sample.loc[sample.clean_name==beta, 'name_group'] = B

Answer 1

使用itertools.combinations32k行肯定会使代码变慢.这是一种在较小的数据集上使用numpy而不是pandas 来实现以下目标的方法:

1. 实现一个按某种条件(谓词)对公司名称进行分组的功能
2. 使功能比发布的实现更快

使用此帖子作为从不同角度攻击您的问题的方法.

特定

在这里,我们建立公司名称的小单子A,B,C和Aa:

import itertools as it
import collections as ct

import numpy as np


companies = "A B C Aa".split()

码

步骤1

首先,我们将创建一个2D数组,其中水平和垂直索引是相同的公司名称.矩阵内部将包含合并的公司名称:

# 1. Build a 2D array of joined strings
def get_2darray(seq):
    """Return a 2D array of identical axes."""
    x = np.array(seq)
    y = np.array(seq)

    xx = x[:, np.newaxis]
    yy = y[np.newaxis, :]

    return np.core.defchararray.add(xx, yy)                # ref 001

演示

arr = get_2darray(companies)
arr
# array([['AA', 'AB', 'AC', 'AAa'],
#        ['BA', 'BB', 'BC', 'BAa'],
#        ['CA', 'CB', 'CC', 'CAa'],
#        ['AaA', 'AaB', 'AaC', 'AaAa']], 
#       dtype='<U4')

第2步

其次,我们实现了一个group列举类似公司的功能.给定一个2D数组,func将使用辅助函数()将每个元素"转换"为一个组号:

# 2. Group companies by "similarity", e.g. "AB" == "BA"
def group(func, arr, pred=None, verbose=False):
    """Return an array of items enumerated by similarity."""
    if pred is None:
        # Set diagnol to zero
        pred = lambda x: len(set(x)) != len(x)

    dd = ct.defaultdict(it.count().__next__)
    dd[""] = np.nan 

    # opt_func = np.vectorize(func)                        # optional, slower
    opt_func = np.frompyfunc(func, 3, 1)                   # ref 002

    m = opt_func(arr, dd, pred)
    if verbose: print(dd)
    return m


def transform(item, lookup, pred):
    """Return a unique group number element-wise."""
    unique_idx = "".join(sorted(item.lower()))
    name_group = lookup[unique_idx]
    if pred(item):
        return 0
    else:
        return name_group

演示

groups = group(transform, arr, verbose=True)
groups
# defaultdict(<method-wrapper '__next__' of itertools.count object at 0x00000000062BE408>,
# {'': nan, 'aaa': 3, 'aac': 8, 'ab': 1, 
# 'cc': 7, 'aa': 0, 'bc': 5, 'aaaa': 9,
# 'ac': 2, 'bb': 4, 'aab': 6})

# array([[0, 1, 2, 0],
#        [1, 0, 5, 6],
#        [2, 5, 0, 8],
#        [0, 6, 8, 0]], dtype=object)

每个公司名称都使用唯一编号进行分组.

第3步

您现在可以通过切割groups数组来访问两家公司的组号:

# 3. Lookup the group number shared by companies
reversed_lookup = {v:k for k, v in enumerate(companies)}

def group_number(arr, a, b):
    """Return the name_group given company names, in 2D array `m`."""
    i, j = reversed_lookup[a], reversed_lookup[b]
    return arr[i, j]


for companies in [["B", "C"], ["A", "B"], ["C", "C"]]:
    msg = "Companies {}: group {}"
    print(msg.format(" & ".join(companies), group_number(groups, *companies)))


# Companies B & C: group 5
# Companies A & B: group 1
# Companies C & C: group 0

细节

步骤1

为何使用数组？ numpy数组允许像pandas一样快速查找.此外,我们以后可以使用在C级实现的操作来优化性能(这些是快速的).

为什么要在数组中合并公司名称？合并字符串的2D数组用于比较公司名称.这种比较方式类似于统计相关矩阵.

第2步

群体如何确定？ 公司名称被传递给特殊字典(dd),该字典仅在找到新密钥时指定递增的整数.该字典用于跟踪组,因为transform辅助函数应用于每个元素.

为什么要使用辅助函数？ 该tranform函数将数组中的每个项目转换为组号.请注意,跟踪字典(lookup)是使用谓词传入的.以下是关于这些group参数的一些注释:

• 跟踪字典的键是通过降低和排序给定字符串来完成的.此技术在内部用于将字符串与交换的公司名称等同.例如,合并公司"AB"和"BA"应属于同一组.
• 谓词由用户确定.如果没有给出谓词(pred=None),则应用默认谓词,它会天真地比较具有相同名称的字符串(特别是在诊断中).

您可能希望使用另一个谓词.例如,从默认谓词中,任何一组降低的字符串都是等效的A == Aa == AaAa(见数组的角分配给组0).这里是区分一个另一样品谓词A从Aa(分别为组0和3):

pred = lambda x: all(not(v%2) for k, v in ct.Counter(x).items())
group(transform, arr, pred)
# array([[0, 1, 2, 3],
#        [1, 0, 5, 6],
#        [2, 5, 0, 8],
#        [3, 6, 8, 0]], dtype=object)

性能如何优化？ 一些操作被矢量化以帮助使用C实现加速代码.在group函数中,numpy.frompyfun包装辅助函数.确定这种特定的"通用功能"比矢量化功能更快numpy.vectorize.另请参阅Scipy讲义,了解有关优化numpy代码的更多方法.

第3步

如何找到两家公司的团体编号？ 这只需通过从group函数中切片返回的数组来完成.group_number是一个查询数组的切片函数.由于索引现在是步骤2中的数字,我们从起始的有序序列构建一个反向字典,companies以便按公司名称查找相应的数字索引.注意,反向字典是在切片函数之外构建的,以避免在每次查询后重建字典.

性能

它有多快？ 对于<10行的简单序列,速度是亚毫秒:

%timeit group(transform, arr)
# 10000 loops, best of 3: 110 µs per loop

为了演示,让我们将这些数据扩展到大约1000行(除此之外,即使创建数据集也需要很长时间并消耗内存).

test = tuple(map(str, range(1000)))
full_arr = get_2darray(test)
print(full_arr.shape)
full_arr
# (1000, 1000)
# array([['00', '01', '02', ..., '0997', '0998', '0999'],
#        ['10', '11', '12', ..., '1997', '1998', '1999'],
#        ['20', '21', '22', ..., '2997', '2998', '2999'],
#        ..., 
#        ['9970', '9971', '9972', ..., '997997', '997998', '997999'],
#        ['9980', '9981', '9982', ..., '998997', '998998', '998999'],
#        ['9990', '9991', '9992', ..., '999997', '999998', '999999']], 
#       dtype='<U6')

%timeit group(transform, full_arr)
# 1 loop, best of 3: 5.3 s per loop

通过仅评估矩阵的一半来节省一些计算时间:

half_arr = np.triu(test)
half_arr
# array([['00', '01', '02', ..., '0997', '0998', '0999'],
#        ['', '11', '12', ..., '1997', '1998', '1999'],
#        ['', '', '22', ..., '2997', '2998', '2999'],
#        ..., 
#        ['', '', '', ..., '997997', '997998', '997999'],
#        ['', '', '', ..., '', '998998', '998999'],
#        ['', '', '', ..., '', '', '999999']], 
#       dtype='<U6')

%timeit group(transform, half_arr)
# 1 loop, best of 3: 3.61 s per loop

注意:未对32k行的数据集执行分析.

结论

在这种方法中,上述目标是通过以下方式实现的:

1. 将数据整理和评估小数据集分成步骤1和2.
2. 通过在步骤3中对最终的numpy数组进行分析.

考虑使用numpy来优化C级的比较功能.虽然这篇文章中的性能测试可能仍需要时间,但numpy为进一步优化提供了空间.此外,这个代码很可能比OP的数据集花费的时间少于8小时.需要进一步的分析来评估这种方法的复杂性.如果复杂性是合理的,则用户可以决定如何继续,例如在多个线程上进行并行处理.这些任务留给可能感兴趣的人.

参考

• 001:如何合并numpy数组中的字符串
• 002:矢量化功能