{"id":366140,"date":"2024-05-21T02:53:02","date_gmt":"2024-05-21T02:53:02","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=366140"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-05-21T02:53:02","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=366140","title":{"rendered":"<span>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u043d\u0430 WL<\/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\/w1560\/getpro\/habr\/upload_files\/26f\/135\/cd3\/26f135cd32d673ae8ee1adb4ad1fa7c9.png\" alt=\"\u041f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043f\u0440\u043e\u0441\u0438\u0442 \u044f\u0434\u0440\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u043f\u043e\u0434 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a\" title=\"\u041f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043f\u0440\u043e\u0441\u0438\u0442 \u044f\u0434\u0440\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u043f\u043e\u0434 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a\" width=\"800\" height=\"400\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/26f\/135\/cd3\/26f135cd32d673ae8ee1adb4ad1fa7c9.png\"\/><\/p>\n<div><figcaption><em>\u041f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043f\u0440\u043e\u0441\u0438\u0442 \u044f\u0434\u0440\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u043f\u043e\u0434 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a<\/em><\/figcaption><\/div>\n<\/figure>\n<p>\u042d\u0442\u043e \u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0435\u043d\u0438\u0435 \u043c\u043e\u0435\u0439 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0438, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u043b\u0430 <a href=\"https:\/\/habr.com\/ru\/articles\/787784\/\" rel=\"noopener noreferrer nofollow\">\u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u043d\u0430 Wolfram Language<\/a>. \u041d\u0430 \u044d\u0442\u043e\u0442 \u0440\u0430\u0437 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0434\u0435\u043b\u0430\u0442\u044c \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a. \u0413\u0434\u0435-\u0442\u043e \u0435\u0433\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043f\u0438\u0441\u043e\u043a \u043b\u0438\u0431\u043e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043c\u0430\u0441\u0441\u0438\u0432. \u0412 C# \u044d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u0442\u0438\u043f\u043e\u043c <code>List&lt;T><\/code>, \u0430 \u0432 Java \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0445\u043e\u0436\u0438\u043c \u043a\u043b\u0430\u0441\u0441\u043e\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f <code>ArrayList<\/code>, \u0445\u043e\u0442\u044f \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044f \u043f\u043e\u043c\u043d\u044e \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0435\u0433\u043e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043c\u0430\u0441\u0441\u0438\u0432. <\/p>\n<p>\u0426\u0435\u043b\u044c \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 &#8212; \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0435\u0439 \u0438 \u0442\u0440\u044e\u043a\u043e\u0432 \u044f\u0437\u044b\u043a\u0430 Wolfram. \u0410 \u0442\u0430\u043a \u0436\u0435 \u044d\u0442\u043e \u0440\u0443\u043a\u043e\u0432\u043e\u0434\u0441\u0442\u0432\u043e \u043f\u043e \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044e \u0441\u0432\u043e\u0438\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u044d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043b\u0435\u0437\u043d\u0430 \u0442\u0435\u043c, \u0447\u0442\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u0438\u0437\u0443\u0447\u0430\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0438 \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445. <\/p>\n<p>\u041d\u0438\u0436\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430\/\u0441\u043f\u0438\u0441\u043a\u0430 \u043d\u0430 <em>Wolfram Language<\/em>.<\/p>\n<h2>\u041d\u0435\u043c\u043d\u043e\u0433\u043e \u043e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0441\u043f\u0438\u0441\u043a\u0435<\/h2>\n<p>\u041a\u0430\u043a \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u044d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u0445\u043e\u0436\u0430 \u043d\u0430 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432, \u0441 \u0442\u0435\u043c \u043e\u0442\u043b\u0438\u0447\u0438\u0435\u043c, \u0447\u0442\u043e \u0443 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0440\u0430\u0437\u043c\u0435\u0440 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439, \u0430 \u0443 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u043e\u043d \u043c\u043e\u0436\u0435\u0442 \u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f. \u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0432\u043e\u0442 \u0438 \u0432\u0441\u0435. \u0412\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0435\u0433\u043e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 &#8212; \u044d\u0442\u043e \u0443\u0436\u0435 \u0432\u043e\u043f\u0440\u043e\u0441 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438. \u041a\u0430\u043a\u0438\u043c\u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c\u0438 \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043c\u0430\u0441\u0441\u0438\u0432: <\/p>\n<ul>\n<li>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432 \u043d\u0430\u0447\u0430\u043b\u043e \u0438 \u043a\u043e\u043d\u0435\u0446 \u0437\u0430 <strong>O(1)<\/strong><\/p>\n<\/li>\n<li>\n<p>\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438\u0437 \u043d\u0430\u0447\u0430\u043b\u0430 \u0438 \u043a\u043e\u043d\u0446\u0430 \u0437\u0430 <strong>O(1)<\/strong><\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0437\u0430 <strong>O(1)<\/strong><\/p>\n<\/li>\n<li>\n<p>\u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0443 \u0437\u0430 <strong>O(n)<\/strong> \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0438\u0441\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u0437\u0430 <strong>O(n)<\/strong><\/p>\n<\/li>\n<\/ul>\n<p>\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u0443\u0434\u0435\u0442 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0442\u044c \u044d\u0442\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c \u043c\u044b \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u043f\u0440\u044f\u043c\u043e \u0441\u0435\u0439\u0447\u0430\u0441! <\/p>\n<h2>\u0421\u043f\u0438\u0441\u043e\u043a<\/h2>\n<p>\u0412 Wolfram Language \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u043f\u0438\u0441\u043e\u043a, \u0442.\u0435. <code>List<\/code>. \u042d\u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043b\u044e\u0431\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u0438 \u0438\u043c\u0435\u0435\u0442 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0430\u0437\u043c\u0435\u0440. \u041d\u043e \u0434\u0435\u043b\u043e \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0432 \u043d\u0435\u043c \u043d\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u044b. \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u044d\u0442\u043e!<\/p>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430: <\/p>\n<pre><code class=\"haskell\">ClearAll[\"`*\"];   $HistoryLength = 0; <\/code><\/pre>\n<p>\u041f\u0443\u0441\u0442\u043e\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0441\u043e\u0437\u0434\u0430\u0435\u0442\u0441\u044f \u0432\u043e\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"haskell\">list1 = {}; <\/code><\/pre>\n<p>\u0414\u043b\u044f \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0441\u043f\u0438\u0441\u043a\u0430 \u0434\u0430\u043d\u043d\u044b\u043c\u0438 \u043c\u044b \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u0441\u0432\u043e\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e. \u0412 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043e\u043d\u0430 \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0434\u043b\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430:<\/p>\n<pre><code class=\"vala\">SetAttributes[append, HoldFirst];   append[list_, item_] :=  list = Append[list, item]; <\/code><\/pre>\n<p>\u0417\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0435\u0433\u043e \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u0432\u0440\u0435\u043c\u044f, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430: <\/p>\n<pre><code class=\"haskell\">appendTime =  Table[{i, AbsoluteTiming[append[list1, i]][[1]]}, {i, 1, 5000}];<\/code><\/pre>\n<p>\u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043d\u0435\u0442, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u0435\u0435 \u0441\u0430\u043c\u0438: <\/p>\n<pre><code class=\"haskell\">SetAttributes[remove, HoldFirst];   remove[list_Symbol] :=  list = Delete[list, -1]; <\/code><\/pre>\n<p>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0435\u043c \u0432\u0440\u0435\u043c\u044f \u044d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430. \u041e\u0447\u0438\u0449\u0430\u0435\u043c, \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u043e \u043d\u043e\u0432\u043e\u0439 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u0440\u0430\u0437\u0443 \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e. <\/p>\n<pre><code class=\"haskell\">list1 = {};   removeTime = Table[ { i,  append[list1, i];  append[list1, i];  AbsoluteTiming[remove[list1]][[1]] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u041f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <code>part<\/code>. \u0411\u0443\u0434\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0438 \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u0441\u0441\u0438\u0432\u0430: <\/p>\n<pre><code class=\"haskell\">part[list_, i_] :=  list[[i]];   list1 = {};   partTime =  Table[ { i,  append[list1, i];  With[{j = RandomInteger[{1, i}]},   AbsoluteTiming[part[list1, j]][[1]] ] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e &#8212; \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a \u0436\u0435 \u043a\u0430\u043a \u0438 \u0441 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435\u043c \u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c: <\/p>\n<pre><code class=\"haskell\">SetAttributes[insert, HoldFirst];   insert[list_, item_, i_] :=  list = Insert[list, item, i];   list1 = {1};   insertTime =  Table[ { i,  With[{j = RandomInteger[{1, i}]},   AbsoluteTiming[insert[list1, i, j]][[1]] ] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u0418 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 &#8212; \u043f\u043e\u0438\u0441\u043a. \u0411\u0443\u0434\u0435\u043c \u043a\u0430\u043a \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c \u043f\u0443\u043d\u043a\u0442\u0435 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e, \u0430 \u0437\u0430\u0442\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u0435\u0433\u043e \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <code>position<\/code>:<\/p>\n<pre><code class=\"haskell\">position[list_, item_] :=  Position[list, item];   list1 = {1};   positionTime =  Table[ { i,  With[{j = RandomInteger[{1, i}]},   insert[list1, i, j];  AbsoluteTiming[position[list1, i]][[1]] ] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u041f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u0433\u0440\u0430\u0444\u0438\u043a \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430: <\/p>\n<pre><code class=\"haskell\">ListPlot[{appendTime, removeTime, insertTime},  PlotLegends -> {\"append\", \"remove\", \"insert\"},  ImageSize -> Large,  PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/fbc\/6b6\/a49\/fbc6b6a49daca9adeb2887f2dc7200d8.png\" alt=\"\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430\" title=\"\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430\" width=\"786\" height=\"448\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fbc\/6b6\/a49\/fbc6b6a49daca9adeb2887f2dc7200d8.png\"\/><\/p>\n<div><figcaption><em>\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430<\/em><\/figcaption><\/div>\n<\/figure>\n<pre><code class=\"haskell\">ListPlot[{positionTime},  PlotLegends -> {\"position\"},  ImageSize -> Large,  PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/58a\/5d3\/132\/58a5d31323992279d53e0da0425d88ad.png\" alt=\"\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430. \u0412\u0440\u0435\u043c\u044f \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043b \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0433\u0440\u0430\u0444\u0438\u043a\" title=\"\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430. \u0412\u0440\u0435\u043c\u044f \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043b \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0433\u0440\u0430\u0444\u0438\u043a\" width=\"788\" height=\"453\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/58a\/5d3\/132\/58a5d31323992279d53e0da0425d88ad.png\"\/><\/p>\n<div><figcaption><em>\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430. \u0412\u0440\u0435\u043c\u044f \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043b \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0433\u0440\u0430\u0444\u0438\u043a<\/em><\/figcaption><\/div>\n<\/figure>\n<pre><code class=\"haskell\">ListPlot[{partTime},   PlotLegends -> {\"part\"},   ImageSize -> Large,   PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/8a6\/3dd\/3ee\/8a63dd3eea091487951f1238dafdb359.png\" alt=\"\u0425\u043e\u0442\u044c \u0442\u0443\u0442 \u0432\u0441\u0435 \u0445\u043e\u0440\u043e\u0448\u043e! \u0414\u043e\u0441\u0442\u0443\u043f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0437\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u041d\u0430 \u0444\u043e\u043d\u0435 \u0434\u0440\u0443\u0433\u0438\u0445 \u0433\u0440\u0430\u0444\u0438\u043a\u043e\u0432 \u044d\u0442\u043e\u0442 \u0431\u0443\u0434\u0435\u0442 \u0441\u043b\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u0441 \u043e\u0441\u044c\u044e X, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d \u0442\u043e\u0436\u0435 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\" title=\"\u0425\u043e\u0442\u044c \u0442\u0443\u0442 \u0432\u0441\u0435 \u0445\u043e\u0440\u043e\u0448\u043e! \u0414\u043e\u0441\u0442\u0443\u043f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0437\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u041d\u0430 \u0444\u043e\u043d\u0435 \u0434\u0440\u0443\u0433\u0438\u0445 \u0433\u0440\u0430\u0444\u0438\u043a\u043e\u0432 \u044d\u0442\u043e\u0442 \u0431\u0443\u0434\u0435\u0442 \u0441\u043b\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u0441 \u043e\u0441\u044c\u044e X, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d \u0442\u043e\u0436\u0435 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\" width=\"763\" height=\"450\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8a6\/3dd\/3ee\/8a63dd3eea091487951f1238dafdb359.png\"\/><\/p>\n<div><figcaption><em>\u0425\u043e\u0442\u044c \u0442\u0443\u0442 \u0432\u0441\u0435 \u0445\u043e\u0440\u043e\u0448\u043e! \u0414\u043e\u0441\u0442\u0443\u043f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0437\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u041d\u0430 \u0444\u043e\u043d\u0435 \u0434\u0440\u0443\u0433\u0438\u0445 \u0433\u0440\u0430\u0444\u0438\u043a\u043e\u0432 \u044d\u0442\u043e\u0442 \u0431\u0443\u0434\u0435\u0442 \u0441\u043b\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u0441 \u043e\u0441\u044c\u044e X, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d \u0442\u043e\u0436\u0435 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e<\/em><\/figcaption><\/div>\n<\/figure>\n<p>\u0427\u0442\u043e \u043c\u044b \u0438\u043c\u0435\u0435\u043c? \u0412\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u0432\u044b\u0448\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0437\u0430 <strong>O(n)<\/strong> \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0437\u0430 <strong>O(1)<\/strong>.<\/p>\n<h2>\u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n<p>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u0440\u0438\u0441\u0442\u0443\u043f\u0438\u043c \u043a \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430! \u041d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b 3 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0438\u0437 \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u0442\u0430\u0442\u044c\u0438 (\u043a\u0440\u043e\u043c\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0438 \u043f\u043e\u0438\u0441\u043a\u0430) \u0438\u043c\u0435\u043b\u0438 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <strong>O(1)<\/strong>. \u041a\u0430\u043a \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c? \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442:<\/p>\n<ul>\n<li>\n<p>\u0420\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u0447\u0438\u0441\u043b\u043e \u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/p>\n<\/li>\n<li>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0437\u0430\u043f\u0438\u0441\u044c\u044e \u0432 \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e, \u0430 \u044d\u0442\u043e \u0431\u044b\u0441\u0442\u0440\u043e<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0437\u0430\u043f\u0438\u0441\u044c \u043d\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044e\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e + 1, \u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430<\/p>\n<\/li>\n<li>\n<p>\u041a\u043e\u0433\u0434\u0430 \u0447\u0438\u0441\u043b\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u0435\u043d\u044c\u0448\u0435 \u0447\u0435\u043c \u0444\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 &#8212; \u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0440\u0438\u0441\u0442\u0443\u043f\u0438\u043c \u043a \u0435\u0433\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430 &#8212; \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u0441\u0432\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b, \u0437\u0430\u0434\u0430\u0434\u0438\u043c \u0435\u043c\u0443 \u0430\u0442\u0440\u0438\u0431\u0443\u0442 <code>HoldFirst<\/code> (\u043e\u043d \u043f\u043e\u043c\u043e\u0436\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0441\u0441\u044b\u043b\u043a\u0443) \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430:<\/p>\n<pre><code class=\"haskell\">ClearAll[DynamicList];   SetAttributes[DynamicList, HoldFirst]  createDynamicList[] :=  With[{ref = Unique[\"DYNAMICLIST`$\"]},  ref = &lt;| \"Data\" -> {0},  \"Length\" -> 0,     (*\u0447\u0438\u0441\u043b\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432*) \"Capacity\" -> 1    (*\u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u0439 \u0440\u0430\u0437\u043c\u0435\u0440*) |>;  DynamicList[ref] ]; <\/code><\/pre>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u043d\u0430 \u043d\u0435\u043c \u0442\u0435 5 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0438 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 <code>List<\/code>. \u042f \u0441\u043e\u0437\u043d\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0435 \u0431\u0443\u0434\u0443 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c <code>prepend<\/code> \u0434\u043b\u044f \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0432 \u043d\u0430\u0447\u0430\u043b\u043e \u0438 <code>pop<\/code> \u0434\u043b\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438\u0437 \u043d\u0430\u0447\u0430\u043b\u0430, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u043d\u0438 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u0439 <code>append<\/code> \u0438 <code>remove<\/code> \u0442\u043e\u043b\u044c\u043a\u043e \u0441 \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u043a\u043e\u043d\u0446\u0430. <\/p>\n<p>\u0412 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u044f \u0443\u0431\u0435\u0440\u0443 \u0430\u0442\u0440\u0438\u0431\u0443\u0442, \u0442\u0430\u043a \u043a\u0430\u043a \u0441\u0435\u0439\u0447\u0430\u0441 \u043e\u043d \u043d\u0430\u043c \u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0438 \u0441\u043e\u0437\u0434\u0430\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u0441\u0430\u043c\u0438\u043c \u0442\u0438\u043f\u043e\u043c <code>DynamicList<\/code>:<\/p>\n<pre><code class=\"haskell\">ClearAttributes[append, HoldFirst]  DynamicList \/: append[DynamicList[ref_Symbol], item_] :=  With[{len = ref[\"Length\"], capacity = ref[\"Capacity\"]},  If[len === capacity,  ref[\"Data\"] = Join[ref[\"Data\"], ConstantArray[0, len]];  ref[\"Capacity\"] = capacity * 2;  ];  ref[\"Length\"] = len + 1;  ref[[\"Data\", len + 1]] = item ]; <\/code><\/pre>\n<p>\u042d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0435\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u043d\u044b\u0439. \u0414\u0435\u043b\u043e \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0438 \u0441\u043f\u0438\u0441\u043a\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0447\u0430\u0441\u0442\u043e\u0442\u0430 \u0432\u044b\u0437\u043e\u0432\u0430 \u044d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 \u0438 \u043c\u0435\u043d\u044c\u0448\u0435, \u0442.\u0435. \u0441\u043d\u0438\u0436\u0430\u0442\u044c\u0441\u044f \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u0438. \u0425\u043e\u0442\u044c \u0438 \u043e\u0434\u0438\u043d \u0432\u044b\u0437\u043e\u0432 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0441\u043f\u0438\u0441\u043a\u0430 &#8212; \u044d\u0442\u043e &#171;\u0442\u044f\u0436\u0435\u043b\u0430\u044f&#187; \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f, \u043d\u043e \u0434\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0441\u043f\u0438\u0441\u043a\u043e\u0432 \u043e\u043d\u0430 \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0434\u043a\u043e, \u0447\u0442\u043e \u043d\u0435 \u0432\u043b\u0438\u044f\u0435\u0442 \u043d\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c. <\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u0436\u0435 \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043c\u0435\u0442\u043e\u0434 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438\u0437 \u043a\u043e\u043d\u0446\u0430: <\/p>\n<pre><code class=\"haskell\">ClearAttributes[remove, HoldFirst];   DynamicList \/: remove[DynamicList[ref_Symbol]] :=  With[{ len = ref[\"Length\"],  capacity = ref[\"Capacity\"],  item = ref[[\"Data\", ref[\"Length\"]]] },  If[len === capacity \/ 2,  ref[\"Data\"] = ref[[\"Data\", ;; len \/ 2]];  ref[\"Capacity\"] = capacity \/ 2;  ];  ref[\"Length\"] = len - 1;  ref[[\"Data\", len]] = 0;  item ]; <\/code><\/pre>\n<p>\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0431\u0443\u0434\u0435\u0442 \u0447\u0443\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u0435\u0435: <\/p>\n<pre><code class=\"haskell\">ClearAttributes[insert, HoldFirst];   DynamicList \/: insert[DynamicList[ref_Symbol], item_, i_Integer] :=  With[{len = ref[\"Length\"], capacity = ref[\"Capacity\"]},  If[len === capacity,  ref[\"Data\"] = Join[ref[\"Data\"], ConstantArray[0, len]];  ref[\"Capacity\"] = capacity * 2;   ];  ref[\"Length\"] = len + 1;  ref[[\"Data\"]] = Join[ref[[\"Data\", 1 ;; i - 1]], {item}, ref[[\"Data\", i ;; -2]]];  item ]; <\/code><\/pre>\n<p>\u0418 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0438 \u0447\u0430\u0441\u0442\u0438: <\/p>\n<pre><code class=\"haskell\">DynamicList \/: position[DynamicList[ref_Symbol], item_] :=  Position[ref[[\"Data\", 1 ;; ref[\"Length\"]]], item]; <\/code><\/pre>\n<pre><code class=\"haskell\">DynamicList \/: part[DynamicList[ref_Symbol], i_Integer] :=  If[Abs[i] &lt;= ref[\"Length\"],      ref[[\"Data\", i]],      Message[General::partw, i, DynamicList[ref]] ]; <\/code><\/pre>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 &#8212; \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439:<\/p>\n<pre><code class=\"haskell\">DynamicList \/: Normal[DynamicList[ref_Symbol]] :=  ref[[\"Data\", 1 ;; ref[\"Length\"]]];   DynamicList \/: DeleteObject[DynamicList[ref_Symbol]] :=  ClearAll[ref]; <\/code><\/pre>\n<h2>\u041f\u043b\u0430\u0448\u043a\u0430 \u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/h2>\n<p>\u042f \u043f\u043e \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u0438 \u043f\u0440\u0438\u0432\u0435\u0434\u0443 \u043a\u043e\u0434, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0442\u044c \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0432 \u0432\u0438\u0434\u0435 <code>SummaryBox<\/code>. \u041d\u0438\u043a\u0430\u043a\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u044d\u0442\u0430 \u0448\u0442\u0443\u043a\u0430 \u0437\u0430 \u0441\u043e\u0431\u043e\u0439 \u043d\u0435 \u043a\u0440\u043e\u0435\u0442: <\/p>\n<pre><code class=\"haskell\">$dynamicListIcon = Import[\"https:\/\/wolfr.am\/1jEFx2BBO\"];  DynamicList \/: MakeBoxes[object: DynamicList[ref_Symbol],  form: (StandardForm | TraditionalForm)] :=  Module[{above, below},  above = { {BoxForm`SummaryItem[{\"Ref: \", Defer[ref]}], SpanFromLeft},  {BoxForm`SummaryItem[{\"Length: \", ref[\"Length\"]}], SpanFromLeft},  {BoxForm`SummaryItem[{\"Capacity: \", ref[\"Capacity\"]}], SpanFromLeft} };  below = {};   BoxForm`ArrangeSummaryBox[ DynamicList,  object,  $dynamicListIcon,  above,  below,  form,  \"Interpretable\" -> Automatic ] ];<\/code><\/pre>\n<p>\u0418 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432. \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a: <\/p>\n<pre><code class=\"haskell\">dynamicList1 = createDynamicList[]<\/code><\/pre>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b: <\/p>\n<pre><code class=\"haskell\">append[dynamicList1, #]&amp; \/@ Range[10]<\/code><\/pre>\n<p>\u0423\u0434\u0430\u043b\u044f\u0435\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e: <\/p>\n<pre><code class=\"haskell\">Do[remove[dynamicList1], {3}]<\/code><\/pre>\n<p>\u0412\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430:<\/p>\n<pre><code class=\"haskell\">Normal[dynamicList1]<\/code><\/pre>\n<p>\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430: <\/p>\n<pre><code class=\"haskell\">DeleteObject[dynamicList1]<\/code><\/pre>\n<p>\u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0447\u0442\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 \u043f\u0443\u0441\u0442\u043e:<\/p>\n<pre><code class=\"haskell\">dynamicList1[[1]]<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/371\/026\/29d\/37102629de79acfabee11d5c2a806068.png\" alt=\"\u041a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0432 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441\u0435 \u0431\u043b\u043e\u043a\u043d\u043e\u0442\u0430\" title=\"\u041a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0432 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441\u0435 \u0431\u043b\u043e\u043a\u043d\u043e\u0442\u0430\" width=\"848\" height=\"855\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/371\/026\/29d\/37102629de79acfabee11d5c2a806068.png\"\/><\/p>\n<div><figcaption><em>\u041a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0432 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441\u0435 \u0431\u043b\u043e\u043a\u043d\u043e\u0442\u0430<\/em><\/figcaption><\/div>\n<\/figure>\n<h2>\u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/h2>\n<p>\u041d\u0443 \u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0442\u0435\u0441\u0442\u043e\u0432. \u0422\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u043f\u0435\u0440\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438 \u0432\u0441\u0435 \u0442\u0435 \u0436\u0435 \u0441\u0430\u043c\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043d\u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0441\u043f\u0438\u0441\u043a\u0435, \u0442\u043e \u043a\u043e\u0434 \u0434\u043b\u044f \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u0431\u0435\u0437 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f. \u041d\u0443\u0436\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e <code>list1<\/code> \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430 <code>dynamicList1<\/code>:<\/p>\n<pre><code class=\"haskell\">DeleteObject[dynamicList1];   dynamicList1 = createDynamicList[];   appendTime =  Table[{i, AbsoluteTiming[append[dynamicList1, i]][[1]]}, {i, 1, 5000}];   DeleteObject[dynamicList1];   dynamicList1 = createDynamicList[];   removeTime = Table[ { i,  append[dynamicList1, i];  append[dynamicList1, i];  AbsoluteTiming[remove[dynamicList1]][[1]] },  {i, 1, 5000} ]; <\/code><\/pre>\n<p>\u0418 \u0433\u0440\u0430\u0444\u0438\u043a: <\/p>\n<pre><code class=\"haskell\">ListPlot[{appendTime, removeTime},  PlotLegends -> {\"append\", \"remove\"},  ImageSize -> Large,  PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/b83\/7e2\/362\/b837e2362c23e77a8d5d57af32c4fad4.png\" alt=\"\u0421 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u0447\u0438\u0441\u043b\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u0440\u0435\u043c\u044f \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0435 \u0431\u043b\u0438\u0436\u0435 \u043a \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0435. \u0421\u0442\u0443\u043f\u0435\u043d\u044c\u043a\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0442 \u0441\u043e \u0441\u0442\u0435\u043f\u0435\u043d\u044f\u043c\u0438 \u0434\u0432\u043e\u0439\u043a\u0438: 2^10 ~ 1000, 2^11 ~ 2000, 2^12 ~ 4000\" title=\"\u0421 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u0447\u0438\u0441\u043b\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u0440\u0435\u043c\u044f \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0435 \u0431\u043b\u0438\u0436\u0435 \u043a \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0435. \u0421\u0442\u0443\u043f\u0435\u043d\u044c\u043a\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0442 \u0441\u043e \u0441\u0442\u0435\u043f\u0435\u043d\u044f\u043c\u0438 \u0434\u0432\u043e\u0439\u043a\u0438: 2^10 ~ 1000, 2^11 ~ 2000, 2^12 ~ 4000\" width=\"791\" height=\"448\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b83\/7e2\/362\/b837e2362c23e77a8d5d57af32c4fad4.png\"\/><\/p>\n<div><figcaption><em>\u0421 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u0447\u0438\u0441\u043b\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u0440\u0435\u043c\u044f \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0435 \u0431\u043b\u0438\u0436\u0435 \u043a \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0435. \u0421\u0442\u0443\u043f\u0435\u043d\u044c\u043a\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0442 \u0441\u043e \u0441\u0442\u0435\u043f\u0435\u043d\u044f\u043c\u0438 \u0434\u0432\u043e\u0439\u043a\u0438: 2^10 ~ 1000, 2^11 ~ 2000, 2^12 ~ 4000<\/em><\/figcaption><\/div>\n<\/figure>\n<p>\u0410 \u0432\u043e\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u043f\u043e\u0438\u0441\u043a\u0430 \u0438 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u043d\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u043b\u0438 \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c\u0441\u044f. \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c: <\/p>\n<pre><code class=\"haskell\">DeleteObject[dynamicList1];   dynamicList1 = createDynamicList[];   insertTime =  Table[ { i,  With[{j = RandomInteger[{1, i}]},   AbsoluteTiming[insert[dynamicList1, i, j]][[1]] ] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u0418 \u0433\u0440\u0430\u0444\u0438\u043a: <\/p>\n<pre><code class=\"haskell\">ListPlot[{insertTime},  PlotLegends -> {\"insert\"},  ImageSize -> Large,  PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/c56\/1d6\/d34\/c561d6d349786252227e23b54a0a2baa.png\" alt=\"\u041e \u0447\u0443\u0434\u043e! \u0414\u0430\u0436\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0441\u0442\u0430\u043b\u0430 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0435\u0435, \u0442\u0430\u043a \u043a\u0430\u043a \u0442\u0435\u043f\u0435\u0440\u044c \u043e\u043d\u0430 \u0440\u0430\u0441\u0442\u0435\u0442 \u0441\u0442\u0443\u043f\u0435\u043d\u0447\u0430\u0442\u043e!\" title=\"\u041e \u0447\u0443\u0434\u043e! \u0414\u0430\u0436\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0441\u0442\u0430\u043b\u0430 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0435\u0435, \u0442\u0430\u043a \u043a\u0430\u043a \u0442\u0435\u043f\u0435\u0440\u044c \u043e\u043d\u0430 \u0440\u0430\u0441\u0442\u0435\u0442 \u0441\u0442\u0443\u043f\u0435\u043d\u0447\u0430\u0442\u043e!\" width=\"772\" height=\"444\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c56\/1d6\/d34\/c561d6d349786252227e23b54a0a2baa.png\"\/><\/p>\n<div><figcaption><em>\u041e \u0447\u0443\u0434\u043e! \u0414\u0430\u0436\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0441\u0442\u0430\u043b\u0430 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0435\u0435, \u0442\u0430\u043a \u043a\u0430\u043a \u0442\u0435\u043f\u0435\u0440\u044c \u043e\u043d\u0430 \u0440\u0430\u0441\u0442\u0435\u0442 \u0441\u0442\u0443\u043f\u0435\u043d\u0447\u0430\u0442\u043e!<\/em><\/figcaption><\/div>\n<\/figure>\n<p>\u0411\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u043f\u0435\u0440\u0435\u0441\u043e\u0437\u0434\u0430\u0435\u0442 \u0441\u043f\u0438\u0441\u043e\u043a \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u043d\u044b, \u0442\u043e \u043f\u0440\u0438 \u043e\u0434\u043d\u043e\u043c \u0438 \u0442\u043e\u0439 \u0436\u0435 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0435 <code>\"Capacity\"<\/code> \u0432\u0440\u0435\u043c\u044f \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439, \u043d\u043e \u0432\u0441\u0435 \u0436\u0435 \u043e\u043d\u043e \u0440\u0430\u0441\u0442\u0435\u0442 \u0441\u0442\u0443\u043f\u0435\u043d\u0447\u0430\u0442\u043e. <\/p>\n<p>\u041d\u0443 \u0438 \u043f\u043e\u0438\u0441\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b\u043b \u0441\u0430\u043c\u044b\u043c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u044b\u043c: <\/p>\n<pre><code class=\"haskell\">DeleteObject[dynamicList1];   dynamicList1 = createDynamicList[];   positionTime =  Table[ { i,  With[{j = RandomInteger[{1, i}]},   insert[dynamicList1, i, j];  AbsoluteTiming[position[dynamicList1, i]][[1]] ] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u0413\u0440\u0430\u0444\u0438\u043a: <\/p>\n<pre><code class=\"haskell\">ListPlot[{positionTime},  PlotLegends -> {\"position\"},  ImageSize -> Large,  PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/bf6\/f51\/09c\/bf6f5109c9f0a2207c433ba905b930ef.png\" alt=\"\u0422\u0443\u0442 \u0431\u0435\u0437 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439\" title=\"\u0422\u0443\u0442 \u0431\u0435\u0437 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439\" width=\"789\" height=\"452\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bf6\/f51\/09c\/bf6f5109c9f0a2207c433ba905b930ef.png\"\/><\/p>\n<div><figcaption><em>\u0422\u0443\u0442 \u0431\u0435\u0437 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439<\/em><\/figcaption><\/div>\n<\/figure>\n<p>\u0420\u0435\u043c\u0430\u0440\u043a\u0430 \u043a\u0430\u0441\u0430\u0442\u0435\u043b\u044c\u043d\u043e <code>Position<\/code>. \u0414\u0435\u043b\u043e \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u044d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0438\u0449\u0435\u0442 \u0432\u0441\u0435 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u0430 \u0438 \u0434\u043e \u043a\u043e\u043d\u0446\u0430 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. <\/p>\n<h2>\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h2>\n<p>\u041d\u0430 \u044d\u0442\u043e\u043c \u043d\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f \u0432\u0441\u0435, <strong>\u0432\u0441\u0435\u043c \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435<\/strong>! \u041d\u0430\u0434\u0435\u044e\u0441\u044c, \u0434\u043b\u044f \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0432\u0448\u0438\u0445 \u044d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0439 \u0438 \u0432\u044b \u0443\u0437\u043d\u0430\u043b\u0438 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u043e \u044f\u0437\u044b\u043a\u0435 Wolfram \u0438 \u043b\u0443\u0447\u0448\u0435 \u043f\u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u043b\u0438\u0441\u044c \u0441 \u0442\u0435\u043c, \u043a\u0430\u043a \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0442\u0441\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445, \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0414\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0421\u043f\u0438\u0441\u043e\u043a. <\/p>\n<p>\u0411\u043b\u043e\u043a\u043d\u043e\u0442 \u0441 \u043a\u043e\u0434\u043e\u043c \u0438\u0437 \u0441\u0442\u0430\u0442\u044c\u0438 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u0441\u043a\u0430\u0447\u0430\u0442\u044c \u0438\u0437 \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u044f \u043d\u0430 <a href=\"https:\/\/github.com\/KirillBelovTest\/kirillbelovtest.github.io\/blob\/main\/DynamicList.nb\" rel=\"noopener noreferrer nofollow\"><em>GitHub<\/em><\/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\/788460\/\"> https:\/\/habr.com\/ru\/articles\/788460\/<\/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><em>\u041f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043f\u0440\u043e\u0441\u0438\u0442 \u044f\u0434\u0440\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u043f\u043e\u0434 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a<\/em><\/figcaption><\/div>\n<\/figure>\n<p>\u042d\u0442\u043e \u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0435\u043d\u0438\u0435 \u043c\u043e\u0435\u0439 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0438, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u043b\u0430 <a href=\"https:\/\/habr.com\/ru\/articles\/787784\/\" rel=\"noopener noreferrer nofollow\">\u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u043d\u0430 Wolfram Language<\/a>. \u041d\u0430 \u044d\u0442\u043e\u0442 \u0440\u0430\u0437 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0434\u0435\u043b\u0430\u0442\u044c \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a. \u0413\u0434\u0435-\u0442\u043e \u0435\u0433\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043f\u0438\u0441\u043e\u043a \u043b\u0438\u0431\u043e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043c\u0430\u0441\u0441\u0438\u0432. \u0412 C# \u044d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u0442\u0438\u043f\u043e\u043c <code>List&lt;T><\/code>, \u0430 \u0432 Java \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0445\u043e\u0436\u0438\u043c \u043a\u043b\u0430\u0441\u0441\u043e\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f <code>ArrayList<\/code>, \u0445\u043e\u0442\u044f \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044f \u043f\u043e\u043c\u043d\u044e \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0435\u0433\u043e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043c\u0430\u0441\u0441\u0438\u0432. <\/p>\n<p>\u0426\u0435\u043b\u044c \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 &#8212; \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0435\u0439 \u0438 \u0442\u0440\u044e\u043a\u043e\u0432 \u044f\u0437\u044b\u043a\u0430 Wolfram. \u0410 \u0442\u0430\u043a \u0436\u0435 \u044d\u0442\u043e \u0440\u0443\u043a\u043e\u0432\u043e\u0434\u0441\u0442\u0432\u043e \u043f\u043e \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044e \u0441\u0432\u043e\u0438\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u044d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043b\u0435\u0437\u043d\u0430 \u0442\u0435\u043c, \u0447\u0442\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u0438\u0437\u0443\u0447\u0430\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0438 \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445. <\/p>\n<p>\u041d\u0438\u0436\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430\/\u0441\u043f\u0438\u0441\u043a\u0430 \u043d\u0430 <em>Wolfram Language<\/em>.<\/p>\n<h2>\u041d\u0435\u043c\u043d\u043e\u0433\u043e \u043e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0441\u043f\u0438\u0441\u043a\u0435<\/h2>\n<p>\u041a\u0430\u043a \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u044d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u0445\u043e\u0436\u0430 \u043d\u0430 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432, \u0441 \u0442\u0435\u043c \u043e\u0442\u043b\u0438\u0447\u0438\u0435\u043c, \u0447\u0442\u043e \u0443 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0440\u0430\u0437\u043c\u0435\u0440 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439, \u0430 \u0443 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u043e\u043d \u043c\u043e\u0436\u0435\u0442 \u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f. \u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0432\u043e\u0442 \u0438 \u0432\u0441\u0435. \u0412\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0435\u0433\u043e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 &#8212; \u044d\u0442\u043e \u0443\u0436\u0435 \u0432\u043e\u043f\u0440\u043e\u0441 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438. \u041a\u0430\u043a\u0438\u043c\u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c\u0438 \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043c\u0430\u0441\u0441\u0438\u0432: <\/p>\n<ul>\n<li>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432 \u043d\u0430\u0447\u0430\u043b\u043e \u0438 \u043a\u043e\u043d\u0435\u0446 \u0437\u0430 <strong>O(1)<\/strong><\/p>\n<\/li>\n<li>\n<p>\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438\u0437 \u043d\u0430\u0447\u0430\u043b\u0430 \u0438 \u043a\u043e\u043d\u0446\u0430 \u0437\u0430 <strong>O(1)<\/strong><\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0437\u0430 <strong>O(1)<\/strong><\/p>\n<\/li>\n<li>\n<p>\u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0443 \u0437\u0430 <strong>O(n)<\/strong> \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0438\u0441\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u0437\u0430 <strong>O(n)<\/strong><\/p>\n<\/li>\n<\/ul>\n<p>\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u0443\u0434\u0435\u0442 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0442\u044c \u044d\u0442\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c \u043c\u044b \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u043f\u0440\u044f\u043c\u043e \u0441\u0435\u0439\u0447\u0430\u0441! <\/p>\n<h2>\u0421\u043f\u0438\u0441\u043e\u043a<\/h2>\n<p>\u0412 Wolfram Language \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u043f\u0438\u0441\u043e\u043a, \u0442.\u0435. <code>List<\/code>. \u042d\u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043b\u044e\u0431\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u0438 \u0438\u043c\u0435\u0435\u0442 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0430\u0437\u043c\u0435\u0440. \u041d\u043e \u0434\u0435\u043b\u043e \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0432 \u043d\u0435\u043c \u043d\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u044b. \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u044d\u0442\u043e!<\/p>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430: <\/p>\n<pre><code class=\"haskell\">ClearAll[\"`*\"];   $HistoryLength = 0; <\/code><\/pre>\n<p>\u041f\u0443\u0441\u0442\u043e\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0441\u043e\u0437\u0434\u0430\u0435\u0442\u0441\u044f \u0432\u043e\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"haskell\">list1 = {}; <\/code><\/pre>\n<p>\u0414\u043b\u044f \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0441\u043f\u0438\u0441\u043a\u0430 \u0434\u0430\u043d\u043d\u044b\u043c\u0438 \u043c\u044b \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u0441\u0432\u043e\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e. \u0412 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043e\u043d\u0430 \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0434\u043b\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430:<\/p>\n<pre><code class=\"vala\">SetAttributes[append, HoldFirst];   append[list_, item_] :=  list = Append[list, item]; <\/code><\/pre>\n<p>\u0417\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0435\u0433\u043e \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u0432\u0440\u0435\u043c\u044f, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430: <\/p>\n<pre><code class=\"haskell\">appendTime =  Table[{i, AbsoluteTiming[append[list1, i]][[1]]}, {i, 1, 5000}];<\/code><\/pre>\n<p>\u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043d\u0435\u0442, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u0435\u0435 \u0441\u0430\u043c\u0438: <\/p>\n<pre><code class=\"haskell\">SetAttributes[remove, HoldFirst];   remove[list_Symbol] :=  list = Delete[list, -1]; <\/code><\/pre>\n<p>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0435\u043c \u0432\u0440\u0435\u043c\u044f \u044d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430. \u041e\u0447\u0438\u0449\u0430\u0435\u043c, \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u043e \u043d\u043e\u0432\u043e\u0439 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u0440\u0430\u0437\u0443 \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e. <\/p>\n<pre><code class=\"haskell\">list1 = {};   removeTime = Table[ { i,  append[list1, i];  append[list1, i];  AbsoluteTiming[remove[list1]][[1]] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u041f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <code>part<\/code>. \u0411\u0443\u0434\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0438 \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u0441\u0441\u0438\u0432\u0430: <\/p>\n<pre><code class=\"haskell\">part[list_, i_] :=  list[[i]];   list1 = {};   partTime =  Table[ { i,  append[list1, i];  With[{j = RandomInteger[{1, i}]},   AbsoluteTiming[part[list1, j]][[1]] ] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e &#8212; \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a \u0436\u0435 \u043a\u0430\u043a \u0438 \u0441 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435\u043c \u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c: <\/p>\n<pre><code class=\"haskell\">SetAttributes[insert, HoldFirst];   insert[list_, item_, i_] :=  list = Insert[list, item, i];   list1 = {1};   insertTime =  Table[ { i,  With[{j = RandomInteger[{1, i}]},   AbsoluteTiming[insert[list1, i, j]][[1]] ] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u0418 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 &#8212; \u043f\u043e\u0438\u0441\u043a. \u0411\u0443\u0434\u0435\u043c \u043a\u0430\u043a \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c \u043f\u0443\u043d\u043a\u0442\u0435 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e, \u0430 \u0437\u0430\u0442\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u0435\u0433\u043e \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <code>position<\/code>:<\/p>\n<pre><code class=\"haskell\">position[list_, item_] :=  Position[list, item];   list1 = {1};   positionTime =  Table[ { i,  With[{j = RandomInteger[{1, i}]},   insert[list1, i, j];  AbsoluteTiming[position[list1, i]][[1]] ] },  {i, 1, 5000} ];<\/code><\/pre>\n<p>\u041f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u0433\u0440\u0430\u0444\u0438\u043a \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430: <\/p>\n<pre><code class=\"haskell\">ListPlot[{appendTime, removeTime, insertTime},  PlotLegends -> {\"append\", \"remove\", \"insert\"},  ImageSize -> Large,  PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\">\n<div><figcaption><em>\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430<\/em><\/figcaption><\/div>\n<\/figure>\n<pre><code class=\"haskell\">ListPlot[{positionTime},  PlotLegends -> {\"position\"},  ImageSize -> Large,  PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\">\n<div><figcaption><em>\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043f\u0438\u0441\u043a\u0430. \u0412\u0440\u0435\u043c\u044f \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043b \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0433\u0440\u0430\u0444\u0438\u043a<\/em><\/figcaption><\/div>\n<\/figure>\n<pre><code class=\"haskell\">ListPlot[{partTime},   PlotLegends -> {\"part\"},   ImageSize -> Large,   PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\">\n<div><figcaption><em>\u0425\u043e\u0442\u044c \u0442\u0443\u0442 \u0432\u0441\u0435 \u0445\u043e\u0440\u043e\u0448\u043e! \u0414\u043e\u0441\u0442\u0443\u043f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0437\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u041d\u0430 \u0444\u043e\u043d\u0435 \u0434\u0440\u0443\u0433\u0438\u0445 \u0433\u0440\u0430\u0444\u0438\u043a\u043e\u0432 \u044d\u0442\u043e\u0442 \u0431\u0443\u0434\u0435\u0442 \u0441\u043b\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u0441 \u043e\u0441\u044c\u044e X, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d \u0442\u043e\u0436\u0435 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e<\/em><\/figcaption><\/div>\n<\/figure>\n<p>\u0427\u0442\u043e \u043c\u044b \u0438\u043c\u0435\u0435\u043c? \u0412\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u0432\u044b\u0448\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0437\u0430 <strong>O(n)<\/strong> \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0437\u0430 <strong>O(1)<\/strong>.<\/p>\n<h2>\u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n<p>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u0440\u0438\u0441\u0442\u0443\u043f\u0438\u043c \u043a \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430! \u041d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b 3 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0438\u0437 \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u0442\u0430\u0442\u044c\u0438 (\u043a\u0440\u043e\u043c\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0438 \u043f\u043e\u0438\u0441\u043a\u0430) \u0438\u043c\u0435\u043b\u0438 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <strong>O(1)<\/strong>. \u041a\u0430\u043a \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c? \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442:<\/p>\n<ul>\n<li>\n<p>\u0420\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u0447\u0438\u0441\u043b\u043e \u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/p>\n<\/li>\n<li>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0437\u0430\u043f\u0438\u0441\u044c\u044e \u0432 \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e, \u0430 \u044d\u0442\u043e \u0431\u044b\u0441\u0442\u0440\u043e<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0437\u0430\u043f\u0438\u0441\u044c \u043d\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044e\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e + 1, \u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430<\/p>\n<\/li>\n<li>\n<p>\u041a\u043e\u0433\u0434\u0430 \u0447\u0438\u0441\u043b\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u0435\u043d\u044c\u0448\u0435 \u0447\u0435\u043c \u0444\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 &#8212; \u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0440\u0438\u0441\u0442\u0443\u043f\u0438\u043c \u043a \u0435\u0433\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430 &#8212; \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u0441\u0432\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b, \u0437\u0430\u0434\u0430\u0434\u0438\u043c \u0435\u043c\u0443 \u0430\u0442\u0440\u0438\u0431\u0443\u0442 <code>HoldFirst<\/code> (\u043e\u043d \u043f\u043e\u043c\u043e\u0436\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0441\u0441\u044b\u043b\u043a\u0443) \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430:<\/p>\n<pre><code class=\"haskell\">ClearAll[DynamicList];   SetAttributes[DynamicList, HoldFirst]  createDynamicList[] :=  With[{ref = Unique[\"DYNAMICLIST`$\"]},  ref = &lt;| \"Data\" -> {0},  \"Length\" -> 0,     (*\u0447\u0438\u0441\u043b\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432*) \"Capacity\" -> 1    (*\u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u0439 \u0440\u0430\u0437\u043c\u0435\u0440*) |>;  DynamicList[ref] ]; <\/code><\/pre>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u043d\u0430 \u043d\u0435\u043c \u0442\u0435 5 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0438 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 <code>List<\/code>. \u042f \u0441\u043e\u0437\u043d\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0435 \u0431\u0443\u0434\u0443 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c <code>prepend<\/code> \u0434\u043b\u044f \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0432 \u043d\u0430\u0447\u0430\u043b\u043e \u0438 <code>pop<\/code> \u0434\u043b\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438\u0437 \u043d\u0430\u0447\u0430\u043b\u0430, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u043d\u0438 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u0439 <code>append<\/code> \u0438 <code>remove<\/code> \u0442\u043e\u043b\u044c\u043a\u043e \u0441 \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u043a\u043e\u043d\u0446\u0430. <\/p>\n<p>\u0412 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u044f \u0443\u0431\u0435\u0440\u0443 \u0430\u0442\u0440\u0438\u0431\u0443\u0442, \u0442\u0430\u043a \u043a\u0430\u043a \u0441\u0435\u0439\u0447\u0430\u0441 \u043e\u043d \u043d\u0430\u043c \u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0438 \u0441\u043e\u0437\u0434\u0430\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u0441\u0430\u043c\u0438\u043c \u0442\u0438\u043f\u043e\u043c <code>DynamicList<\/code>:<\/p>\n<pre><code class=\"haskell\">ClearAttributes[append, HoldFirst]  DynamicList \/: append[DynamicList[ref_Symbol], item_] :=  With[{len = ref[\"Length\"], capacity = ref[\"Capacity\"]},  If[len === capacity,  ref[\"Data\"] = Join[ref[\"Data\"], ConstantArray[0, len]];  ref[\"Capacity\"] = capacity * 2;  ];  ref[\"Length\"] = len + 1;  ref[[\"Data\", len + 1]] = item ]; <\/code><\/pre>\n<p>\u042d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0435\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u043d\u044b\u0439. \u0414\u0435\u043b\u043e \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0438 \u0441\u043f\u0438\u0441\u043a\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0447\u0430\u0441\u0442\u043e\u0442\u0430 \u0432\u044b\u0437\u043e\u0432\u0430 \u044d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 \u0438 \u043c\u0435\u043d\u044c\u0448\u0435, \u0442.\u0435. \u0441\u043d\u0438\u0436\u0430\u0442\u044c\u0441\u044f \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u0438. \u0425\u043e\u0442\u044c \u0438 \u043e\u0434\u0438\u043d \u0432\u044b\u0437\u043e\u0432 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0441\u043f\u0438\u0441\u043a\u0430 &#8212; \u044d\u0442\u043e &#171;\u0442\u044f\u0436\u0435\u043b\u0430\u044f&#187; \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f, \u043d\u043e \u0434\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0441\u043f\u0438\u0441\u043a\u043e\u0432 \u043e\u043d\u0430 \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0434\u043a\u043e, \u0447\u0442\u043e \u043d\u0435 \u0432\u043b\u0438\u044f\u0435\u0442 \u043d\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c. <\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u0436\u0435 \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043c\u0435\u0442\u043e\u0434 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438\u0437 \u043a\u043e\u043d\u0446\u0430: <\/p>\n<pre><code class=\"haskell\">ClearAttributes[remove, HoldFirst];   DynamicList \/: remove[DynamicList[ref_Symbol]] :=  With[{ len = ref[\"Length\"],  capacity = ref[\"Capacity\"],  item = ref[[\"Data\", ref[\"Length\"]]] },  If[len === capacity \/ 2,  ref[\"Data\"] = ref[[\"Data\", ;; len \/ 2]];  ref[\"Capacity\"] = capacity \/ 2;  ];  ref[\"Length\"] = len - 1;  ref[[\"Data\", len]] = 0;  item ]; <\/code><\/pre>\n<p>\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0431\u0443\u0434\u0435\u0442 \u0447\u0443\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u0435\u0435: <\/p>\n<pre><code class=\"haskell\">ClearAttributes[insert, HoldFirst];   DynamicList \/: insert[DynamicList[ref_Symbol], item_, i_Integer] :=  With[{len = ref[\"Length\"], capacity = ref[\"Capacity\"]},  If[len === capacity,  ref[\"Data\"] = Join[ref[\"Data\"], ConstantArray[0, len]];  ref[\"Capacity\"] = capacity * 2;   ];  ref[\"Length\"] = len + 1;  ref[[\"Data\"]] = Join[ref[[\"Data\", 1 ;; i - 1]], {item}, ref[[\"Data\", i ;; -2]]];  item ]; <\/code><\/pre>\n<p>\u0418 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0438 \u0447\u0430\u0441\u0442\u0438: <\/p>\n<pre><code class=\"haskell\">DynamicList \/: position[DynamicList[ref_Symbol], item_] :=  Position[ref[[\"Data\", 1 ;; ref[\"Length\"]]], item]; <\/code><\/pre>\n<pre><code class=\"haskell\">DynamicList \/: part[DynamicList[ref_Symbol], i_Integer] :=  If[Abs[i] &lt;= ref[\"Length\"],      ref[[\"Data\", i]],      Message[General::partw, i, DynamicList[ref]] ]; <\/code><\/pre>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 &#8212; \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439:<\/p>\n<pre><code class=\"haskell\">DynamicList \/: Normal[DynamicList[ref_Symbol]] :=  ref[[\"Data\", 1 ;; ref[\"Length\"]]];   DynamicList \/: DeleteObject[DynamicList[ref_Symbol]] :=  ClearAll[ref]; <\/code><\/pre>\n<h2>\u041f\u043b\u0430\u0448\u043a\u0430 \u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/h2>\n<p>\u042f \u043f\u043e \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u0438 \u043f\u0440\u0438\u0432\u0435\u0434\u0443 \u043a\u043e\u0434, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0442\u044c \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0432 \u0432\u0438\u0434\u0435 <code>SummaryBox<\/code>. \u041d\u0438\u043a\u0430\u043a\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u044d\u0442\u0430 \u0448\u0442\u0443\u043a\u0430 \u0437\u0430 \u0441\u043e\u0431\u043e\u0439 \u043d\u0435 \u043a\u0440\u043e\u0435\u0442: <\/p>\n<pre><code class=\"haskell\">$dynamicListIcon = Import[\"https:\/\/wolfr.am\/1jEFx2BBO\"];  DynamicList \/: MakeBoxes[object: DynamicList[ref_Symbol],  form: (StandardForm | TraditionalForm)] :=  Module[{above, below},  above = { {BoxForm`SummaryItem[{\"Ref: \", Defer[ref]}], SpanFromLeft},  {BoxForm`SummaryItem[{\"Length: \", ref[\"Length\"]}], SpanFromLeft},  {BoxForm`SummaryItem[{\"Capacity: \", ref[\"Capacity\"]}], SpanFromLeft} };  below = {};   BoxForm`ArrangeSummaryBox[ DynamicList,  object,  $dynamicListIcon,  above,  below,  form,  \"Interpretable\" -> Automatic ] ];<\/code><\/pre>\n<p>\u0418 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432. \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a: <\/p>\n<pre><code class=\"haskell\">dynamicList1 = createDynamicList[]<\/code><\/pre>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b: <\/p>\n<pre><code class=\"haskell\">append[dynamicList1, #]&amp; \/@ Range[10]<\/code><\/pre>\n<p>\u0423\u0434\u0430\u043b\u044f\u0435\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e: <\/p>\n<pre><code class=\"haskell\">Do[remove[dynamicList1], {3}]<\/code><\/pre>\n<p>\u0412\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430:<\/p>\n<pre><code class=\"haskell\">Normal[dynamicList1]<\/code><\/pre>\n<p>\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430: <\/p>\n<pre><code class=\"haskell\">DeleteObject[dynamicList1]<\/code><\/pre>\n<p>\u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0447\u0442\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 \u043f\u0443\u0441\u0442\u043e:<\/p>\n<pre><code class=\"haskell\">dynamicList1[[1]]<\/code><\/pre>\n<figure class=\"full-width\">\n<div><figcaption><em>\u041a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0432 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441\u0435 \u0431\u043b\u043e\u043a\u043d\u043e\u0442\u0430<\/em><\/figcaption><\/div>\n<\/figure>\n<h2>\u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/h2>\n<p>\u041d\u0443 \u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0442\u0435\u0441\u0442\u043e\u0432. \u0422\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u043f\u0435\u0440\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438 \u0432\u0441\u0435 \u0442\u0435 \u0436\u0435 \u0441\u0430\u043c\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043d\u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0441\u043f\u0438\u0441\u043a\u0435, \u0442\u043e \u043a\u043e\u0434 \u0434\u043b\u044f \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u0431\u0435\u0437 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f. \u041d\u0443\u0436\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e <code>list1<\/code> \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430 <code>dynamicList1<\/code>:<\/p>\n<pre><code class=\"haskell\">DeleteObject[dynamicList1];   dynamicList1 = createDynamicList[];   appendTime =  Table[{i, AbsoluteTiming[append[dynamicList1, i]][[1]]}, {i, 1, 5000}];   DeleteObject[dynamicList1];   dynamicList1 = createDynamicList[];   removeTime = Table[ { i,  append[dynamicList1, i];  append[dynamicList1, i];  AbsoluteTiming[remove[dynamicList1]][[1]] },  {i, 1, 5000} ]; <\/code><\/pre>\n<p>\u0418 \u0433\u0440\u0430\u0444\u0438\u043a: <\/p>\n<pre><code class=\"haskell\">ListPlot[{appendTime, removeTime},  PlotLegends -> {\"append\", \"remove\"},  ImageSize -> Large,  PlotTheme -> \"Detailed\" ]<\/code><\/pre>\n<figure class=\"full-width\">\n<div><figcaption><em>\u0421 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u0447\u0438\u0441\u043b\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u0440\u0435\u043c\u044f \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0435 \u0431\u043b\u0438\u0436\u0435 \u043a \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0435. \u0421\u0442\u0443\u043f\u0435\u043d\u044c\u043a\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0442 \u0441\u043e \u0441\u0442\u0435\u043f\u0435\u043d\u044f\u043c\u0438 \u0434\u0432\u043e\u0439\u043a\u0438: 2^10 ~ 1000, 2^11 ~ 2000, 2^12 ~ 4000<\/em><\/figcaption><\/div>\n<\/figure>\n<p>\u0410 \u0432\u043e\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0442\u0430\u0432\u043a\u0438,<\/p>\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-366140","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/366140","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=366140"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/366140\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=366140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=366140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=366140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}