{"action":"created","issue":{"url":"https://api.github.com/repos/javaslang/javaslang/issues/560","labels_url":"https://api.github.com/repos/javaslang/javaslang/issues/560/labels{/name}","comments_url":"https://api.github.com/repos/javaslang/javaslang/issues/560/comments","events_url":"https://api.github.com/repos/javaslang/javaslang/issues/560/events","html_url":"https://github.com/javaslang/javaslang/issues/560","id":105087140,"number":560,"title":"Boost our HAMT time complexity for some operations from O(n) to effectively O(1)","user":{"login":"danieldietrich","id":743833,"avatar_url":"https://avatars.githubusercontent.com/u/743833?v=3","gravatar_id":"","url":"https://api.github.com/users/danieldietrich","html_url":"https://github.com/danieldietrich","followers_url":"https://api.github.com/users/danieldietrich/followers","following_url":"https://api.github.com/users/danieldietrich/following{/other_user}","gists_url":"https://api.github.com/users/danieldietrich/gists{/gist_id}","starred_url":"https://api.github.com/users/danieldietrich/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/danieldietrich/subscriptions","organizations_url":"https://api.github.com/users/danieldietrich/orgs","repos_url":"https://api.github.com/users/danieldietrich/repos","events_url":"https://api.github.com/users/danieldietrich/events{/privacy}","received_events_url":"https://api.github.com/users/danieldietrich/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/javaslang/javaslang/labels/feature","name":"feature","color":"009800"}],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/javaslang/javaslang/milestones/18","html_url":"https://github.com/javaslang/javaslang/milestones/2.0.0","labels_url":"https://api.github.com/repos/javaslang/javaslang/milestones/18/labels","id":1091674,"number":18,"title":"2.0.0","description":"","creator":{"login":"danieldietrich","id":743833,"avatar_url":"https://avatars.githubusercontent.com/u/743833?v=3","gravatar_id":"","url":"https://api.github.com/users/danieldietrich","html_url":"https://github.com/danieldietrich","followers_url":"https://api.github.com/users/danieldietrich/followers","following_url":"https://api.github.com/users/danieldietrich/following{/other_user}","gists_url":"https://api.github.com/users/danieldietrich/gists{/gist_id}","starred_url":"https://api.github.com/users/danieldietrich/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/danieldietrich/subscriptions","organizations_url":"https://api.github.com/users/danieldietrich/orgs","repos_url":"https://api.github.com/users/danieldietrich/repos","events_url":"https://api.github.com/users/danieldietrich/events{/privacy}","received_events_url":"https://api.github.com/users/danieldietrich/received_events","type":"User","site_admin":false},"open_issues":15,"closed_issues":122,"state":"open","created_at":"2015-04-30T20:29:59Z","updated_at":"2015-09-06T11:08:49Z","due_on":null,"closed_at":null},"comments":2,"created_at":"2015-09-06T11:08:49Z","updated_at":"2015-09-06T11:15:50Z","closed_at":null,"body":"As stated in #559 our following HAMT operations are currently linear instead of effectively constant:\r\n\r\n* tail()\r\n* prepend()\r\n* insert()\r\n\r\nScala also does use the HAMT, at least for HashSet, with eff. const. time for all operations. See http://docs.scala-lang.org/overviews/collections/performance-characteristics.html. Also the [LAMP paper](http://lampwww.epfl.ch/papers/idealhashtrees.pdf) says that HAMT operations are O(1), e.g. remove(key).\r\n\r\nWe need to investigate further if and how to get eff. const. time for the operations mentioned above."},"comment":{"url":"https://api.github.com/repos/javaslang/javaslang/issues/comments/138071090","html_url":"https://github.com/javaslang/javaslang/issues/560#issuecomment-138071090","issue_url":"https://api.github.com/repos/javaslang/javaslang/issues/560","id":138071090,"user":{"login":"danieldietrich","id":743833,"avatar_url":"https://avatars.githubusercontent.com/u/743833?v=3","gravatar_id":"","url":"https://api.github.com/users/danieldietrich","html_url":"https://github.com/danieldietrich","followers_url":"https://api.github.com/users/danieldietrich/followers","following_url":"https://api.github.com/users/danieldietrich/following{/other_user}","gists_url":"https://api.github.com/users/danieldietrich/gists{/gist_id}","starred_url":"https://api.github.com/users/danieldietrich/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/danieldietrich/subscriptions","organizations_url":"https://api.github.com/users/danieldietrich/orgs","repos_url":"https://api.github.com/users/danieldietrich/repos","events_url":"https://api.github.com/users/danieldietrich/events{/privacy}","received_events_url":"https://api.github.com/users/danieldietrich/received_events","type":"User","site_admin":false},"created_at":"2015-09-06T11:15:50Z","updated_at":"2015-09-06T11:15:50Z","body":"@ruslansennov Ok, that's nice!\r\n\r\nBut then this whole operation should be O(1) and no further index update is needed, right?\r\n\r\n```java\r\nVector<T> tail() {\r\n    final Iterator<T> iterator = iterator(); // O(1)\r\n    if (!iterator.hasNext()) { // O(1)\r\n        throw new UnsupportedOperationException(\"tail of empty Vector\");\r\n    }\r\n    final T key = iterator.next(); // O(1)\r\n    return new Vector<>(tree.remove(key)); // O(1) and tree indices are aligned new, right?\r\n}\r\n```\r\n"}}