{"action":"created","issue":{"url":"https://api.github.com/repos/RxSwiftCommunity/RxDataSources/issues/151","repository_url":"https://api.github.com/repos/RxSwiftCommunity/RxDataSources","labels_url":"https://api.github.com/repos/RxSwiftCommunity/RxDataSources/issues/151/labels{/name}","comments_url":"https://api.github.com/repos/RxSwiftCommunity/RxDataSources/issues/151/comments","events_url":"https://api.github.com/repos/RxSwiftCommunity/RxDataSources/issues/151/events","html_url":"https://github.com/RxSwiftCommunity/RxDataSources/issues/151","id":247121498,"number":151,"title":"What is using diff algorithm?","user":{"login":"muukii","id":1888355,"avatar_url":"https://avatars0.githubusercontent.com/u/1888355?v=4","gravatar_id":"","url":"https://api.github.com/users/muukii","html_url":"https://github.com/muukii","followers_url":"https://api.github.com/users/muukii/followers","following_url":"https://api.github.com/users/muukii/following{/other_user}","gists_url":"https://api.github.com/users/muukii/gists{/gist_id}","starred_url":"https://api.github.com/users/muukii/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/muukii/subscriptions","organizations_url":"https://api.github.com/users/muukii/orgs","repos_url":"https://api.github.com/users/muukii/repos","events_url":"https://api.github.com/users/muukii/events{/privacy}","received_events_url":"https://api.github.com/users/muukii/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2017-08-01T16:06:55Z","updated_at":"2017-08-02T15:39:36Z","closed_at":null,"body":"What is using diff algorithm in RxDataSouces?\r\nI would like to know good points or bad points compared with [IGListDiff](https://github.com/Instagram/IGListKit/blob/master/Source/Common/IGListDiff.mm) (or something)\r\n\r\nIGListDiff of IGListKit uses Paul Heckel's Diff Algorithm.\r\nhttps://github.com/lxcid/ListDiff\r\n\r\nThanks."},"comment":{"url":"https://api.github.com/repos/RxSwiftCommunity/RxDataSources/issues/comments/319710990","html_url":"https://github.com/RxSwiftCommunity/RxDataSources/issues/151#issuecomment-319710990","issue_url":"https://api.github.com/repos/RxSwiftCommunity/RxDataSources/issues/151","id":319710990,"user":{"login":"kzaher","id":1641148,"avatar_url":"https://avatars1.githubusercontent.com/u/1641148?v=4","gravatar_id":"","url":"https://api.github.com/users/kzaher","html_url":"https://github.com/kzaher","followers_url":"https://api.github.com/users/kzaher/followers","following_url":"https://api.github.com/users/kzaher/following{/other_user}","gists_url":"https://api.github.com/users/kzaher/gists{/gist_id}","starred_url":"https://api.github.com/users/kzaher/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kzaher/subscriptions","organizations_url":"https://api.github.com/users/kzaher/orgs","repos_url":"https://api.github.com/users/kzaher/repos","events_url":"https://api.github.com/users/kzaher/events{/privacy}","received_events_url":"https://api.github.com/users/kzaher/received_events","type":"User","site_admin":false},"created_at":"2017-08-02T15:39:36Z","updated_at":"2017-08-02T15:39:36Z","body":"Hi,\r\n\r\nI'm only superficially familiar with IGListDiff so please double check this.\r\n\r\nI don't think they are using Paul Hackel's diff algorithm, but they are using something similar.\r\n\r\nWe are using similar algorithm to what they are using but with some differences:\r\n* we've got support for two level section + item animations, so that's a + (I don't think they support it, like moving items between sections, etc...). Please double check this, I think they only support it in a kind of recursive way, so they'll do diff per sections. I'm not sure do and how they support dynamic number of sections.\r\n* we've decided to not support duplicate items or sections because that would require us to have arrays per key, but they have decided to handle that case (that's a tradeoff so that's - and + depending how you look at it). In case there are duplicates we fallback to non animated refresh because that is ambiguity and invalid data as I see it.\r\n* our structures are also set up so they can support table view editing operations out of the box. I'm assuming that's why they have those controllers in their data source, but don't have time to investigate. We can use normal `tableView.rx.item*` to update the data.\r\n\r\nI'm hoping ours algorithm is faster than theirs, but I haven't done any benchmarks 🙈 . If it's not, challenge accepted 😆. If you have time to set up that benchmark that would be great, although they are only calculating single level, so that's a bit cheating 😆 .\r\n\r\nNeither ours or IGListDiff will calculate minimal number of changes in all cases like some dynamic programming algorithms, but dynamic programming algorithms require O(n^2) in worst case while ours and IGListDiff require O(n) in worst case if you consider dictionary operations as O(1), and they generate pretty good results IMHO."}}
{"actor":{"display_login":"kzaher"}}