python-3.x 记忆海量数据的出现顺序，使用列表+集合还是字典？

yshpjwxd  于 2023-08-08  发布在  Python
关注(0)|答案(3)|浏览(140)

我有数百万（毫不夸张）行数据，如下所示：

  1. sample = [
  2.     [16777216, 33554431, None, 'AU', False, False, False, False],
  3.     [16777216, 16777471, 13335, 'AU', False, True, False, False],
  4.     [16777472, 16777727, None, 'CN', False, False, False, False],
  5.     [16777728, 16778239, None, 'CN', False, False, False, False],
  6.     [16778240, 16779263, 38803, 'AU', False, False, False, False],
  7.     [16778496, 16778751, 38803, 'AU', False, False, False, False],
  8.     [16779264, 16781311, None, 'CN', False, False, False, False],
  9.     [16781312, 16785407, None, 'JP', False, False, False, False],
  10.     [16781312, 16781567, 2519, 'JP', False, False, False, False],
  11.     [16785408, 16793599, None, 'CN', False, False, False, False],
  12.     [16785408, 16785663, 141748, 'CN', False, False, False, False],
  13.     [16793600, 16809983, 18144, 'JP', False, False, False, False],
  14.     [16809984, 16842751, 23969, 'TH', False, False, False, False],
  15.     [16809984, 16826367, 23969, 'TH', False, False, False, False],
  16.     [16809984, 16818175, 23969, 'TH', False, False, False, False],
  17.     [16809984, 16810239, 23969, 'TH', False, False, False, False],
  18.     [16810240, 16810495, 23969, 'TH', False, False, False, False],
  19.     [16810496, 16811007, 23969, 'TH', False, False, False, False],
  20.     [16811008, 16811263, 23969, 'TH', False, False, False, False],
  21.     [16811264, 16811519, 23969, 'TH', False, False, False, False],
  22.     [16812032, 16812287, 23969, 'TH', False, False, False, False],
  23.     [16812288, 16812543, 23969, 'TH', False, False, False, False],
  24.     [16812544, 16812799, 23969, 'TH', False, False, False, False],
  25.     [16812800, 16813055, 23969, 'TH', False, False, False, False],
  26.     [16813312, 16813567, 23969, 'TH', False, False, False, False],
  27.     [16814080, 16818175, 23969, 'TH', False, False, False, False],
  28.     [16818176, 16826367, 23969, 'TH', False, False, False, False],
  29.     [16818176, 16819199, 23969, 'TH', False, False, False, False],
  30.     [16819200, 16819455, 23969, 'TH', False, False, False, False],
  31.     [16819456, 16819711, 23969, 'TH', False, False, False, False],
  32.     [16819712, 16819967, 23969, 'TH', False, False, False, False],
  33.     [16819968, 16820223, 23969, 'TH', False, False, False, False]
  34. ]

字符串
它们代表IPv4网络，我也有关于IPv6网络的数据。
我从一个文本文件中获取了数据，我希望将数据转换为sqlite3数据库。事实上，我已经这样做了，但数据每天更新，因为我不会进入这里的原因，我需要经常更新我的数据库了。
从示例中可以看到，只有开始和结束是唯一的，其他六个元素的组有大量的重复。以这种方式存储行是非常低效的，如果我们只存储其他元素的唯一组，并用对存储组的引用来替换行中的这些元素，通过这种方式压缩数据，我们可以保存大量的存储空间（我的数据就是这样）。
存储压缩数据的一种简单方法是将重复的元素按其出现的顺序存储在列表中，并用它们在列表中的索引替换它们在行中的位置。
基本思想很简单，从一个空列表开始，对于每一行，检查数据是否在列表中，如果不在，则将数据追加到列表中，并在追加之前将行中的数据替换为列表的长度，否则，将数据替换为列表中数据的索引。
问题是，列表成员检查使用线性搜索，这是O（n），对于大数据非常低效，我的数据真的很大，这会花费很多时间。在我的例子中，即使是二分搜索也会很慢，正如你所看到的，我不能在这里进行二分搜索。
但是集合成员检查的时间复杂度是O（1），它几乎是常数，它非常快，而且不管它包含多少元素都保持很快，所以这正是我所需要的。
其过程如下：

  1. groups = []
  2. unique_groups = set()
  3. compressed = []
  4. for row in sample:
  5.     data = tuple(row[2:])
  6.     if data in unique_groups:
  7.         compressed.append([*row[:2], groups.index(data)])
  8.     else:
  9.         unique_groups.add(data)
  10.         compressed.append([*row[:2], len(groups)])
  11.         groups.append(data)

型
这种方法的问题在于，list.index使用的是线性搜索，这对于我上面解释的目的来说是低效的，而且对于我需要存储它的两个副本的每个唯一组，它将使用所需空间的两倍。
另一种方法是使用字典，如下所示：

  1. groups = {}
  2. compressed = []
  3. for row in sample:
  4.     data = tuple(row[2:])
  5.     compressed.append([*row[:2], groups.setdefault(data, len(groups))])

