2

我正在从exercism.io做一个练习，我必须在其中为机器人生成随机名称。在我完成这个测试之前，我能够通过大部分测试：

[Fact]
public void Robot_names_are_unique()
{
    var names = new HashSet<string>();
    for (int i = 0; i < 10_000; i++) {
        var robot = new Robot();
        Assert.True(names.Add(robot.Name));
    }
}

经过一番谷歌搜索，我偶然发现了几个解决方案，并发现了 Fisher-Yates 算法。我试图将它实现到我自己的解决方案中，但不幸的是，我无法通过最终测试，我很困惑。如果有人能指出我正确的方向，我将不胜感激。我的代码如下：

编辑：我忘了提到字符串的格式必须遵循：@"^[AZ]{2}\d{3}$"

public class Robot
{
string _name;
Random r = new Random();
string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string nums = "0123456789";

public Robot()
{
    _name = letter() + num();
}

public string Name
{
    get { return _name; }
}

private string letter() => GetString(2 ,alpha.ToCharArray(), r);

private string num() => GetString(3, nums.ToCharArray(), r);

public void Reset() => _name = letter() + num();

public string GetString(int length,char[] chars, Random rnd)
{
    Shuffle(chars, rnd);
    return new string(chars, 0, length);
}

public void Shuffle(char[] _alpha, Random r)
{


    for(int i = _alpha.Length - 1; i > 1; i--)
    {
        int j = r.Next(i);
        char temp = _alpha[i];
        _alpha[i] = _alpha[j];
        _alpha[j] = temp;
    }

}

}
4

4 回答 4

2

任何 ID 的第一条规则是：

它有多大，有多少可能的价值并不重要——如果你创造了足够多的价值，你最终会发生冲突。

引用 Hithchikers Guide 中的 Trillian 的话：“[A colission] 并非不可能。只是真的，真的不太可能。”

但是在这种情况下，我认为是您在循环中创建随机实例。这是使用 Random 时的经典初学者错误。您不应该为每个机器人实例创建一个新的随机实例，您应该为您重复使用的应用程序创建一个。像所有伪随机数生成器一样，随机数是确定性的。相同的输入 - 相同的输出。

由于您没有指定种子值，它将使用以毫秒为单位的时间。最后，在前 20 次以上的循环迭代之间，Wich 将变得相同。所以它将有相同的种子和相同的输入，所以相同的输出。

于 2020-02-05T18:27:48.360 回答
2

唯一名称的最简单解决方案是使用 GUID。理论上，可以生成非唯一的 GUID，但它非常接近于零。

这是示例代码：

var newUniqueName = Guid.NewGuid().ToString();

当然 GUID 看起来并不漂亮，但它们真的很容易使用。

编辑：由于我错过了格式的附加要求，因此我认为 GUID 格式是不可接受的。

这也是一种简单的方法。由于格式是两个字母（26^2 可能值）和 3 位数字（10^3 可能值），最终可能值的数量是 26^2 * 10^3 = 676 * 1000 = 676000。这个数字非常小，所以随机可用于生成 0-675999 范围内的随机整数，然后可以将该数字转换为名称。这是示例代码：

            var random = new System.Random();
            var value = random.Next(676000);
            var name = ((char)('A' + (value % 26))).ToString();
            value /= 26;
            name += (char)('A' + (value % 26));
            value /= 26;
            name += (char)('0' + (value % 10));
            value /= 10;
            name += (char)('0' + (value % 10));
            value /= 10;
            name += (char)('0' + (value % 10));

关于可能的相同名称的通常免责声明也适用于此，因为我们有 676000 个可能的变体和 10000 个必需的名称。

EDIT2：尝试了上面的代码并使用在 9915 和 9950 个唯一名称之间产生的随机数生成 10000 个名称。那不好。我会在类成员中使用一个简单的静态作为计数器而不是随机数生成器。

于 2020-02-05T19:16:24.013 回答
1

首先，让我们回顾一下您的代码失败的测试：

  • 创建了 10.000 个实例
  • 必须都有不同的名称

因此，不知何故，当创建 10000 个“随机”名称时，您的代码会产生至少两个相同的名称。

现在，让我们看看您正在使用的命名方案：

AB123

我们可以创建的唯一名称的最大数量是 468000 (26 * 25 * 10 * 9 * 8)。

这似乎不应该是一个问题，因为10000 < 468000- 但这就是生日悖论的来源！

来自维基百科：

在概率论中，生日问题或生日悖论涉及在一组n随机选择的人中，其中一些人生日相同的概率。

为了解决您的问题而重写，我们最终会问：

在一组10000 个随机选择的人中，其中一些人的名字相同的概率是多少？

维基百科文章还列出了一个函数，用于估计两个人同名的概率达到 50% 所需的人数：

生日问题约N

其中m是可能的不同值的总数。应用这个m=468000给我们〜806 - 这意味着在仅创建806个随机命名Robot的s之后，它们中的两个具有相同名称的可能性已经有50％。

当你到达 Robot #10000 时，没有生成两个相同名称的机会基本上是 0。

正如其他人所指出的，您可以通过使用 aGuid作为机器人名称来解决此问题。

如果您想保留命名约定，您也可以通过实施具有适当周期的LCG并将其用作不易发生冲突的“命名生成器”来解决此问题。

于 2020-02-06T14:48:49.113 回答
0

这是您可以做到的一种方法：

  1. 生成所有可能名称的列表
  2. 对于每个机器人，从列表中随机选择一个名称
  3. 从列表中删除选定的名称，使其无法再次选择

有了这个，你甚至不需要洗牌。像这样的东西（注意，我偷了 Optional Option 的生成名称的方法，因为它非常聪明，我懒得想我自己的）：

public class Robot
{
    private static List<string> names;
    private static Random rnd = new Random();
    public string Name { get; private set; }

    static Robot()
    {
        Console.WriteLine("Initializing");
        // Generate possible candidates
        names = Enumerable.Range(0, 675999).Select(i => 
        {
            var sb = new StringBuilder(5);
            sb.Append((char)('A' + i % 26));
            i /= 26;
            sb.Append((char)('A' + i % 26));
            i /= 26;
            sb.Append(i % 10);
            i /= 10;
            sb.Append(i % 10);
            i /= 10;
            sb.Append(i % 10);
            return sb.ToString();
        }).ToList();
    }

    public Robot()
    {
        // Note: if this needs to be multithreaded, then you'd need to do some work here
        // to avoid two threads trying to take a name at the same time
        // Also note: you should probably check that names.Count > 0 
        // and throw an error if not
        var i = rnd.Next(0, names.Count - 1);
        Name = names[i];
        names.RemoveAt(i);
    }
}

这是一个生成 20 个随机名称的小提琴。它们只能是唯一的，因为一旦使用它们就会被删除。

然而，关于多头的这一点非常重要。如果您需要能够并行生成机器人，那么您需要添加一些代码（例如锁定代码的关键部分）以确保一次只能从候选列表中选择和删除一个名称，或者否则事情会变得非常糟糕，非常快。这就是为什么当人们需要一个随机 id 并合理期望它是唯一的，而不用担心其他线程同时尝试相同的事情时，他们使用 GUID。可能的 GUID 的绝对数量使得冲突不太可能发生。但是只有 676,000 个可能的值，你没有那种奢侈

于 2020-02-10T18:32:29.090 回答