草庐IT

c# - 在 .NET 中生成所有整数的随机、非重复序列

coder 2023-07-10 原文

.NET 中有没有办法生成 的序列?全部 32 位整数 ( Int32 ) 以随机顺序,没有重复,并且以内存高效的方式?内存高效意味着最多只使用几百兆字节的主内存。

理想情况下,序列应该类似于 IEnumerable<int> ,并且仅在请求时才按顺序延迟返回下一个数字。

我做了一些快速研究,发现了一些部分解决方案:

  • 使用 maximal linear feedback shift register - 如果我理解正确,它只会生成递增序列的数字,并没有涵盖整个范围
  • 使用 Fisher-Yates或其他集合上的改组算法 - 鉴于大范围
  • ,这将违反内存限制
  • Maintaining a set-like collection and keep generating a random integer (也许使用 Random )直到它不重复,即它不在集合中 - 除了可能无法满足内存要求之外,在生成序列中的最后一个数字时它会变得非常慢。
  • 超过 32 位的随机排列,但是我想不出确保不可重复性的方法。

  • 是否有另一种方式来看待这个问题——也许利用固定的值范围——这将提供满足内存要求的解决方案?也许 .NET 类库带有一些有用的东西?

    更新 1

    感谢大家对解决方案的见解和创造性建议。我将尽快尝试实现和测试(为了正确性和内存效率)这里提出的 2 或 3 个最有希望的解决方案,发布结果,然后选择一个“赢家”。

    更新 2

    我尝试在 comment below 中实现 hvd 的建议.我尝试同时使用 BitArray在 .NET 和我的自定义实现中,因为 .NET 仅限于 int.MaxValue条目,因此不足以涵盖整个整数范围。

    我喜欢这个想法的简单性,如果它运行良好,我愿意“牺牲”这 512 MB 的内存。不幸的是,运行时间很慢,在我的机器上生成下一个随机数最多需要几十秒,我的机器有 3.5 GHz Core i7 CPU。所以不幸的是,如果您要求生成很多很多随机数,这是 Not Acceptable 。我想这是可以预测的,如果我没记错的话,它是一个 O(M x N) 算法,其中 N 是 2^32,M 是请求的整数的数量,因此所有这些迭代都会产生影响。

    理想情况下,我想在 O(1) 时间内生成下一个随机数,同时仍然满足内存要求,也许这里建议的下一个算法适合于此。我会尽快给他们试一试。

    更新 3

    我刚刚测试了 Linear Congruential Generator我可以说我对结果很满意。它看起来像是该线程中获胜者位置的有力竞争者。

    正确性 :所有整数只生成一次(我使用位向量来检查这一点)。

    随机性 : 挺好的。

    内存使用 : 太好了,只有几个字节。

    运行时间 :非常快地生成下一个随机整数,正如您可以从 O(1) 算法中期望的那样。生成每个整数总共花费了大约。在我的机器上 11 秒。

    总而言之,如果您不是在寻找高度随机化的序列,我会说这是一种非常合适的技术。

    更新 4

    模块化multiplicative inverse technique下面描述的行为与 LCG 技术非常相似 - 这并不奇怪,因为两者都基于模算术 - 尽管我发现为了产生令人满意的随机序列而实现它有点不那么直接。

    我发现一个有趣的区别是,这种技术似乎比 LCG 更快:生成整个序列大约需要 8 秒,而 LCG 需要 11 秒。除此之外,关于内存效率、正确性和随机性的所有其他评论都是相同的。

    更新 5

    看起来像用户 TomTom在我在评论中指出我发现它比需要的更快生成重复数字之后,我在没有通知的情况下删除了他们对 Mersenne Twister 的回答。所以我想这完全排除了 Mersenne Twister。

    更新 6

    我测试了另一种看起来很有希望的建议技术,Skip32 ,虽然我真的很喜欢随机数的质量,但该算法不适合在可接受的时间内生成整个整数范围。因此,不幸的是,与能够完成该过程的其他技术相比,它有所不足。我在 C# 中使用了来自 here 的实现,顺便说一句-我更改了代码以将轮数减少到1,但仍然无法及时完成。

    毕竟,从上述结果来看,我个人对解决方案的选择是 modular multiplicative inverses 技术,紧随其后的是 linear congruential generator .有些人可能会争辩说,这在某些方面不如其他技术,但考虑到我最初的限制,我会说它最适合他们。

    最佳答案

    Is there a way in .NET



    实际上,这可以用大多数语言完成

    to generate a sequence of all the 32-bit integers (Int32)



    是的。

    in random order,



    在这里我们需要就术语达成一致,因为“随机”并不是大多数人认为的那样。稍后会详细介绍这一点。

    without repetitions,



    是的。

    and in a memory-efficient manner?



    是的。

    Memory-efficient would mean using a maximum of just a few hundred mega bytes of main memory.



    好的,那么几乎不使用内存是可以接受的吗? ;-)

    在提出建议之前,我们需要弄清楚“随机性”的问题。真正随机的东西没有明显的模式。因此,连续运行该算法数百万次理论上可以在所有迭代中返回相同的值。如果你抛出“必须与之前的迭代不同”的概念,那么它就不再是随机的了。然而,将所有要求放在一起看,似乎真正要求的是“不同的整数分布模式”。这是可行的。

    那么如何有效地做到这一点呢?利用 Modular multiplicative inverses .我用它来回答以下问题,该问题具有在特定范围内生成非重复、伪随机样本数据的类似要求:

    Generate different random time in the given interval

    我首先在这里了解了这个概念 ( generate seemingly random unique numeric ID in SQL Server ),您可以使用以下任一在线计算器来确定您的“整数”和“模乘逆 (MMI)”值:
  • http://planetcalc.com/3311/
  • http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php

  • 在此处应用该概念,您将使用 Int32.MaxSize 作为 Modulo 值。

    这将给出一个明确的随机分布外观,没有发生冲突的机会,也不需要存储已经使用的值的内存。

    唯一的初始问题是,给定相同的“整数”和“MMI”值,分布模式总是相同的。因此,您可以通过将“随机”生成的 Int 添加到起始值来想出不同的模式(正如我相信我在关于在 SQL Server 中生成示例数据的回答中所做的那样),或者您可以预先生成“Integer”和相应的“MMI”值,将它们存储在配置文件/字典中,并使用 .NET 随机函数在每次运行开始时选择一个。即使您存储 100 个组合,也几乎没有内存使用(假设它不在配置文件中)。事实上,如果同时存储为 Int 并且字典使用 Int 作为索引,那么 1000 个值大约是 12k?

    更新

    笔记:
  • 结果中有一个模式,但除非您在任何特定时刻都有足够的结果来查看总数,否则无法辨别。对于大多数用例,这是可以接受的,因为值的接收者不会有大量的值,或者知道它们是按顺序分配的,没有任何间隙(并且需要了解以确定是否存在模式) .
  • 特定运行的公式中只需要两个变量值中的一个——“整数”和“模乘逆 (MMI)”。因此:
  • 每对给出两个不同的序列
  • 如果在内存中维护一个集合,只需要一个简单的数组,并且假设数组索引只是数组基地址在内存中的一个偏移量,那么所需的内存应该只有4个字节*容量(即1024个选项是只有 4k,对吗?)

  • 这是一些测试代码。它是用 T-SQL 为 Microsoft SQL Server 编写的,因为这是我主要工作的地方,它还有一个优点,那就是让测试唯一性、最小值和最大值等变得非常容易,无需编译任何东西。该语法适用于 SQL Server 2008 或更新版本。对于 SQL Server 2005,还没有引入变量的初始化,所以每个 DECLARE包含 =只需要分成 DECLARE本身和一个 SET @Variable = ...但是,该变量正在初始化。和 SET @Index += 1;需要变成 SET @Index = @Index + 1; .

    如果您提供产生任何重复的值,测试代码将出错。最后的查询指示是否有任何差距,因为可以推断出,如果表变量人口没有错误(因此没有重复),并且值的总数是预期的数字,那么可能只有差距(即缺失)值)如果实际 MIN 和 MAX 值中的一个或两个都在预期值之外。

    请注意,此测试代码并不意味着任何值是预先生成的或需要存储的。该代码仅存储值以测试唯一性和最小值/最大值。在实践中,所有需要的是简单的公式,所有需要传递给它的是:
  • 容量(尽管在这种情况下也可以进行硬编码)
  • MMI/整数值
  • 当前“索引”

  • 所以你只需要维护 2 - 3 个简单的值。

    DECLARE @TotalCapacity INT = 30; -- Modulo; -5 to +4 = 10 OR Int32.MinValue
                                     -- to Int32.MaxValue = (UInt32.MaxValue + 1)
    DECLARE @MMI INT = 7; -- Modular Multiplicative Inverse (MMI) or
                          -- Integer (derived from @TotalCapacity)
    
    DECLARE @Offset INT = 0; -- needs to stay at 0 if min and max values are hard-set
    -----------
    DECLARE @Index INT = (1 + @Offset); -- start
    
    DECLARE @EnsureUnique TABLE ([OrderNum] INT NOT NULL IDENTITY(1, 1),
                                 [Value] INT NOT NULL UNIQUE);
    SET NOCOUNT ON;
    
    BEGIN TRY
        WHILE (@Index < (@TotalCapacity + 1 + @Offset)) -- range + 1
        BEGIN
            INSERT INTO @EnsureUnique ([Value]) VALUES (
                     ((@Index * @MMI) % @TotalCapacity) - (@TotalCapacity / 2) + @Offset
                                                       );
            SET @Index += 1;
        END;
    END TRY
    BEGIN CATCH
        DECLARE @Error NVARCHAR(4000) = ERROR_MESSAGE();
        RAISERROR(@Error, 16, 1);
        RETURN;
    END CATCH;
    
    SELECT * FROM @EnsureUnique ORDER BY [OrderNum] ASC;
    SELECT COUNT(*) AS [TotalValues],
           @TotalCapacity AS [ExpectedCapacity],
           MIN([Value]) AS [MinValue],
           (@TotalCapacity / -2) AS [ExpectedMinValue],
           MAX([Value]) AS [MaxValue],
           (@TotalCapacity / 2) - 1 AS [ExpectedMaxValue]
    FROM   @EnsureUnique;
    

    关于c# - 在 .NET 中生成所有整数的随机、非重复序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35102073/

    有关c# - 在 .NET 中生成所有整数的随机、非重复序列的更多相关文章

    1. ruby-on-rails - Ruby net/ldap 模块中的内存泄漏 - 2

      作为我的Rails应用程序的一部分,我编写了一个小导入程序,它从我们的LDAP系统中吸取数据并将其塞入一个用户表中。不幸的是,与LDAP相关的代码在遍历我们的32K用户时泄漏了大量内存,我一直无法弄清楚如何解决这个问题。这个问题似乎在某种程度上与LDAP库有关,因为当我删除对LDAP内容的调用时,内存使用情况会很好地稳定下来。此外,不断增加的对象是Net::BER::BerIdentifiedString和Net::BER::BerIdentifiedArray,它们都是LDAP库的一部分。当我运行导入时,内存使用量最终达到超过1GB的峰值。如果问题存在,我需要找到一些方法来更正我的代

    2. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串? - 2

      我试图获取一个长度在1到10之间的字符串,并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符,然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

    3. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们? - 2

      我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

    4. ruby - 如何模拟 Net::HTTP::Post? - 2

      是的,我知道最好使用webmock,但我想知道如何在RSpec中模拟此方法:defmethod_to_testurl=URI.parseurireq=Net::HTTP::Post.newurl.pathres=Net::HTTP.start(url.host,url.port)do|http|http.requestreq,foo:1endresend这是RSpec:let(:uri){'http://example.com'}specify'HTTPcall'dohttp=mock:httpNet::HTTP.stub!(:start).and_yieldhttphttp.shou

    5. ruby-on-rails - 跳过状态机方法的所有验证 - 2

      当我的预订模型通过rake任务在状态机上转换时,我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用,我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested

    6. ruby - Nokogiri 剥离所有属性 - 2

      我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点? 最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者,如果您需要做一些更复杂的事情,有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog

    7. ruby - 获取模块中定义的所有常量的值 - 2

      我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组,即["apple","boy"]? 最佳答案 为了做到这一点,请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c

    8. c# - 如何在 ruby​​ 中调用 C# dll? - 2

      如何在ruby​​中调用C#dll? 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器,如果它还没有,则使用Ruby的WIN32OLE库来调用它;看看RubyCLR,其中一位作者是JohnLam,他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了,可能不支持.Net2.0以上的版本);正如其他地方已经提到的,看看使用IronRuby,如果这是您的技术选择。有一个主题是here.请注意,最后一篇文章实际上来自JohnLam(看起来像是2009年3月),他似乎很自在地断言RubyCL

    9. C# 到 Ruby sha1 base64 编码 - 2

      我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时,我得到了相同sha

    10. ruby - Net::HTTP 获取源代码和状态 - 2

      我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态,而无需发出第二个请求。有没有办法用另一种方法做到这一点?我一直在查看文档,但似乎找不到我要找的东西。 最佳答案 在我看来,除非您需要一些真正的低级访问或控制,否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur

    随机推荐