python - 如何实现有效的算法来计算大型数据集的多个不同值？

问题描述

我试图找到一种最快的方法来计算一个巨大的表中的许多唯一值，其中行数很容易在 1 亿到 100 亿之间。在这种特殊情况下，我正在处理 128 位整数。

我试图理解，为什么 pandas 方法能取得更好的结果（用 100 万行测试），因为它似乎在列级别进行操作，感觉效率低下。这应该如何在 C++ 中实现？我最初创建 c++ 版本的尝试非常慢（比 Python 慢）。我使用了 std:set、std:pair 和 std:map。

第一次尝试如下所示：

import time
from collections import defaultdict as ddict
import pandas as pd

df = pd.DataFrame([])  # Load table with two columns containing 128 bit integers.

class Timer:
    def __enter__(self):
        self.start = time.time()
        return self

    def __exit__(self, *args):
        self.end = time.time()
        self.interval = self.end - self.start
        print("time elapsed:" ,self.interval)


with Timer():
    print(df['left'].nunique())
    print(df['right'].nunique())
    left_grp = df.groupby('left')
    print(left_grp['right'].nunique().max())
    right_grp = df.groupby('right')
    print(right_grp['left'].nunique().max())

下面是纯 Python 示例，它逐行处理数组，据我了解，这应该更有效。它仅比 pandas 版本慢 3 倍。

with Timer():
    uniques1 = set()
    uniques2 = set()

    uniques3 = ddict(set)
    uniques4 = ddict(set)

    for i in range(len(ndarray)):
        uniques1.add(ndarray[i]['left'])
        uniques2.add(ndarray[i]['right'])
        uniques3[ndarray[i]['left']].add(ndarray[i]['right'])
        uniques4[ndarray[i]['right']].add(ndarray[i]['left'])

    print(len(uniques1))
    print(len(uniques2))
    print(max(len(v) for v in uniques3.values()))
    print(max(len(v) for v in uniques4.values()))

关于如何在 C++ 中有效地实现上述纯 Python 代码的任何建议？我在下面尝试使用 c++。

#include <stdint.h>
#include <map>
#include <bits/stdc++.h>
#include <algorithm>

typedef std::pair<uint64_t, uint64_t> uint128_t;
typedef std::set<uint128_t> set128_t;
typedef std::map<uint128_t, set128_t > map128_t;


namespace nunique_highperf{
    int get_max(const map128_t& map) {
        int best = 0;
        auto it = map.begin();

        while (it != map.end()) {
            best = std::max(best, (int)it->second.size());
            it++;
        }

        return best;
    }

    void default_update(map128_t &map, uint128_t left, uint128_t right) {
        set128_t temp;
        map.emplace(left, temp);
        temp = map[left];
        temp.insert(right);
        map[left] = temp;
    }

    void uniques_from_table(uint64_t **sessions, int rows) {
        set128_t uniques1;
        set128_t uniques2;
        map128_t uniques3;
        map128_t uniques4;

        for (int i=0; i<rows; i++) {
            uint128_t left = std::make_pair(sessions[i][0], sessions[i][1]);
            uint128_t right = std::make_pair(sessions[i][2], sessions[i][3]);

            uniques1.insert(left);
            uniques2.insert(right);

            default_update(uniques3, left, right);
            default_update(uniques4, right, left);
        }

        printf("%d\n", uniques1.size());
        printf("%d\n", uniques2.size());
        printf("%d\n", get_max(uniques3));
        printf("%d\n", get_max(uniques4));
    }
}

在实际实现中，将有多个列（而不是示例中的 2 个），从中计算唯一元素的数量，因此我不只是要求最快的方法来计算单个列的不同值，而是在多个列以及列对。

编辑：添加了 c++ 代码

标签： pythonc++pandasperformance

void default_update(map128_t &map, uint128_t left, uint128_t right) { set128_t temp; auto temp_pair = map.emplace(left, temp); temp_pair.first->second.insert(right); }

python - 如何实现有效的算法来计算大型数据集的多个不同值？

问题描述

解决方案

推荐阅读