Примечание Я не говорю на рубине, но я намереваюсь сделать позже сделал версию ruby только для сравнения скорости:)
Если вы просто итерируете все числа от 0 до 117648 (ruby <<< 'print "666666".to_i(7)') и напечатаете их в формате base-7, вы по крайней мере отбросите любые числа, содержащие 7,8,9.Это включает в себя предложение по оптимизации, предложенное MrE, помимо поднятия задачи на простую int-арифметику вместо манипуляций с последовательностью символов.
Все, что остается, - это проверить наличие хотя бы одного 6. Это сделаеталгоритм пропускает не более 6 элементов подряд, поэтому я считаю его менее важным (среднее количество пропускаемых элементов в общем диапазоне составляет 40%).
Простой тест для 6666666666
(обратите внимание, что это означает вывод 222 009 073 (222M) строк 6-ти чисел)
Оставаясь близко к этой идее, я написал этот весьма оптимизированный код C (я нене говори рубина) чтобы продемонстрировать идею.Я запустил его до 282475248 (соответствует 6666666666 (мод 7)), так что это было больше для измерения: 0m26.5s
#include <stdio.h>
static char buf[11];
char* const bufend = buf+10;
char* genbase7(int n)
{
char* it = bufend; int has6 = 0;
do
{
has6 |= 6 == (*--it = n%7);
n/=7;
} while(n);
return has6? it : 0;
}
void asciify(char* rawdigits)
{
do { *rawdigits += '0'; }
while (++rawdigits != bufend);
}
int main()
{
*bufend = 0; // init
long i;
for (i=6; i<=282475248; i++)
{
char* b7 = genbase7(i);
if (b7)
{
asciify(b7);
puts(b7);
}
}
}
Я также протестировал другой подход, который неудивительноработает менее чем в два раза быстрее, потому что
- эта версия напрямую манипулирует результатами в виде строки ascii, готовой к отображению
- эта версия сокращает флаг
has6 для более глубоких уровней рекурсии - эта версия также оптимизирует «переворот» последней цифры, когда требуется «6»
- код просто короче ...
Выполняетсявремя: 0m12.8s
#include <stdio.h>
#include <string.h>
inline void recursive_permute2(char* const b, char* const m, char* const e, int has6)
{
if (m<e)
for (*m = '0'; *m<'7'; (*m)++)
recursive_permute2(b, m+1, e, has6 || (*m=='6'));
else
if (has6)
for (*e = '0'; *e<'7'; (*e)++)
puts(b);
else /* optimize for last digit must be 6 */
puts((*e='6', b));
}
inline void recursive_permute(char* const b, char* const e)
{
recursive_permute2(b, b, e-1, 0);
}
int main()
{
char buf[] = "0000000000";
recursive_permute(buf, buf+sizeof(buf)/sizeof(*buf)-1);
}
Контрольные показатели измеряются с помощью:
gcc -O4 t6.c -o t6
time ./t6 > /dev/null