How can I implement the cycle of generating IP addresses according to this algorithm:

As we know, an IP address consists of a mask

*.*.*.*

Suppose we have IP 94.122.67.83

You need to create such IP addresses in which:

The sum of the numbers 1 and 2 parts will be equal, that is: 9 + 4 + 1 + 2 + 2 = 6 + 7 + 8 + 3

  • @ Dmitry Alekseevich, you regretted that the C code is simply a search for options, and not your task. I concluded the "happy" IP. Code in UPDATE my answer. Together with the output of 3084214728 bytes to / dev / null 27 sec on DualCore 2.7 GHz (total 215397594 IP). - avp
  • @avp I can not understand, or I am an idiot, or php, c and python lag. C does not compile code, php.exe opens a black window and that's it, python refuses to start. :( - Dmitry Alekseevich
  • one
    I use Windows (and both XP 32-bit and 7 64-bit) MinGW gcc. I just tried again. In Emacs, I opened the ips.c file (Copy / Paste) into it the text from my answer (the one after UPDATE-2 ) and saved it. In the console window ( cmd ) I executed the following commands: chcp 1251 gcc -O3 -o ips ips.c ips> nul I already have the necessary font in the console. How to make see my comment below. Everything worked for 24730 msec. Describe in detail what you are doing, what you see. - avp
  • Everything, I have already achieved the result. PHP CLI still does not start. (just a black console window - nothing more). Python gave an error on line 1. And then, that just did not do. Helped Dev-C ++ - Dmitry Alekseevich
  • Of course it's late, but !: Why do you need to keep it ? How do you want to use it? - timka_s

4 answers 4

 $ips = array(); for ($n1 = 0; $n1 < 256; $n1++) for ($n2 = 0; $n2 < 256; $n2++) for ($n3 = 0; $n3 < 256; $n3++) for ($n4 = 0; $n4 < 256; $n4++) { $sn1 = $sn2 = 0; $strn12 = $n1.$n2; $strn34 = $n3.$n4; for ($i = 0; $i < strlen($strn12); $i++) $sn1 += (int) $strn12{$i}; for ($i = 0; $i < strlen($strn34); $i++) $sn2 += (int) $strn34{$i}; if ($sn1 == $sn2) $ips []= "$n1.$n2.$n3.$n4"; } print_r($ips);

The script will give all possible IP (v4) described in the question. And yes, Monsieur knows a lot about perversions)

  • Parse error: syntax error, unexpected ')', expecting ';' in gen.php on line 11 - Dmitry Alekseevich
  • Sorry,; ; $i++ added. You are more careful with the launch, I have no idea how much it will work. Would try first on small numbers (not 256, but 11, for example). - Sh4dow
  • one
    Yes, thank you, in fact, I hardly deserve the answer) max_execution_time better to put 0. 9999 - this is less than 3 hours) - Sh4dow
  • 2
    @ Sh4dow, with all due respect, could be more elegant to write :) - Alex Kapustin
  • one
    Well, in your case, logically, just before entering a proxy into the database, do something like this: // $ proxy - an object with a proxy (ip, port, date, etc.) $ num = explode ('.', $ Proxy-> ip); $ left = $ right = 0; foreach (array ($ num [0], $ num [1]) as $ n) $ left + = floor ($ n * 0.01) + floor (($ n% 100) * 0.1) + ($ n% 10) ; foreach (array ($ num [2], $ num [3]) as $ n) $ right + = floor ($ n * 0.01) + floor (($ n% 100) * 0.1) + ($ n% 10) ; if ($ left == $ right) $ proxy-> is_happy = true; And for the sake of this goal, storing a base of 3 + GB seems strange to me) Moreover, it’s not a fact that a request to it will pass faster - Sh4dow