型
这样会快得多，但我不知道它的空间复杂性。我听说Python dict的内存很贵，但是使用list + set的方法，每个项目都会存储两次......
可能对于少量数据，第一种方法使用的空间较少，但对于大量数据，第二种方法使用的空间较少，而我的数据非常大。我不知道它们将如何扩展，而且我还没有进行测试，仅仅加载我的数据就需要1 GB的RAM，而且我不能可靠地生成与我的数据具有相同重复级别的测试用例，因为我从来没有保存过中间阶段。
那么，哪种方法的空间复杂性更低呢？要知道，我还需要性能，因此存在一个折衷方案，如果速度更快的方法占用大约两倍的空间，但执行时间只有十分之一，这是可以接受的，但如果占用十倍的空间，那么即使是即时的，也是不可接受的（我只有16 GiB RAM，这是有限的）。

编辑

所有现有的答案都不能解决我的问题。
因为我需要先用Python处理数据。有很多包含不同数据的重叠区域、包含相同数据的重叠区域以及包含相同数据的相邻区域，我需要处理这些区域以避免重叠，数据始终来自较小的区域，我将从较大的区域中减去较小的区域，然后合并包含相同数据的相邻区域。这样就不会有歧义，数据也尽可能的小。
有关更多详细信息和代码，请参见此question。
给定上面的示例，结果将是：

  1. [(16777216, 16777471, 1),
  2.  (16777472, 16778239, 2),
  3.  (16778240, 16779263, 3),
  4.  (16779264, 16781311, 2),
  5.  (16781312, 16781567, 5),
  6.  (16781568, 16785407, 4),
  7.  (16785408, 16785663, 6),
  8.  (16785664, 16793599, 2),
  9.  (16793600, 16809983, 7),
  10.  (16809984, 16842751, 8),
  11.  (16842752, 33554431, 0)]

型
不，我敢肯定，我不能使用sqlite3来做这件事。
然后，我将在sqlite3数据库中存储两个表。
一个包含上述数据，但每隔一个数据行会递增1（sqlite3识别码是以1起始）。另附以下资料：

  1. [(None, 'AU', False, False, False, False),
  2.  (13335, 'AU', False, True, False, False),
  3.  (None, 'CN', False, False, False, False),
  4.  (38803, 'AU', False, False, False, False),
  5.  (None, 'JP', False, False, False, False),
  6.  (2519, 'JP', False, False, False, False),
  7.  (141748, 'CN', False, False, False, False),
  8.  (18144, 'JP', False, False, False, False),
  9.  (23969, 'TH', False, False, False, False)]

型
在第一个数据表中，第三个数据行是第二个数据表中实际数据的ID。
这是为了实现最大的存储效率，然后可以通过sqlite3压缩进一步补充。
但我需要这些数据。而sqlite3无法单独实现这一点。
实际上，我并不想使用sqlite3或Pandas DataFrame等，我只将数据存储在sqlite3数据库中，因为我需要在会话之间持久化数据，而任何其他序列化格式（如JSON和CSV）对此都是低效的。Pickle可以非常高效，但它不安全，也不兼容不同版本。
不，我已经在基于磁盘的数据库上对sqlite3查询的性能进行了基准测试，由于I/O延迟，按ID检索一个项的单个查询需要几毫秒才能完成，这是不可接受的。我将在程序启动时从数据库中加载所有数据。
因为根据我的基准测试，DataFrame在我的机器上也很慢。
我的目标是找到网络中任何给定的IP地址，为此我将在开始处做二分查找，并确定IP小于或等于结束处，如下所示：

  1. from bisect import bisect
  3. ASN = [
  4.     (None, 'AU', False, False, False, False),
  5.     (13335, 'AU', False, True, False, False),
  6.     (None, 'CN', False, False, False, False),
  7.     (38803, 'AU', False, False, False, False),
  8.     (None, 'JP', False, False, False, False),
  9.     (2519, 'JP', False, False, False, False),
  10.     (141748, 'CN', False, False, False, False),
  11.     (18144, 'JP', False, False, False, False),
  12.     (23969, 'TH', False, False, False, False)
  13. ]
  15. NETWORKS = [
  16.     (16777216, 16777471, 1),
  17.     (16777472, 16778239, 2),
  18.     (16778240, 16779263, 3),
  19.     (16779264, 16781311, 2),
  20.     (16781312, 16781567, 5),
  21.     (16781568, 16785407, 4),
  22.     (16785408, 16785663, 6),
  23.     (16785664, 16793599, 2),
  24.     (16793600, 16809983, 7),
  25.     (16809984, 16842751, 8),
  26.     (16842752, 33554431, 0)
  27. ]
  29. STARTS, ENDS, ASNS = zip(*NETWORKS)
  31. def get_network(ip):
  32.     index = bisect(STARTS, ip) - 1
  33.     if ip <= (end := ENDS[index]):
  34.         return [STARTS[index], end, *ASN[index]]
  35.     return None

型

如果你想了解更多细节，请参阅this。

* 更新**

