{"action":"closed","issue":{"url":"https://api.github.com/repos/fatih/set/issues/30","repository_url":"https://api.github.com/repos/fatih/set","labels_url":"https://api.github.com/repos/fatih/set/issues/30/labels{/name}","comments_url":"https://api.github.com/repos/fatih/set/issues/30/comments","events_url":"https://api.github.com/repos/fatih/set/issues/30/events","html_url":"https://github.com/fatih/set/issues/30","id":149248987,"number":30,"title":"Needs Big-O time complexity in documentation.","user":{"login":"RayfenWindspear","id":2687517,"avatar_url":"https://avatars.githubusercontent.com/u/2687517?v=3","gravatar_id":"","url":"https://api.github.com/users/RayfenWindspear","html_url":"https://github.com/RayfenWindspear","followers_url":"https://api.github.com/users/RayfenWindspear/followers","following_url":"https://api.github.com/users/RayfenWindspear/following{/other_user}","gists_url":"https://api.github.com/users/RayfenWindspear/gists{/gist_id}","starred_url":"https://api.github.com/users/RayfenWindspear/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RayfenWindspear/subscriptions","organizations_url":"https://api.github.com/users/RayfenWindspear/orgs","repos_url":"https://api.github.com/users/RayfenWindspear/repos","events_url":"https://api.github.com/users/RayfenWindspear/events{/privacy}","received_events_url":"https://api.github.com/users/RayfenWindspear/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2016-04-18T19:29:56Z","updated_at":"2016-04-22T17:20:13Z","closed_at":"2016-04-22T17:20:13Z","body":"Without time complexity information for each Set method, it is difficult to determine whether or not to use this library. I thought about using this library, until I read the code for Intersect, which calls Union twice, which in turn calls Copy. The whole operation is hardly optimized. I DO understand that this library is for convenience purposes and I am NOT intending to bash your code, but if people are to rely on such libraries, they at least need to know the complexity of the operations.\r\n\r\nTo further make my point, I added a benchmark for a piece of code I wrote for the intersection of two sets, which I make no claim as being the fastest implementation, but the order is easily worked out as: \r\nO( (len(set1) + len(set2)) * O(map) )\r\n\r\n(I took the liberty of interleaving the results for easier comparison.)\r\n\r\n```\r\n// Returns the intersection of two slices\r\nfunc SimpleIntersection(l1 []int, l2 []int) []int { // O((len(l1) + len(l2)) * O(map))\r\n\tret := []int{}\r\n\tm := make(map[int]bool, len(l1))\r\n\r\n\tfor _, item := range l1 {\r\n\t\tm[item] = true\r\n\t}\r\n\r\n\tfor _, item := range l2 {\r\n\t\tif m[item] == true {\r\n\t\t\tret = append(ret, item)\r\n\t\t}\r\n\t}\r\n\treturn ret\r\n}\r\n```\r\n\r\n```\r\nPASS\r\nBenchmarkSetEquality-4              \t   10000\t    780659 ns/op\r\nBenchmarkSubset-4                   \t   10000\t    801358 ns/op\r\nBenchmarkIntersection10-4           \t  100000\t     13075 ns/op\r\nBenchmarkSimpleIntersection10-4     \t 2000000\t       601 ns/op\r\nBenchmarkIntersection100-4          \t   10000\t    118579 ns/op\r\nBenchmarkSimpleIntersection100-4    \t  200000\t      6183 ns/op\r\nBenchmarkIntersection1000-4         \t    1000\t   1302503 ns/op\r\nBenchmarkSimpleIntersection1000-4   \t   30000\t     53364 ns/op\r\nBenchmarkIntersection10000-4        \t     100\t  13888576 ns/op\r\nBenchmarkSimpleIntersection10000-4  \t    3000\t    573658 ns/op\r\nBenchmarkIntersection100000-4       \t      10\t 175577891 ns/op\r\nBenchmarkSimpleIntersection100000-4 \t     200\t   7036305 ns/op\r\nBenchmarkIntersection1000000-4      \t       1\t2828214630 ns/op\r\nBenchmarkSimpleIntersection1000000-4\t      10\t 144838095 ns/op\r\nok  \tgithub.com/fatih/set\t41.404s\r\n```"}}