{"id":367066,"date":"2024-05-21T03:13:20","date_gmt":"2024-05-21T03:13:20","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=367066"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=367066","title":{"rendered":"<span>\u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/754\/9fa\/899\/7549fa8991b7256c56825e792033e484.jpg\" alt=\"\u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0435 \u043d\u0435\u0431\u043e \u043d\u0430\u0434 \u0414\u0438\u0430\u043d\u043e\u0439 \u0438 \u041a\u043e\u043d\u0451\u043c \u0411\u043e\u0434\u0436\u0435\u043a\u043e\u043c\" title=\"\u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0435 \u043d\u0435\u0431\u043e \u043d\u0430\u0434 \u0414\u0438\u0430\u043d\u043e\u0439 \u0438 \u041a\u043e\u043d\u0451\u043c \u0411\u043e\u0434\u0436\u0435\u043a\u043e\u043c\" width=\"1366\" height=\"768\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/754\/9fa\/899\/7549fa8991b7256c56825e792033e484.jpg\" data-blurred=\"true\"\/><\/p>\n<div><figcaption>\u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0435 \u043d\u0435\u0431\u043e \u043d\u0430\u0434 \u0414\u0438\u0430\u043d\u043e\u0439 \u0438 \u041a\u043e\u043d\u0451\u043c \u0411\u043e\u0434\u0436\u0435\u043a\u043e\u043c<\/figcaption><\/div>\n<\/figure>\n<p>\u041a\u043e\u0433\u0434\u0430-\u0442\u043e \u044f \u043f\u0438\u0441\u0430\u043b \u043f\u043e\u0441\u0442 \u043f\u0440\u043e \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 <a href=\"https:\/\/habr.com\/ru\/articles\/673776\/\" rel=\"noopener noreferrer nofollow\">\u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445<\/a>. \u0421\u0440\u0435\u0434\u0438 \u043d\u0438\u0445 \u0431\u044b\u043b \u0442.\u043d. sparse set. \u0422\u0430\u043c \u043c\u044b \u043e\u043f\u0438\u0441\u0430\u043b\u0438 \u0435\u0433\u043e \u0432 \u043e\u0431\u0449\u0438\u0445 \u0447\u0435\u0440\u0442\u0430\u0445, \u043e\u043f\u0443\u0441\u0442\u0438\u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0435\u0442\u0430\u043b\u0438 (\u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u043f\u043e\u0437\u0436\u0435 \u0441\u0442\u0430\u0442\u044c\u044f \u0431\u044b\u043b\u0430 \u0434\u043e\u043f\u043e\u043b\u043d\u0435\u043d\u0430). \u041d\u043e \u043a\u0440\u043e\u043c\u0435 sparse set \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0438 \u0434\u0440\u0443\u0433\u0438\u0435 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445! \u041d\u0430 \u043d\u0438\u0445 \u0441\u0435\u0433\u043e\u0434\u043d\u044f \u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c : )<\/p>\n<h2>Sparse Array (Sparse Matrix)<\/h2>\n<p>\u041a\u043e\u0433\u0434\u0430 \u043c\u044b \u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043f\u0440\u043e \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b, \u043c\u044b \u0447\u0430\u0449\u0435 \u0432\u0441\u0435\u0433\u043e \u0438\u043c\u0435\u0435\u043c \u0432 \u0432\u0438\u0434\u0443 \u043d\u0435\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 0 \u0438\u043b\u0438 None\/null). \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0433\u043b\u044f\u043d\u0435\u043c \u043d\u0430 \u043a\u0430\u043a\u043e\u0439-\u043d\u0438\u0431\u0443\u0434\u044c \u0432\u0435\u043a\u0442\u043e\u0440 (\u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0441\u043c\u044b\u0441\u043b\u0435):<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"A = \\begin{pmatrix} 1 &amp; 0 &amp; 0 &amp; 4 &amp; 0 &amp; 2 &amp; 0 &amp; 0 \\end{pmatrix}\" alt=\"A = \\begin{pmatrix} 1 &amp; 0 &amp; 0 &amp; 4 &amp; 0 &amp; 2 &amp; 0 &amp; 0 \\end{pmatrix}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/695\/522\/792\/69552279280ddc5f871db5f15ae3ca4b.svg\" width=\"278\" height=\"22\"\/><\/p>\n<p>\u0418\u043b\u0438 \u043d\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u0443:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"B = \\begin{pmatrix}  1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\\\ 4 &amp; -2 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\\ \\end{pmatrix}\" alt=\"B = \\begin{pmatrix}  1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\\\ 4 &amp; -2 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\\ \\end{pmatrix}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ec6\/88e\/424\/ec688e42481ca4467c0615743e9009fe.svg\" width=\"224\" height=\"132\"\/><\/p>\n<p>\u041a\u0430\u043a \u0432 \u0432\u0435\u043a\u0442\u043e\u0440\u0435 <strong>\u0410<\/strong>, \u0442\u0430\u043a \u0438 \u0432 \u0431\u043b\u043e\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 <strong>\u0412<\/strong>, \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0443\u043b\u0435\u0432\u044b\u0435. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0442\u044c \u0432 \u0442\u0430\u043a\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u0435\u0441\u043b\u0438 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u0421\u0430\u043c\u044b\u0435 \u043f\u043e\u043d\u044f\u0442\u043d\u044b\u0435 \u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u2013 \u044d\u0442\u043e \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432:<\/p>\n<p><img class=\"formula\" source=\"f: i -> value, \u0434\u043b\u044f\\ \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \\\\ f: (i, j) -> value,  \u0434\u043b\u044f\\ \u043c\u0430\u0442\u0440\u0438\u0446\u044b&#187; alt=&#187;f: i -> value, \u0434\u043b\u044f\\ \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \\\\ f: (i, j) -> value,  \u0434\u043b\u044f\\ \u043c\u0430\u0442\u0440\u0438\u0446\u044b&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0d1\/084\/5b8\/0d10845b874af9daba4fa0744bbf8ccc.svg&#187; width=&#187;697&#8243; height=&#187;59&#8243;\/><\/p>\n<p>\u0418\u043b\u0438 \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432: \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u2013 \u043e\u0434\u0438\u043d \u043d\u0430 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0443 \u0438 \u043e\u0434\u0438\u043d \u043d\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435; \u0430 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u2013 \u0434\u0432\u0430 \u043d\u0430 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0438 \u043e\u0434\u0438\u043d \u043d\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432\u044b\u0448\u0435 \u043f\u043e\u0434\u043e\u0431\u043d\u0430\u044f \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u0442\u0430\u043a:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\begin{matrix}   i: &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\\\  j: &amp; 0 &amp; 1 &amp; 0 &amp; 1 \\\\  v: &amp; 1 &amp; 1 &amp; 4 &amp; -2 \\\\  \\end{matrix}\" alt=\"\\begin{matrix}   i: &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\\\  j: &amp; 0 &amp; 1 &amp; 0 &amp; 1 \\\\  v: &amp; 1 &amp; 1 &amp; 4 &amp; -2 \\\\  \\end{matrix}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ada\/c08\/ce9\/adac08ce90d2681a60daed326259db7e.svg\" width=\"159\" height=\"78\"\/><\/p>\n<p>\u0418\u043b\u0438 \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432 \u0441\u043f\u0438\u0441\u043e\u043a (\u043e\u0434\u043d\u043e-\/\u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0439), \u0433\u0434\u0435 \u043d\u043e\u0434\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u0440\u0430\u0437\u0443 \u0432\u0441\u0435 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u041d\u0435 \u0441\u0443\u0442\u044c \u0432\u0430\u0436\u043d\u043e. \u041a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u044f \u0432\u0435\u0437\u0434\u0435 \u043e\u0434\u043d\u0430 \u0438 \u0442\u0430 \u0436\u0435.<\/p>\n<p>\u041f\u043e\u0434\u043e\u0431\u043d\u044b\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u043f\u043e\u043c\u043e\u0433\u0430\u044e\u0442 \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u0438 \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f\u0445 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u0442\u0438\u043f\u0430\u043c\u0438 \u043c\u0430\u0442\u0440\u0438\u0446: \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0431\u043b\u043e\u0447\u043d\u044b\u0445\/\u0438\u043d\u043e\u0433\u0434\u0430 \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u044b\u0445\/\u0434\u0438\u0430\u0433\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445. \u0415\u0441\u0442\u044c \u0433\u043e\u0442\u043e\u0432\u044b\u0435 \u043f\u0430\u043a\u0435\u0442\u044b \u0434\u043b\u044f python, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0438\u0435 \u044d\u0442\u0443 \u043b\u043e\u0433\u0438\u043a\u0443 (<a href=\"https:\/\/docs.scipy.org\/doc\/scipy\/tutorial\/sparse.html\" rel=\"noopener noreferrer nofollow\">scipy.sparse<\/a>).<\/p>\n<p>\u0422\u0443\u0442 \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u043d\u0435\u0442 \u043a\u0430\u043a\u0438\u0445-\u0442\u043e \u0446\u0435\u043f\u043b\u044f\u044e\u0449\u0438\u0445 \u0438\u0434\u0435\u0439. \u041d\u043e \u0434\u0430\u043b\u044c\u0448\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0435\u0435!<\/p>\n<h2>Sparse List<\/h2>\n<p>Sparse list \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u0441\u043c\u044b\u0441\u043b\u0435. \u0412 \u043a\u0430\u043a\u043e\u043c? \u042f \u043f\u043e\u043a\u0430 \u043d\u0435 \u0441\u043a\u0430\u0436\u0443.<\/p>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0434\u0435\u043b\u0430\u0442\u044c \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u044e\u0449\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 (\u0432\u0441\u0442\u0430\u0432\u043a\u0430, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435) \u0437\u0430 <strong>O(1)<\/strong> \u0438 \u043d\u0435 \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u044e\u0449\u0438\u0435 (\u043e\u0431\u0445\u043e\u0434 \u0432 \u043b\u044e\u0431\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443) \u0437\u0430 <strong>O(n)<\/strong>. \u0418 \u0434\u043b\u044f \u0432\u0441\u0435\u0433\u043e \u044d\u0442\u043e\u0433\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u0430 \u043e\u0434\u043d\u0430 \u043b\u0438\u0448\u044c \u043d\u043e\u0434\u0430 \u0441\u043f\u0438\u0441\u043a\u0430 (\u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u0438\u0441\u043a\u0430\u0442\u044c \u0441\u043e\u0441\u0435\u0434\u043d\u044e\u044e, \u043a\u0430\u043a \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430. \u0421 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u043c\u044b \u0432\u044b\u043d\u0443\u0436\u0434\u0435\u043d\u044b \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043f\u043e \u0434\u0432\u0430 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u043d\u043e\u0434\u0443 (\u0432 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0440\u0435\u0430\u043b\u0438\u044f\u0445 \u044d\u0442\u043e \u0447\u0430\u0449\u0435 \u0432\u0441\u0435\u0433\u043e \u0446\u0435\u043b\u044b\u0445 16 \u0431\u0430\u0439\u0442!). \u041c\u043e\u0436\u043d\u043e \u043b\u0438 \u043a\u0430\u043a-\u0442\u043e \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0443\u0445\u0443\u0434\u0448\u0438\u0442\u044c \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u044b, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0432 \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438?<\/p>\n<p>\u0414\u0430! \u0410 \u0447\u0442\u043e, \u0435\u0441\u043b\u0438 \u043c\u044b \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u043f\u043e\u043b\u0442\u043e\u0440\u0430\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a? \u041d\u0443 \u0442\u043e \u0435\u0441\u0442\u044c \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u044c \u0443 \u043d\u0435\u0433\u043e \u0447\u0442\u043e-\u0442\u043e \u043c\u0435\u0436\u0434\u0443 \u0435\u0434\u0438\u043d\u0438\u0446\u0435\u0439 \u0438 \u0434\u0432\u043e\u0439\u043a\u043e\u0439. \u0414\u043e\u0441\u0442\u0438\u0447\u044c \u044d\u0442\u043e\u0433\u043e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0438\u043c\u0435\u044f \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u043e\u0434\u044b \u0431\u0443\u0434\u0443\u0442 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u043c\u0438.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/e58\/81d\/506\/e5881d50666411815ddccd9e8882ec7e.png\" width=\"2286\" height=\"774\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e58\/81d\/506\/e5881d50666411815ddccd9e8882ec7e.png\"\/><\/figure>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043d\u043e\u0434 \u0441 \u0434\u0432\u0443\u043c\u044f \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f\u043c\u0438, \u043e\u0434\u0438\u043d \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043d\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0443\u044e \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u0443\u044e \u043d\u043e\u0434\u0443, \u0430 \u0434\u0440\u0443\u0433\u043e\u0439 \u2013 \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u043d\u043e\u0434\u0443. \u0422.\u043a. \u0440\u0430\u0437\u043c\u0435\u0440 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u201c\u043f\u043e\u0434\u0441\u043f\u0438\u0441\u043a\u0430\u201d \u043a\u043e\u043d\u0435\u0447\u0435\u043d \u0438 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d \u0437\u0430\u0440\u0430\u043d\u0435\u0435, \u043b\u044e\u0431\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u0441\u0451 \u0435\u0449\u0451 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 <strong>O(1)<\/strong>, \u043f\u0440\u044f\u043c\u043e \u043a\u0430\u043a \u0443 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 (\u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0441 \u0441\u0438\u043b\u044c\u043d\u043e \u0432\u044b\u0440\u043e\u0441\u0448\u0435\u0439 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439). \u0412\u0434\u0443\u043c\u0447\u0438\u0432\u044b\u0439 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044c \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u0441\u0442\u0430\u0432\u043e\u043a \u0432 \u043e\u0434\u0438\u043d \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u043f\u043e\u0434\u0441\u043f\u0438\u0441\u043e\u043a \u0438 \u0432\u0441\u0435 \u043d\u0430\u0448\u0438 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0438 \u0441\u043b\u043e\u043c\u0430\u044e\u0442\u0441\u044f! \u041d\u043e \u043d\u0438\u043a\u0442\u043e \u043d\u0435 \u043c\u0435\u0448\u0430\u0435\u0442 \u043d\u0430\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u044d\u0442\u0438\u0445 \u0441\u0430\u043c\u044b\u0445 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043f\u043e\u0434\u0441\u043f\u0438\u0441\u043a\u043e\u0432 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 (\u043d\u0430 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435 3, \u0435\u0441\u043b\u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u043d\u043e\u0434\u044b \u043d\u0430 \u043a\u043e\u043d\u0446\u0430\u0445). \u0422\u043e \u0435\u0441\u0442\u044c, \u0435\u0441\u043b\u0438 \u0432\u044b \u0443\u0436\u0435 \u0432\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u0443\u044e \u043d\u043e\u0434\u0443 \u043f\u043e\u0441\u043b\u0435 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u043e\u0439, \u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0439\u0442\u0435 \u0435\u0451 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u043e\u0439 \u0438 \u043f\u043e\u043f\u0440\u0430\u0432\u044c\u0442\u0435 \u0441\u0441\u044b\u043b\u043a\u0438 \u0443 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043d\u0443\u0436\u043d\u043e \u0447\u0443\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0440\u0438\u0441\u0435\u0434\u0430\u043d\u0438\u0439 \u0432 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043d\u043e \u0432\u0441\u0451 \u0436\u0435 \u0432\u0430\u043c \u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0442\u044c \u0441 \u0441\u0430\u043c\u043e\u0433\u043e \u043d\u0430\u0447\u0430\u043b\u0430 \u0432\u0430\u0448\u0435\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0443\u044e \u043d\u043e\u0434\u0443 \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0439. \u0412\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u043e\u0439\u0442\u0438 \u0432\u043f\u0435\u0440\u0451\u0434 \u0438 \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u0442\u044c \u043f\u0435\u0440\u0432\u0443\u044e \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u0443\u044e \u043d\u043e\u0434\u0443, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0440\u044b\u0433\u043d\u0443\u0442\u044c \u043d\u0430\u0437\u0430\u0434. <\/p>\n<p>\u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0443 \u0432\u0430\u0441 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u043d\u043e\u0434\u044b \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u0434\u0440\u0443\u0433 \u043e\u0442 \u0434\u0440\u0443\u0433\u0430, \u043e\u043d \u0438 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u043c.<\/p>\n<p>\u041a\u0430\u043a \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u0441\u0430\u043c\u044b\u0439 \u201c\u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0441\u0442\u0438\u201d? \u0425\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u043e\u0442\u0432\u0435\u0442\u0430 \u043d\u0435\u0442. \u042d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043f\u0443\u0442\u0451\u043c \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0433\u0430\u0434\u0430\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u043f\u0438\u0441\u0430\u0442\u044c \u043f\u043e\u0434\u043e\u0431\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0441\u0438\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0449\u0435 (\u0434\u0430 \u0438 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 \u043c\u0435\u043d\u044c\u0448\u0435), \u0435\u0441\u043b\u0438 \u043d\u043e\u0434\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0447\u0435\u0440\u0435\u0434\u0443\u044e\u0442\u0441\u044f. \u041e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u0441\u043f\u0438\u0441\u043e\u043a \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u0438\u043b\u044c\u043d\u043e \u0434\u0435\u0448\u0435\u0432\u043b\u0435, \u0435\u0441\u043b\u0438 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u043d\u043e\u0434\u044b \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0442\u0441\u044f \u0447\u0430\u0449\u0435.<\/p>\n<p>\u0410 \u043a\u0430\u043a \u043f\u0430\u043c\u044f\u0442\u044c \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0442\u044c? \u0421 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u043a\u043e\u0434\u0430 \u043c\u043e\u0436\u0435\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u0436\u0435\u043b\u0430\u043d\u0438\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0447\u0442\u043e-\u0442\u043e \u0432\u0440\u043e\u0434\u0435 <code>union<\/code>\/<code>std::variant<\/code>, \u043d\u043e \u0442\u0430\u043a\u0438\u0435 \u0442\u0438\u043f\u044b \u0431\u0443\u0434\u0443\u0442 \u0438\u043c\u0435\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0438\u0437 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432. \u0422\u043e \u0435\u0441\u0442\u044c \u0432 \u0438\u0442\u043e\u0433\u0435 \u043c\u044b \u0432\u0441\u0451 \u0435\u0449\u0451 \u0438\u043c\u0435\u0435\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0441\u0440\u0430\u0432\u043d\u0438\u043c\u043e\u0435 \u0441 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u043c \u0441\u043f\u0438\u0441\u043a\u043e\u043c.<\/p>\n<p>\u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u043a\u0440\u0430\u0441\u0438\u0432\u043e \u043d\u0438\u043a\u0430\u043a. \u0412\u0430\u043c \u0432 \u043b\u044e\u0431\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0443\u0436\u043d\u043e \u0443\u043c\u0435\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u043d\u043e\u0434\u0430\u043c\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 (\u0442\u0443\u0442 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043c\u043e\u0447\u044c type-erasure \u0432 \u043a\u0430\u043a\u043e\u043c-\u0442\u043e \u0432\u0438\u0434\u0435). \u041f\u043b\u044e\u0441 \u043d\u0443\u0436\u043d\u043e \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0443\u044e \u043d\u043e\u0434\u0443 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c \u0432 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435, \u0447\u0442\u043e\u0431\u044b \u0431\u0440\u0430\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u043d\u043e\u0434\u0443\/\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u0431\u044b\u043b\u043e \u0443\u0434\u043e\u0431\u043d\u0435\u0435. \u041d\u043e \u0437\u0430\u0442\u043e \u0437\u0430\u0434\u0430\u0447\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u043a\u0430\u043a\u043e\u0439 \u0442\u0438\u043f \u0443 \u043d\u043e\u0434\u044b, \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u0430\u044f. \u0422.\u043a. \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u0432\u044b\u0440\u043e\u0432\u043d\u0435\u043d\u044b \u0432 \u043f\u0430\u043c\u044f\u0442\u0438, \u0443 \u0432\u0430\u0441 \u0432\u0441\u0435\u0433\u0434\u0430 \u0435\u0441\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043d\u0443\u043b\u0435\u0432\u044b\u0445 \u043c\u043b\u0430\u0434\u0448\u0438\u0445 \u0431\u0438\u0442\u043e\u0432. \u041a\u0430\u043a \u0440\u0430\u0437 \u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u0431\u0440\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0438\u0437 \u044d\u0442\u0438\u0445 \u0431\u0438\u0442\u043e\u0432 \u0438 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u0432 1, \u0435\u0441\u043b\u0438 \u043d\u043e\u0434\u0430 \u0438\u043c\u0435\u0435\u0442 \u0435\u0449\u0451 \u0438 \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0439 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c (\u0432\u0430\u0436\u043d\u043e \u043d\u0435 \u0437\u0430\u0431\u044b\u0442\u044c \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u0431\u0438\u0442 \u0432 \u043d\u043e\u043b\u044c \u043f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u044d\u0442\u043e\u043c\u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044e \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u043d\u043e\u0434\u0435). \u0410 \u0435\u0449\u0451 \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b, \u043a\u043e\u0433\u0434\u0430 \u0432\u044b \u0445\u043e\u0442\u0438\u0442\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u043d\u043e\u0434\u0443 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u0432 \u0434\u0440\u0443\u0433\u043e\u0439: \u0440\u0430\u0437 \u043e\u043d\u0430 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u0441\u0432\u043e\u0439 \u0442\u0438\u043f, \u0432\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u043d\u043e\u0432\u043e \u043e\u0441\u0432\u043e\u0431\u043e\u0434\u0438\u0442\u044c\/\u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c. \u041c\u043e\u0436\u043d\u043e \u043f\u0440\u0438 \u0436\u0435\u043b\u0430\u043d\u0438\u0438 \u0432 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043d\u043e\u0434\u0430\u0445 \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043d\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043f\u043e\u0447\u0442\u0438 \u043d\u0438\u043a\u0443\u0434\u0430 \u043d\u0435 \u0443\u0445\u043e\u0434\u044f\u0442 + \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u044b \u0442\u0443\u0442 \u0432\u043e\u043e\u0431\u0449\u0435 \u0447\u0442\u043e-\u0442\u043e \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u043c.<\/p>\n<p>\u0412\u043e\u0442 <a href=\"https:\/\/locklessinc.com\/downloads\/sparse.c\" rel=\"noopener noreferrer nofollow\">\u0441\u0441\u044b\u043b\u043a\u0430<\/a> \u043d\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e, \u0435\u0441\u043b\u0438 \u043e\u0447\u0435\u043d\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u043f\u043e\u0432\u0442\u044b\u043a\u0430\u0442\u044c.<\/p>\n<h2>Sparse Deque (sparque)<\/h2>\n<p>Sparse deque \u043d\u0435\u0434\u0430\u0432\u043d\u043e <a href=\"https:\/\/www.reddit.com\/r\/cpp\/comments\/1ad3yf4\/data_structure_introducing_sparque_the_sequence\/?share_id=-b0F1DwaTAiGoHeyIsj6-&amp;utm_medium=ios_app&amp;utm_name=iossmf&amp;utm_source=share&amp;utm_term=14\" rel=\"noopener noreferrer nofollow\">\u0432\u044b\u043b\u043e\u0436\u0438\u043b<\/a> \u043e\u0434\u0438\u043d \u0438\u0437 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u0439 reddit. \u041c\u044b \u043f\u0440\u043e\u0431\u0435\u0436\u0438\u043c\u0441\u044f \u043f\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043c, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c, \u043a\u0430\u043a \u0436\u0435 \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442.<\/p>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u044c, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 B-\u0434\u0435\u0440\u0435\u0432\u043e (\u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u043c\u043e\u0436\u043d\u043e <a href=\"https:\/\/habr.com\/ru\/companies\/otus\/articles\/459216\/\" rel=\"noopener noreferrer nofollow\">\u0442\u0443\u0442<\/a>). B-\u0434\u0435\u0440\u0435\u0432\u043e, \u0433\u0440\u0443\u0431\u043e \u0433\u043e\u0432\u043e\u0440\u044f, \u2013 \u044d\u0442\u043e m-\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430. \u0422\u043e \u0435\u0441\u0442\u044c \u043a\u0430\u0436\u0434\u0430\u044f \u043d\u043e\u0434\u0430 \u043c\u043e\u0436\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u0435\u0442\u0435\u0439. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0434\u0435\u043b\u0430\u0442\u044c \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0435 \u0434\u043b\u044f \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043d\u043e \u0441 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u043e\u043c \u043f\u043e \u0431\u041e\u043b\u044c\u0448\u0435\u043c\u0443 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044e. \u0410 \u0435\u0449\u0451 \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u043c\u043e\u0433\u0430\u0435\u0442 \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u0445\u043e\u0442\u044f \u0433\u043b\u0443\u0431\u0438\u043d\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043c\u0435\u043d\u044c\u0448\u0435, \u043d\u043e \u043d\u0435 \u0441\u0442\u043e\u0438\u0442 \u0437\u0430\u0431\u044b\u0432\u0430\u0442\u044c \u0438 \u043f\u0440\u043e \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u044e\u0449\u0443\u044e \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0443, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u0443\u044e \u0441 \u0431\u041e\u043b\u044c\u0448\u0438\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439. \u0412\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043e\u043d\u043e \u043a\u0430\u043a-\u0442\u043e \u0442\u0430\u043a:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/83c\/677\/b55\/83c677b55a4a70b3349e5a62b608686a.png\" width=\"1534\" height=\"378\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/83c\/677\/b55\/83c677b55a4a70b3349e5a62b608686a.png\"\/><\/figure>\n<p>\u0414\u0430\u043b\u0435\u0435 \u0443 \u043d\u0430\u0441 \u0431\u044b\u0432\u0430\u044e\u0442 B+-\u0434\u0435\u0440\u0435\u0432\u044c\u044f. \u042d\u0442\u043e \u0442\u0430\u043a\u0438\u0435 B-\u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u0438\u043c\u0438\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0435 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432. \u041e\u043d\u0438 \u0445\u0440\u0430\u043d\u044f\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043b\u0438\u0441\u0442\u044c\u044f\u0445, \u0430 \u0432 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u043f\u0438\u0438 \u043a\u043b\u044e\u0447\u0435\u0439 (\u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0447\u0442\u043e-\u0442\u043e \u0432\u0440\u043e\u0434\u0435 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430):<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/94e\/8a0\/afc\/94e8a0afca9a791a34f3557275dbe23e.png\" width=\"746\" height=\"375\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/94e\/8a0\/afc\/94e8a0afca9a791a34f3557275dbe23e.png\"\/><\/figure>\n<p>\u0412 \u043b\u0438\u0441\u0442\u044c\u044f\u0445 B+-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043e\u0431\u044b\u0447\u043d\u043e \u0445\u0440\u0430\u043d\u044f\u0442 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043b\u0438\u0441\u0442, \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u0430\u043c \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432\u0430\u0448\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0431\u0435\u0437 \u043f\u043e\u0434\u044a\u0451\u043c\u043e\u0432 \u0438 \u0441\u043f\u0443\u0441\u043a\u043e\u0432 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443.<\/p>\n<p>\u0418 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u043a\u0443\u0441\u043e\u0447\u0435\u043a, \u044d\u0442\u043e <a href=\"https:\/\/www.chiark.greenend.org.uk\/~sgtatham\/algorithms\/cbtree.html\" rel=\"noopener noreferrer nofollow\">counted B-\u0434\u0435\u0440\u0435\u0432\u043e<\/a> \u2013 B-\u0434\u0435\u0440\u0435\u0432\u043e, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u0435\u0431\u0451\u043d\u043a\u0430 \u043c\u044b \u0445\u0440\u0430\u043d\u0438\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u0435\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/29a\/ba3\/1ea\/29aba31ea8e00a3e43df78de2984ab75.png\" width=\"578\" height=\"281\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/29a\/ba3\/1ea\/29aba31ea8e00a3e43df78de2984ab75.png\"\/><\/figure>\n<p>\u0412\u043e\u0442 sparque \u2013 \u044d\u0442\u043e counted B+-\u0434\u0435\u0440\u0435\u0432\u043e. \u0421 \u043e\u0433\u043e\u0432\u043e\u0440\u043e\u0447\u043a\u043e\u0439, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u0432 \u043a\u0430\u043d\u043e\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u043c B+-\u0434\u0435\u0440\u0435\u0432\u0435 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0438 \u043a\u043b\u044e\u0447\u0438, \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u0442\u0443\u0442 \u043c\u044b \u0445\u0440\u0430\u043d\u0438\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f (\u0432 \u043b\u0438\u0441\u0442\u044c\u044f\u0445). \u0412 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445 \u0443 \u043d\u0430\u0441 \u043e\u0441\u0442\u0430\u044e\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0438 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u0430\u043c\u0438 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043d\u0430 \u044d\u0442\u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u044f. \u0422\u0430\u043a \u0447\u0442\u043e \u043d\u0430 \u043d\u0438\u0436\u043d\u0435\u043c \u0443\u0440\u043e\u0432\u043d\u0435 (\u0432 \u043b\u0438\u0441\u0442\u044c\u044f\u0445) \u043d\u0430\u0448\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043a\u0430\u043a \u0441\u043f\u0438\u0441\u043e\u043a \u0431\u043b\u043e\u043a\u043e\u0432, \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439. \u0427\u0435\u043c \u043d\u0435 deque! \u041f\u0440\u0430\u0432\u0434\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0431\u043b\u043e\u043a \u0432 \u043b\u0438\u0441\u0442\u0435 \u044d\u0442\u043e \u0447\u0442\u043e-\u0442\u043e \u0432\u0440\u043e\u0434\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043e\u0436\u043d\u043e \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0441 \u043e\u0431\u043e\u0438\u0445 \u043a\u043e\u043d\u0446\u043e\u0432, \u0442\u0430\u043a \u0447\u0442\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u0431\u044b\u0441\u0442\u0440\u0435\u0435. <\/p>\n<p>\u0421\u0442\u041e\u044f\u0442 \u043e\u043d\u0438 \u0443 \u043d\u0430\u0441 \u0442\u0430\u043a:<\/p>\n<ul>\n<li>\n<p>\u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 <strong>O(log_m(n))<\/strong> \u2013 \u0442\u0430\u043a \u043a\u0430\u043a \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u043c, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432, \u043d\u0430\u0434\u043e \u0441\u043f\u0443\u0441\u0442\u0438\u0442\u0441\u044f \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0434\u043e \u0435\u0433\u043e \u043b\u0438\u0441\u0442\u0430. \u042d\u0442\u043e \u0434\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u0432 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u043c <code>std::deque<\/code> \u0441 \u0435\u0433\u043e <strong>O(1)<\/strong>, \u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0440\u043e\u0434\u0435 \u0442\u0440\u0435\u0439\u0434\u043e\u0444\u043e\u043c \u0434\u043b\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u0434\u0440\u0443\u0433\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439;<\/p>\n<\/li>\n<li>\n<p>\u0430\u0432\u0442\u043e\u0440 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442, \u0447\u0442\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u0430\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0432 \u043d\u0430\u0447\u0430\u043b\u043e\/\u043a\u043e\u043d\u0435\u0446 \u2013 <strong>O(1)<\/strong>. \u0417\u0432\u0443\u0447\u0438\u0442 \u0441\u043e\u043c\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0442.\u043a., \u043a\u0440\u043e\u043c\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u043d\u0443\u0436\u043d\u043e \u0435\u0449\u0451 \u043f\u0435\u0440\u0435\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043e\u0442 \u043b\u0438\u0441\u0442\u0430 \u0434\u043e \u043a\u043e\u0440\u043d\u044f \u0432\u0441\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432. \u0427\u0442\u043e \u043e\u043d \u0438 <a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h#L4143\" rel=\"noopener noreferrer nofollow\">\u0434\u0435\u043b\u0430\u0435\u0442 \u0432 push_back<\/a> \u0432 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h#L3713\" rel=\"noopener noreferrer nofollow\">update_counts_plus<\/a>. \u041d\u043e \u043c\u043e\u0436\u0435\u0442 \u044f \u0447\u0442\u043e-\u0442\u043e \u043d\u0435 \u043f\u043e\u043d\u044f\u043b \u00af\\_(\u30c4)_\/\u00af<\/p>\n<p>UPD: \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0435\u043d \u043e\u0442\u0432\u0435\u0442: <a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h#L91\" rel=\"noopener noreferrer nofollow\">https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h#L91<\/a><\/p>\n<\/li>\n<li>\n<p>\u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \u2013 <strong>O(m)<\/strong>, \u0433\u0434\u0435 m \u2013 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432 \u0431\u043b\u043e\u043a\u0435 \u043b\u0438\u0441\u0442\u0430;<\/p>\n<\/li>\n<li>\n<p>\u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u2013 <strong>O(n)<\/strong>.<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0430\u043c\u044f\u0442\u044c <strong>O(n)<\/strong>.<\/p>\n<p>\u041f\u043e\u0447\u0435\u043c\u0443 \u0430\u0432\u0442\u043e\u0440 \u0440\u0435\u0448\u0438\u043b \u043d\u0430\u0437\u0432\u0430\u0442\u044c \u044d\u0442\u0443 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0439, \u0434\u043e\u0441\u0442\u043e\u0432\u0435\u0440\u043d\u043e \u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e.<\/p>\n<p><a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/bench\/sparque\/README.md\" rel=\"noopener noreferrer nofollow\">\u0422\u0443\u0442<\/a> \u0435\u0441\u0442\u044c \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438 \u043e\u0442 \u0430\u0432\u0442\u043e\u0440\u0430 \u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441 \u0434\u0440\u0443\u0433\u0438\u043c\u0438 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430\u043c\u0438. \u0410 <a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h\" rel=\"noopener noreferrer nofollow\">\u0442\u0443\u0442<\/a> \u2013 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f.<\/p>\n<h2>Sparse Set<\/h2>\n<p>\u0412\u0441\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u0436\u0435 \u0442\u0430\u043a\u043e\u0435 sparse set. <\/p>\n<p>Sparse set \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0432\u0441\u0451 \u0442\u0435 \u0436\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u0447\u0442\u043e \u0438 \u0434\u0440\u0443\u0433\u043e\u0439 \u0437\u043d\u0430\u043a\u043e\u043c\u044b\u0439 \u0432\u0430\u043c set. \u041d\u043e \u0441 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u043e\u043d \u0432\u0441\u0451 \u0436\u0435 \u0431\u043b\u0438\u0436\u0435 \u043a <code>std::vector&lt;bool><\/code>\/<code>std::bitset<\/code>. \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0434\u0432\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0438 \u0440\u0430\u0437\u043c\u0435\u0440:<\/p>\n<pre><code class=\"cpp\">template &lt;int R> struct SparseSet { int size_ = 0; int dense_[R]; int sparse_[R]; };<\/code><\/pre>\n<p><code>dense_<\/code> \u044d\u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439. <code>sparse_<\/code> \u0436\u0435 \u0445\u0440\u0430\u043d\u0438\u0442 \u0438\u043d\u0434\u0435\u043a\u0441 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 <code>dense_<\/code>, \u0442.\u0435. \u0435\u0441\u043b\u0438 <code>dense_[i] = v<\/code>, \u0442\u043e <code>sparse_[v] = i<\/code> (\u0432\u043c\u0435\u0441\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043c\u043e\u0436\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c). \u0422\u043e\u0433\u0434\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"cpp\">void Add(int val) { dense_[size_] = val; sparse_[val] = size_; ++size_; }<\/code><\/pre>\n<p>\u0414\u043b\u044f \u043f\u0443\u0449\u0435\u0433\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u043c\u044b \u0432\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u0432 \u043d\u0430\u0448 \u0441\u0435\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f: 3, 2, 5, 1, 0.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/241\/2b2\/3b8\/2412b23b832e3221b80c6c15bf34f507.png\" width=\"1087\" height=\"387\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/241\/2b2\/3b8\/2412b23b832e3221b80c6c15bf34f507.png\"\/><\/figure>\n<p>\u041f\u0440\u0438 \u044d\u0442\u043e\u043c <code>size_<\/code> \u0440\u0430\u0432\u0435\u043d 5. \u0412 \u043f\u0443\u0441\u0442\u044b\u0445 \u043a\u043b\u0435\u0442\u043a\u0430\u0445 \u0443 \u043d\u0430\u0441 \u043d\u0438\u0447\u0435\u0433\u043e \u043b\u0435\u0436\u0438\u0442.\u00a0<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u0432 \u0441\u0432\u043e\u0451\u043c \u0441\u0435\u0442\u0435:<\/p>\n<pre><code class=\"cpp\">bool Contains(int val) { return sparse_[val] &lt; size_ &amp;&amp; dense_[sparse_[val]] == val; }<\/code><\/pre>\n<p>\u0415\u0441\u043b\u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u0434\u0432\u043e\u0439\u043a\u0438, \u0442\u043e \u043d\u0430\u0448\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0432\u0438\u0434:<\/p>\n<pre><code class=\"cpp\">sparse_[2] &lt; 5 &amp;&amp; dense_[sparse_[2]] == 2<\/code><\/pre>\n<p>\u0427\u0442\u043e \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e<\/p>\n<pre><code class=\"cpp\">1 &lt; 5 &amp;&amp; 2 == 2<\/code><\/pre>\n<p>\u0414\u0432\u043e\u0439\u043a\u0430 \u0432 \u0441\u0435\u0442\u0435!<\/p>\n<p>\u0414\u043b\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u0435\u0442\u0435 \u043d\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f, \u043c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u043c\u0443\u0441\u043e\u0440\u043d\u044b\u0435 \u044f\u0447\u0435\u0439\u043a\u0438 (\u0435\u0441\u043b\u0438 \u0440\u0430\u043d\u0435\u0435 \u0442\u0430\u043c \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043b\u0435\u0436\u0430\u043b\u043e) \u0438 \u0432\u0440\u044f\u0434 \u043b\u0438 \u043d\u0430\u0448\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043f\u0440\u043e\u0439\u0434\u0451\u0442 (\u0442\u0430\u043c \u0432\u0441\u0451-\u0442\u0430\u043a\u0438 \u043c\u0443\u0441\u043e\u0440). <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u0442\u043e \u0442\u0443\u0442 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0435 \u043f\u0440\u0438\u0441\u0435\u0434\u0430\u043d\u0438\u0435. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0443\u0434\u0430\u043b\u0438\u0442\u044c 0. \u0422\u0443\u0442 \u0432\u0441\u0451 \u043f\u0440\u043e\u0441\u0442\u043e. \u041d\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u0438 \u044d\u0442\u043e\u0442 \u043d\u043e\u043b\u044c \u0437\u0430\u0442\u0440\u0451\u0442\u0441\u044f \u043f\u0440\u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0432\u0441\u0442\u0430\u0432\u043a\u0435. \u0410 \u0435\u0441\u043b\u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 <code>dense_<\/code>? \u0422\u043e\u0433\u0434\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 <code>dense_<\/code> \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0438\u043d\u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0432 <code>sparse_<\/code>. \u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0441 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435\u043c \u0434\u0432\u043e\u0439\u043a\u0438: <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/50d\/2b0\/083\/50d2b008394571f2bbea37d11465f24f.png\" width=\"1128\" height=\"408\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/50d\/2b0\/083\/50d2b008394571f2bbea37d11465f24f.png\"\/><\/figure>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043c\u043e\u0436\u043d\u043e \u0441\u043f\u043e\u043a\u043e\u0439\u043d\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c <code>size_<\/code>. \u0412 \u043a\u043e\u0434\u0435 \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u0442\u0430\u043a:<\/p>\n<pre><code class=\"cpp\"> bool Remove(int i) {    if (dense_[size_ - 1] != i) {      int last_element = dense_[size_ - 1];      dense_[sparse_[i]] = last_element;      sparse_[last_element] = sparse_[i];    }    --size_;  }<\/code><\/pre>\n<p>\u041d\u0443 \u0438 \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0435\u0441\u043b\u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043e\u0447\u0438\u0441\u0442\u0438\u0442\u044c \u0432\u0441\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445, \u043d\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043e\u0434\u043d\u043e \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435:<\/p>\n<pre><code class=\"cpp\">void \u0421lear() { size_ = 0; }<\/code><\/pre>\n<p>\u0412\u0441\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 (\u043e\u0442 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0434\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f) \u0437\u0430 <code>O(1)<\/code>! <\/p>\n<p>\u0421\u0432\u0435\u0440\u0445\u0443 \u0435\u0449\u0451 \u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0443 \u0432\u0430\u0441 \u043b\u0435\u0436\u0430\u0442 \u0440\u044f\u0434\u043e\u043c \u0432 \u043f\u0430\u043c\u044f\u0442\u0438, \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0438 \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u043f\u043e \u0441\u0435\u0442\u0443.<\/p>\n<p>\u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u043e\u0434\u043e\u0431\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0438\u043c\u0435\u0435\u0442 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043d\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u043d\u0430 \u043c\u043e\u0436\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c. \u0410 \u0435\u0449\u0451, \u0435\u0441\u043b\u0438 \u0443 \u0432\u0430\u0441 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0442\u0438\u043f\u044b, \u043f\u0440\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u0432\u0430\u043c \u0432\u0441\u0451 \u0436\u0435 \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0432\u044b\u0437\u044b\u0432\u0430\u0442\u044c \u0434\u0435\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440\u044b. \u041d\u043e \u044d\u0442\u043e \u0443\u0436\u0435 \u043c\u0435\u043b\u043e\u0447\u0438. <\/p>\n<p>\u0412 folly \u0435\u0441\u0442\u044c \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e <a href=\"https:\/\/github.com\/facebook\/folly\/blob\/main\/folly\/container\/SparseByteSet.h\" rel=\"noopener noreferrer nofollow\">\u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/a>. \u041e\u043d\u0438 \u0444\u0438\u043a\u0441\u0438\u0440\u0443\u044e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440, \u0438\u0437-\u0437\u0430 \u0447\u0435\u0433\u043e \u0442\u0435\u0440\u044f\u0435\u0442\u0441\u044f \u0442\u043e\u0447\u043a\u0430 \u043a\u0430\u0441\u0442\u043e\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u041d\u043e \u043c\u043e\u0436\u0435\u0442 \u043a\u0442\u043e-\u0442\u043e \u0438\u0445 \u0443\u0431\u0435\u0434\u0438\u0442, \u0447\u0442\u043e \u0442\u0430\u043a \u043d\u0435 \u043d\u0430\u0434\u043e?)<\/p>\n<p>\u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u043d\u0435 \u0441\u0442\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438, \u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438. \u0418 \u043c\u043e\u0436\u043d\u043e \u0434\u0430\u0436\u0435 \u0434\u0435\u043b\u0430\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0445 \u0442\u0438\u043f\u043e\u0432 \u2013 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f! \u041f\u0440\u0430\u0432\u0434\u0430, \u043d\u0435 \u043b\u044e\u0431\u043e\u0433\u043e. \u0422.\u043a. \u043f\u043e \u0444\u0430\u043a\u0442\u0443 \u043c\u044b \u0437\u043d\u0430\u0435\u043c \u0432\u0441\u0451 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0445 \u0442\u0438\u043f\u043e\u0432, \u0442\u043e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c \u043d\u0430\u0434\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0438 \u043f\u0440\u0438 \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u0434\u043b\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u044b\u0445 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432, \u0434\u0430\u0431\u044b \u043d\u0435 \u0431\u044b\u043b\u043e \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0439. \u0412 \u044d\u0442\u043e\u043c \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043c\u043e\u0447\u044c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Perfect_hash_function\" rel=\"noopener noreferrer nofollow\">perfect hashing<\/a>.<\/p>\n<h2>Sparse Map<\/h2>\n<p>\u041b\u0430\u0434\u043d\u043e. Sparse Map \u044d\u0442\u043e \u043f\u0440\u0430\u043d\u043a. \u041d\u0438\u0447\u0435\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0433\u043e \u0442\u0443\u0442 \u043d\u0435\u0442. \u041f\u0440\u043e\u0441\u0442\u043e \u0432\u043c\u0435\u0441\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 <code>dense_<\/code> \u0442\u0435\u043f\u0435\u0440\u044c \u043c\u044b \u0445\u0440\u0430\u043d\u0438\u043c \u043f\u0430\u0440\u0443 <code>(key, value)<\/code>, \u0430 <code>sparse_<\/code> \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0441 \u043a\u043b\u044e\u0447\u0430\u043c\u0438. <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0430 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438, \u043c\u043e\u0436\u043d\u043e \u0433\u043b\u044f\u043d\u0443\u0442\u044c <a href=\"https:\/\/www.codeproject.com\/Articles\/859324\/Fast-Implementations-of-Sparse-Sets-in-Cplusplus\" rel=\"noopener noreferrer nofollow\">\u0442\u0443\u0442<\/a>.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/1b2\/986\/ad4\/1b2986ad40447c19d8ec9bd554a1d14d.jpeg\" width=\"1280\" height=\"1280\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1b2\/986\/ad4\/1b2986ad40447c19d8ec9bd554a1d14d.jpeg\" data-blurred=\"true\"\/><\/figure>\n<p>\u0415\u0441\u043b\u0438 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0433\u043b\u044f\u043d\u0443\u0442\u044c <a href=\"https:\/\/github.com\/golang\/go\/blob\/795414d1c628f763defa43199ab51ea3dc3241d8\/src\/cmd\/compile\/internal\/ssa\/sparsemap.go\" rel=\"noopener noreferrer nofollow\">\u043d\u0430 Golang<\/a> \u0438\u043b\u0438 \u043f\u043e\u043a\u043e\u043f\u0430\u0442\u044c\u0441\u044f \u0432 \u043f\u043b\u044e\u0441\u043e\u0432\u044b\u0445 <a href=\"https:\/\/tessil.github.io\/sparse-map\/sparse__map_8h_source.html\" rel=\"noopener noreferrer nofollow\">\u0434\u0435\u0431\u0440\u044f\u0445<\/a> \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u043b\u0438\u0431\u044b. <\/p>\n<hr\/>\n<p>\u041f\u043e\u0434\u043f\u0438\u0441\u044b\u0432\u0430\u0439\u0442\u0435\u0441\u044c \u0438\u043b\u0438 \u043d\u0435 \u043f\u043e\u0434\u043f\u0438\u0441\u044b\u0432\u0430\u0439\u0442\u0435\u0441\u044c \u043d\u0430 \u043c\u043e\u0439 \u043a\u0430\u043d\u0430\u043b \u043f\u0440\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0438 C++: <a href=\"http:\/\/t.me\/thisnotes\" rel=\"noopener noreferrer nofollow\">t.me\/thisnotes<\/a>.<\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/790844\/\"> https:\/\/habr.com\/ru\/articles\/790844\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\">\n<div><figcaption>\u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0435 \u043d\u0435\u0431\u043e \u043d\u0430\u0434 \u0414\u0438\u0430\u043d\u043e\u0439 \u0438 \u041a\u043e\u043d\u0451\u043c \u0411\u043e\u0434\u0436\u0435\u043a\u043e\u043c<\/figcaption><\/div>\n<\/figure>\n<p>\u041a\u043e\u0433\u0434\u0430-\u0442\u043e \u044f \u043f\u0438\u0441\u0430\u043b \u043f\u043e\u0441\u0442 \u043f\u0440\u043e \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 <a href=\"https:\/\/habr.com\/ru\/articles\/673776\/\" rel=\"noopener noreferrer nofollow\">\u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445<\/a>. \u0421\u0440\u0435\u0434\u0438 \u043d\u0438\u0445 \u0431\u044b\u043b \u0442.\u043d. sparse set. \u0422\u0430\u043c \u043c\u044b \u043e\u043f\u0438\u0441\u0430\u043b\u0438 \u0435\u0433\u043e \u0432 \u043e\u0431\u0449\u0438\u0445 \u0447\u0435\u0440\u0442\u0430\u0445, \u043e\u043f\u0443\u0441\u0442\u0438\u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0435\u0442\u0430\u043b\u0438 (\u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u043f\u043e\u0437\u0436\u0435 \u0441\u0442\u0430\u0442\u044c\u044f \u0431\u044b\u043b\u0430 \u0434\u043e\u043f\u043e\u043b\u043d\u0435\u043d\u0430). \u041d\u043e \u043a\u0440\u043e\u043c\u0435 sparse set \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0438 \u0434\u0440\u0443\u0433\u0438\u0435 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445! \u041d\u0430 \u043d\u0438\u0445 \u0441\u0435\u0433\u043e\u0434\u043d\u044f \u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c : )<\/p>\n<h2>Sparse Array (Sparse Matrix)<\/h2>\n<p>\u041a\u043e\u0433\u0434\u0430 \u043c\u044b \u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043f\u0440\u043e \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b, \u043c\u044b \u0447\u0430\u0449\u0435 \u0432\u0441\u0435\u0433\u043e \u0438\u043c\u0435\u0435\u043c \u0432 \u0432\u0438\u0434\u0443 \u043d\u0435\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 0 \u0438\u043b\u0438 None\/null). \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0433\u043b\u044f\u043d\u0435\u043c \u043d\u0430 \u043a\u0430\u043a\u043e\u0439-\u043d\u0438\u0431\u0443\u0434\u044c \u0432\u0435\u043a\u0442\u043e\u0440 (\u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0441\u043c\u044b\u0441\u043b\u0435):<\/p>\n<p>\u0418\u043b\u0438 \u043d\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u0443:<\/p>\n<p>\u041a\u0430\u043a \u0432 \u0432\u0435\u043a\u0442\u043e\u0440\u0435 <strong>\u0410<\/strong>, \u0442\u0430\u043a \u0438 \u0432 \u0431\u043b\u043e\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 <strong>\u0412<\/strong>, \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0443\u043b\u0435\u0432\u044b\u0435. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0442\u044c \u0432 \u0442\u0430\u043a\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u0435\u0441\u043b\u0438 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u0421\u0430\u043c\u044b\u0435 \u043f\u043e\u043d\u044f\u0442\u043d\u044b\u0435 \u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u2013 \u044d\u0442\u043e \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432:<\/p>\n<p> value, \u0434\u043b\u044f\\ \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \\\\ f: (i, j) -> value,  \u0434\u043b\u044f\\ \u043c\u0430\u0442\u0440\u0438\u0446\u044b&#187; alt=&#187;f: i -> value, \u0434\u043b\u044f\\ \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \\\\ f: (i, j) -> value,  \u0434\u043b\u044f\\ \u043c\u0430\u0442\u0440\u0438\u0446\u044b&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0d1\/084\/5b8\/0d10845b874af9daba4fa0744bbf8ccc.svg&#187; width=&#187;697&#8243; height=&#187;59&#8243;\/><\/p>\n<p>\u0418\u043b\u0438 \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432: \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u2013 \u043e\u0434\u0438\u043d \u043d\u0430 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0443 \u0438 \u043e\u0434\u0438\u043d \u043d\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435; \u0430 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u2013 \u0434\u0432\u0430 \u043d\u0430 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0438 \u043e\u0434\u0438\u043d \u043d\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432\u044b\u0448\u0435 \u043f\u043e\u0434\u043e\u0431\u043d\u0430\u044f \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u0442\u0430\u043a:<\/p>\n<p>\u0418\u043b\u0438 \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432 \u0441\u043f\u0438\u0441\u043e\u043a (\u043e\u0434\u043d\u043e-\/\u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0439), \u0433\u0434\u0435 \u043d\u043e\u0434\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u0440\u0430\u0437\u0443 \u0432\u0441\u0435 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u041d\u0435 \u0441\u0443\u0442\u044c \u0432\u0430\u0436\u043d\u043e. \u041a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u044f \u0432\u0435\u0437\u0434\u0435 \u043e\u0434\u043d\u0430 \u0438 \u0442\u0430 \u0436\u0435.<\/p>\n<p>\u041f\u043e\u0434\u043e\u0431\u043d\u044b\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u043f\u043e\u043c\u043e\u0433\u0430\u044e\u0442 \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u0438 \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f\u0445 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u0442\u0438\u043f\u0430\u043c\u0438 \u043c\u0430\u0442\u0440\u0438\u0446: \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0431\u043b\u043e\u0447\u043d\u044b\u0445\/\u0438\u043d\u043e\u0433\u0434\u0430 \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u044b\u0445\/\u0434\u0438\u0430\u0433\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445. \u0415\u0441\u0442\u044c \u0433\u043e\u0442\u043e\u0432\u044b\u0435 \u043f\u0430\u043a\u0435\u0442\u044b \u0434\u043b\u044f python, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0438\u0435 \u044d\u0442\u0443 \u043b\u043e\u0433\u0438\u043a\u0443 (<a href=\"https:\/\/docs.scipy.org\/doc\/scipy\/tutorial\/sparse.html\" rel=\"noopener noreferrer nofollow\">scipy.sparse<\/a>).<\/p>\n<p>\u0422\u0443\u0442 \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u043d\u0435\u0442 \u043a\u0430\u043a\u0438\u0445-\u0442\u043e \u0446\u0435\u043f\u043b\u044f\u044e\u0449\u0438\u0445 \u0438\u0434\u0435\u0439. \u041d\u043e \u0434\u0430\u043b\u044c\u0448\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0435\u0435!<\/p>\n<h2>Sparse List<\/h2>\n<p>Sparse list \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u0441\u043c\u044b\u0441\u043b\u0435. \u0412 \u043a\u0430\u043a\u043e\u043c? \u042f \u043f\u043e\u043a\u0430 \u043d\u0435 \u0441\u043a\u0430\u0436\u0443.<\/p>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0434\u0435\u043b\u0430\u0442\u044c \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u044e\u0449\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 (\u0432\u0441\u0442\u0430\u0432\u043a\u0430, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435) \u0437\u0430 <strong>O(1)<\/strong> \u0438 \u043d\u0435 \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u044e\u0449\u0438\u0435 (\u043e\u0431\u0445\u043e\u0434 \u0432 \u043b\u044e\u0431\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443) \u0437\u0430 <strong>O(n)<\/strong>. \u0418 \u0434\u043b\u044f \u0432\u0441\u0435\u0433\u043e \u044d\u0442\u043e\u0433\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u0430 \u043e\u0434\u043d\u0430 \u043b\u0438\u0448\u044c \u043d\u043e\u0434\u0430 \u0441\u043f\u0438\u0441\u043a\u0430 (\u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u0438\u0441\u043a\u0430\u0442\u044c \u0441\u043e\u0441\u0435\u0434\u043d\u044e\u044e, \u043a\u0430\u043a \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430. \u0421 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u043c\u044b \u0432\u044b\u043d\u0443\u0436\u0434\u0435\u043d\u044b \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043f\u043e \u0434\u0432\u0430 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u043d\u043e\u0434\u0443 (\u0432 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0440\u0435\u0430\u043b\u0438\u044f\u0445 \u044d\u0442\u043e \u0447\u0430\u0449\u0435 \u0432\u0441\u0435\u0433\u043e \u0446\u0435\u043b\u044b\u0445 16 \u0431\u0430\u0439\u0442!). \u041c\u043e\u0436\u043d\u043e \u043b\u0438 \u043a\u0430\u043a-\u0442\u043e \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0443\u0445\u0443\u0434\u0448\u0438\u0442\u044c \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u044b, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0432 \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438?<\/p>\n<p>\u0414\u0430! \u0410 \u0447\u0442\u043e, \u0435\u0441\u043b\u0438 \u043c\u044b \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u043f\u043e\u043b\u0442\u043e\u0440\u0430\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a? \u041d\u0443 \u0442\u043e \u0435\u0441\u0442\u044c \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u044c \u0443 \u043d\u0435\u0433\u043e \u0447\u0442\u043e-\u0442\u043e \u043c\u0435\u0436\u0434\u0443 \u0435\u0434\u0438\u043d\u0438\u0446\u0435\u0439 \u0438 \u0434\u0432\u043e\u0439\u043a\u043e\u0439. \u0414\u043e\u0441\u0442\u0438\u0447\u044c \u044d\u0442\u043e\u0433\u043e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0438\u043c\u0435\u044f \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u043e\u0434\u044b \u0431\u0443\u0434\u0443\u0442 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u043c\u0438.<\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043d\u043e\u0434 \u0441 \u0434\u0432\u0443\u043c\u044f \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f\u043c\u0438, \u043e\u0434\u0438\u043d \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043d\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0443\u044e \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u0443\u044e \u043d\u043e\u0434\u0443, \u0430 \u0434\u0440\u0443\u0433\u043e\u0439 \u2013 \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u043d\u043e\u0434\u0443. \u0422.\u043a. \u0440\u0430\u0437\u043c\u0435\u0440 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u201c\u043f\u043e\u0434\u0441\u043f\u0438\u0441\u043a\u0430\u201d \u043a\u043e\u043d\u0435\u0447\u0435\u043d \u0438 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d \u0437\u0430\u0440\u0430\u043d\u0435\u0435, \u043b\u044e\u0431\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u0441\u0451 \u0435\u0449\u0451 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 <strong>O(1)<\/strong>, \u043f\u0440\u044f\u043c\u043e \u043a\u0430\u043a \u0443 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 (\u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0441 \u0441\u0438\u043b\u044c\u043d\u043e \u0432\u044b\u0440\u043e\u0441\u0448\u0435\u0439 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439). \u0412\u0434\u0443\u043c\u0447\u0438\u0432\u044b\u0439 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044c \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u0441\u0442\u0430\u0432\u043e\u043a \u0432 \u043e\u0434\u0438\u043d \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u043f\u043e\u0434\u0441\u043f\u0438\u0441\u043e\u043a \u0438 \u0432\u0441\u0435 \u043d\u0430\u0448\u0438 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0438 \u0441\u043b\u043e\u043c\u0430\u044e\u0442\u0441\u044f! \u041d\u043e \u043d\u0438\u043a\u0442\u043e \u043d\u0435 \u043c\u0435\u0448\u0430\u0435\u0442 \u043d\u0430\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u044d\u0442\u0438\u0445 \u0441\u0430\u043c\u044b\u0445 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043f\u043e\u0434\u0441\u043f\u0438\u0441\u043a\u043e\u0432 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 (\u043d\u0430 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435 3, \u0435\u0441\u043b\u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u043d\u043e\u0434\u044b \u043d\u0430 \u043a\u043e\u043d\u0446\u0430\u0445). \u0422\u043e \u0435\u0441\u0442\u044c, \u0435\u0441\u043b\u0438 \u0432\u044b \u0443\u0436\u0435 \u0432\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u0443\u044e \u043d\u043e\u0434\u0443 \u043f\u043e\u0441\u043b\u0435 \u043e\u0434\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u043e\u0439, \u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0439\u0442\u0435 \u0435\u0451 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u043e\u0439 \u0438 \u043f\u043e\u043f\u0440\u0430\u0432\u044c\u0442\u0435 \u0441\u0441\u044b\u043b\u043a\u0438 \u0443 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043d\u0443\u0436\u043d\u043e \u0447\u0443\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0440\u0438\u0441\u0435\u0434\u0430\u043d\u0438\u0439 \u0432 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043d\u043e \u0432\u0441\u0451 \u0436\u0435 \u0432\u0430\u043c \u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0442\u044c \u0441 \u0441\u0430\u043c\u043e\u0433\u043e \u043d\u0430\u0447\u0430\u043b\u0430 \u0432\u0430\u0448\u0435\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0443\u044e \u043d\u043e\u0434\u0443 \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0439. \u0412\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u043e\u0439\u0442\u0438 \u0432\u043f\u0435\u0440\u0451\u0434 \u0438 \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u0442\u044c \u043f\u0435\u0440\u0432\u0443\u044e \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u0443\u044e \u043d\u043e\u0434\u0443, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0440\u044b\u0433\u043d\u0443\u0442\u044c \u043d\u0430\u0437\u0430\u0434. <\/p>\n<p>\u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0443 \u0432\u0430\u0441 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u043d\u043e\u0434\u044b \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u0434\u0440\u0443\u0433 \u043e\u0442 \u0434\u0440\u0443\u0433\u0430, \u043e\u043d \u0438 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u043c.<\/p>\n<p>\u041a\u0430\u043a \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u0441\u0430\u043c\u044b\u0439 \u201c\u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0441\u0442\u0438\u201d? \u0425\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u043e\u0442\u0432\u0435\u0442\u0430 \u043d\u0435\u0442. \u042d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043f\u0443\u0442\u0451\u043c \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0433\u0430\u0434\u0430\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u043f\u0438\u0441\u0430\u0442\u044c \u043f\u043e\u0434\u043e\u0431\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0441\u0438\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0449\u0435 (\u0434\u0430 \u0438 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 \u043c\u0435\u043d\u044c\u0448\u0435), \u0435\u0441\u043b\u0438 \u043d\u043e\u0434\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0447\u0435\u0440\u0435\u0434\u0443\u044e\u0442\u0441\u044f. \u041e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u0441\u043f\u0438\u0441\u043e\u043a \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u0438\u043b\u044c\u043d\u043e \u0434\u0435\u0448\u0435\u0432\u043b\u0435, \u0435\u0441\u043b\u0438 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u043d\u043e\u0434\u044b \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0442\u0441\u044f \u0447\u0430\u0449\u0435.<\/p>\n<p>\u0410 \u043a\u0430\u043a \u043f\u0430\u043c\u044f\u0442\u044c \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0442\u044c? \u0421 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u043a\u043e\u0434\u0430 \u043c\u043e\u0436\u0435\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u0436\u0435\u043b\u0430\u043d\u0438\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0447\u0442\u043e-\u0442\u043e \u0432\u0440\u043e\u0434\u0435 <code>union<\/code>\/<code>std::variant<\/code>, \u043d\u043e \u0442\u0430\u043a\u0438\u0435 \u0442\u0438\u043f\u044b \u0431\u0443\u0434\u0443\u0442 \u0438\u043c\u0435\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0438\u0437 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432. \u0422\u043e \u0435\u0441\u0442\u044c \u0432 \u0438\u0442\u043e\u0433\u0435 \u043c\u044b \u0432\u0441\u0451 \u0435\u0449\u0451 \u0438\u043c\u0435\u0435\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0441\u0440\u0430\u0432\u043d\u0438\u043c\u043e\u0435 \u0441 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u043c \u0441\u043f\u0438\u0441\u043a\u043e\u043c.<\/p>\n<p>\u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u043a\u0440\u0430\u0441\u0438\u0432\u043e \u043d\u0438\u043a\u0430\u043a. \u0412\u0430\u043c \u0432 \u043b\u044e\u0431\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0443\u0436\u043d\u043e \u0443\u043c\u0435\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u043d\u043e\u0434\u0430\u043c\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 (\u0442\u0443\u0442 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043c\u043e\u0447\u044c type-erasure \u0432 \u043a\u0430\u043a\u043e\u043c-\u0442\u043e \u0432\u0438\u0434\u0435). \u041f\u043b\u044e\u0441 \u043d\u0443\u0436\u043d\u043e \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0443\u044e \u043d\u043e\u0434\u0443 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c \u0432 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435, \u0447\u0442\u043e\u0431\u044b \u0431\u0440\u0430\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u043d\u043e\u0434\u0443\/\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u0431\u044b\u043b\u043e \u0443\u0434\u043e\u0431\u043d\u0435\u0435. \u041d\u043e \u0437\u0430\u0442\u043e \u0437\u0430\u0434\u0430\u0447\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u043a\u0430\u043a\u043e\u0439 \u0442\u0438\u043f \u0443 \u043d\u043e\u0434\u044b, \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u0430\u044f. \u0422.\u043a. \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u0432\u044b\u0440\u043e\u0432\u043d\u0435\u043d\u044b \u0432 \u043f\u0430\u043c\u044f\u0442\u0438, \u0443 \u0432\u0430\u0441 \u0432\u0441\u0435\u0433\u0434\u0430 \u0435\u0441\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043d\u0443\u043b\u0435\u0432\u044b\u0445 \u043c\u043b\u0430\u0434\u0448\u0438\u0445 \u0431\u0438\u0442\u043e\u0432. \u041a\u0430\u043a \u0440\u0430\u0437 \u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u0431\u0440\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0438\u0437 \u044d\u0442\u0438\u0445 \u0431\u0438\u0442\u043e\u0432 \u0438 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u0432 1, \u0435\u0441\u043b\u0438 \u043d\u043e\u0434\u0430 \u0438\u043c\u0435\u0435\u0442 \u0435\u0449\u0451 \u0438 \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0439 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c (\u0432\u0430\u0436\u043d\u043e \u043d\u0435 \u0437\u0430\u0431\u044b\u0442\u044c \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u0431\u0438\u0442 \u0432 \u043d\u043e\u043b\u044c \u043f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u044d\u0442\u043e\u043c\u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044e \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u043d\u043e\u0434\u0435). \u0410 \u0435\u0449\u0451 \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b, \u043a\u043e\u0433\u0434\u0430 \u0432\u044b \u0445\u043e\u0442\u0438\u0442\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u043d\u043e\u0434\u0443 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u0432 \u0434\u0440\u0443\u0433\u043e\u0439: \u0440\u0430\u0437 \u043e\u043d\u0430 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u0441\u0432\u043e\u0439 \u0442\u0438\u043f, \u0432\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u043d\u043e\u0432\u043e \u043e\u0441\u0432\u043e\u0431\u043e\u0434\u0438\u0442\u044c\/\u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c. \u041c\u043e\u0436\u043d\u043e \u043f\u0440\u0438 \u0436\u0435\u043b\u0430\u043d\u0438\u0438 \u0432 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043d\u043e\u0434\u0430\u0445 \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043d\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043f\u043e\u0447\u0442\u0438 \u043d\u0438\u043a\u0443\u0434\u0430 \u043d\u0435 \u0443\u0445\u043e\u0434\u044f\u0442 + \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u044b \u0442\u0443\u0442 \u0432\u043e\u043e\u0431\u0449\u0435 \u0447\u0442\u043e-\u0442\u043e \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u043c.<\/p>\n<p>\u0412\u043e\u0442 <a href=\"https:\/\/locklessinc.com\/downloads\/sparse.c\" rel=\"noopener noreferrer nofollow\">\u0441\u0441\u044b\u043b\u043a\u0430<\/a> \u043d\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e, \u0435\u0441\u043b\u0438 \u043e\u0447\u0435\u043d\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u043f\u043e\u0432\u0442\u044b\u043a\u0430\u0442\u044c.<\/p>\n<h2>Sparse Deque (sparque)<\/h2>\n<p>Sparse deque \u043d\u0435\u0434\u0430\u0432\u043d\u043e <a href=\"https:\/\/www.reddit.com\/r\/cpp\/comments\/1ad3yf4\/data_structure_introducing_sparque_the_sequence\/?share_id=-b0F1DwaTAiGoHeyIsj6-&amp;utm_medium=ios_app&amp;utm_name=iossmf&amp;utm_source=share&amp;utm_term=14\" rel=\"noopener noreferrer nofollow\">\u0432\u044b\u043b\u043e\u0436\u0438\u043b<\/a> \u043e\u0434\u0438\u043d \u0438\u0437 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u0439 reddit. \u041c\u044b \u043f\u0440\u043e\u0431\u0435\u0436\u0438\u043c\u0441\u044f \u043f\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043c, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c, \u043a\u0430\u043a \u0436\u0435 \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442.<\/p>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u044c, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 B-\u0434\u0435\u0440\u0435\u0432\u043e (\u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u043c\u043e\u0436\u043d\u043e <a href=\"https:\/\/habr.com\/ru\/companies\/otus\/articles\/459216\/\" rel=\"noopener noreferrer nofollow\">\u0442\u0443\u0442<\/a>). B-\u0434\u0435\u0440\u0435\u0432\u043e, \u0433\u0440\u0443\u0431\u043e \u0433\u043e\u0432\u043e\u0440\u044f, \u2013 \u044d\u0442\u043e m-\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430. \u0422\u043e \u0435\u0441\u0442\u044c \u043a\u0430\u0436\u0434\u0430\u044f \u043d\u043e\u0434\u0430 \u043c\u043e\u0436\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u0435\u0442\u0435\u0439. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0434\u0435\u043b\u0430\u0442\u044c \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0435 \u0434\u043b\u044f \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043d\u043e \u0441 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u043e\u043c \u043f\u043e \u0431\u041e\u043b\u044c\u0448\u0435\u043c\u0443 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044e. \u0410 \u0435\u0449\u0451 \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u043c\u043e\u0433\u0430\u0435\u0442 \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u0445\u043e\u0442\u044f \u0433\u043b\u0443\u0431\u0438\u043d\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043c\u0435\u043d\u044c\u0448\u0435, \u043d\u043e \u043d\u0435 \u0441\u0442\u043e\u0438\u0442 \u0437\u0430\u0431\u044b\u0432\u0430\u0442\u044c \u0438 \u043f\u0440\u043e \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u044e\u0449\u0443\u044e \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0443, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u0443\u044e \u0441 \u0431\u041e\u043b\u044c\u0448\u0438\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439. \u0412\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043e\u043d\u043e \u043a\u0430\u043a-\u0442\u043e \u0442\u0430\u043a:<\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u0414\u0430\u043b\u0435\u0435 \u0443 \u043d\u0430\u0441 \u0431\u044b\u0432\u0430\u044e\u0442 B+-\u0434\u0435\u0440\u0435\u0432\u044c\u044f. \u042d\u0442\u043e \u0442\u0430\u043a\u0438\u0435 B-\u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u0438\u043c\u0438\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0435 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432. \u041e\u043d\u0438 \u0445\u0440\u0430\u043d\u044f\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043b\u0438\u0441\u0442\u044c\u044f\u0445, \u0430 \u0432 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u043f\u0438\u0438 \u043a\u043b\u044e\u0447\u0435\u0439 (\u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0447\u0442\u043e-\u0442\u043e \u0432\u0440\u043e\u0434\u0435 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430):<\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u0412 \u043b\u0438\u0441\u0442\u044c\u044f\u0445 B+-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043e\u0431\u044b\u0447\u043d\u043e \u0445\u0440\u0430\u043d\u044f\u0442 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043b\u0438\u0441\u0442, \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u0430\u043c \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432\u0430\u0448\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0431\u0435\u0437 \u043f\u043e\u0434\u044a\u0451\u043c\u043e\u0432 \u0438 \u0441\u043f\u0443\u0441\u043a\u043e\u0432 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443.<\/p>\n<p>\u0418 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u043a\u0443\u0441\u043e\u0447\u0435\u043a, \u044d\u0442\u043e <a href=\"https:\/\/www.chiark.greenend.org.uk\/~sgtatham\/algorithms\/cbtree.html\" rel=\"noopener noreferrer nofollow\">counted B-\u0434\u0435\u0440\u0435\u0432\u043e<\/a> \u2013 B-\u0434\u0435\u0440\u0435\u0432\u043e, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u0435\u0431\u0451\u043d\u043a\u0430 \u043c\u044b \u0445\u0440\u0430\u043d\u0438\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u0435\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430:<\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u0412\u043e\u0442 sparque \u2013 \u044d\u0442\u043e counted B+-\u0434\u0435\u0440\u0435\u0432\u043e. \u0421 \u043e\u0433\u043e\u0432\u043e\u0440\u043e\u0447\u043a\u043e\u0439, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u0432 \u043a\u0430\u043d\u043e\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u043c B+-\u0434\u0435\u0440\u0435\u0432\u0435 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0438 \u043a\u043b\u044e\u0447\u0438, \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u0442\u0443\u0442 \u043c\u044b \u0445\u0440\u0430\u043d\u0438\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f (\u0432 \u043b\u0438\u0441\u0442\u044c\u044f\u0445). \u0412 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445 \u0443 \u043d\u0430\u0441 \u043e\u0441\u0442\u0430\u044e\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0438 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u0430\u043c\u0438 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043d\u0430 \u044d\u0442\u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u044f. \u0422\u0430\u043a \u0447\u0442\u043e \u043d\u0430 \u043d\u0438\u0436\u043d\u0435\u043c \u0443\u0440\u043e\u0432\u043d\u0435 (\u0432 \u043b\u0438\u0441\u0442\u044c\u044f\u0445) \u043d\u0430\u0448\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043a\u0430\u043a \u0441\u043f\u0438\u0441\u043e\u043a \u0431\u043b\u043e\u043a\u043e\u0432, \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439. \u0427\u0435\u043c \u043d\u0435 deque! \u041f\u0440\u0430\u0432\u0434\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0431\u043b\u043e\u043a \u0432 \u043b\u0438\u0441\u0442\u0435 \u044d\u0442\u043e \u0447\u0442\u043e-\u0442\u043e \u0432\u0440\u043e\u0434\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043e\u0436\u043d\u043e \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0441 \u043e\u0431\u043e\u0438\u0445 \u043a\u043e\u043d\u0446\u043e\u0432, \u0442\u0430\u043a \u0447\u0442\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u0431\u044b\u0441\u0442\u0440\u0435\u0435. <\/p>\n<p>\u0421\u0442\u041e\u044f\u0442 \u043e\u043d\u0438 \u0443 \u043d\u0430\u0441 \u0442\u0430\u043a:<\/p>\n<ul>\n<li>\n<p>\u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 <strong>O(log_m(n))<\/strong> \u2013 \u0442\u0430\u043a \u043a\u0430\u043a \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u043c, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432, \u043d\u0430\u0434\u043e \u0441\u043f\u0443\u0441\u0442\u0438\u0442\u0441\u044f \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0434\u043e \u0435\u0433\u043e \u043b\u0438\u0441\u0442\u0430. \u042d\u0442\u043e \u0434\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u0432 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u043c <code>std::deque<\/code> \u0441 \u0435\u0433\u043e <strong>O(1)<\/strong>, \u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0440\u043e\u0434\u0435 \u0442\u0440\u0435\u0439\u0434\u043e\u0444\u043e\u043c \u0434\u043b\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u0434\u0440\u0443\u0433\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439;<\/p>\n<\/li>\n<li>\n<p>\u0430\u0432\u0442\u043e\u0440 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442, \u0447\u0442\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u0430\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0432 \u043d\u0430\u0447\u0430\u043b\u043e\/\u043a\u043e\u043d\u0435\u0446 \u2013 <strong>O(1)<\/strong>. \u0417\u0432\u0443\u0447\u0438\u0442 \u0441\u043e\u043c\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0442.\u043a., \u043a\u0440\u043e\u043c\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u043d\u0443\u0436\u043d\u043e \u0435\u0449\u0451 \u043f\u0435\u0440\u0435\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043e\u0442 \u043b\u0438\u0441\u0442\u0430 \u0434\u043e \u043a\u043e\u0440\u043d\u044f \u0432\u0441\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432. \u0427\u0442\u043e \u043e\u043d \u0438 <a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h#L4143\" rel=\"noopener noreferrer nofollow\">\u0434\u0435\u043b\u0430\u0435\u0442 \u0432 push_back<\/a> \u0432 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h#L3713\" rel=\"noopener noreferrer nofollow\">update_counts_plus<\/a>. \u041d\u043e \u043c\u043e\u0436\u0435\u0442 \u044f \u0447\u0442\u043e-\u0442\u043e \u043d\u0435 \u043f\u043e\u043d\u044f\u043b \u00af\\_(\u30c4)_\/\u00af<\/p>\n<p>UPD: \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0435\u043d \u043e\u0442\u0432\u0435\u0442: <a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h#L91\" rel=\"noopener noreferrer nofollow\">https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h#L91<\/a><\/p>\n<\/li>\n<li>\n<p>\u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \u2013 <strong>O(m)<\/strong>, \u0433\u0434\u0435 m \u2013 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432 \u0431\u043b\u043e\u043a\u0435 \u043b\u0438\u0441\u0442\u0430;<\/p>\n<\/li>\n<li>\n<p>\u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u2013 <strong>O(n)<\/strong>.<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0430\u043c\u044f\u0442\u044c <strong>O(n)<\/strong>.<\/p>\n<p>\u041f\u043e\u0447\u0435\u043c\u0443 \u0430\u0432\u0442\u043e\u0440 \u0440\u0435\u0448\u0438\u043b \u043d\u0430\u0437\u0432\u0430\u0442\u044c \u044d\u0442\u0443 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0439, \u0434\u043e\u0441\u0442\u043e\u0432\u0435\u0440\u043d\u043e \u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e.<\/p>\n<p><a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/bench\/sparque\/README.md\" rel=\"noopener noreferrer nofollow\">\u0422\u0443\u0442<\/a> \u0435\u0441\u0442\u044c \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438 \u043e\u0442 \u0430\u0432\u0442\u043e\u0440\u0430 \u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441 \u0434\u0440\u0443\u0433\u0438\u043c\u0438 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430\u043c\u0438. \u0410 <a href=\"https:\/\/github.com\/gaujay\/indivi_collection\/blob\/main\/src\/indivi\/sparque.h\" rel=\"noopener noreferrer nofollow\">\u0442\u0443\u0442<\/a> \u2013 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f.<\/p>\n<h2>Sparse Set<\/h2>\n<p>\u0412\u0441\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u0436\u0435 \u0442\u0430\u043a\u043e\u0435 sparse set. <\/p>\n<p>Sparse set \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0432\u0441\u0451 \u0442\u0435 \u0436\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u0447\u0442\u043e \u0438 \u0434\u0440\u0443\u0433\u043e\u0439 \u0437\u043d\u0430\u043a\u043e\u043c\u044b\u0439 \u0432\u0430\u043c set. \u041d\u043e \u0441 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u043e\u043d \u0432\u0441\u0451 \u0436\u0435 \u0431\u043b\u0438\u0436\u0435 \u043a <code>std::vector&lt;bool><\/code>\/<code>std::bitset<\/code>. \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0434\u0432\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0438 \u0440\u0430\u0437\u043c\u0435\u0440:<\/p>\n<pre><code class=\"cpp\">template &lt;int R> struct SparseSet { int size_ = 0; int dense_[R]; int sparse_[R]; };<\/code><\/pre>\n<p><code>dense_<\/code> \u044d\u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439. <code>sparse_<\/code> \u0436\u0435 \u0445\u0440\u0430\u043d\u0438\u0442 \u0438\u043d\u0434\u0435\u043a\u0441 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 <code>dense_<\/code>, \u0442.\u0435. \u0435\u0441\u043b\u0438 <code>dense_[i] = v<\/code>, \u0442\u043e <code>sparse_[v] = i<\/code> (\u0432\u043c\u0435\u0441\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043c\u043e\u0436\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c). \u0422\u043e\u0433\u0434\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"cpp\">void Add(int val) { dense_[size_] = val; sparse_[val] = size_; ++size_; }<\/code><\/pre>\n<p>\u0414\u043b\u044f \u043f\u0443\u0449\u0435\u0433\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u043c\u044b \u0432\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u0432 \u043d\u0430\u0448 \u0441\u0435\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f: 3, 2, 5, 1, 0.<\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u041f\u0440\u0438 \u044d\u0442\u043e\u043c <code>size_<\/code> \u0440\u0430\u0432\u0435\u043d 5. \u0412 \u043f\u0443\u0441\u0442\u044b\u0445 \u043a\u043b\u0435\u0442\u043a\u0430\u0445 \u0443 \u043d\u0430\u0441 \u043d\u0438\u0447\u0435\u0433\u043e \u043b\u0435\u0436\u0438\u0442.\u00a0<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u0432 \u0441\u0432\u043e\u0451\u043c \u0441\u0435\u0442\u0435:<\/p>\n<pre><code class=\"cpp\">bool Contains(int val) { return sparse_[val] &lt; size_ &amp;&amp; dense_[sparse_[val]] == val; }<\/code><\/pre>\n<p>\u0415\u0441\u043b\u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u0434\u0432\u043e\u0439\u043a\u0438, \u0442\u043e \u043d\u0430\u0448\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0432\u0438\u0434:<\/p>\n<pre><code class=\"cpp\">sparse_[2] &lt; 5 &amp;&amp; dense_[sparse_[2]] == 2<\/code><\/pre>\n<p>\u0427\u0442\u043e \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e<\/p>\n<pre><code class=\"cpp\">1 &lt; 5 &amp;&amp; 2 == 2<\/code><\/pre>\n<p>\u0414\u0432\u043e\u0439\u043a\u0430 \u0432 \u0441\u0435\u0442\u0435!<\/p>\n<p>\u0414\u043b\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u0435\u0442\u0435 \u043d\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f, \u043c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u043c\u0443\u0441\u043e\u0440\u043d\u044b\u0435 \u044f\u0447\u0435\u0439\u043a\u0438 (\u0435\u0441\u043b\u0438 \u0440\u0430\u043d\u0435\u0435 \u0442\u0430\u043c \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043b\u0435\u0436\u0430\u043b\u043e) \u0438 \u0432\u0440\u044f\u0434 \u043b\u0438 \u043d\u0430\u0448\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043f\u0440\u043e\u0439\u0434\u0451\u0442 (\u0442\u0430\u043c \u0432\u0441\u0451-\u0442\u0430\u043a\u0438 \u043c\u0443\u0441\u043e\u0440). <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u0442\u043e \u0442\u0443\u0442 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0435 \u043f\u0440\u0438\u0441\u0435\u0434\u0430\u043d\u0438\u0435. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0443\u0434\u0430\u043b\u0438\u0442\u044c 0. \u0422\u0443\u0442 \u0432\u0441\u0451 \u043f\u0440\u043e\u0441\u0442\u043e. \u041d\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u0438 \u044d\u0442\u043e\u0442 \u043d\u043e\u043b\u044c \u0437\u0430\u0442\u0440\u0451\u0442\u0441\u044f \u043f\u0440\u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0432\u0441\u0442\u0430\u0432\u043a\u0435. \u0410 \u0435\u0441\u043b\u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 <code>dense_<\/code>? \u0422\u043e\u0433\u0434\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 <code>dense_<\/code> \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0438\u043d\u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0432 <code>sparse_<\/code>. \u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0441 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435\u043c \u0434\u0432\u043e\u0439\u043a\u0438: <\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043c\u043e\u0436\u043d\u043e \u0441\u043f\u043e\u043a\u043e\u0439\u043d\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c <code>size_<\/code>. \u0412 \u043a\u043e\u0434\u0435 \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u0442\u0430\u043a:<\/p>\n<pre><code class=\"cpp\"> bool Remove(int i) {    if (dense_[size_ - 1] != i) {      int last_element = dense_[size_ - 1];      dense_[sparse_[i]] = last_element;      sparse_[last_element] = sparse_[i];<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-367066","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/367066","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=367066"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/367066\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=367066"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=367066"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=367066"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}