F(F(n)) = -n

[109]

ах да, я ж тут эту задачку типа решил. напомню, кто не знает: требуется написать функцию, принимающую аргумент типа int, которая, будучи дважды приложена, меняет знак числа.

static class I_Function
{
	static void Main()
	{
		Console.WriteLine("F(F(42)) = {0}", F(F(42)));
		Console.WriteLine("F(F(-5)) = {0}", F(F(-5)));
		Console.ReadKey();
	}

	static object F(object num)
	{
		if (num is Helper)
			return -((Helper)num).num;
		else if (num is int)
		{
			if ((int)num == int.MinValue)
				throw new Exception("Unsupported argument value");
			else
				return new Helper((int)num);
		}
		else throw new Exception("Unsupported argument type");
	}

	class Helper { internal int num; internal Helper(int num) { this.num = num; } }
}

претензий по поводу MinValue не предлагать: ряд функций, принимающих int, бросают на него. в частности, все функции, которым зачем-то надо делать Abs().

претензии по поводу возврата boxed int вместо ожидаемого unboxed более интересны. напомню, что это задачка для интервью. формальная отмазка могла бы звучать как "требование unboxed int не было озвучено в явном виде" :)

на самом деле, мой код просто демонстрирует идею - поскольку если постараться, то пойнтер можно упихать в соответствующего размера целочисленный тип, а потом, при разборе, аккуратно проверять, лежит ли в том месте нужный тип. тогда и unboxed можно возвращать.

Comments

[faceted-jacinth.livejournal.com]

Аааа! Отлично!


пойнтер можно упихать в соответствующего размера целочисленный тип, а потом, при разборе, аккуратно проверять, лежит ли в том месте нужный тип.
----
Неа, нельзя, бокснутый инт отличается от анбокснутого наличием классАйди (именно это позволяет тебе его отличить от хелпера) и тебе оно обязательно понадобится, хоть один бит дополнительный, но нужен, чтобы отличить инт от неинта-позволяющего-достать-или-вычислить-предыдущий-инт.

[109.livejournal.com]

поясняю: входящий инт кастить в пойнтер и проверять, лежит ли по этому адресу инстанс хелпера. если нет, то вызов - первый по счёту, если да - то второй.

[faceted-jacinth.livejournal.com]

И чо? Спорим, я такую функцию перебором уроню меньше чем за секунду?

[109.livejournal.com]

в смысле - уроню? эксепшн и означает, что там не лежит инстанс хелпера.

[faceted-jacinth.livejournal.com]

Не, ты не понял.

Вначале я делаю что-нить вроде
object zzz = F(42);
(и GC.KeepAlive в конце какой-нибудь)
а потом либо перебираю, либо прямо получаю его адрес, тогда вызов F(addr) даст мне -42, а вот вызов
int i = F(F(addr))
кинет эксепшен, невзирая на то, что addr -- обычный инт и всё такое.

Более того, у меня есть сильные подозрения, что мне вовсе не обязательно создавать F(42) ручками, что тупо тыкаясь в нужное место виртуальной памяти я наверняка попаду в объект, оставшийся от предыдущих тыканий и ещё не собранный GC.

Более того, я могу завести себе специальный массивчег байтов, записать туда немножко магии и ткнуть в него твою функцию, которая честно воспримет его содержимое как объект.

Читерство это, беспонтовое совершенно.

Ты ж фактически что предлагаешь: заводим глобальный хэштейбл, в котором хранятся значения, полученные от предыдущих вызовов F(). Как только очередное значение становится ненужным (о чём нам магически сообщает манагед енвайронмент), мы его из хэштейбла выкидываем. Окей, если манагед энвайронмент действительно удаляет неиспользуемые вещи сразу, а мы вызываем функцию только как F(F(i)), то в хэштейбле постоянно будет либо ноль, либо один элемент и она, фактически, станет эквивалентна беспонтовому использованию статической переменной, так? Как только мы первый раз вызываем F(i) отдельно, запоминая результат где-нибудь для чего-нибудь, у нас появляется неиллюзорный риск того, что очередная функциея спутает свой параметр с индексом в хэштейбле (раньше она не могла этого сделать, потому что либо это и был индекс, либо хэштейбл была пуста).

[faceted-jacinth.livejournal.com]

