{"id":2365,"date":"2008-07-26T10:26:20","date_gmt":"2008-07-26T08:26:20","guid":{"rendered":"http:\/\/vasil.ludost.net\/blog\/?p=2365"},"modified":"2008-07-26T10:27:17","modified_gmt":"2008-07-26T08:27:17","slug":"2008-07-26-%d0%b4%d0%b5%d0%bd-%d0%bd%d0%b0-%d0%b0%d0%b4%d0%bc%d0%b8%d0%bd%d1%81%d0%ba%d0%b8%d1%8f-%d0%bc%d0%b0%d1%85%d0%bc%d1%83%d1%80%d0%bb%d1%83%d0%ba","status":"publish","type":"post","link":"https:\/\/vasil.ludost.net\/blog\/?p=2365","title":{"rendered":"2008-07-26 \u0434\u0435\u043d \u043d\u0430 \u0430\u0434\u043c\u0438\u043d\u0441\u043a\u0438\u044f \u043c\u0430\u0445\u043c\u0443\u0440\u043b\u0443\u043a"},"content":{"rendered":"<p>\u0421\u043d\u043e\u0449\u0438 \u0432 \u0441\u0440\u0435\u0434\u043d\u043e \u043f\u0438\u044f\u043d\u043e \u0441\u044a\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u043a\u043e\u043b\u043e \u0435\u0434\u0438\u043d \u0441\u043f\u043e\u0440 \u0441 \u0413\u0443\u043d\u0438\u043d\u0441\u043a\u0438 (\u0434\u044a\u043b\u0436\u0430 \u043c\u0443 \u0435\u0434\u043d\u0430 \u0431\u0438\u0440\u0430) \u043d\u0430\u043f\u0438\u0441\u0430\u0445 \u0435\u0434\u043d\u043e \u0442\u0435\u0441\u0442\u043e\u0432\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u0447\u0435&#8230;<\/p>\n<p>\u0412\u044a\u043f\u0440\u043e\u0441\u044a\u0442 \u0431\u0435\u0448\u0435 \u0441\u043b\u0435\u0434\u043d\u0438\u044f &#8211; \u0430\u043a\u043e \u0438\u043c\u0430\u043c\u0435 \u0434\u0432\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0441 2^16 \u0435\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u043a\u0430\u0442\u043e \u0432\u0441\u0435\u043a\u0438 \u0435\u043b\u0435\u043c\u0435\u043d\u0442 \u043c\u043e\u0436\u0435 \u0434\u0430 \u0435 \u043e\u0442 0 \u0434\u043e 2^32, \u043a\u0430\u043a\u044a\u0432 \u0435 \u0448\u0430\u043d\u0441\u044a\u0442 \u0441\u0435\u0447\u0435\u043d\u0438\u0435\u0442\u043e \u043d\u0430 \u0434\u0432\u0435\u0442\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0434\u0430 \u043d\u0435 \u0435 \u043f\u0440\u0430\u0437\u043d\u043e\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e. \u041f\u043e\u043d\u0435\u0436\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u0442\u043e \u0430\u043b\u043a\u043e\u0445\u043e\u043b \u043d\u0435 \u043f\u0440\u0435\u0434\u0440\u0430\u0437\u043f\u043e\u043b\u0430\u0433\u0430\u0448\u0435 \u043a\u044a\u043c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 (\u0430 \u0447\u0435\u0440\u0432\u043e\u0442\u043e \u0441\u0430\u043c\u043e \u043d\u0438 \u043f\u0440\u0435\u043f\u0441\u0443\u0432\u0430 \u0438 \u043e\u0442\u043a\u0430\u0437\u0430 \u0434\u0430 \u0433\u043e \u0441\u043c\u0435\u0442\u043d\u0435), \u043d\u0430\u043f\u0438\u0441\u0430\u0445 \u0441\u043b\u0435\u0434\u043d\u043e\u0442\u043e \u043d\u0435\u0449\u043e, \u043a\u043e\u0435\u0442\u043e \u0434\u0430 \u0432\u0430\u0434\u0438 \u043d\u044f\u043a\u0430\u043a\u0432\u0430 \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0430:<br \/>\n(\u0434\u0430 \u0441\u0435 \u043e\u0442\u0431\u0435\u043b\u0435\u0436\u0438, \u0437\u0430 \u043f\u0440\u044a\u0432 \u043f\u044a\u0442 \u0443\u0441\u043f\u044f\u0432\u0430\u043c \u0434\u0430 \u0438\u0437\u043f\u043e\u043b\u0437\u0432\u0430\u043c qsort() :) )<\/p>\n<pre>\r\n#include &lt;stdio.h&gt;\r\n#include &lt;unistd.h&gt;\r\n#include &lt;sys\/types.h&gt;\r\n#include &lt;sys\/fcntl.h&gt;\r\n#include &lt;stdlib.h&gt;\r\n\r\n#define LEN 65536\r\n\r\n#define NTEST 100\r\n\r\nstatic int compare(const void *a, const void *b)\r\n{\r\n        if (*((int *) a) &gt; *((int *) b)) return 1;\r\n        if (*((int *) a) &lt; *((int *) b)) return -1;\r\n        return 0;\r\n}\r\n\r\n\r\nint do_whatever()\r\n{\r\n\tint s0[LEN],s1[LEN];\r\n\r\n        int i=0,j=0;\r\n\r\n        int rndsrc;\r\n        rndsrc=open(\"\/dev\/urandom\",O_RDONLY);\r\n        read(rndsrc,s0,(sizeof(int)*LEN));\r\n        read(rndsrc,s1,(sizeof(int)*LEN));\r\n        close(rndsrc);\r\n\r\n        qsort (s0,LEN,sizeof(int),compare);\r\n        qsort (s1,LEN,sizeof(int),compare);\r\n\r\n\twhile ( (s0[i]!=s1[j]) && (i&lt;LEN) && (j&lt;LEN))\r\n\t{\r\n\t\tif (s0[i]&lt;s1[j]) { if (!i&lt;LEN) i++; }\r\n\t\t\telse {if (!j&lt;LEN) j++;};\r\n\r\n\t}\r\n\tif (s0[i]==s1[j]) return 1;\r\n        return 0;\r\n\r\n}\r\n\r\nint main()\r\n{\r\n\tint i,num=0;\r\n\r\n\tfor (i=0;i&lt;NTEST;i++)\r\n\t\tnum+=do_whatever();\r\n\tprintf (\"tests %d true %d false %d\\n\",NTEST,num,NTEST-num);\r\n\treturn 0;\r\n}\r\n<\/pre>\n<p>\u0413\u0443\u043d\u0438\u043d\u0441\u043a\u0438 \u0442\u0432\u044a\u0440\u0434\u0435\u0448\u0435, \u0447\u0435 \u0448\u0430\u043d\u0441\u044a\u0442 \u043a\u043b\u043e\u043d\u0438 \u043a\u044a\u043c 1, \u0438 \u0435 \u043f\u0440\u0430\u0432 &#8211; \u0441\u043f\u043e\u0440\u0435\u0434 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043a\u0430\u0442\u0430 \u0438\u0437\u043b\u0438\u0437\u0430 \u043d\u0430\u0434 1:2, \u043a\u043e\u0435\u0442\u043e \u0441\u0438 \u043a\u043b\u043e\u043d\u0438 \u043a\u044a\u043c 1 :)<\/p>\n<p>\u0410, \u0434\u0430, \u0428\u043e\u043f\u043e\u0432, \u043a\u0430\u043a \u043c\u043e\u0436\u0430 \u0434\u0430 \u043c\u0435 \u0447\u0435\u0440\u043f\u0438\u0448 \u0434\u0432\u0435 \u0431\u0438\u0440\u0438, \u0441\u043b\u0435\u0434 \u043a\u0430\u0442\u043e \u0431\u044f\u0445 \u043f\u0438\u043b \u0442\u043e\u043b\u043a\u043e\u0432\u0430. \u041f\u043e\u043b\u043e\u0432\u0438\u043d\u0430\u0442\u0430 \u0441\u0443\u0442\u0440\u0438\u043d \u043c\u0438 \u0441\u0435 \u0438\u0441\u043a\u0430\u0448\u0435 \u0434\u0430 \u0441\u044a\u043c \u0443\u043c\u0440\u044f\u043b :).<\/p>\n<p>\u041a\u043e\u0439\u0442\u043e \u043f\u043e\u043c\u043d\u0438 \u043f\u043e\u0432\u0435\u0447\u0435 \u043e\u0442 \u043f\u0440\u0430\u0437\u043d\u0443\u0432\u0430\u043d\u0435\u0442\u043e &#8211; \u0434\u0430 \u043f\u0438\u0448\u0435.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u0421\u043d\u043e\u0449\u0438 \u0432 \u0441\u0440\u0435\u0434\u043d\u043e \u043f\u0438\u044f\u043d\u043e \u0441\u044a\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u043a\u043e\u043b\u043e \u0435\u0434\u0438\u043d \u0441\u043f\u043e\u0440 \u0441 \u0413\u0443\u043d\u0438\u043d\u0441\u043a\u0438 (\u0434\u044a\u043b\u0436\u0430 \u043c\u0443 \u0435\u0434\u043d\u0430 \u0431\u0438\u0440\u0430) \u043d\u0430\u043f\u0438\u0441\u0430\u0445 \u0435\u0434\u043d\u043e \u0442\u0435\u0441\u0442\u043e\u0432\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u0447\u0435&#8230; \u0412\u044a\u043f\u0440\u043e\u0441\u044a\u0442 \u0431\u0435\u0448\u0435 \u0441\u043b\u0435\u0434\u043d\u0438\u044f &#8211; \u0430\u043a\u043e \u0438\u043c\u0430\u043c\u0435 \u0434\u0432\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0441 2^16 \u0435\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u043a\u0430\u0442\u043e \u0432\u0441\u0435\u043a\u0438 \u0435\u043b\u0435\u043c\u0435\u043d\u0442 \u043c\u043e\u0436\u0435 \u0434\u0430 \u0435 \u043e\u0442 0 \u0434\u043e 2^32, \u043a\u0430\u043a\u044a\u0432 \u0435 \u0448\u0430\u043d\u0441\u044a\u0442 \u0441\u0435\u0447\u0435\u043d\u0438\u0435\u0442\u043e \u043d\u0430 \u0434\u0432\u0435\u0442\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0434\u0430 \u043d\u0435 \u0435 \u043f\u0440\u0430\u0437\u043d\u043e\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e. \u041f\u043e\u043d\u0435\u0436\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u0442\u043e \u0430\u043b\u043a\u043e\u0445\u043e\u043b \u043d\u0435 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[15],"class_list":["post-2365","post","type-post","status-publish","format-standard","hentry","category-general","tag-15"],"_links":{"self":[{"href":"https:\/\/vasil.ludost.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2365","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vasil.ludost.net\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vasil.ludost.net\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vasil.ludost.net\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vasil.ludost.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2365"}],"version-history":[{"count":0,"href":"https:\/\/vasil.ludost.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2365\/revisions"}],"wp:attachment":[{"href":"https:\/\/vasil.ludost.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2365"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vasil.ludost.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2365"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vasil.ludost.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2365"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}