我已经对对象的大小进行了基准测试，对于任意生成的数据，dict的空间复杂度更小，而dict的时间复杂度也更好。然而，观察到的一个重要事实是，基准测试报告的对象的内存使用量在数百兆字节的范围内，但我实际上并没有观察到解释器使用那么多的RAM。

  1. from itertools import product
  2. from typing import Mapping, Sequence, Set
  4. def get_size(obj: object) -> int:
  5.     size = obj.__sizeof__()
  6.     if isinstance(obj, Mapping):
  7.         size += sum(get_size(k) + get_size(v) for k, v in obj.items())
  8.     elif isinstance(obj, Sequence | Set) and not isinstance(obj, str):
  9.         size += sum(get_size(e) for e in obj)
  10.     return size
  12. def generate(a, b, mode):
  13.     gen = ((i, j, *k) for i, j in product(range(a), range(b)) for k in product((0, 1), repeat=4))
  14.     if mode:
  15.         return {k: i for i, k in enumerate(gen)}
  16.     l = list(gen)
  17.     return l, set(l)
  19. print(get_size(generate(16, 16, 0)))
  20. print(get_size(generate(16, 16, 1)))
  21. print(get_size(generate(256, 256, 0)))
  22. print(get_size(generate(256, 256, 1)))
  23. ls = list(range(32768))
  24. d = dict.fromkeys(range(32768))
  1. 2060792
  2. 1210444
  3. 528477112
  4. 314540108
  6. In [348]: %timeit ls.index(128)
  7. 1.67 µs ± 20.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
  9. In [349]: %timeit ls.index(4096)
  10. 52.2 µs ± 810 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
  12. In [350]: %timeit d[128]
  13. 48.8 ns ± 0.758 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
  15. In [351]: %timeit d[4096]
  16. 61 ns ± 0.937 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

总体而言，dict方法明显优于list + set方法。但我们能做得更好吗？

python-3.x

3条答案

按热度按时间
omqzjyyz

omqzjyyz1#

您可以通过以下方式更改数据库结构：

元数据：

  1. PK and (the six repeating columns)

字符串

数据：

  1. PK FK(PK of Metadata) and (the two main data col)

型
为了更快的执行，你可以使用pandas。
所以，首先我会将这些数据转换为DataFrame，然后我将执行以下操作。
1.创建两个DataFrame作为我们的新数据库表，即一个用于元数据，一个用于实际数据。
1.然后，您可以使用unique获取六列中的唯一一列，并将其存储在元数据DataFrame中。
1.在六列上使用groupby，并将其保存在数据DataFrame中。
1.然后，您可以使用to_sql直接将DataFrame存储在数据库中。

展开查看全部
赞(0）分享  回复(0）举报  2023-08-08
oxosxuxt

oxosxuxt2#

您没有必要在RAM中操作如此大的数据集。您可以在SQLite数据库中进行数据压缩，而不是使用Python集合和列表。
想到的数据库设计是将您的“唯一组”存储在它们自己的表中，然后从存储记录的另一个表中引用它。
大概是这样的：

  1. CREATE TABLE unique_group(
  2.     id INTEGER PRIMARY KEY,
  3.     first INTEGER,
  4.     second TEXT,
  5.     third BOOLEAN,
  6.     fourth BOOLEAN,
  7.     fifth BOOLEAN,
  8.     sixth BOOLEAN,
  9.     UNIQUE (first, second, third, fourth, fifth, sixth)
  10. );
  12. CREATE TABLE sample(
  13.     first INTEGER,
  14.     second INTEGER,
  15.     group_id INTEGER REFERENCES unique_group(id)
  16. );

字符串
在将数据插入数据库时，使用INSERT OR IGNORE INTO unique_group (...) VALUES (...)语句写入unique_group表。然后获取唯一组表中该行的id并在示例表中引用它。

展开查看全部
赞(0）分享  回复(0）举报  2023-08-08
kqlmhetl

kqlmhetl3#

首先使用类似下面的代码创建一个表

  1. CREATE TABLE sample(
  2.     id INTEGER PRIMARY KEY,
  3.     col1 INTEGER,
  4.     col2 TEXT,
  5.     col3 BOOLEAN,
  6.     col5 BOOLEAN,
  7.     col6 BOOLEAN,
  8.     col7 BOOLEAN,
  9.     col8 BOOLEAN,
  10.     UNIQUE (col3, col4, col5, col6, col7, col8)
  11. );

字符串
你可以将这个嵌套列表转换成一个pandas dataframe：

  1. df = pd.DataFrame(sample, columns=[columns you defined in the database])

型
你可以使用df.to_sql()在数据库中插入数据。
如果你不想在数据库中创建唯一的约束，但想事先删除重复的数据，你也可以在 Dataframe 中这样做。

  1. df.drop_duplicates(
  2.   subset = [columns you want to be unique together],
  3.   keep = 'last').reset_index(drop = True)

型
无论如何，我建议你将dataframe转换为parquet文件（这是非常轻的），而不是转储到一个基于文件的数据库。您可以简单地执行df.to_parquet()将其转换为 parquet 文件。

展开查看全部
赞(0）分享  回复(0）举报  2023-08-08
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com