тайпкаст забыл =(

[109.livejournal.com]

многаслофф, ниасилил. ты говоришь про случай, когда по данному адресу лежит валидный хелпер, но "не наш"? или что? сценариев-то тут на пальцах одной руки.

если ты про "не наш" хелпер, то отличить его от "нашего" тоже легко, достаточно в хелпере stack frame сохранить. ну и после второго вызова надо, конечно, помечать хелпер невалидным, чтобы с GC не было race conditions.

далее, говорить "вызов F() кинет эксепшн" - неправильно. как напишем, так и будет делать. в частности, если по адресу нет валидного хелпера, то рантайм нам кидает эксепшн, мы его ловим, и дальше считаем вход обычным интом.

[faceted-jacinth.livejournal.com]

Ох, что-то я херню какую-то написал.

Смотри, ты пишешь int F(int value), которая пытается сконвертить инт в адрес, достать оттуда хелпер, из него инт и вернуть обратное значение.

Если ты подразумеваешь, что твоя функция работает только когда я её вызываю как F(F(someValue)), то, типа, не очень понятно, зачем вообще с этим заморачиваться: заводишь статическую переменную int?, если она не нулл, то возвращаешь значение и обнуляешь, если нулл -- то прописываешь значение и возвращаешь что угодно -- потому что значение параметра ты просто игнорируешь второй раз, ты обязан его проигнорировать и вернуть то, что достал из статической переменной. Но это неинтересно, не правда ли?

Если же ты позволяешь мне написать

int a = F(42);
int b = F(23);
Console.WriteLine(F(a) + F(b));

то я легко могу заставить твою функцию вернуть что-нибудь не то. Если я знаю, как именно она устроена, то могу заставить вернуть что угодно, если нет, то могу с достаточно большой вероятностью заставить просто вернуть не то перебором.

Потому что фактически ты используешь память как кривой хэштейбл. У тебя там будет функция bool TryGetValue(int addressб out int value), которая как бы должна работать в точности по семантике аналогичной хэштейбловской. Понимаешь?

И вот она _всегда_ будет давать ложные срабатывания, как бы ты её ни написал. Причём ложные срабатывания двух видов, первый -- когда я получаю свой int a = F(42) а потом вызываю F(F(a)) (возвращающую мне вовсе не -a, а адрес нового хелпера, в котором запомнилось число 42. Второй -- когда я честно вызываю F(F(0x40000000 + someValue)) и случайно попадаю на кусок памяти, в котором случайно оказался классАйди хелпера и какое-то значение.

[109.livejournal.com]

1. requirements были только про F(F()), так что правильность результатов после манипуляции с промежуточными результатами никто не гарантировал. если не манипулировать, а использовать как есть, то всё будет работать.

2. твой код F(a) + F(b) будет работать безо всяких проблем - по обоим адресам a b лежат валидные хелперы. даже несмотря на то, что не обязан (requirements выдавали только на F(F()))

3. нет, в static нельзя писать (мультитредность).

4. ложного срабатывания №1 не будет, потому что задачу F(F(F())) мы не решали, мы решали задачу F(F())

5. ложного срабатывания №2 тоже не будет - я же сказал, записывать stack frame, чтобы чужого хелпера от своего отличить. ну или threadID записывать, для простоты.

6. я понимаю, что слово "хэштейбл" - красивое. но где тут у нас хэш, for fuck's sake? тэйбл - это да, в том смысле, в каком вообще heap - это тэйбл.

[faceted-jacinth.livejournal.com]

1,2,3: окей, если хочешь мультитредности, используй TLS. Или ручками делай TLS: заведи статический хэштейбл, локай его и пихай/доставай значение по threadId.
Задачу вычисления F(F(a)) (без возможности манипуляции промежуточными результатами, да и как ими поманипулируешь, у тебя F(a) возвращает всегда ноль, например) это решает. Судя по простоте этого, задача настолько неинтересна, что особого рассмотрения не заслуживает.

4. Лолшто? У тебя в реквайрментах записано: "Написать F(x) такую что F(F(x)) = -x за исключением тех случаев, когда существует y, такой что x = F(y)"? Я там что-то такого уточнения не видел! Это ж ключевой момент, что F(x) должно сработать корректно на ЛЮБОМ x, а тут оно вдруг перестаёт работать на тех x, которые совпадают с возвращаемыми значениями.

5. Ага, ага. И контрольную сумму ещё. А лучше две. Стекфрейм тебе, кстати, не поможет совершенно, я всё в одной функции делаю.

6. Ну да, не совсем хэштейбл, ок. Ты согласен, что ты воспринимаешь память как хранилище, держащее интерфейс

int AddValue(int value); //returns hashed key
bool TryGetValue(int key, out int value);

? И ничего больше? Ты согласен, что память и попытки скастить адрес в объект вообще говоря являются крайне плохой имплементацией этого интерфейса? И что даже очень хорошая имплементация этого интерфейса обломается на пункте 4?

7. Кстати, и от себя вопрос ещё. Ты думал, что ты будешь делать с GC? =)

[109.livejournal.com]

чё-то ты опять многаслоф написал. стекфрейм поможет при мультитредности, а не при манипуляции с промежуточными результатами - я же написал "или threadID". и как-то ты оперируешь словосочетанием "перестаёт работать", как установленым фактом, хотя ни разу этого не продемонстрировал.

#4 - ещё раз. моя имплементация работает безо всяких исключений для F(F(x)), если промежуточными результатами не манипулировать. включая многотредность. есть возражения?

на самом деле, конечно, нужно просто добавить public static implicit operator int(Helper h), чтобы можно было результат напрямую инту присваивать - и всё, с синтактической точки задача тоже будет решена (с точки зрения прохождения тестов она и до того была решена).

[ivan-gandhi.livejournal.com]

Подобное решение можно и на фортране написать - умножай на i, и все дела.

В этом что-то есть, конечно.

[109.livejournal.com]

ну, теперь-то тебе завидно, конечно!

[109.livejournal.com]

и потом, где же твой знаменитый тест-драйвнутый подход? попробуй написать тест, который этот код не пройдёт.