#php #циклы
Как можно реализовать цикл генерации IP адресов по такому алгоритму: Как мы знаем, IP адрес состоит из маски *.*.*.* Допустим, у нас IP 94.122.67.83 Нужно создать такие IP адреса в которых: Сумма цифр 1 и 2 части будут равны, тоесть: 9+4+1+2+2 = 6+7+8+3
Ответы
Ответ 1
$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); Скрипт выдаст все возможные IP (v4), описанные в вопросе. И таки да, мсье знает толк в извращениях)Ответ 2
Как вариант с некоторой оптимизацией, могу предложить такое ( 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' ); Генерация всех IP из [0-25].*.*.* заняла 99058ms - и примерно 600 МБ оперативки Для всех IP из условия ( а их - 215397594 ) нужно 3ГБ минимум.Ответ 3
Т.к. по условию задачи, левая и правая части IP адреса равны, то нету смысла перебирать все варианты, достаточно перебрать только левую (или правую) часть. Так же, т.к. валидными являются все варианты левой части, то разумно сразу сгенерировать все возможные варианты левой части с заранее рассчитанной суммой. Запускать через 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"); } } } И тоже самое на питоне: 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. Ради спортивного интереса запустил все листинги у себя. Получились следующие результаты: PHP, интерпретатор PHP 5.3.8 $ time php ips.php >/dev/null real 7m41.531s user 6m52.086s sys 0m47.807s Python, интерпретатор python 3.2 $ time python3.2 ips.py > /dev/null real 2m41.555s user 2m40.742s sys 0m0.212s Python, интерпретатор pypy 1.7 с включенной JIT-компиляцией $ time pypy ips.py > /dev/null real 0m47.937s user 0m47.415s sys 0m0.344s C, листинг от @avp скомпилирован gcc 4.6.2 (пришлось выпилить от туда mtime, из-за отсутствия таковой функции) $ 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, перебор всех вариантов от @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Ответ 4
Генерация и вывод всех адресов на Си Только что обнаружил ошибку в ней, результат, приведенный внизу (с учетом вывода) не корректен. puts(str); надо перенести во внутренний цикл В этом случае (вывод в /dev/null т.к. на диске у меня места под 64Гбайт файл нет) время работы 4m 43.46s #include#include #include #include 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); } При копи-паст слегка отступы сползли. Запустил с записью в файл на диск 1m 13.08s размер файла 246808576 байт. комментарий Да питон с 19 минутами это здорово. Язык мне (заочно) симпатичен. Не думал, что такой шустрый интерпретатор. UPDATE Да. Комментарии закончились. Ради интереса сделал еще один оптимизированный вариант и записал все IP на диск 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$ Машина I5-2500 3.3 GHz 4GB Windows-7 64-bit, VirtualBox Ubuntu 10.04 64-bit 4cpu 1GB Время генерации с записью в /dev/null 29.043 sec, с записью в файл 719769 msec (12 минут). Оптимизированный код: /* Перебор разных IP */ #include #include #include #include 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); } Функция mtime() возвращает текущее время в миллисекундах, для экономии места опускаю ее код. М.б. будет время и желание сделаю параллельный вариант (IMHO время с записью на диск все равно останется порядка 12 мин.), попробую загрузить все 4 cpu. UPDATE-2 Программа выводит все "счастливые" IP. Вместе с выводом 3084214728 байт в /dev/null 27 sec на DualCore 2.7 GHz (всего 215397594 IP). #include #include #include #include #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,"%d.x.x.x\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); }
Комментариев нет:
Отправить комментарий