2011-12-09 fizzbuzz
by Vasil KolevСтранен сезон е. Сутринта валя, два дни подред пия, едвам намирам време да си свърша работата (не щото е много, а щото нещата се припокриват и има чакане) и съм пил вечерта, че да блогна.
Всички вероятно са чували какво е fizzbuzz, но пак да го кажа, накратко – задачка да се отпечатат числата от 1 до 100, като ако числото се дели на 3, вместо него се печата “Fizz”, ако се дели на 5 вместо него се печата “Buzz”, а ако се дели на 15 вместо него се печата “FizzBuzz”.
(това се дава на интервюта да се види дали човека изобщо може да програмира)
Оригиналното решение, което всеки може да напише на листче (говорим само за C) изглежда така:
for (i=1;i< =100;i++) { if (i%3==0) printf("Fizz"); if (i%5==0) printf("Buzz"); if (i%3!=0 && i%5!=0) printf("%d",i); printf("\n"); }
(което е почти същото на повечето езици за програмиране)
Оптимизираният вариант, който ми хрумна изглеждаше по следния начин:
int i,p; char *s[4]= {"%d\n", "Fizz\n", "Buzz\n", "FizzBuzz\n"}; int s3[3]={1,0,0},s5[5]={2,0,0,0,0}; for (i=1;i<=100;i++) { p= s3[i%3] | s5[i%5]; printf(s[p],i); }
(накратко си избира максимално бързо format string-а, като се прави индекса му от два бита – единия за дали се дели на 3, другия на 5, след което се вика printf() с него и аргумента, а ако във format string-а няма “%”, то вторият аргумент изобщо не се гледа)
Методът с lookup таблиците е известен от зората на програмирането и е един от най-хубавите примери за time-memory trade-off.
Това решение няма branch-ове (т.е. if() и компания) в основния си код, но пък разчита на printf(), който не е особено бърз. На пиенето на Титов му хрумна, че може да се направи масив от функции, които да правят различните неща, но па на мен идеята за call и ret не ми хареса особено, за това се замислих и открих, че в C всъщност има масив от label-и. Съответно, ето извратено и максимално бързо решение:
int i,p; static void *pos[4]= {&&digit, &&fizz, &&buzz, &&fizzbuzz}; int s3[3]={1,0,0},s5[5]={2,0,0,0,0}; char buff[2048]; char dgts[16]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'}; int buffpos=0; for (i=1;i<=100;i++) { p= s3[i%3] | s5[i%5]; goto *pos[p]; fizz: memcpy(&buff[buffpos],"Fizz", 4); buffpos+=4; goto end; buzz: memcpy(&buff[buffpos],"Buzz", 4); buffpos+=4; goto end; fizzbuzz: memcpy(&buff[buffpos],"FizzBuzz", 8); buffpos+=8; goto end; digit: buff[buffpos++]=dgts[i/16]; buff[buffpos++]=dgts[i%16]; end: buff[buffpos++]='\n'; } write(1,buff, buffpos);
(т.е. както в предния пример имаме масив от format string-ове, тук имаме масив от позиции, на които директно можем да скочим. Също така не викаме никакви външни функции (memcpy се inline-ва и е от едни по-бързи инструкции) и единствения branch, който имаме е за for() (който също може да се избегне с една lookup таблица и едни goto-та, ама това вече ще е гадно)
Човек, способен да напише подобен код на интервю вероятно трябва да го пратят в Карлуково.
Ако на някой му хрумне нещо по-забавно, да пише :)
Update: Оптимизация – да се изместят p3, p5 и dgts като глобални променливи, понеже ако са във функцията, компилатора ги прави на много mov-ове.
Tags: крокодилски, работа
December 9th, 2011 at 03:18
Е, очевидно, двете деления с остатък могат да се заменят само с едно:
int s15[15]={3,0,0,1,0,2,1,0,0,1,2,0,1,0,0}
…
p=s15[i%15]
После и %15 може да се разкара примерно така:
int i, i_mod_15;
for (i=1, i_mod_15=1;i<=100;i++) {
p=s15[i_mod_15];
…
i_mod_15++;
if (i_mod_15 == 15)
i_mod_15 = 0;
}
последният if може да се направи без branch на i686, с CMOVxx инструкция:
http://www.rcollins.org/p6/opcodes/CMOV.html
(не знам дали C компилаторът ще се сети да го направи, ама принципно би трябвало да поддържа CMOV, ако му кажеш да компилира за P6+ и включиш оптимизациите)
December 9th, 2011 at 03:33
Също, не е вярно това, което си написал за версията с goto-тата, че няма branch-ове, тъй като goto-то _е_ branch :)
December 9th, 2011 at 10:40
Едно бързо решение на задачата би било, ако се зададе константен стринг, съответстващ на 100-те числа и той да се отпечата. Разбира се, в повечето случаи, кандидата, който предложи подобно решение, няма да бъде назначен. Според мен напоследък, за разлика от ранните години на програмирането, все по-важни са следните неща:
1. Кода да е добре документиран;
2. Кода да е лесно разбираем от различни от създателя му програмисти;
3. Кода да е гъвкав. Ако условието на задачата се промени, наложителните промени в кода да са минимални.
4. Кода да е защитен, срещу евентуални грешки на други програмисти, които го използват
Ето едно примерно решение, което би ми харесало:
/**
* Функция, която отпечатва числа от зададен интервал, като заменя тези от тях,
* които се делят на специални делители, със специални стрингове. Когато числото
* се дели на няколко делителя, специалните стрингове се конкатинират
*
* @param int $iMin Начало на интервала
* @param int $iMax Край на интервала
* @param array $specials Списък със ‘специални’ делители и съответстващи им стрингове
*/
function printFizzBuzz($iMin = 1, $iMax = 100, $specials = array(3 => ‘Fizz’, 5 => ‘Buzz’))
{
// Очакваме, че краят входния интервал не е по-малък от началото му
expect($iMin <= $iMax);
for($i = $iMin; $i $spStr) {
if($i % $spDiv == 0) {
// Конкатинираме към буфера “специалния” текст, съответстващ на делителя
$buff .= $spStr;
}
}
// Ако нямаме “специален” стринг, подготвяме за отпечатване текущото число
$buff = $buff ? $buff : $i;
// Отпечатваме текущото число
echo “” . $buff;
}
}
December 9th, 2011 at 11:12
Сигурен съм, че навсякъде има branch-ове, въпроса е къде са по-малко и къде са по-предвидими. Виж кое за какво време се изпълнява и виж при различни оптимизации на компилатора :D
December 9th, 2011 at 13:13
HAI
CAN HAS STDIO?
I HAS A VAR IZ 0
IM IN YR LOOP
UPZ VAR!!1
IZ VAR BIGR THAN 100?
GTFO.
KTHX
IZ VAR LEFTOVAR 15 LIEK 0?
VISIBLE “FIZZBUZZ”
KTHX
ORLY?
IZ VAR LEFTOVAR 5 LIEK 0?
VISIBLE “BUZZ”
KTHX
ORLY?
IZ VAR LEFTOVAR 3 LIEK 0?
VISIBLE “FIZZ”
KTHX
NOWAI
VISIBLE VAR
KTHX
KTHX
KTHXBYE
December 9th, 2011 at 15:13
Всичките решения тук са незадоволителни. Ако трябва да се променя или разширява логиката на програмата става лошо. Защо не сте отделили изписването на число/физ/бъз от цикъла?! Слабо, слабо, колеги.
Първото нещо, което трябва да се гледа е дали кандидатът има усет за логически ненатоварен код (не знам дали някой е ползвал този кретенски термин :)).
П.С. Коментарите си имат своето място и това определено не е на всеки ред от програмата! В горния пример само първият коментар е на място.
December 9th, 2011 at 16:14
В първия оптимизиран вариант, не е ли пропуснато едно %d?
В смисъл, реда
char *s[4]= {“\n”, “Fizz\n”, “Buzz\n”, “FizzBuzz\n”};
да бъде
char *s[4]= {“%d\n”, “Fizz\n”, “Buzz\n”, “FizzBuzz\n”};
Не, че е съществено за дискусията, но го гледах известно време и не мога да си обясня как ще работи без него.
December 9th, 2011 at 16:28
@Радослав, да, вярно, орпавих го.
December 9th, 2011 at 17:11
а
ajde i az da se iztropam tuka, na common lisp
December 9th, 2011 at 18:44
Абе вие сте абсолютни аматьори, като сте почнали го докарайте докрай!
char * say[100] = { “1\n”, “2\n”, “Fizz\n”, “4\n”, “Buzz\n”, “Fizz\n”, “7\n”, “8\n”, “Fizz\n”, “Buzz\n”, “11\n”, “Fizz\n”, “13\n”, “14\n”, “FizzBuzz\n”, “16\n”, “17\n”, “Fizz\n”, “19\n”, “Buzz\n”, “Fizz\n”, “22\n”, “23\n”, “Fizz\n”, “Buzz\n”, “26\n”, “Fizz\n”, “28\n”, “29\n”, “FizzBuzz\n”, “31\n”, “32\n”, “Fizz\n”, “34\n”, “Buzz\n”, “Fizz\n”, “37\n”, “38\n”, “Fizz\n”, “Buzz\n”, “41\n”, “Fizz\n”, “43\n”, “44\n”, “FizzBuzz\n”, “46\n”, “47\n”, “Fizz\n”, “49\n”, “Buzz\n”, “Fizz\n”, “52\n”, “53\n”, “Fizz\n”, “Buzz\n”, “56\n”, “Fizz\n”, “58\n”, “59\n”, “FizzBuzz\n”, “61\n”, “62\n”, “Fizz\n”, “64\n”, “Buzz\n”, “Fizz\n”, “67\n”, “68\n”, “Fizz\n”, “Buzz\n”, “71\n”, “Fizz\n”, “73\n”, “74\n”, “FizzBuzz\n”, “76\n”, “77\n”, “Fizz\n”, “79\n”, “Buzz\n”, “Fizz\n”, “82\n”, “83\n”, “Fizz\n”, “Buzz\n”, “86\n”, “Fizz\n”, “88\n”, “89\n”, “FizzBuzz\n”, “91\n”, “92\n”, “Fizz\n”, “94\n”, “Buzz\n”, “Fizz\n”, “97\n”, “98\n”, “Fizz\n”, “Buzz\n” };
for (i=1;i< =100;i++)
{
printf(say[i]);
}
;]
December 9th, 2011 at 18:50
Чакайте, тва не е оптимално, има бранчове!
ето по добро:
char * say_this = “1\n
2\n
Fizz\n
4\n
Buzz\n
Fizz\n
7\n
8\n
Fizz\n
Buzz\n
11\n
Fizz\n
13\n
14\n
FizzBuzz\n
16\n
17\n
Fizz\n
19\n
Buzz\n
Fizz\n
22\n
23\n
Fizz\n
Buzz\n
26\n
Fizz\n
28\n
29\n
FizzBuzz\n
31\n
32\n
Fizz\n
34\n
Buzz\n
Fizz\n
37\n
38\n
Fizz\n
Buzz\n
41\n
Fizz\n
43\n
44\n
FizzBuzz\n
46\n
47\n
Fizz\n
49\n
Buzz\n
Fizz\n
52\n
53\n
Fizz\n
Buzz\n
56\n
Fizz\n
58\n
59\n
FizzBuzz\n
61\n
62\n
Fizz\n
64\n
Buzz\n
Fizz\n
67\n
68\n
Fizz\n
Buzz\n
71\n
Fizz\n
73\n
74\n
FizzBuzz\n
76\n
77\n
Fizz\n
79\n
Buzz\n
Fizz\n
82\n
83\n
Fizz\n
Buzz\n
86\n
Fizz\n
88\n
89\n
FizzBuzz\n
91\n
92\n
Fizz\n
94\n
Buzz\n
Fizz\n
97\n
98\n
Fizz\n
Buzz\n”;
printf(say_this);
December 9th, 2011 at 19:25
И това не е оптимално, използвай write(). printf() има ненужен parser.
December 9th, 2011 at 20:02
iMac:~ zaphod$ time for((i=0;i/dev/null; done
real 2m52.991s
user 0m29.622s
sys 1m39.910s
iMac:~ zaphod$ time for((i=0;i/dev/null; done
real 2m53.679s
user 0m29.991s
sys 1m39.895s
iMac:~ zaphod$
December 9th, 2011 at 20:04
off, нещо беше одрязано :) първото е варианта със стринга, второто на маниакса лейбълите
December 10th, 2011 at 07:07
perl -e ‘print+(Fizz)[$_%3].(Buzz)[$_%5]||$_,$/for 1..100’
December 11th, 2011 at 00:24
Принципно можеш да набуташ цялата програмна логика в printf-то, но това не е оптимизация, а чиста проба обфускация:
for (i=1; i> 16) + (n & 0xFFFF);
n = (n >> 8) + (n & 0x00FF);
n = (n >> 4) + (n & 0x000F);
n = (n >> 2) + (n & 0x0003);
n = (n >> 2) + (n & 0x0003);
return (0x0924 >> (n <> 16) + (n & 0xFFFF);
n = (n >> 8) + (n & 0x00FF);
n = (n >> 4) + (n & 0x000F);
n = (n >> 4) – ((n >> 2) & 3) + (n & 3);
return (01043210432 >> 3 * (n + 3)) & 7;
}
@Черво, има си предикат zerop :)
December 11th, 2011 at 00:30
Нещо горе се сбърка, виж тук: http://pastebin.com/GkGM0JYZ Не помня откъде съм намерил кода, но си струва, ако делението е бавно.
December 11th, 2011 at 01:22
(link: http://pastebin.com/tEkePZBA )
Като стана дума за compile-time оптимизации от сорта на големия низ… ахъм.
December 11th, 2011 at 02:21
Ха! Някой вече е написал по-чисто решение на FizzBuzz с темплейти:
http://labs.cybozu.co.jp/blog/kazuho/archives/2008/04/fizzbuzz_cpp_template.php
December 11th, 2011 at 21:02
И fizzbuzz ви възбужда ?? :О
December 11th, 2011 at 21:13
@viz, възбуждат ни извращенията :)
December 12th, 2011 at 00:04
Ситуацията тук е “спести време, спаси лаптоп”. :-)
December 14th, 2011 at 01:08
Аматьори…
December 15th, 2011 at 13:36
Възбуждат и още как, на монитора му изгоря червеното от срам.
: FIZZ DUP 3 MOD 0= 0< IF ." FIZZ" 0 SWAP – THEN ;
: BUZZ DUP DUP 5 MOD 0= 0< IF 0< IF ." BUZZ" ELSE ." BUZZ" THEN ELSE 0< IF
DROP ELSE ." " . THEN THEN ;
: FIZZBUZZ CR 101 1 DO I FIZZ BUZZ LOOP ;
Между другото в C няма възможност да се вземе адрес на label, тоя гъдел е от GCC.
December 15th, 2011 at 14:00
Едно решение от колегите: http://ideone.com/rVUsw
December 15th, 2011 at 14:20
И още едно: http://ideone.com/1pOoC
December 16th, 2011 at 03:03
Тези дни се упражнявам да пиша на Erlang :)
fb(N) when N rem 15 == 0 -> fizzbuzz;
fb(N) when N rem 3 == 0 -> fizz;
fb(N) when N rem 5 == 0 -> buzz;
fb(N) -> N.
fb() -> io:format(“~p”, [[fb(X) || X <- lists:seq(1,100)]]).
December 20th, 2011 at 02:01
Имам странното усещане, че голямата lookup таблица е най-бързото решение. modulo операциите са бавни (поне на x86 и вероятно на почти всяка друга архитектура). goto и branching-а са скъпи операции, еб*ваш майката на pipeline-а доволно добре. memcpy() така или иначе е overhead. Лошият голям цикъл до 100 можеш да го unroll-неш, понеже знаеш броя на итерациите. Според мен решението с голямата lookup таблица със 100 елемента готови за печатане с puts е най-бързото (и съответно най-грозното ако решиш да смениш броя на итерациите).
December 20th, 2011 at 02:05
Иначе ехех решението на NOP e най-бързо :)
January 6th, 2013 at 17:06
Вчера си нямах работа и си играех с това на PHP:
<?php
for ($i=1;$i<=100;$i++)
{
echo ( ( ( ( $i % 5 ) != 0 ) && ( ($i % 3) != 0 ) ) ? $i : ( ( ( ($i % 3) === 0) ? 'Fizz' : '' ) . ( (($i % 5) === 0) ? 'Buzz' : '' ) ) ) . '’;
}
?>
March 5th, 2017 at 22:57
Хайде и от мен един
for our $i (1..100){
print ” vizz\n” if ($i%3==0);
print ” buzz\n” if ($i%5==0);
print ” vizzbuzz\n” if ($i%15==0);
}
March 6th, 2017 at 00:09
@viz, браво бе. Я сега виж по-горните и си опрви грешките :)
March 6th, 2017 at 14:16
Добре де.. :D
#!/usr/bin/perl
for my $i (1..100){
printf “vizz” if ($i%3==0);
printf “buzz” if ($i%5==0);
printf “%d”, $i if ($i%3!=0 && $i%5!=0);
printf “\n”;
}
#!/usr/bin/perl
my @fb = (“1\n”, “2\n”, “Fizz\n”, “4\n”, “Buzz\n”, “Fizz\n”, “7\n”, “8\n”,
“Fizz\n”, “Buzz\n”, “11\n”, “Fizz\n”, “13\n”, “14\n”, “FizzBuzz\n”,
“16\n”, “17\n”, “Fizz\n”, “19\n”, “Buzz\n”, “Fizz\n”, “22\n”, “23\n”,
“Fizz\n”, “Buzz\n”, “26\n”, “Fizz\n”, “28\n”, “29\n”, “FizzBuzz\n”,
“31\n”, “32\n”, “Fizz\n”, “34\n”, “Buzz\n”, “Fizz\n”, “37\n”, “38\n”,
“Fizz\n”, “Buzz\n”, “41\n”, “Fizz\n”, “43\n”, “44\n”, “FizzBuzz\n”,
“46\n”, “47\n”, “Fizz\n”, “49\n”, “Buzz\n”, “Fizz\n”, “52\n”, “53\n”,
“Fizz\n”, “Buzz\n”, “56\n”, “Fizz\n”, “58\n”, “59\n”, “FizzBuzz\n”,
“61\n”, “62\n”, “Fizz\n”, “64\n”, “Buzz\n”, “Fizz\n”, “67\n”, “68\n”,
“Fizz\n”, “Buzz\n”, “71\n”, “Fizz\n”, “73\n”, “74\n”, “FizzBuzz\n”,
“76\n”, “77\n”, “Fizz\n”, “79\n”, “Buzz\n”, “Fizz\n”, “82\n”, “83\n”,
“Fizz\n”, “Buzz\n”, “86\n”, “Fizz\n”, “88\n”, “89\n”, “FizzBuzz\n”,
“91\n”, “92\n”, “Fizz\n”, “94\n”, “Buzz\n”, “Fizz\n”, “97\n”, “98\n”,
“Fizz\n”, “Buzz\n”);
print @fb;
#!/usr/bin/perl
for my $i (1..100) {
!($i%15) ? print “FizzBuzz\n” :
!($i%3) ? print “Fizz\n” :
!($i%5) ? print “Buzz\n” :
print $i.”\n”;
}
March 6th, 2017 at 14:40
Може и така..
print (($_ % 15 ? $_ % 5 ? $_ % 3 ? $_ : ‘vizz’ : ‘buzz’ : ‘vizzbuzz’) . “\n”) || $_ for 1..100;
March 6th, 2017 at 18:03
#!/usr/bin/perl
use feature(say);
use utf8;
binmode(STDOUT, utf8);
my @fb = (“1”, “2”, “Визз”, “4”, “Бъзз”, “Визз”, “7”, “8”,
“Визз”, “Бъзз”, “11”, “Визз”, “13”, “14”, “ВиззБъзз”,
“16”, “17”, “Визз”, “19”, “Бъзз”, “Визз”, “22”, “23”,
“Визз”, “Бъзз”, “26”, “Визз”, “28”, “29”, “ВиззБъзз”,
“31”, “32”, “Визз”, “34”, “Бъзз”, “Визз”, “37”, “38”,
“Визз”, “Бъзз”, “41”, “Визз”, “43”, “44”, “ВиззБъзз”,
“46”, “47”, “Визз”, “49”, “Бъзз”, “Визз”, “52”, “53”,
“Визз”, “Бъзз”, “56”, “Визз”, “58”, “59”, “ВиззБъзз”,
“61”, “62”, “Визз”, “64”, “Бъзз”, “Визз”, “67”, “68”,
“Визз”, “Бъзз”, “71”, “Визз”, “73”, “74”, “ВиззБъзз”,
“76”, “77”, “Визз”, “79”, “Бъзз”, “Визз”, “82”, “83”,
“Визз”, “Бъзз”, “86”, “Визз”, “88”, “89”, “ВиззБъзз”,
“91”, “92”, “Визз”, “94”, “Бъзз”, “Визз”, “97”, “98”,
“Визз”, “Бъзз”);
say join(“\n”,reverse(@fb));