时间戳

首页 > 解决方案 > 非常大范围内随机排列的元素索引

python - 非常大范围内随机排列的元素索引

问题描述

我正在处理一个非常大范围的值（0 到大约 10^6128），我需要一种 Python 方法来执行具有随机排列范围的双向查找。

较小数据集的示例：

import random

values = list(range(10))  # the actual range is too large to do this
random.shuffle(values)

def map_value(n):
    return values[n]

def unmap_value(n):
    return values.index(n)

我需要一种方法来实现具有上述非常大范围内的值的map_valueand方法。unmap_value

标签： python

解决方案

创建 10**6128 个值的固定排列是昂贵的 - 内存方面。

您可以即时从您的范围创建值并将它们存储在一个/两个字典中。

如果您只绘制比较少的值，则一个 dict 可能就足够了，如果您有很多值，则可能需要 2 来更快地查找。

本质上你

  • 查找一个值，如果不存在则生成一个索引，存储它并返回它
  • 查找索引，如果不存在，则生成一个值，存储并返回它

使用固定的随机种子应该导致相同的序列：

import random

class big_range():
    random.seed(42) 
    pos_value = {}
    value_pos = {}

    def map_value(self, n):
        p = big_range.value_pos.get(n)
        while p is None:
            p = random.randrange(10**6128) # works, can't use random.choice(range(10**6128))
            if p in big_range.pos_value:
                p = None
            else:
                big_range.pos_value[p]=n
                big_range.value_pos[n]=p
        return p


    def unmap_value(self, n):
        p = big_range.pos_value.get(n)
        while p is None:
            p = random.randrange(10**6128) # works, can't use random.choice(range(10**6128)) 
            if p in big_range.pos_value:
                p = None
            else:
                big_range.pos_value[n]=p
                big_range.value_pos[p]=n
        return p

br = big_range()

for i in range(10):
    print(br.map_value(i))

print(big_range.pos_value)  
print(big_range.value_pos)

输出：

Gibberisch巨大的数字......但它的工作原理。

出于查找原因，您将每个数字存储两次（一次作为 pos:number，一次作为 number:pos）。您可能想检查在内存耗尽之前可以生成多少个数字。

您只能使用一个 dict，但在这种情况下查找索引的值不是 O(1) 而是 O(n)，因为您需要遍历dict.items()查找值并返回索引。

如果您在两者之间执行其他随机操作，则重复性会中断，因为您更改了随机的“状态” - 您可能需要在类内部进行更多封装，并且可能需要random.getstate() / random.setstate()在生成新随机后存储最后一个状态。 ..

如果您查找大多数值，如果您简单地保持从 0 到 10**6128 的循环索引，则生成“不存在的值”将花费越来越长的时间......

这有点脆弱，更像是一个思想实验——我不知道为什么需要一个 10**6128 范围的数字......

推荐阅读