13

读完这个问题后,我开始怀疑:是否有可能有一个不修改或复制原始列表的洗牌算法?

说清楚:

想象一下,给你一个对象列表。列表大小可以是任意的,但假设它非常大(例如,10,000,000 个项目)。您需要以随机顺序打印出列表中的项目,并且需要尽可能快地完成。但是,您不应该:

  • 复制原始列表,因为它非常大,复制会浪费大量内存(可能会达到可用 RAM 的限制);
  • 修改原始列表,因为它以某种方式排序,而稍后的其他部分取决于它的排序。
  • 创建一个索引列表,因为列表非常大,复制需要太多时间和内存。(澄清:这是指任何其他列表,其元素数量与原始列表相同)。

这可能吗?

补充:更多说明。

  1. 我希望列表以真正随机的方式洗牌,所有排列的可能性相同(当然,假设我们有一个适当的 Rand() 函数开始)。
  2. 建议我制作一个指针列表、索引列表或任何其他与原始列表具有相同数量元素的列表,被原始问题明确认为是低效的。如果需要,您可以创建其他列表,但它们应该比原始列表小几个数量级。
  3. 原始列表就像一个数组,您可以通过它在 O(1) 中的索引从中检索任何项目。(所以没有双向链表的东西,你必须遍历列表才能找到你想要的项目。)

补充 2:好的,让我们这样说:你有一个 1TB 的硬盘,里面装满了数据项,每个 512 字节大(一个扇区)。您想在洗牌所有项目时将所有这些数据复制到另一个 1TB 硬盘。您希望尽可能快地执行此操作(单次传递数据等)。你有 512MB 的可用 RAM,不要指望交换。(这是一个理论上的场景,我在实践中没有这样的东西。我只是想找到完美的algorithm.item。)

4

11 回答 11

13

好吧,这有点取决于您除了洗牌之外的随机性,即所有洗牌是否应该尽可能地发生,或者分布是否可以倾斜。

有一些数学方法可以产生 N 个整数的“随机”排列,所以如果 P 是从 0..N-1 到 0..N-1 的排列,您可以将 x 从 0 迭代到 N-1 并且输出列表项 L(P(x)) 而不是 L(x) 并且您已经获得了改组。可以例如使用模算术来获得这样的排列。例如,如果 N 是素数,则 P(x)=(x * k) mod N 是任何 0 < k < N 的置换(但将 0 映射到 0)。对于素数 N 类似,例如 P(x)=(x^3) mod N 应该是一个排列(但映射 0 到 0 和 1 到 1)。这个解决方案可以很容易地扩展到非素数 N,方法是选择 N 之上的最小素数(称为 M),置换到 M,并丢弃 N 之上的置换索引(类似下面)。

应该注意,模幂运算是许多密码算法(例如 RSA、Diffie-Hellman)的基础,并且被该领域的专家认为是一种强伪随机操作。

另一种简单的方法(不需要素数)是首先扩展域,以便您考虑 M 而不是 N,其中 M 是 N 之上 2 的最小幂。因此,例如,如果 N=12,则设置 M=16。然后你使用双射位操作,例如

P(x) = ((x ^ 0xf) ^ (x << 2) + 3) & 0xf

然后,当您输出列表时,您将 x 从 0 迭代到 M-1,并且仅当 P(x) 实际上 < N 时才输出 L(P(x))。

一个“真正的、无偏的随机”解决方案可以通过固定一个加密强的分组密码(例如 AES)和一个随机密钥(k)然后迭代序列来构建

AES(k, 0), AES(k, 1), ...

并从序列 iff AES(k,i) < N 中输出相应的项。这可以在恒定空间(密码所需的内部存储器)中完成,并且与随机排列无法区分(由于密码的密码学特性) ) 但显然很慢。对于 AES,您需要迭代直到 i = 2^128。

于 2009-12-08T12:42:12.200 回答
4

您不能复制、修改或跟踪您访问过的元素?我会说这是不可能的。除非我误解了你的第三个标准。

我认为这意味着您不能说,制作一个包含 10,000,000 个相应布尔值的数组,当您打印相应的元素时设置为 true。并且您不允许列出 10,000,000 个索引、打乱列表并按该顺序打印出元素。

于 2009-12-08T12:42:13.977 回答
2

这 10,000,000 个项目只是对实际项目的引用(或指针),因此您的列表不会那么大。对于所有引用 + 该列表的内部变量的大小,在 32 位架构上只有 ~40MB。如果您的物品小于参考尺寸,您只需复制整个列表。

于 2009-12-08T12:42:36.397 回答
2

使用真正的随机数生成器不可能做到这一点,因为您必须:

  • 记住已经选择了哪些数字并跳过它们(这需要 O(n) 布尔值列表,并且随着您跳过越来越多的数字,运行时间会逐渐恶化);或者
  • 在每次选择后减少池(这需要修改原始列表或单独的 O(n) 列表来修改)。

在你的问题中,这些都不是可能性,所以我不得不说“不,你不能这样做”。

在这种情况下,我倾向于使用已使用值的位掩码,但不会跳过,因为如前所述,随着使用值的累积,运行时间会变得更糟。

