c# - 现有元素的 HashSet 性能添加与包含

coder 2024-05-25 原文

由于某些原因，当元素已存在于 哈希集。

证明:

    Stopwatch watch = new Stopwatch();
    int size = 10000;
    int iterations = 10000;


    var s = new HashSet<int>();
    for (int i = 0; i < size; i++) {
        s.Add(i);
    }

    Console.WriteLine(watch.Time(() =>
    {
        for (int i = 0; i < size; i++) {
            s.Add(i);
        }
    }, iterations));

    s = new HashSet<int>();
    for (int i = 0; i < size; i++) {
        s.Add(i);
    }

    // outputs: 47,074,764

    Console.WriteLine(watch.Time(() =>
    {
        for (int i = 0; i < size; i++) {
            if (!s.Contains(i))
                s.Add(i);
        }
    }, iterations));

    // outputs: 41,125,219

为什么 Contains 对于已经存在的元素比 Add 更快？

注意:我正在使用来自另一个 SO 问题的 Stopwatch 扩展。

    public static long Time(this Stopwatch sw, Action action, int iterations) {
        sw.Reset();
        sw.Start();
        for (int i = 0; i < iterations; i++) {
            action();
        }
        sw.Stop();

        return sw.ElapsedTicks;
    }

更新:内部测试表明，大的性能差异只发生在 x64 版本的 .NET 框架上。使用 32 位版本的框架 Contains 似乎以与添加相同的速度运行(事实上，在某些测试运行中，带有 contains 的版本运行速度慢了一个百分点)在框架的 X64 版本上，带有 contains 的版本似乎运行速度提高约 15%。

最佳答案

AddIfNotPresent 执行 Contains 不执行的附加除法。查看 Contains 的 IL:

IL_000a:  call       instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
  IL_000f:  stloc.0
  IL_0010:  ldarg.0
  IL_0011:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_0016:  ldloc.0
  IL_0017:  ldarg.0
  IL_0018:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_001d:  ldlen
  IL_001e:  conv.i4
  IL_001f:  rem
  IL_0020:  ldelem.i4
  IL_0021:  ldc.i4.1
  IL_0022:  sub
  IL_0023:  stloc.1

这是计算哈希码的存储桶位置。结果保存在本地内存位置 1。

AddIfNotPresent 做类似的事情，但它还将计算值保存在位置 2，以便它可以在该项目不存在的情况下将该项目插入到该位置的哈希表中。它之所以保存，是因为稍后在查找该项目的循环中修改了其中一个位置。不管怎样，这里是 AddIfNotPresent 的相关代码:

IL_0011:  call       instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
  IL_0016:  stloc.0
  IL_0017:  ldloc.0
  IL_0018:  ldarg.0
  IL_0019:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_001e:  ldlen
  IL_001f:  conv.i4
  IL_0020:  rem
  IL_0021:  stloc.1
  IL_0022:  ldarg.0
  IL_0023:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_0028:  ldloc.0
  IL_0029:  ldarg.0
  IL_002a:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_002f:  ldlen
  IL_0030:  conv.i4
  IL_0031:  rem
  IL_0032:  ldelem.i4
  IL_0033:  ldc.i4.1
  IL_0034:  sub
  IL_0035:  stloc.2

无论如何，我认为额外的划分是导致添加比包含花费更多时间的原因。乍一看，似乎可以排除额外的鸿沟，但如果不花更多时间破译 IL，我不能肯定地说。

关于c# - 现有元素的 HashSet 性能添加与包含，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/628141/

c#HashSet IL code performance

有关c# - 现有元素的 HashSet 性能添加与包含的更多相关文章

ruby - 我需要将 Bundler 本身添加到 Gemfile 中吗？ - 2
当我使用Bundler时，是否需要在我的Gemfile中将其列为依赖项？毕竟，我的代码中有些地方需要它。例如，当我进行Bundler设置时:require"bundler/setup" 最佳答案没有。您可以尝试，但首先您必须用鞋带将自己抬离地面。关于ruby-我需要将Bundler本身添加到Gemfile中吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/4758609/
ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2
为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar
ruby - 将 Bootstrap Less 添加到 Sinatra - 2
我有一个ModularSinatra应用程序，我正在尝试将Bootstrap添加到应用程序中。get'/bootstrap/application.css'doless:"bootstrap/bootstrap"end我在views/bootstrap中有所有less文件，包括bootstrap.less。我收到这个错误:Less::ParseErrorat/bootstrap/application.css'reset.less'wasn'tfound.Bootstrap.less的第一行是://CSSReset@import"reset.less";我尝试了所有不同的路径格式，但它
ruby - 续集在添加关联时访问many_to_many连接表 - 2
我正在使用Sequel构建一个愿望list系统。我有一个wishlists和itemstable和一个items_wishlists连接表(该名称是续集选择的名称)。items_wishlists表还有一个用于facebookid的额外列(因此我可以存储opengraph操作)，这是一个NOTNULL列。我还有Wishlist和Item具有续集many_to_many关联的模型已建立。Wishlist类也有:selectmany_to_many关联的选项设置为select:[:items.*,:items_wishlists__facebook_action_id].有没有一种方法可以
ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2
我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。最佳答案
c# - 如何在 ruby 中调用 C# dll？ - 2
如何在ruby中调用C#dll？最佳答案我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL
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
ruby - 可以通过多少种方法将方法添加到 ruby 对象？ - 2
当谈到运行时自省(introspection)和动态代码生成时，我认为ruby没有任何竞争对手，可能除了一些lisp方言。前几天，我正在做一些代码练习来探索ruby的动态功能，我开始想知道如何向现有对象添加方法。以下是我能想到的3种方法:obj=Object.new#addamethoddirectlydefobj.new_method...end#addamethodindirectlywiththesingletonclassclass这只是冰山一角，因为我还没有探索instance_eval、module_eval和define_method的各种组合。是否有在线/离线资
ruby - 如何在 Ruby 中向现有方法定义添加语句 - 2
我注意到类定义，如果我打开classMyClass，并在不覆盖的情况下添加一些东西我仍然得到了之前定义的原始方法。添加的新语句扩充了现有语句。但是对于方法定义，我仍然想要与类定义相同的行为，但是当我打开defmy_method时似乎,def中的现有语句和end被覆盖了，我需要重写一遍。那么有什么方法可以使方法定义的行为与定义相同，类似于super，但不一定是子类？最佳答案我想您正在寻找alias_method:classAalias_method:old_func,:funcdeffuncold_func#similartoca
ruby-on-rails - 添加回形针新样式不影响旧上传的图像 - 2
我有带有Logo图像的公司模型has_attached_file:logo我用他们的Logo创建了许多公司。现在，我需要添加新样式has_attached_file:logo,:styles=>{:small=>"30x15>",:medium=>"155x85>"}我是否应该重新上传所有旧数据以重新生成新样式？我不这么认为……或者有什么rake任务可以重新生成样式吗？最佳答案参见Thumbnail-Generation.如果rake任务不适合你，你应该能够在控制台中使用一个片段来调用重新处理!关于相关公司

c# - 现有元素的 HashSet 性能添加与包含

有关c# - 现有元素的 HashSet 性能添加与包含的更多相关文章

随机推荐