As an option with some optimization, I can offer this (javascript):

 console.time( 'test' ); function num2sum( val ){ return ( ~~( val / 100 ) + ~~( val % 100 / 10 ) + ~~( val % 10 ) ); } sum = []; for ( i = 0; i < 256; i++ ) sum.push( num2sum( i ) ); pair = []; for ( n1 = 0; n1 < 256; n1++ ){ for ( n2 = 0; n2 < 256; n2++ ){ sum2 = sum[ n1 ] + sum[ n2 ]; ( pair[ sum2 ] || ( pair[ sum2 ] = [] ) ).push( '.' + n1 + '.' + n2 ); } } res = []; for ( n1 = 0; n1 < 256; n1++ ){ console.log(n1); for ( n2 = 0; n2 < 256; n2++ ){ sum2 = sum[ n1 ] + sum[ n2 ]; sum34 = pair[ sum2 ]; for ( n34 = 0; n34 < sum34.length; n34++ ){ res.push( n1 + '.' + n2 + sum34[ n34 ] ); } } } console.timeEnd( 'test' );

Generation of all IPs from [0-25].*.*.* 99058ms - and approximately 600 MB of RAM

For all IPs from the condition (and there are 215397594 of them) you need 3GB minimum.

    1. Because according to the condition of the problem, the left and right parts of the IP address are equal, then there is no point in going through all the options; it’s enough to go through the left (or right) part.
    2. Also, because Since all variants of the left part are valid, it is reasonable to immediately generate all possible variants of the left part with a pre-calculated amount.

    Run via php_cli.

     function sum($string) { $result = 0; for ($i = 0; $i < strlen($string); $i++) { $result += (int)$string[$i]; } return $result; } $ipSet = array(); for ($part1 = 1; $part1 < 255; $part1++) { $sum1 = sum((string)$part1); for ($part2 = 1; $part2 < 255; $part2++) { $numberSum = $sum1 + sum((string)$part2); if (isset($ipSet[$numberSum])) { $ipSet[$numberSum][] = "$part1.$part2"; } else { $ipSet[$numberSum] = array("$part1.$part2"); } } } foreach ($ipSet as $ipParts) { foreach ($ipParts as $partLeft) { foreach ($ipParts as $partRight) { fwrite(STDOUT, "$partLeft.$partRight\n"); } } }

    And the same thing on python:

     import sys from collections import defaultdict ip_set = defaultdict(lambda : []) for part1 in range(1, 255): sum1 = sum(map(int, str(part1))) for part2 in range(1, 255): number_sum = sum1 + sum(map(int, str(part2))) ip_set[number_sum].append('%d.%d' % (part1, part2)) for ip_parts in ip_set.values(): for part_left in ip_parts: for part_right in ip_parts: # заменил print на прямой вывод в stdout sys.stdout.write( '%s.%s\n' % (part_left, part_right) )

    UPD. For the sake of sports interest, I launched all the listings at my place. The following results were obtained:

    PHP interpreter PHP 5.3.8

     $ time php ips.php >/dev/null real 7m41.531s user 6m52.086s sys 0m47.807s

    Python interpreter python 3.2

     $ time python3.2 ips.py > /dev/null real 2m41.555s user 2m40.742s sys 0m0.212s

    Python, pypy 1.7 interpreter with JIT compilation enabled

     $ time pypy ips.py > /dev/null real 0m47.937s user 0m47.415s sys 0m0.344s

    C, listing from @avp compiled gcc 4.6.2 (I had to cut mtime from there, due to the lack of such a function)

     $ gcc -O3 -march=native -mtune=native ipc2.c -o ipc2 $ time ./ipc2 > /dev/null Поиск количества "Счастливых" IP (nested loops) Всего 215397594 "Счастливых" IP вывод 3084214728 байт real 0m22.702s user 0m22.597s sys 0m0.020s

    C, iterate all options from @avp

     $ gcc -O2 ips.c -o ips $ time ./ips > /dev/null End 295 str=255.255.255.255 real 4m54.712s user 4m51.914s sys 0m1.676s
    • Just for the sake of interest: on C Linux under VirtualBox on 32-bit Windows-XP Dual-Core 2.7 GHz with recording all the results in / dev / null 1m 3.90s The size of the program is 49 lines. To the question of the effectiveness of programming environments - avp
    • one
      Of course, I would be surprised if it were otherwise :) In addition, I brought more "honest" results with the output to the file. With output in / dev / null it would be two times faster. By the way, the source code for C - Ilya Pirogov would have been
    • Updated the answer. I suppose that if you had only a bust of IPs satisfying the condition, then the execution time would be less. But even such results, in my opinion, are very indicative :) Especially considering the amount of code :) - Ilya Pirogov
    • @Ilya Pirogov, if you want to supplement your statistics, I made an optimized C program (it is in UPDATE-2 of my answer), which displays IPs that match the condition, so to say, "happy". I work for 27 seconds. when outputting to / dev / null ~ 3Gbytes. Compiled gcc -O3 - avp
    • one
      @Ilya Pirogov, great, great table. When writing "happy" to the file, I think there won't be much difference between C and pypy. I recorded the file in almost 2 minutes. - avp pm

    Generation and output of all C addresses

    Just found an error in it, the result below (taking into account the output) is not correct. puts (str); it is necessary to transfer to the internal loop In this case (output to / dev / null since I have no space for a 64GB file on the disk) the operating time is 4m 43.46s

     #include <stdio.h> #include <time.h> #include <string.h> #include <stdlib.h> main () { int i,n1,n2,n3,n4; char str[100], *p, *q; char *nn[256]; for (i = 0; i < 256; i++) { sprintf (str,"%d",i); nn[i] = strdup(str); } time_t start = time(NULL); for (n1 = 0; n1 < 256; n1++) for (n2 = 0; n2 < 256; n2++) { for (n3 = 0; n3 < 256; n3++) { for (n4 = 0; n4 < 256; n4++) { p = str; q = nn[n1]; while (*q) *p++ = *q++; *p++ = '.'; q = nn[n2]; while (*q) *p++ = *q++; *p++ = '.'; q = nn[n3]; while (*q) *p++ = *q++; *p++ = '.'; q = nn[n4]; while (*q) *p++ = *q++; *p++ = 0; } puts(str); } } fprintf (stderr,"End %ld str=%s\n",time(NULL)-start,str); exit(0); }

    When copy-paste slightly indents slid.

    Launched to write to a file on disk 1m 13.08s file size 246808576 bytes.

    comment Yes python with 19 minutes is great. My language is (in absentia) likable. I did not think that such a smart interpreter.

    UPDATE

    Yes. Comments are over. For the sake of interest, I made another optimized version and burned all IPs to disk

     avp@avp-ubu1:/media/sf_sharedir$ head iplist 0.0.0.0 0.0.0.1 0.0.0.2 0.0.0.3 0.0.0.4 0.0.0.5 0.0.0.6 0.0.0.7 0.0.0.8 0.0.0.9 avp@avp-ubu1:/media/sf_sharedir$ tail iplist 255.255.255.247 255.255.255.248 255.255.255.249 255.255.255.250 255.255.255.251 255.255.255.252 255.255.255.253 255.255.255.254 255.255.255.255 avp@avp-ubu1:/media/sf_sharedir$ ll /media/sf_sharedir/iplist -rwxrwx--- 1 root vboxsf 68719476736 2012-01-13 00:05 /media/sf_sharedir/iplist* avp@avp-ubu1:/media/sf_sharedir$

    Machine I5-2500 3.3 GHz 4GB Windows-7 64-bit, VirtualBox Ubuntu 10.04 64-bit 4cpu 1GB

    The generation time with the write to / dev / null is 29.043 sec, with writing to the file 719769 msec (12 minutes).

    Optimized code:

     /* Перебор разных IP */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> long long mtime(void); // 1. Тривиальный перебор 2^32, генерация строковой формы main (int ac, char *av) { long long start = mtime(); int l, n1, n2, n3, n4, k1, k2, k3; char *outbuf = malloc((l = 256*256*16)+1); outbuf[l] = 0; char str[20], *digs[256], *p, *q; fprintf (stderr,"Тривиальный перебор 4 млрд. IP\n"); for (n1 = 0; n1 < 256; n1++) { sprintf (str,"%d",n1); digs[n1] = strdup(str); } for (n1 = 0; n1 < 256; n1++) { for (k1 = 0, q = digs[n1]; *q; k1++) str[k1] = *q++; str[k1++] = '.'; for (n2 = 0; n2 < 256; n2++) { for (k2 = k1, q = digs[n2]; *q; k2++) str[k2] = *q++; str[k2++] = '.'; p = outbuf; for (n3 = 0; n3 < 256; n3++) { for (k3 = k2, q = digs[n3]; *q; k3++) str[k3] = *q++; str[k3++] = '.'; // здесь k3 длина str for (n4 = 0; n4 < 256; n4++) { memcpy(p,str,k3); p+=k3; for (q = digs[n4]; *q;) *p++ = *q++; *p++ = '\n'; } } write (1,outbuf,p-outbuf); // fprintf (stderr,"%sXXX\n",str); } } fprintf (stderr,"End %lld msec\n",mtime()-start); exit (0); }

    The mtime () function returns the current time in milliseconds, to save space, omit its code.

    Mb there will be time and desire to make a parallel version (IMHO time with recording to disk will still remain about 12 minutes), I will try to load all 4 cpu.

    UPDATE-2

    The program displays all the "happy" IP. Together with the output of 3084214728 bytes to / dev / null 27 sec on DualCore 2.7 GHz (total 215397594 IP).

     #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #ifdef WIN32 #define mtime clock #else long long mtime(void); #endif #define OUTPUT 1 main () { long long start = mtime(), sumo = 0; int b, b1, b2, b3, b4, s1, s2, ss1, ss2, k = 0; #if OUTPUT char *outbuf = malloc(256*256*16+1); char str[20], *digs[256], *p, *q; for (b = 0; b < 256; b++) { sprintf (str,"%d",b); digs[b] = strdup(str); } #endif fprintf (stderr,"Поиск количества \"Счастливых\" IP (nested loops)\n"); for (b1 = 0; b1 < 256; b1++) { b = b1; s1 = b%10; b = b/10; s1 += b%10; s1 += b/10; // fprintf (stderr,"%dxxx\n",b1); for (b2 = 0; b2 < 256; b2++) { b = b2; ss1 = s1 + b%10; b = b/10; ss1 += b%10; ss1 += b/10; #if OUTPUT p = outbuf; #endif for (b3 = 0; b3 < 256; b3++) { b = b3; s2 = b%10; b = b/10; s2 += b%10; s2 += b/10; for (b4 = 0; b4 < 256; b4++) { b = b4; ss2 = s2 + b%10; b = b/10; ss2 += b%10; ss2 += b/10; if (ss1 == ss2) { k++; #if OUTPUT for (q = digs[b1]; *q;) *p++ = *q++; *p++ = '.'; for (q = digs[b2]; *q;) *p++ = *q++; *p++ = '.'; for (q = digs[b3]; *q;) *p++ = *q++; *p++ = '.'; for (q = digs[b4]; *q;) *p++ = *q++; *p++ = '\n'; #endif } } } #if OUTPUT write (1,outbuf,p-outbuf); sumo += (p-outbuf); #endif } } fprintf (stderr,"Всего %d \"Счастливых\" IP (%lld msec) вывод %lld байт\n", k,mtime()-start,sumo); }
    • You are going through an exhaustive search, and not only IP that satisfies the condition, t.ch. the comparison is not correct. But nevertheless, he added performance results to his answer. - Ilya Pirogov
    • Yes, just a complete search and generation in string form 4 billion times. The time of work was just interesting, and sketched in a few minutes. By the way, if you're interested, I replaced the contents of the inner loop (all while () ...) with one sprintf () , I think 90% would write like that, and the time has increased to 35m 2.86s! Your program on python is not a complete enumeration of all IPs, but a solution to the issue of sums? - avp
    • > Your program on python is not a complete enumeration of all IPs, but a solution to the issue of amounts? Yes exactly. There is busting a total of 210 million. IP - Ilya Pirogov
    • Hm I apologize, just now I noticed your remark about puts(str) . After transferring it to the internal loop, the program has been working for more than half an hour and this without replacing whiles with sprintf. It looks like you have an error in the algorithm somewhere. - Ilya Pirogov
    • one
      What really would finish the question of the effectiveness of programming environments. Full brute force IP on Python: import sys, itertools for ip in itertools.product (* (xrange (256),) * 4): sys.stdout.write ('% d.% D.% D.% D \ n '% ip) Run for: real 19m59.251s user 19m43.120s sys 0m0.051s Ie about 4 times slower than your code. UPD. Yes, the interpreter here is pypy. Normal CPython, I think it will be 5 times slower. - Ilya Pirogov