位掩码将大大优于 39Gb 的原始列表(1000 万位仅约 1.2M),即使它仍然是 O(n),也比您要求的要少很多数量级。

为了解决运行时问题,每次只生成一个随机数,如果相关的“已使用”位已设置,则向前扫描位掩码,直到找到设置的位。

这意味着您不会四处闲逛,急需随机数生成器为您提供一个尚未使用的数字。运行时间只会变得与扫描 1.2M 数据所花费的时间一样糟糕。

当然,这意味着在任何时候选择的特定数字都是基于已经选择的数字而倾斜的,但是,由于这些数字无论如何都是随机的,所以倾斜是随机的(如果这些数字一开始并不是真正随机的,那么倾斜就无关紧要了)。

如果您想要更多种类,您甚至可以交替搜索方向(向上或向下扫描)。

底线:我不相信你要求的东西是可行的,但请记住,我以前犯过错,因为我的妻子会迅速而频繁地证明:-) 但是,与所有事情一样,通常有办法绕过此类问题。

于 2009-12-08T13:23:55.093 回答
2

这是一个非常简单的证明,证明任何 PRNG 方案都不起作用:

PRNG 的想法有两个阶段:首先,选择一个 PRNG 及其初始状态;其次,使用 PRNG 对输出进行洗牌。嗯,有N个!可能的排列,所以你至少需要N! 不同的可能开始状态,进入第 2 阶段。这意味着在第 2 阶段开始时,您必须至少有log 2 N!状态位,这是不允许的。

然而,这并不排除算法在运行时从环境中接收新随机位的方案。例如,可能有一个 PRNG 懒惰地读取其初始状态但保证不会重复。我们能证明不存在吗?

假设我们确实有一个完美的洗牌算法。想象一下,我们开始运行它,当它运行到一半时,我们让计算机进入睡眠状态。现在程序的完整状态已经保存在某个地方。让S是程序在这个中间标记处可能处于的所有可能状态的集合。

由于算法是正确的并且保证会终止,因此有一个函数f,给定保存的程序状态加上任何足够长的位串,产生一个有效的磁盘读取和写入序列,完成 shuffle。计算机本身就实现了这个功能。但将其视为一个数学函数:

f : (S × bits) → 读写序列

然后,很简单,存在一个函数g它只给定保存的程序状态,生成一组尚未读取和写入的磁盘位置。(只需将一些任意位串传递给f,然后查看结果。)

g : S一组读写位置

证明的剩余部分是表明g的域包含至少N C N/2 个不同的集合,而不管算法的选择如何。如果这是真的,那么S的元素必须至少有那么多,因此程序的状态必须在中间标记处包含至少log 2 N C N/2位,这违反了要求。

不过,我不确定如何证明最后一点,因为要读取的位置集或写入的位置集可能是低熵的,具体取决于算法。我怀疑有一些明显的信息论原则可以解决问题。标记这个社区维基,希望有人会提供它。

于 2009-12-09T16:33:02.530 回答
1

听起来不可能。

但是 10,000,000 个 64 位指针只有大约 76MB。

于 2009-12-08T12:45:06.017 回答
1

线性反馈移位寄存器几乎可以做你想做的事——生成一个数字列表,直到某个限制,但以(合理的)随机顺序。它产生的模式在统计上与您对尝试随机性的期望相似,它甚至不接近加密安全。Berlekamp-Massey 算法允许您基于输出序列对等效 LFSR 进行逆向工程。

鉴于您需要约 10,000,000 个项目的列表,您需要一个 24 位最大长度的 LFSR,并简单地丢弃大于列表大小的输出。

就其价值而言,与同期典型的线性同余 PRNG 相比,LFSR 通常相当快。在硬件中,LFSR非常简单,由一个 N 位寄存器和 M 个 2 输入 XOR 组成(其中 M 是抽头数——有时只有几个,很少超过六个左右)。

于 2009-12-08T18:53:31.263 回答
0

如果有足够的空间,您可以将节点的指针存储在一个数组中,创建一个位图并获取指向下一个所选项目的随机整数。如果已经选择(您将其存储在位图中),则获取最接近的一个(左侧或右侧,您可以随机化),直到没有剩余项目。

如果没有足够的空间,那么你可以在不存储节点指针的情况下做同样的事情,但是时间会受到影响(这就是时空权衡☺)。

于 2009-12-08T12:46:35.717 回答
0

您可以使用分组密码创建伪随机的“安全”排列 - 请参见此处。他们的关键见解是,给定一个长度为 n 位的分组密码,您可以使用“折叠”将其缩短为 m < n 位,然后使用 antti.huima 已经提到的技巧来从中生成更小的排列,而无需花费大量时间丢弃超出范围的值。

于 2009-12-08T16:52:41.757 回答
0

本质上,您需要的是一个随机数生成器,每个生成数字 0..n-1 一次。

