草庐IT

ios - Swift 的 map 和 filter 函数时间复杂度

coder 2023-09-12 原文

我使用 Swift 4 以两种不同的方式实现了下面的 numJewelsInStones 函数。

我想比较每个实现的时间和空间复杂度。但是，我在一个实现中使用了一些 native 方法，例如过滤字符串，然后在另一个实现中将字符串映射到单个字符数组。我想知道这些 native 函数的时间复杂度。另外，如果我使用字符串范围来获取字符串中每个字符的出现情况会怎样。我想了解这些原生函数，特别是在 Swift 中，如何影响整个 Big O。

实现 1: 过滤字符串(使用 for 循环，如果我忽略过滤函数，我会说大 O 是 O(n)，这是正确的吗？)

//J - represents types of stones that are jewels
//S - represents the stones I have
func numJewelsInStones(_ J: String, _ S: String) -> Int { 
    var sum = 0 //Sum - represents how many of the stones I have are also jewels
    for jewel in J {
        sum = sum + S.filter {$0 == jewel}.count //add sum of occurrences for each stone that is a jewel
    }
    return sum 
}
print(numJewelsInStones("aA", "aAAbbbb")) //prints 3
print(numJewelsInStones("z", "ZZ"))       //prints 0

实现 2: 我做的第一件事是将字符串映射到单个字符数组，否则我会在行 counts[stone ] = (counts[stone] ?? 0) + 1

更新:只是注意到我意识到如果我只是将 counts 字典的定义更改为 var counts，我什至不需要将字符串映射到字符数组: [Character: Int] = [:] 这样可以避免上述错误。哎呀。不过，为了这个问题，我将保留原样。

func numJewelsInStones2(_ J: String, _ S: String) -> Int {
        let jewels = J.map { String($0) }
        let stones = S.map { String($0) }
        var counts: [String: Int] = [:]
        var sum = 0
    for stone in stones {
        counts[stone] = (counts[stone] ?? 0) + 1 //frequency count dict
    }
    for jewel in jewels { //for every jewel
        if let count = counts[jewel]  { //if the jewel exists in the frequency count dict
            sum = sum + count //add its count to the total sum
        }
    }
    return sum
}

print(numJewelsInStones2("aA", "aAAbbbb")) //prints 3
print(numJewelsInStones2("z", "ZZ"))       //prints 0

最佳答案

Swift标准库中的所有高阶函数，如map、flatMap/compactMap、filter 和 reduce 通常具有 O(n) 时间复杂度，因为它们都在调用它们的完整集合上工作，并且它们只访问每个元素一次，所以它们具有线性时间复杂度。

考虑到这一点，您的第一个实现具有 O(J*S) 时间复杂度，因为对于 J 中的每个元素，您都遍历了 的所有元素S 使用 filter。

另一方面，您的第二个实现具有大致线性的时间复杂度，具体取决于哪个 String 中有更多的 Character，S 或 J，它的时间复杂度是O(J)或O(S)，因为你没有任何嵌套循环，你只需要遍历J 和 S 顺序。

实现 1 或 2 是否更有效完全取决于 J 和 S 的大小。

关于ios - Swift 的 map 和 filter 函数时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49887447/

filterSwiftcodenumJewelsInStonessectionios

有关ios - Swift 的 map 和 filter 函数时间复杂度的更多相关文章

  1. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  2. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  3. ruby-on-rails - Ruby 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  4. ruby - 在 Ruby 中有条件地定义函数 - 2

    我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

  5. ruby - 如何验证 IO.copy_stream 是否成功 - 2

    这里有一个很好的答案解释了如何在Ruby中下载文件而不将其加载到内存中:https://stackoverflow.com/a/29743394/4852737require'open-uri'download=open('http://example.com/image.png')IO.copy_stream(download,'~/image.png')我如何验证下载文件的IO.copy_stream调用是否真的成功——这意味着下载的文件与我打算下载的文件完全相同，而不是下载一半的损坏文件？documentation说IO.copy_stream返回它复制的字节数，但是当我还没有下

  6. ruby-on-rails - 将 Ruby 中的日期/时间格式化为 YYYY-MM-DD HH :MM:SS - 2

    这个问题在这里已经有了答案:Railsformattingdate(4个答案)关闭4年前。我想格式化Time.Now函数以显示YYYY-MM-DDHH:MM:SS而不是:“2018-03-0909:47:19+0000”该函数需要放在时间中.现在功能。require‘roo’require‘roo-xls’require‘byebug’file_name=ARGV.first||“Template.xlsx”excel_file=Roo::Spreadsheet.open(“./#{file_name}“,extension::xlsx)xml=Nokogiri::XML::Build

  7. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  8. Ruby 文件 IO 定界符？ - 2

    我正在尝试解析一个文本文件，该文件每行包含可变数量的单词和数字，如下所示:foo4.500bar3.001.33foobar如何读取由空格而不是换行符分隔的文件？有什么方法可以设置File("file.txt").foreach方法以使用空格而不是换行符作为分隔符？ 最佳答案 接受的答案将slurp文件，这可能是大文本文件的问题。更好的解决方案是IO.foreach.它是惯用的，将按字符流式传输文件:File.foreach(filename,""){|string|putsstring}包含“thisisanexample”结果的

  9. ruby-on-rails - before_filter 运行多个方法 - 2

    是否有可能:before_filter:authenticate_user!||:authenticate_admin! 最佳答案 before_filter:do_authenticationdefdo_authenticationauthenticate_user!||authenticate_admin!end 关于ruby-on-rails-before_filter运行多个方法，我们在StackOverflow上找到一个类似的问题： https://

  10. ruby - 在 Ruby 中按名称传递函数 - 2

    如何在Ruby中按名称传递函数？(我使用Ruby才几个小时，所以我还在想办法。)nums=[1,2,3,4]#Thisworks,butismoreverbosethanI'dlikenums.eachdo|i|putsiend#InJS,Icouldjustdosomethinglike:#nums.forEach(console.log)#InF#,itwouldbesomethinglike:#List.iternums(printf"%A")#InRuby,IwishIcoulddosomethinglike:nums.eachputs在Ruby中能不能做到类似的简洁？我可以只

随机推荐