6

Как можно реализовать цикл генерации IP адресов по такому алгоритму:

Как мы знаем, IP адрес состоит из маски

*.*.*.*

Допустим, у нас IP 94.122.67.83

Нужно создать такие IP адреса в которых:

Сумма цифр 1 и 2 части будут равны, тоесть: 9+4+1+2+2 = 6+7+8+3

9
  • @Дмитрий Алексеевич, Вы сожалели, что код на Си просто перебор вариантов, а не Ваша задача. Я сделал вывод "счастливых" IP. Код в UPDATE моего ответа. Вместе с выводом 3084214728 байт в /dev/null 27 sec на DualCore 2.7 GHz (всего 215397594 IP).
    – avp
    Commented 13 янв. 2012 в 9:45
  • @avp Я не могу понять, или я идиот, или php, cи и питон лагают. Си не компилит код, php.exe открывает чёрное окно и всё, python запускать отказывается. :( Commented 13 янв. 2012 в 16:39
  • 1
    Я пользуюсь в Windows (и и XP 32-bit и в 7 64-bit) MinGW gcc. Только что я попробовал еще раз. В Emacs открыл файл ips.c скопировал (Copy/Paste) в него текст из моего ответа (тот что после UPDATE-2) и сохранил. В окошке консоли (cmd) выполнил команды: chcp 1251 gcc -O3 -o ips ips.c ips > nul Нужный шрифт в консоли у меня уже стоит. Как сделать см. мой комментарий внизу. Все отработало за 24730 msec. Опишите подробно что делаете, что видите.
    – avp
    Commented 13 янв. 2012 в 18:29
  • Всё, результата я уже достиг. PHP CLI у меня до сих пор не запускается. (просто чёрное окно консоли - ничего больше). Python выдавал ошибку на 1 строчке. А дальше, что только не делал. Помог Dev-C++ Commented 13 янв. 2012 в 18:38
  • Конечно поздно, но!: Зачем вам это надо хранить? Как вы это хотите использовать?
    – timka_s
    Commented 13 янв. 2012 в 18:57

4 ответа 4

5
$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), описанные в вопросе. И таки да, мсье знает толк в извращениях)

9
  • Parse error: syntax error, unexpected ')', expecting ';' in gen.php on line 11 Commented 11 янв. 2012 в 19:51
  • Пардон, ; $i++ дописал. Вы аккуратнее с запуском, я вообще не представляю, сколько он работать будет. Попробовали бы сперва на малых числах (не 256, а 11, например).
    – Sh4dow
    Commented 11 янв. 2012 в 20:16
  • 1
    Да, спасибо, на самом деле вряд ли ответ того заслужил) max_execution_time лучше ставить 0. 9999 - это меньше 3 часов)
    – Sh4dow
    Commented 11 янв. 2012 в 21:08
  • 2
    @Sh4dow, при всем уважении, могли бы и более изящней написать :) Commented 11 янв. 2012 в 22:53
  • 1
    Ну вот в вашем случае логгично просто перед заносом прокси в базу делать примерно так: // $proxy - объект с проксей(ip, порт, дата и пр.) $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; А хранить ради этой цели базу в 3+ГБ мне кажется странным) Тем более, не факт, что запрос к ней пройдет быстрее
    – Sh4dow
    Commented 12 янв. 2012 в 13:24
5

