Здравствуйте, Заяц, Вы писали:
BB>>- почему List<byte>? почему не массив? З>Так ведь нужен набор переменной длины. З>Да и в msdn написано, что "The List<T> class is the generic equivalent of the ArrayList class." А про ArrayList — что это просто динамический массив "Implements the IList interface using an array whose size is dynamically increased as required".
Для хранения-то можно и в массив конвертировать. У вас же immutable объект, как я понял.
BB>>- вычисление факториала, очевидно, может пользоваться ближащим закэшированным значением; З>Второй метод FactorialWithCache так и делает. Рекурсивно вызвав себя сколько-то раз он дойдёт до ближайшего закэшированного. З>Вроде доп. расходы на вызовы и проверки каждый раз по кэшу не должны быть сильно большими на фоне перемножений. Или я ошибаюсь?
Чтобы в этом убедиться нужно измерить производительность. Можно, конечно, попытаться теоретически
порассуждать, но едва ли это будет эффективнее тестирования по времени и результатам.
Рекурсии я бы избегал — слишком медленно получается.
Наличие двух методов Factorial и FactorialWithCache тоже не очень хороший знак.
Я бы сделал один, но с параметром. Что-то типа:
BB>>- Getvalue(bool inExpFormat) — зачем так? почему не ToString(string format)? З>Это просто так у меня получилось, на юниора ж шёл. Конечно надо всё делать со стандартными названиями.
Тут дело скорее не в названии, а в использовании стандартного подхода к форматированию.
И да, забыл сюда же добавить использование StringBuilder вместо конкатенации, использованной вами.
Z>>>Считает вроде правильно, по интернет-калькулятору факториалов проверял. BB>>Где тесты, которые это подтверждают? З>Тесты были, просто здесь не приводил, слишком большие строки там. Проверял просто — несколько значений, типа для 100, 1000 и 5000 взял с калькулятора факториалов и с ними сравнил.
Внутрь методов почти не заглядывал.
Приведу первое, что бросилось в глаза.
Здравствуйте, zayats, Вы писали:
Z>
Z>namespace bigint
Z>{
Z> class BigInt
Z> {
// 1) Нарушение SRP: мух от котлет нужно отделять, т.е. числа отдельно - вычислительные алгоритмы отдельно
//посмотрите в сторону System.Math
// 2) Имена методов должны начинаться с глагола, т.е. не Factorial() а ComputeFactorial()
// в таком случае второй метод может называться GetFactorial()
// не нужно в имени метода описывать способ которым вы что-то делаете, просто само действие
Z> public static BigInt Factorial(int val)
Z> public static BigInt FactorialWithCache(int val)
Z> private static Dictionary<int, BigInt> factsCache_ = new Dictionary<int, BigInt>();
// 3) Неверное, вводящее в заблуждение, название метода.
// этот метод не возвращает значение, он само число преобразует в строку,
// соответственно должен называться или ConvertToString() или просто string Convert()
// но будет значительно лучше, если он будет называться просто ToString()
// и при этом будет переопределять соответствующий виртуальный метод System.Object
// 4) Загадочные сокращения в именах inExpFormat - в экспериментальном формате что-ли?
// как минимум должно быть "еxponential"
Z> public string GetValue(bool inExpFormat = false)
Z>}
//5) Вот это не тест.
[s]Z>static void Main(string[] args)
Z>{
Z> Console.SetOut(new System.IO.StreamWriter("fact.log", true));
Z> for (int i = 0; i <= 5000; ++i)
Z> Console.WriteLine(string.Format("{0:00000}!: {1}", i, BigInt.FactorialWithCache(i).GetValue()));
Z>}
Z>
Предыстория такова. Хотел на С#-юниора устроиться, проходил телефонное интервью. И среди прочего интервьюер спросил "а вот если тебе надо посчитать точный факториал некоего большого числа, например, 2000, как будешь делать?". Я ответил, что мол, напишу класс для работы с целыми числами любой длины и потом факториал с ними посчитаю. О, говорит, он, круто, давай напиши такое тестовое задание, присылай нам и на собеседование приходи, там обсудим. Вот я и написал нижеследующее, пришёл на собеседование, вроде поговорили, обсудили. И потом всё стихло, ни звонков, ничего. Сейчас-то я работаю в другом месте, всё ок. Но интересно стало, это насколько плох мой код, из-за него меня не взяли, или уже на собеседовании облажался, или просто не понравился.
Покритикуйте, пожалуйста. Что класс недоделан я знаю, вчастности нет оператора -. Ну и си-стиль наверное прёт. Но главное мне было нужно факториал сделать. Считает вроде правильно, по интернет-калькулятору факториалов проверял.
Заранее спасибо.
using System;
using System.Collections.Generic;
namespace bigint
{
class BigInt
{
public BigInt() { }
public BigInt(int val)
{
isPos_ = (val >= 0);
int v = Math.Abs(val);
while (v > 0)
{
val_.Add((byte)(v % 10));
v /= 10;
}
}
public BigInt(BigInt val)
{
isPos_ = val.isPos_;
val_.AddRange(val.val_);
}
public static BigInt operator+(BigInt val1, BigInt val2)
{
if (val1.isPos_ == val2.isPos_)
return Add(val1, val2);
else
return Deduct(val1, val2);
}
public static BigInt operator+(BigInt val1, int val2)
{
return val1 + new BigInt(val2);
}
public static BigInt operator*(BigInt val, int n)
{
BigInt retVal = new BigInt() { isPos_ = n >= 0 ? val.isPos_ : !val.isPos_};
int absN = Math.Abs(n);
if (absN == 0)
return retVal;
if (absN == 1)
return retVal + val;
int sqrt = (int)Math.Floor(Math.Sqrt(absN));
BigInt tmp = new BigInt(val);
for (int i = 0; i < sqrt - 1; ++i)
tmp = tmp + val;
for (int i = 0; i < absN / sqrt; ++i)
retVal = retVal + tmp;
for (int i = 0; i < absN % sqrt; ++i)
retVal = retVal + val;
return retVal;
}
public static BigInt Factorial(int val)
{
BigInt retVal = new BigInt(1);
for (int i = 2; i <= val; i++)
retVal = retVal * i;
return retVal;
}
private static Dictionary<int, BigInt> factsCache_ = new Dictionary<int, BigInt>();
public static BigInt FactorialWithCache(int val)
{
if (val <= 1)
return new BigInt(1);
if (!factsCache_.ContainsKey(val))
factsCache_.Add(val, FactorialWithCache(val - 1) * val);
return factsCache_[val];
}
public string GetValue(bool inExpFormat = false)
{
string retVal = "";
if (val_.Count == 0)
return"0";
if (!inExpFormat)
{
foreach (var n in val_)
retVal = n.ToString() + retVal;
if (!isPos_)
retVal = "-" + retVal;
}
else
{
for (int i = Math.Max(val_.Count - 9, 0); i < val_.Count; ++i)
{
if (i == val_.Count - 1)
retVal = "." + retVal;
retVal = val_[i] + retVal;
}
retVal += " x 10^" + (val_.Count - 1).ToString();
if (!isPos_)
retVal = "-" + retVal;
}
return retVal;
}
private static BigInt Add(BigInt val1, BigInt val2)
{
BigInt retVal = new BigInt(val1) { isPos_ = val1.isPos_ };
int minSize = Math.Min(retVal.val_.Count, val2.val_.Count);
bool trans = false;
for (int i = 0; i < minSize; ++i)
{
int n = retVal.val_[i] + val2.val_[i];
if (trans)
++n;
trans = (n > 9);
retVal.val_[i] = (byte)(n % 10);
}
if (retVal.val_.Count < val2.val_.Count)
for (int i = minSize; i < val2.val_.Count; ++i)
retVal.val_.Add(val2.val_[i]);
if (trans)
{
int i = minSize;
while (trans)
{
if (retVal.val_.Count == i)
{
retVal.val_.Add(1);
trans = false;
}
else
{
int n = retVal.val_[i] + 1;
trans = (n > 9);
retVal.val_[i] = (byte)(n % 10);
}
++i;
}
}
return retVal;
}
private static BigInt Deduct(BigInt val1, BigInt val2)
{
bool isGrt = isGreaterOrEqual(val1.val_, val2.val_);
BigInt retVal = new BigInt(isGrt ? val1 : val2) { isPos_ = isGrt ? val1.isPos_ : !val1.isPos_ };
int minSize = Math.Min(val1.val_.Count, val2.val_.Count);
bool trans = false;
for (int i = 0; i < minSize; ++i)
{
int n = retVal.val_[i] - (isGrt ? val2.val_[i] : val1.val_[i]);
if (trans)
--n;
trans = (n < 0);
if (n < 0)
n += 10;
retVal.val_[i] = (byte)(n % 10);
}
int ii = retVal.val_.Count - 1;
while (ii >= 0 && retVal.val_[ii] == 0)
{
retVal.val_.RemoveAt(ii);
--ii;
}
if (retVal.val_.Count == 0)
retVal.isPos_ = false;
return retVal;
}
private static bool isGreaterOrEqual(List<byte> l1, List<byte> l2)
{
if (l1.Count > l2.Count)
return true;
if (l1.Count < l2.Count)
return false;
if (l1.Count == 0)
return true;
for (int i = l1.Count -1; i >= 0; --i)
{
if (l1[i] > l2[i])
return true;
if (l1[i] < l2[i])
return false;
}
return true;
}
private List<byte> val_ = new List<byte>();
private bool isPos_ = true;
}
}
Использование:
static void Main(string[] args)
{
Console.SetOut(new System.IO.StreamWriter("fact.log", true));
for (int i = 0; i <= 5000; ++i)
Console.WriteLine(string.Format("{0:00000}!: {1}", i, BigInt.FactorialWithCache(i).GetValue()));
}
Здравствуйте, HowardLovekraft, Вы писали:
HL>А как давно дело было? А то вот...
Это знаю, да. Задача была именно сделать с нуля. Дело было не очень давно.
Здравствуйте, GGoga, Вы писали:
Z>>Предыстория такова. Хотел на С#-юниора устроиться, проходил телефонное интервью... GG>Фирма случаем не в Киеве находится?
Нет, дело в Москве происходило.
Re: Покритикуйте тестовой задание про факториал.
От:
Аноним
Дата:
31.08.12 08:00
Оценка:
Здравствуйте, zayats, Вы писали:
Z>Покритикуйте, пожалуйста. Что класс недоделан я знаю, вчастности нет оператора -. Ну и си-стиль наверное прёт. Но главное мне было нужно факториал сделать. Считает вроде правильно, по интернет-калькулятору факториалов проверял. Z>Заранее спасибо.
Здравствуйте, zayats, Вы писали:
Z>Покритикуйте, пожалуйста. Что класс недоделан я знаю, вчастности нет оператора -. Ну и си-стиль наверное прёт. Но главное мне было нужно факториал сделать.
Навскидку:
1) стиль
— поля в конце, постфиксы, приватные методы с заглавной, тернарный оператор
2) качество:
— immutable поля без readonly;
— почему List<byte>? почему не массив?
— вычисление факториала, очевидно, может пользоваться ближащим закэшированным значением;
— Getvalue(bool inExpFormat) — зачем так? почему не ToString(string format)?
Z>Считает вроде правильно, по интернет-калькулятору факториалов проверял.
Где тесты, которые это подтверждают?
El pueblo unido jamás será vencido.
Re[2]: Покритикуйте тестовой задание про факториал.
От:
Аноним
Дата:
31.08.12 10:21
Оценка:
Здравствуйте, Аноним, Вы писали:
А>http://en.wikipedia.org/wiki/Schönhage–Strassen_algorithm
>In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2215 to 2217 (10,000 to 40,000 decimal digits).
2000! < 2000^2000 < 10^8000
А>Много лишнего кода. Код не читаемый. Постфиксы.
А это да, правда.
Re[2]: Покритикуйте тестовой задание про факториал.
Здравствуйте, IObserver, Вы писали:
IO>И вы правда думаете, что нет библиотек с открытым кодом, которые можно использовать? То есть никому на свете до вас это не понадобилось?
Уверен, что библиотеки есть. Так я же не для практических целей, а как тестовое задание.
Re[3]: Покритикуйте тестовой задание про факториал.
Здравствуйте, Заяц, Вы писали:
З>Здравствуйте, IObserver, Вы писали:
IO>>И вы правда думаете, что нет библиотек с открытым кодом, которые можно использовать? То есть никому на свете до вас это не понадобилось? З>Уверен, что библиотеки есть. Так я же не для практических целей, а как тестовое задание.
Но на собеседовании-то спрашивали не "какое бы вам тестовое задание дать", а "а вот если тебе надо посчитать точный факториал некоего большого числа, например, 2000, как будешь делать?"
Re[2]: Покритикуйте тестовой задание про факториал.
Спасибо за сообщение.
Z>>Покритикуйте, пожалуйста. Что класс недоделан я знаю, вчастности нет оператора -. Ну и си-стиль наверное прёт. Но главное мне было нужно факториал сделать. BB>Навскидку: BB>1) стиль BB>- поля в конце, постфиксы, приватные методы с заглавной, тернарный оператор
Ок. BB>2) качество: BB>- immutable поля без readonly;
Ок. BB>- почему List<byte>? почему не массив?
Так ведь нужен набор переменной длины.
Да и в msdn написано, что "The List<T> class is the generic equivalent of the ArrayList class." А про ArrayList — что это просто динамический массив "Implements the IList interface using an array whose size is dynamically increased as required".
BB>- вычисление факториала, очевидно, может пользоваться ближащим закэшированным значением;
Второй метод FactorialWithCache так и делает. Рекурсивно вызвав себя сколько-то раз он дойдёт до ближайшего закэшированного.
Вроде доп. расходы на вызовы и проверки каждый раз по кэшу не должны быть сильно большими на фоне перемножений. Или я ошибаюсь?
BB>- Getvalue(bool inExpFormat) — зачем так? почему не ToString(string format)?
Это просто так у меня получилось, на юниора ж шёл. Конечно надо всё делать со стандартными названиями.
Z>>Считает вроде правильно, по интернет-калькулятору факториалов проверял. BB>Где тесты, которые это подтверждают?
Тесты были, просто здесь не приводил, слишком большие строки там. Проверял просто — несколько значений, типа для 100, 1000 и 5000 взял с калькулятора факториалов и с ними сравнил.
Re[4]: Покритикуйте тестовой задание про факториал.
Здравствуйте, pentagra, Вы писали:
P>Но на собеседовании-то спрашивали не "какое бы вам тестовое задание дать", а "а вот если тебе надо посчитать точный факториал некоего большого числа, например, 2000, как будешь делать?"
Согласен, я же не полность дословно разговор приводил. Смысл моего ответа был — надо использовать какой-нибудь класс для работы с большими числами и в нём посчитать. На что был ответ — ну вот и давай ты сделаешь такой класс, и факториал заодно в качестве тестового задания. Может конечно я всё не так понял и от меня именно просто использование всего стандартного хотели.
Здравствуйте, zayats, Вы писали:
Z>Предыстория такова. Хотел на С#-юниора устроиться, проходил телефонное интервью. И среди прочего интервьюер спросил "а вот если тебе надо посчитать точный факториал некоего большого числа, например, 2000, как будешь делать?"
Если вопрос был в контексте чего-то, это "чего-то" надо писать. Если просто "от балды", то возможно хотели проверить, кто на том конце — велосипедист, математик или разумный инженер:
Велосипедист: сразу бросится писать свой факториал с блэкджеком и хэшами. Такой сразу идёт в зад, потому что на фирме он должен выдавать быстрый и качественный результат, а не писать каждую ерунду с нуля.
Математик: Тоже, вобщем-то, узколобый для продакшена — сразу полезет в учебники искать сокращённое умножение и т.п., т.е. будет пытаться сделать то же, что и велосипедист, но чуть более продвинуто.
Инженер: сразу начнёт гуглить на пример ГОТОВОГО РЕШЕНИЯ, ибо не он первый, кому понадобились факториалы. Возможно даже, решение давно уже есть в самом .NET; И только потом, не найдя решения, можно браться за ручную работу. Опять же, может даже не сразу в математику, а как топикстартер — на кэше. И только после оценки "недостаточная производительность" лезть в математику.
Но даже с т.з. этого конкретного задания, вы его сделали "overqualified": вам что, дали задание "математическая библиотека"? Нет. Тогда зачем вам эти "большие цифры"? Простая функция "умножить нивротчисло на нивротчисло" решает все проблемы. Это тоже важно: насколько разумно вы умеете решать конкретные задачи. Антипример: "работяги" из Оперы, потратившие уйму времени на "свои контролы", в результате чего до сих пор лажают на элементарном взаимодействии — ребята "переусердствовали" в решении простой задачи: ДВУплатформенный браузер.
