sparse dot product

import%20marimo%0A%0A__generated_with%20%3D%20%220.23.9%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Sparse%20Dot%20Product%0A%0A%20%20%20%20**LeetCode%201570%20(premium)%20%C2%B7%20ML%20interview%20staple**%0A%0A%20%20%20%20Given%20two%20**sparse**%20vectors%20%60v1%60%20and%20%60v2%60%20(lists%20of%20numbers%2C%20mostly%20zeros)%2C%0A%20%20%20%20compute%20their%20dot%20product%20**efficiently**%20%E2%80%94%20without%20multiplying%20pairs%20that%0A%20%20%20%20are%20zero%20in%20either%20vector.%0A%0A%20%20%20%20**ML%20relevance**%3A%20this%20is%20the%20core%20operation%20behind%20sparse%20feature%20vectors%0A%20%20%20%20(TF-IDF%2C%20bag-of-words%2C%20one-hot)%2C%20collaborative%20filtering%2C%20and%20any%0A%20%20%20%20matrix-vector%20product%20with%20a%20CSR%2FCSC%20sparse%20matrix.%20%20At%20scale%2C%20skipping%0A%20%20%20%20zero%20pairs%20can%20reduce%20computation%20by%20100%C3%97.%0A%0A%20%20%20%20%23%23%20Naive%20vs%20efficient%0A%0A%20%20%20%20%7C%20Approach%20%7C%20Time%20%7C%20When%20to%20use%20%7C%0A%20%20%20%20%7C---%7C---%7C---%7C%0A%20%20%20%20%7C%20%60sum(a*b%20for%20a%2Cb%20in%20zip(v1%2C%20v2))%60%20%7C%20O(n)%20%7C%20dense%20vectors%20%7C%0A%20%20%20%20%7C%20Index-set%20intersection%20%7C%20O(nnz%E2%82%81%20%2B%20nnz%E2%82%82)%20%7C%20sparse%20vectors%20%7C%0A%0A%20%20%20%20**Efficient%20approach**%3A%20%20represent%20each%20vector%20as%20%60%7Bindex%3A%20value%7D%60%20for%0A%20%20%20%20non-zero%20entries%2C%20then%20iterate%20over%20the%20*smaller*%20dict%20and%20look%20up%20indices%0A%20%20%20%20in%20the%20*larger*%20one.%0A%0A%20%20%20%20The%20interviewer%20is%20checking%20that%20you%20don't%20loop%20over%20all%20zeros.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20%23%20---%20student%3A%20begin%20---%0A%0A%20%20%20%20def%20sparseDotProduct(v1%3A%20list%2C%20v2%3A%20list)%20-%3E%20float%3A%0A%20%20%20%20%20%20%20%20%22%22%22Compute%20the%20dot%20product%20of%20two%20sparse%20vectors%20efficiently.%0A%0A%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20v1%3A%20list%20of%20numbers%20(mostly%20zeros)%2C%20length%20n%0A%20%20%20%20%20%20%20%20%20%20%20%20v2%3A%20list%20of%20numbers%20(mostly%20zeros)%2C%20same%20length%20n%0A%0A%20%20%20%20%20%20%20%20Returns%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20Scalar%20dot%20product%3A%20sum(v1%5Bi%5D%20*%20v2%5Bi%5D%20for%20i%20in%20range(n))%0A%20%20%20%20%20%20%20%20%20%20%20%20but%20computed%20without%20iterating%20over%20zero%20pairs.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20raise%20NotImplementedError(%22Implement%20sparseDotProduct%22)%0A%0A%20%20%20%20%23%20---%20student%3A%20end%20---%0A%20%20%20%20return%20(sparseDotProduct%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20sparseDotProduct)%3A%0A%20%20%20%20import%20math%20as%20_math%0A%0A%20%20%20%20def%20_oracle(v1%2C%20v2)%3A%0A%20%20%20%20%20%20%20%20return%20sum(a%20*%20b%20for%20a%2C%20b%20in%20zip(v1%2C%20v2))%0A%0A%20%20%20%20_cases%20%3D%20%5B%0A%20%20%20%20%20%20%20%20(%5B1%2C%200%2C%200%2C%202%2C%203%5D%2C%20%5B0%2C%203%2C%200%2C%204%2C%200%5D%2C%208.0)%2C%0A%20%20%20%20%20%20%20%20(%5B0%2C%201%2C%200%2C%200%2C%200%5D%2C%20%5B0%2C%200%2C%200%2C%200%2C%202%5D%2C%200.0)%2C%0A%20%20%20%20%20%20%20%20(%5B1%2C%202%2C%203%5D%2C%20%20%20%20%20%20%20%20%5B4%2C%205%2C%206%5D%2C%20%20%20%20%20%20%2032.0)%2C%0A%20%20%20%20%20%20%20%20(%5B0%2C%200%2C%200%5D%2C%20%20%20%20%20%20%20%20%5B0%2C%200%2C%200%5D%2C%20%20%20%20%20%20%20%200.0)%2C%0A%20%20%20%20%20%20%20%20(%5B0%2C%200%2C%201%5D%2C%20%20%20%20%20%20%20%20%5B0%2C%200%2C%201%5D%2C%20%20%20%20%20%20%20%201.0)%2C%0A%20%20%20%20%20%20%20%20(%5B1.5%2C%200%2C%202.0%5D%2C%20%20%20%20%5B0%2C%203.0%2C%204.0%5D%2C%20%20%20%208.0)%2C%0A%20%20%20%20%5D%0A%0A%20%20%20%20_solved%20%3D%20False%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20for%20_v1%2C%20_v2%2C%20_expected%20in%20_cases%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_got%20%3D%20sparseDotProduct(_v1%5B%3A%5D%2C%20_v2%5B%3A%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20_math.isclose(_got%2C%20_expected%2C%20rel_tol%3D1e-9)%2C%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22sparseDotProduct(%7B_v1%7D%2C%20%7B_v2%7D)%3A%20expected%20%7B_expected%7D%2C%20got%20%7B_got%7D%22%0A%0A%20%20%20%20%20%20%20%20%23%20Efficiency%20check%3A%20result%20on%20large%20sparse%20vectors%20should%20be%20fast%0A%20%20%20%20%20%20%20%20%23%20(a%20naive%20zip-loop%20over%201%20million%20zeros%20would%20be%20slow%20in%20Pyodide)%0A%20%20%20%20%20%20%20%20_n%20%3D%20200_000%0A%20%20%20%20%20%20%20%20_big1%20%3D%20%5B0.0%5D%20*%20_n%3B%20_big1%5B42%5D%20%3D%203.0%3B%20_big1%5B99999%5D%20%3D%207.0%0A%20%20%20%20%20%20%20%20_big2%20%3D%20%5B0.0%5D%20*%20_n%3B%20_big2%5B42%5D%20%3D%202.0%3B%20_big2%5B99999%5D%20%3D%205.0%0A%20%20%20%20%20%20%20%20_got_big%20%3D%20sparseDotProduct(_big1%2C%20_big2)%0A%20%20%20%20%20%20%20%20assert%20_math.isclose(_got_big%2C%2041.0%2C%20rel_tol%3D1e-9)%2C%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22Large%20sparse%3A%20expected%2041.0%2C%20got%20%7B_got_big%7D%22%0A%0A%20%20%20%20%20%20%20%20_result%20%3D%20mo.callout(mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%E2%9C%85%20%60sparseDotProduct%60%20is%20correct%20and%20handles%20large%20sparse%20inputs!%22%0A%20%20%20%20%20%20%20%20)%2C%20kind%3D%22success%22)%0A%20%20%20%20%20%20%20%20_solved%20%3D%20True%0A%20%20%20%20except%20NotImplementedError%20as%20e%3A%0A%20%20%20%20%20%20%20%20_result%20%3D%20mo.callout(mo.md(f%22%E2%9C%8F%EF%B8%8F%20%7Be%7D%22)%2C%20kind%3D%22neutral%22)%0A%20%20%20%20except%20Exception%20as%20e%3A%0A%20%20%20%20%20%20%20%20_result%20%3D%20mo.callout(mo.md(f%22%E2%9D%8C%20%7Be%7D%22)%2C%20kind%3D%22danger%22)%0A%20%20%20%20%23%20---%20capture%20%26%20report%20---%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20import%20inspect%20as%20_inspect%2C%20json%20as%20_json%2C%20js%20as%20_js%0A%20%20%20%20%20%20%20%20from%20pyodide.ffi%20import%20to_js%20as%20_to_js%0A%20%20%20%20%20%20%20%20_srcs%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_fn%20in%20(sparseDotProduct%2C)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_srcs.append(_inspect.getsource(_fn))%0A%20%20%20%20%20%20%20%20%20%20%20%20except%20Exception%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%20%20%20%20%20%20%20%20_payload%20%3D%20_json.dumps(%7B%22notebookId%22%3A%20%22ml_interview%2Fsparse_dot_product%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22code%22%3A%20%22%5Cn%5Cn%22.join(_srcs)%2C%20%22solved%22%3A%20bool(_solved)%7D)%0A%20%20%20%20%20%20%20%20if%20_solved%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ch%20%3D%20_js.BroadcastChannel.new(%22mlp-notebooks%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ch.postMessage(_js.JSON.parse(_json.dumps(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%22type%22%3A%20%22mlp%3Anotebook-solved%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22notebookId%22%3A%20%22ml_interview%2Fsparse_dot_product%22%7D)))%0A%20%20%20%20%20%20%20%20%20%20%20%20_ch.close()%0A%20%20%20%20%20%20%20%20_js.fetch(%22%2Fapi%2Fnotebook-progress%22%2C%20_to_js(%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%22method%22%3A%20%22POST%22%2C%20%22headers%22%3A%20%7B%22Content-Type%22%3A%20%22application%2Fjson%22%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%22credentials%22%3A%20%22include%22%2C%20%22body%22%3A%20_payload%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20dict_converter%3D_js.Object.fromEntries))%0A%20%20%20%20except%20Exception%3A%0A%20%20%20%20%20%20%20%20pass%0A%20%20%20%20mo.output.replace(_result)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A