Как вариант с некоторой оптимизацией, могу предложить такое ( 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ГБ минимум.

5
  1. Т.к. по условию задачи, левая и правая части IP адреса равны, то нету смысла перебирать все варианты, достаточно перебрать только левую (или правую) часть.
  2. Так же, т.к. валидными являются все варианты левой части, то разумно сразу сгенерировать все возможные варианты левой части с заранее рассчитанной суммой.

Запускать через 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
6
  • Просто ради интереса: на Си Linux под VirtualBox на 32-bit Windows-XP Dual-Core 2.7 GHz с записью всех результатов в /dev/null 1m 3.90s Размер программы - 49 строк. К вопросу об эффективности сред программирования
    – avp
    Commented 12 янв. 2012 в 9:03
  • 1
    Разумеется, я бы удивился, если было бы иначе :) Кроме того, я привел более "честные" результаты с выводом в файл. С выводом в /dev/null было бы раза в два быстрее. Кстати, привели бы тогда уж исходник на C Commented 12 янв. 2012 в 9:17
  • Обновил ответ. Предполагаю, что если бы у вас был перебор только IP удовлетворяющих условию, то время выполнения было бы меньше. Но даже такие результаты, по моему, весьма показательны :) Особенно если учесть количество кода :) Commented 12 янв. 2012 в 10:18
  • @Ilya Pirogov, если хотите дополнить свою статистику, то я сделал оптимизированную программку на Си (она в UPDATE-2 моего ответа), которая выводит IP, соответствующие условию, так сказать, "счастливые". Время работы у меня 27 сек. при выводе в /dev/null ~3Gbytes. Компилировал gcc -O3
    – avp
    Commented 13 янв. 2012 в 9:59
  • 1
    @Ilya Pirogov, здорово, отличная таблица. При записи "счастливых" в файл, думаю особой разницы между C и pypy не будет. У меня в файл записалось почти за 2 мин.
    – avp
    Commented 13 янв. 2012 в 14:06
5

Генерация и вывод всех адресов на Си

Только что обнаружил ошибку в ней, результат, приведенный внизу (с учетом вывода) не корректен. puts(str); надо перенести во внутренний цикл В этом случае (вывод в /dev/null т.к. на диске у меня места под 64Гбайт файл нет) время работы 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);
}

При копи-паст слегка отступы сползли.

Запустил с записью в файл на диск 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  <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);
}

Функция mtime() возвращает текущее время в миллисекундах, для экономии места опускаю ее код.

М.б. будет время и желание сделаю параллельный вариант (IMHO время с записью на диск все равно останется порядка 12 мин.), попробую загрузить все 4 cpu.


UPDATE-2

Программа выводит все "счастливые" IP. Вместе с выводом 3084214728 байт в /dev/null 27 sec на DualCore 2.7 GHz (всего 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,"%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);
}
20
  • У вас идет полный перебор, а не только IP удовлетворяющие условию, т.ч. сравнение не корректное. Но тем не менее, добавил результаты выполнения к своему ответу. Commented 12 янв. 2012 в 10:11
  • Да, просто полный перебор и генерация в строковом виде 4 млрд. раз. Просто интересно стало время работы, вот и набросал за несколько минут. Кстати, если интересно, заменил содержимое внутреннего цикла (все эти while()...) на один sprintf(), думаю 90% написало бы так, и время возросло до 35m 2.86s ! Ваша программа на питоне это ведь не полный перебор всех IP, а решение вопроса с суммами ?
    – avp
    Commented 12 янв. 2012 в 11:22
  • > Ваша программа на питоне это ведь не полный перебор всех IP, а решение вопроса с суммами ? Да, именно так. Там перебор всего 210 млн. IP Commented 12 янв. 2012 в 11:51
  • Хм. Прошу прощенья, только сейчас заметил вашу ремарку про puts(str). После переноса его во внутренний цикл программа уже больше получаса работает и это без замены while'ов на sprintf. Похоже у вас где-то ошибка в алгоритме. Commented 12 янв. 2012 в 12:26
  • 1
    Что уж бы добить вопрос об эффективности сред программирования. Полный перебор всех IP на питоне: import sys, itertools for ip in itertools.product(*(xrange(256),) * 4): sys.stdout.write( '%d.%d.%d.%d\n' % ip ) Выполняется за: real 19m59.251s user 19m43.120s sys 0m0.051s Т.е. примерно в 4 раза медленнее вашего кода. UPD. Да, интерпретатор здесь pypy. Обычный CPython, думаю, раз в 5 медленнее будет. Commented 12 янв. 2012 в 14:04

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.