{"action":"created","comment":{"url":"https://api.github.com/repos/cogneco/ooc-kean/pulls/comments/37396101","id":37396101,"diff_hunk":"@@ -247,15 +235,93 @@ FloatVectorList: class extends VectorList<Float> {\n \t\ttempVector free()\n \t\tresult\n \t}\n+\t/* calculate median without copying and sorting the vector\n+\t\t\tWARNING: this function can partially rearange the elements in vector\n+\t*/\n+\tfastMedian: func -> Float {\n+\t\tdata := this _vector _backend as Float*\n+\t\tresult := This _nthElement(this _vector _backend as Float*, 0, this count - 1, this count / 2)\n+\t\tif (Int even(this count))\n+\t\t\tresult = (result + This _nthElement(this _vector _backend as Float*, 0, this count - 1, this count / 2 - 1)) / 2\n+\t\tresult\n+\t}\n \tmovingMedianFilter: func (windowSize: Int) -> This {\n \t\tresult := This new(this count)\n \t\tstart := -((windowSize - 1) / 2)\n \t\tfor (i in 0..this count) {\n \t\t\trange := (start..(start + windowSize - 1)) + i\n \t\t\telementsInWindow := this getSlice(range clamp(0, this count-1))\n-\t\t\tresult add((elementsInWindow as This) median())\n+\t\t\tresult add((elementsInWindow as This) fastMedian())\n \t\t\telementsInWindow free()\n \t\t}\n \t\tresult\n \t}\n+\t_swap: static func (array: Float*, i, j: Int) {\n+\t\tt := array[i]\n+\t\tarray[i] = array[j]\n+\t\tarray[j] = t\n+\t}\n+\t/* partition the array so that all elements less than array[pivot] are moved before this element\n+\t\tand all elements greater than array[pivot] are after it\n+\t\tend should be the last valid array index in the range\n+\t*/\n+\t_partition: static func (array: Float*, start, end, pivot: Int) -> Int {\n+\t\tpivotValue := array[pivot]\n+\t\tThis _swap(array, pivot, end)\n+\t\tresult := start\n+\t\tfor (i in start..end)\n+\t\t\tif (array[i] < pivotValue) {\n+\t\t\t\tThis _swap(array, result, i)\n+\t\t\t\t++result","path":"source/math/FloatVectorList.ooc","position":63,"original_position":63,"commit_id":"96d60cd3b30b5332f2ae87b49f6648fffa98d73d","original_commit_id":"96d60cd3b30b5332f2ae87b49f6648fffa98d73d","user":{"login":"davidhesselbom","id":4319680,"avatar_url":"https://avatars.githubusercontent.com/u/4319680?v=3","gravatar_id":"","url":"https://api.github.com/users/davidhesselbom","html_url":"https://github.com/davidhesselbom","followers_url":"https://api.github.com/users/davidhesselbom/followers","following_url":"https://api.github.com/users/davidhesselbom/following{/other_user}","gists_url":"https://api.github.com/users/davidhesselbom/gists{/gist_id}","starred_url":"https://api.github.com/users/davidhesselbom/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davidhesselbom/subscriptions","organizations_url":"https://api.github.com/users/davidhesselbom/orgs","repos_url":"https://api.github.com/users/davidhesselbom/repos","events_url":"https://api.github.com/users/davidhesselbom/events{/privacy}","received_events_url":"https://api.github.com/users/davidhesselbom/received_events","type":"User","site_admin":false},"body":"You can go ahead and open an issue on https://github.com/cogneco/magic about this leading ++ operator.","created_at":"2015-08-19T09:34:18Z","updated_at":"2015-08-19T09:34:18Z","html_url":"https://github.com/cogneco/ooc-kean/pull/330#discussion_r37396101","pull_request_url":"https://api.github.com/repos/cogneco/ooc-kean/pulls/330","_links":{"self":{"href":"https://api.github.com/repos/cogneco/ooc-kean/pulls/comments/37396101"},"html":{"href":"https://github.com/cogneco/ooc-kean/pull/330#discussion_r37396101"},"pull_request":{"href":"https://api.github.com/repos/cogneco/ooc-kean/pulls/330"}}},"pull_request":{"url":"https://api.github.com/repos/cogneco/ooc-kean/pulls/330","id":42792052,"html_url":"https://github.com/cogneco/ooc-kean/pull/330","diff_url":"https://github.com/cogneco/ooc-kean/pull/330.diff","patch_url":"https://github.com/cogneco/ooc-kean/pull/330.patch","issue_url":"https://api.github.com/repos/cogneco/ooc-kean/issues/330","number":330,"state":"open","locked":false,"title":"FloatVectorList: improved sorting performance and added fast median algorithm","user":{"login":"sebastianbaginski","id":13517893,"avatar_url":"https://avatars.githubusercontent.com/u/13517893?v=3","gravatar_id":"","url":"https://api.github.com/users/sebastianbaginski","html_url":"https://github.com/sebastianbaginski","followers_url":"https://api.github.com/users/sebastianbaginski/followers","following_url":"https://api.github.com/users/sebastianbaginski/following{/other_user}","gists_url":"https://api.github.com/users/sebastianbaginski/gists{/gist_id}","starred_url":"https://api.github.com/users/sebastianbaginski/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sebastianbaginski/subscriptions","organizations_url":"https://api.github.com/users/sebastianbaginski/orgs","repos_url":"https://api.github.com/users/sebastianbaginski/repos","events_url":"https://api.github.com/users/sebastianbaginski/events{/privacy}","received_events_url":"https://api.github.com/users/sebastianbaginski/received_events","type":"User","site_admin":false},"body":"Implementation of quicksort and quickselect for float vectors.\r\nIt is not a general implementation (based on generics or iterators, with a custom comparator function) because of #327 .\r\nProfiling and testing is on my branch https://github.com/sebastianbaginski/ooc-kean/tree/quickselectProfiling  (run *./test.sh math/FloatVectorList*)\r\n\r\nExample profiling results:\r\n> start testing new: 10:20:22\r\n> done testing new: 10:20:26\r\n> start testing old: 10:20:26\r\n> done testing old: 10:26:20\r\n> number of tests: 20000\r\n\r\ncalculating median and sorting for 20.000 random float vectors of length 1000 took ~4 seconds with new implementation vs. ~6 minutes with old.","created_at":"2015-08-19T09:10:09Z","updated_at":"2015-08-19T09:34:18Z","closed_at":null,"merged_at":null,"merge_commit_sha":"b50194ac4b5bd79ec1d13873cf5ce5412e844605","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/cogneco/ooc-kean/pulls/330/commits","review_comments_url":"https://api.github.com/repos/cogneco/ooc-kean/pulls/330/comments","review_comment_url":"https://api.github.com/repos/cogneco/ooc-kean/pulls/comments{/number}","comments_url":"https://api.github.com/repos/cogneco/ooc-kean/issues/330/comments","statuses_url":"https://api.github.com/repos/cogneco/ooc-kean/statuses/96d60cd3b30b5332f2ae87b49f6648fffa98d73d","head":{"label":"sebastianbaginski:quickselect","ref":"quickselect","sha":"96d60cd3b30b5332f2ae87b49f6648fffa98d73d","user":{"login":"sebastianbaginski","id":13517893,"avatar_url":"https://avatars.githubusercontent.com/u/13517893?v=3","gravatar_id":"","url":"https://api.github.com/users/sebastianbaginski","html_url":"https://github.com/sebastianbaginski","followers_url":"https://api.github.com/users/sebastianbaginski/followers","following_url":"https://api.github.com/users/sebastianbaginski/following{/other_user}","gists_url":"https://api.github.com/users/sebastianbaginski/gists{/gist_id}","starred_url":"https://api.github.com/users/sebastianbaginski/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sebastianbaginski/subscriptions","organizations_url":"https://api.github.com/users/sebastianbaginski/orgs","repos_url":"https://api.github.com/users/sebastianbaginski/repos","events_url":"https://api.github.com/users/sebastianbaginski/events{/privacy}","received_events_url":"https://api.github.com/users/sebastianbaginski/received_events","type":"User","site_admin":false},"repo":{"id":39762712,"name":"ooc-kean","full_name":"sebastianbaginski/ooc-kean","owner":{"login":"sebastianbaginski","id":13517893,"avatar_url":"https://avatars.githubusercontent.com/u/13517893?v=3","gravatar_id":"","url":"https://api.github.com/users/sebastianbaginski","html_url":"https://github.com/sebastianbaginski","followers_url":"https://api.github.com/users/sebastianbaginski/followers","following_url":"https://api.github.com/users/sebastianbaginski/following{/other_user}","gists_url":"https://api.github.com/users/sebastianbaginski/gists{/gist_id}","starred_url":"https://api.github.com/users/sebastianbaginski/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sebastianbaginski/subscriptions","organizations_url":"https://api.github.com/users/sebastianbaginski/orgs","repos_url":"https://api.github.com/users/sebastianbaginski/repos","events_url":"https://api.github.com/users/sebastianbaginski/events{/privacy}","received_events_url":"https://api.github.com/users/sebastianbaginski/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/sebastianbaginski/ooc-kean","description":"ooc port of parts of Kean.","fork":true,"url":"https://api.github.com/repos/sebastianbaginski/ooc-kean","forks_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/forks","keys_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/keys{/key_id}","collaborators_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/teams","hooks_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/hooks","issue_events_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/issues/events{/number}","events_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/events","assignees_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/assignees{/user}","branches_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/branches{/branch}","tags_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/tags","blobs_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/git/refs{/sha}","trees_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/git/trees{/sha}","statuses_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/statuses/{sha}","languages_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/languages","stargazers_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/stargazers","contributors_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/contributors","subscribers_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/subscribers","subscription_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/subscription","commits_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/commits{/sha}","git_commits_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/git/commits{/sha}","comments_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/comments{/number}","issue_comment_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/issues/comments{/number}","contents_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/contents/{+path}","compare_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/compare/{base}...{head}","merges_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/merges","archive_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/downloads","issues_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/issues{/number}","pulls_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/pulls{/number}","milestones_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/milestones{/number}","notifications_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/labels{/name}","releases_url":"https://api.github.com/repos/sebastianbaginski/ooc-kean/releases{/id}","created_at":"2015-07-27T08:08:08Z","updated_at":"2015-07-27T08:08:09Z","pushed_at":"2015-08-19T08:52:13Z","git_url":"git://github.com/sebastianbaginski/ooc-kean.git","ssh_url":"git@github.com:sebastianbaginski/ooc-kean.git","clone_url":"https://github.com/sebastianbaginski/ooc-kean.git","svn_url":"https://github.com/sebastianbaginski/ooc-kean","homepage":"","size":6820,"stargazers_count":0,"watchers_count":0,"language":"ooc","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"cogneco:master","ref":"master","sha":"c2f3169bbaab05a8e9b7841b9855799f5e229bcb","user":{"login":"cogneco","id":3601419,"avatar_url":"https://avatars.githubusercontent.com/u/3601419?v=3","gravatar_id":"","url":"https://api.github.com/users/cogneco","html_url":"https://github.com/cogneco","followers_url":"https://api.github.com/users/cogneco/followers","following_url":"https://api.github.com/users/cogneco/following{/other_user}","gists_url":"https://api.github.com/users/cogneco/gists{/gist_id}","starred_url":"https://api.github.com/users/cogneco/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cogneco/subscriptions","organizations_url":"https://api.github.com/users/cogneco/orgs","repos_url":"https://api.github.com/users/cogneco/repos","events_url":"https://api.github.com/users/cogneco/events{/privacy}","received_events_url":"https://api.github.com/users/cogneco/received_events","type":"Organization","site_admin":false},"repo":{"id":25256330,"name":"ooc-kean","full_name":"cogneco/ooc-kean","owner":{"login":"cogneco","id":3601419,"avatar_url":"https://avatars.githubusercontent.com/u/3601419?v=3","gravatar_id":"","url":"https://api.github.com/users/cogneco","html_url":"https://github.com/cogneco","followers_url":"https://api.github.com/users/cogneco/followers","following_url":"https://api.github.com/users/cogneco/following{/other_user}","gists_url":"https://api.github.com/users/cogneco/gists{/gist_id}","starred_url":"https://api.github.com/users/cogneco/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cogneco/subscriptions","organizations_url":"https://api.github.com/users/cogneco/orgs","repos_url":"https://api.github.com/users/cogneco/repos","events_url":"https://api.github.com/users/cogneco/events{/privacy}","received_events_url":"https://api.github.com/users/cogneco/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/cogneco/ooc-kean","description":"ooc port of parts of Kean.","fork":false,"url":"https://api.github.com/repos/cogneco/ooc-kean","forks_url":"https://api.github.com/repos/cogneco/ooc-kean/forks","keys_url":"https://api.github.com/repos/cogneco/ooc-kean/keys{/key_id}","collaborators_url":"https://api.github.com/repos/cogneco/ooc-kean/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/cogneco/ooc-kean/teams","hooks_url":"https://api.github.com/repos/cogneco/ooc-kean/hooks","issue_events_url":"https://api.github.com/repos/cogneco/ooc-kean/issues/events{/number}","events_url":"https://api.github.com/repos/cogneco/ooc-kean/events","assignees_url":"https://api.github.com/repos/cogneco/ooc-kean/assignees{/user}","branches_url":"https://api.github.com/repos/cogneco/ooc-kean/branches{/branch}","tags_url":"https://api.github.com/repos/cogneco/ooc-kean/tags","blobs_url":"https://api.github.com/repos/cogneco/ooc-kean/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/cogneco/ooc-kean/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/cogneco/ooc-kean/git/refs{/sha}","trees_url":"https://api.github.com/repos/cogneco/ooc-kean/git/trees{/sha}","statuses_url":"https://api.github.com/repos/cogneco/ooc-kean/statuses/{sha}","languages_url":"https://api.github.com/repos/cogneco/ooc-kean/languages","stargazers_url":"https://api.github.com/repos/cogneco/ooc-kean/stargazers","contributors_url":"https://api.github.com/repos/cogneco/ooc-kean/contributors","subscribers_url":"https://api.github.com/repos/cogneco/ooc-kean/subscribers","subscription_url":"https://api.github.com/repos/cogneco/ooc-kean/subscription","commits_url":"https://api.github.com/repos/cogneco/ooc-kean/commits{/sha}","git_commits_url":"https://api.github.com/repos/cogneco/ooc-kean/git/commits{/sha}","comments_url":"https://api.github.com/repos/cogneco/ooc-kean/comments{/number}","issue_comment_url":"https://api.github.com/repos/cogneco/ooc-kean/issues/comments{/number}","contents_url":"https://api.github.com/repos/cogneco/ooc-kean/contents/{+path}","compare_url":"https://api.github.com/repos/cogneco/ooc-kean/compare/{base}...{head}","merges_url":"https://api.github.com/repos/cogneco/ooc-kean/merges","archive_url":"https://api.github.com/repos/cogneco/ooc-kean/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/cogneco/ooc-kean/downloads","issues_url":"https://api.github.com/repos/cogneco/ooc-kean/issues{/number}","pulls_url":"https://api.github.com/repos/cogneco/ooc-kean/pulls{/number}","milestones_url":"https://api.github.com/repos/cogneco/ooc-kean/milestones{/number}","notifications_url":"https://api.github.com/repos/cogneco/ooc-kean/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/cogneco/ooc-kean/labels{/name}","releases_url":"https://api.github.com/repos/cogneco/ooc-kean/releases{/id}","created_at":"2014-10-15T13:42:17Z","updated_at":"2015-05-08T13:13:16Z","pushed_at":"2015-08-19T09:10:10Z","git_url":"git://github.com/cogneco/ooc-kean.git","ssh_url":"git@github.com:cogneco/ooc-kean.git","clone_url":"https://github.com/cogneco/ooc-kean.git","svn_url":"https://github.com/cogneco/ooc-kean","homepage":"","size":8934,"stargazers_count":3,"watchers_count":3,"language":"ooc","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":14,"mirror_url":null,"open_issues_count":3,"forks":14,"open_issues":3,"watchers":3,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/cogneco/ooc-kean/pulls/330"},"html":{"href":"https://github.com/cogneco/ooc-kean/pull/330"},"issue":{"href":"https://api.github.com/repos/cogneco/ooc-kean/issues/330"},"comments":{"href":"https://api.github.com/repos/cogneco/ooc-kean/issues/330/comments"},"review_comments":{"href":"https://api.github.com/repos/cogneco/ooc-kean/pulls/330/comments"},"review_comment":{"href":"https://api.github.com/repos/cogneco/ooc-kean/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/cogneco/ooc-kean/pulls/330/commits"},"statuses":{"href":"https://api.github.com/repos/cogneco/ooc-kean/statuses/96d60cd3b30b5332f2ae87b49f6648fffa98d73d"}}}}