Жызненное

[Taviskaron]

Есть что-то прекрасное в том, чтобы в 2 часа ночи, после 6 часов поиска првильного решения, понять КАК можно НА*БАТЬ метаргеля (ассистента препода, который писал домашку), чтобы весь код работал и выдавал правильные результаты, проходил все мыслимые и немыслимые тесты, но при этом был абсолютно неправильным.

А все решила одна маленькая фраза:
"В этом задании можете не проверять входные данные - они всегда будут легальными". Хе-хе-хе. Как там говорилось? BIG MISTAKE.

Технион страшные вещи с людьми делает.

Comments

[Iceman]

Вот отсюда подробнее

[Taviskaron]

Iceman, именно что интересует тебя, юный падаван?

[Iceman]

Что именно за задача и как ты выкрутился. Гиша интересует ))
А то я честный, блин ) Делаю все, как надо, хотя у нас во всех эта строчка присутствует )

[Taviskaron]

Iceman, задача была написать компилятор для языка программирования а-ля Си.
Проблема была в том, что я не мог решить как вести себя в случае:
...
int x = 5 ;
if (x > 0)
int x = -4 ; //legal definition because it is a new scope (single line scope!)
...

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

Решение:
Вся сложная грамматика была послана на йух и упрощена. Теперь в обычной ситуации при получении такого кода я бы имел ошибку вроде:
Error: variable x is previously defined in line: bla-bla-bla.
Пришлось отрубить детектор ошибок. А чтобы не было проблем с корректностью данных в таблице символов, я ненавязчиво менял входной код на:
...
int x = 5 ;
if (x > 0)
int x_ = -4 ;
...
Таким образом "обманывая" алгоритмы и юзера.

Все это легко стало бы явным при первом же тесте типа:

int x = 1 ;
int x = 2; //must throw an error: double definition in the same scope, but my "compiler" will continue to work!

Но! Умничка метаргелет написала, что ошибок во входном коде не будет. Чем сильно облегчила мне жизнь.

Айсман, если ты до сюда дочитал и даже что-то понял - считай ты мега-крут.

А теперь вкратце:
Если есть возможность использовать факт того, что вводные данные ВСЕГДА будут корректными - use it.

[Слушатель]

1. Ага. Переименовывание переменных во вложенных блоках. А чо, нормально, на мамасе похожую фигню проходили (register renaming).
2. Компилятор допускающий (не проверяющий) синтаксическую некорректность входного кода - это очень интересный компилятор. Но да, use the given assumptions.

[Iceman]

Стремно пробовать
Я вроде, почти все понял

У меня сейчас другая задача, я программку написал, домашку по связанным спискам. Сейчас сижу и думаю, через жопу я сделал или нет. Склоняюсь к "да". У меня список, в котором каждый элемент больше обоих своих соседей или меньше обоих своих соседей одновременно. Мне надо добавлять элементы и удалять элементы, сохраняя это свойство списка.

Так я извратился донельзя: сделал функцию "сделать решиму кошерной", которая берет список, переписывает в один проход во временный массив, потом mergesort массиву и еще один проход по списку - запихувает его обратно в порядке обеспечивающем "кошерность" (сначала первый элемент маараха, потом последний, потом рекурсивно позвать ту же функцию для следующего элемента, база по размеру маараха).
То есть для одного сибухиют функции будет O(n+nlog(n)+n) = O(nlog(n)).
Хотя, кстати, не уверен, как именно считать. Не надо допустить что я функцию использую n раз? Вроде же, нет.

Удаление - тем же путем: дошел до нужного элемента, удалил. На оставшийся список применил функцию "сделать кошерным" )

Вот... Кажется, это как-то через

один проход, но не тот

жопу. Но все работает, ведь )

[Taviskaron]

Iceman, сибухиют у тебя квадратичная получается.
n * nlog(n) = (n^2)log(n) -> O((n^2)*log(n))

Рекурсия всегда убивает сибухиют. Попробуй решить итеративно. В принципе, любой сортинг надо стараться довести до O(nlog(n)) сибухиют зман и как можно меньше сибухиют маком.

З.Ы. Сибухиют - супер смешное слово на русском... Как будто бухает кто-то...

[Iceman]

Taviskaron, Зовите меня Брахмапутрой
Я тут выследил таки, как добавлять элементы через О(1).
Теперь надо еще найти как удалять их, сохраняя свойство и сибухиют в районе О(n).

А почему n*nlog(n)?
Я же для одной функции смотрю. Или таки правильно писал и надо предполагать ее использование n раз?
Ну, можно и итеративно, там несложно. Поставить два индекса и бежать одним с одного конца, другим с другого. Рекурсия красивее )

ага, сам прикалываюсь каждый раз, как пишу

[Taviskaron]

Iceman,

Поставить два индекса и бежать одним с одного конца, другим с другого.

Именно.
Если я правильно понимаю, от вас хотят работы с листами, а не "скопируй все в массив" + "перетрахни массив" + "скопируй все обратно в лист".
Правильная работа с листами - это всегда пойнтеры. Много разных пойнтеров.

[Iceman]

Taviskaron, ну, да. Я массивы просто понимаю лучше, чем листы
А у них в формулировке задания - ошибка: нигде не сказано, что надо сделать с хорошим сибухиютом. Сказано - напишите, потом посчитайте сибухиют. Чертов перфекционизм

Я пока алгоритм еще не придумал для удаления.

[Iceman]

хм... Кажись, придумался алгоритм. Надо его как-то в общем виде сформулировать. )