这是一个半生不熟的想法:您可以通过选择一个略大于 n 的素数 p,然后选择一个介于 1 和 p-1 之间的随机 x,其在乘法组 mod p 中的顺序为 p-1(选择随机 xs 和测试哪些满足 x^i != 1 for i < p-1,您只需要在找到一个之前测试一些)。由于 x 然后生成组,只需计算 1 <= i <= p-2 的 x^i mod p,这将为您提供 2 和 p-1 之间的 p-2 个不同的随机(ish)数。减去 2 并丢弃 >= n 的那些,这会为您提供一系列要打印的索引。

这不是非常随机的,但是您可以多次使用相同的技术,将上面的索引 (+1) 用作另一个生成器 x2 模另一个素数 p2 的指数(您需要 n < p2 < p) , 等等。十几次重复应该会让事情变得非常随机。

于 2009-12-10T22:36:54.580 回答
0

我的解决方案取决于一些巧妙计算的数字的数学特性

range = array size
prime = closestPrimeAfter(range)
root = closestPrimitiveRootTo(range/2)
state = root

通过这种设置,我们可以重复计算以下内容,它会以看似随机的顺序对数组的所有元素进行一次迭代,之后它将循环以再次以相同的确切顺序遍历数组。

state = (state * root) % prime

我在 Java 中实现并测试了它,所以我决定将我的代码粘贴在这里以供将来参考。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class PseudoRandomSequence {

    private long            state;
    private final long  range;
    private final long  root;
    private final long  prime;
    //Debugging counter
    private int             dropped = 0;

    public PseudoRandomSequence(int r) {
        range = r;
        prime = closestPrimeAfter(range);
        root = modPow(generator(prime), closestPrimeTo(prime / 2), prime);
        reset();
        System.out.println("-- r:" + range);
        System.out.println("   p:" + prime);
        System.out.println("   k:" + root);
        System.out.println("   s:" + state);
    }

    // https://en.wikipedia.org/wiki/Primitive_root_modulo_n
    private static long modPow(long base, long exp, long mod) {
        return BigInteger.valueOf(base).modPow(BigInteger.valueOf(exp), BigInteger.valueOf(mod)).intValue();
    }

    //http://e-maxx-eng.github.io/algebra/primitive-root.html
    private static long generator(long p) {
        ArrayList<Long> fact = new ArrayList<Long>();
        long phi = p - 1, n = phi;
        for (long i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                fact.add(i);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1) fact.add(n);
        for (long res = 2; res <= p; ++res) {
            boolean ok = true;
            for (long i = 0; i < fact.size() && ok; ++i) {
                ok &= modPow(res, phi / fact.get((int) i), p) != 1;
            }
            if (ok) {
                return res;
            }
        }
        return -1;
    }

    public long get() {
        return state - 1;
    }

    public void advance() {
        //This loop simply skips all results that overshoot the range, which should never happen if range is a prime number.
        dropped--;
        do {
            state = (state * root) % prime;
            dropped++;
        } while (state > range);
    }

    public void reset() {
        state = root;
        dropped = 0;
    }

    private static boolean isPrime(long num) {
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }

    private static long closestPrimeAfter(long n) {
        long up;
        for (up = n + 1; !isPrime(up); ++up)
            ;
        return up;
    }

    private static long closestPrimeBefore(long n) {
        long dn;
        for (dn = n - 1; !isPrime(dn); --dn)
            ;
        return dn;
    }

    private static long closestPrimeTo(long n) {
        final long dn = closestPrimeBefore(n);
        final long up = closestPrimeAfter(n);
        return (n - dn) > (up - n) ? up : dn;
    }

    private static boolean test(int r, int loops) {
        final int array[] = new int[r];
        Arrays.fill(array, 0);
        System.out.println("TESTING: array size: " + r + ", loops: " + loops + "\n");
        PseudoRandomSequence prs = new PseudoRandomSequence(r);
        final long ct = loops * r;
        //Iterate the array 'loops' times, incrementing the value for each cell for every visit. 
        for (int i = 0; i < ct; ++i) {
            prs.advance();
            final long index = prs.get();
            array[(int) index]++;
        }
        //Verify that each cell was visited exactly 'loops' times, confirming the validity of the sequence
        for (int i = 0; i < r; ++i) {
            final int c = array[i];
            if (loops != c) {
                System.err.println("ERROR: array element @" + i + " was " + c + " instead of " + loops + " as expected\n");
                return false;
            }
        }
        //TODO: Verify the "randomness" of the sequence
        System.out.println("OK:  Sequence checked out with " + prs.dropped + " drops (" + prs.dropped / loops + " per loop vs. diff " + (prs.prime - r) + ") \n");
        return true;
    }

    //Run lots of random tests
    public static void main(String[] args) {
        Random r = new Random();
        r.setSeed(1337);
        for (int i = 0; i < 100; ++i) {
            PseudoRandomSequence.test(r.nextInt(1000000) + 1, r.nextInt(9) + 1);
        }
    }

}

这是受图形宝石卷中描述的 2D 图形“溶解”效果的小型 C 实现的启发。1 这反过来是对 2D 的适应,对称为“LFSR”的机制进行了一些优化(此处为维基百科文章此处为原始溶解.c 源代码)。

于 2021-06-21T17:29:25.133 回答