Страницы

Поиск по вопросам

Показаны сообщения с ярлыком теория. Показать все сообщения
Показаны сообщения с ярлыком теория. Показать все сообщения

понедельник, 24 февраля 2020 г.

Аргументы методов в C# по ссылке или по значению?

#c_sharp #clr #теория


Насколько я знаю в сишарпе аргументы передаются по значению. Но тогда я не понимаю
вот чего. Я сейчас смотрю код, в котором присутствует такой метод:

public static string GetRequest(string Url, string UserAgent = "", CookieDictionary
Cookies = null, ProxyType ProxyProto = ProxyType.None, string ProxyString = "")
{
    ...

    try
    {
        HttpResponse response = request.Get(Url);
        Cookies = response.Cookies;
        response_html = response.ToString();
    } 

}


То есть он получает куки, а потом добавляет в них те что получены из ответа.
Если переменные передаются по значению то так по-идее работать не должно, но я проверил
вот так:

CookieDictionary cookies = new CookieDictionary();
string url = "http://mail.ru";
string resp = Web.GetRequest(url, "", cookies, Web.ProxyType.HTTP, "127.0.0.1:8888");
resp = Web.GetRequest(url, "", cookies, Web.ProxyType.HTTP, "127.0.0.1:8888");


При втором запросе передаются куки, которые получены при первом. Кроме того в методе
я пробовал добавлять свои куки через Cookies.Add() и они присутствовали в следующих
вопросах. Почему это работает?
    


Ответы

Ответ 1



В C# действительно аргументы передаются по значению. Вопрос только, что это за аргументы. Если это аргументы — числа или похожие объекты (они называются типами-значениями), то они передаются таки как есть — передаётся их копия. А если аргументы — объекты классов (они называются ссылочными типами), то по значению передаётся ссылка (то есть как бы указатель, если вы знакомы с C) на объект, а не копия самого объекта. По копии ссылки объект доступен точно так же, как и по оригиналу, и это тот же самый объект. Почему это сделано так? Дело в том, что не все объекты можно просто склонировать. И даже если это можно, что делать со ссылками на другие объекты, которые содержит данный объект? Клонировать все внутренние объекты? Это слишком долго и слишком сложно (например, что делать, если ссылки выстраиваются в цикл?). А если внутренние объекты не клонировать, возникает та же проблема: сам объект копируется, а внутренние подобъекты всё равно передадутся по ссылке.

Ответ 2



В отличие от некоторых языков программирования, C # имеет две разновидности типов данных: для значения и для ссылки. Если производительность приложения имеет существенное значение или есть заинтересованность в том, как C# управляет данными и памятью, важно знать различия между этими типами. Если в объявлении переменной используется один из основных встроенных типов данных или определенная пользователем структура данных, значит мы имеем дело с типом значения. Исключение составляет тип данных string, который является ссылочным типом. Структуры и перечисления в C# так же являются значимыми типами(value types). По этому не рекомендуется использовать в качестве аргументов слишком большие структуры, так как это может сказаться на производительности. На счет строк рекомендую прочитать например эту статейку, т.к. со строками не все так очевидно, как могло бы показаться.

воскресенье, 9 февраля 2020 г.

Регистры (теоретический вопрос)

#ассемблер #память #асинхронность #процесс #теория


Здравствуйте, извиняюсь за возможно глупый вопрос, но скажите пожалуйста где располагаются
регистры eax, ebx, ecx, edx, edi, esi, в оперативной памяти или процессоре?

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


Ответы

Ответ 1



регистры располагаются, конечно, в процессоре (если речь о современных распространённых процессорах). попеременно же используются они разными процессами благодаря механизму многозадачности. в грубом приближении: внутри процессора есть таймер, который время от времени посылает процессору сигнал («прерывание»), при получении которого процессор сохраняет текущее содержимое всех регистров в стек (находится в оперативной памяти, обычно каждый процесс имеет собственный стек; а сохраняются туда регистры не только с данными, но и со всякой контрольно-управляющей информацией, типа ip — instruction pointer — адресом следующей выполняемой команды) и передаёт управление по адресу обработчика данного прервывания (обработчик обычно реализован в ядре операционой системы). обработчик выбирает, какой процесс следует запустить следующим (какому процессу отдать очередной «квант времени»), и даёт процессору команду «загрузить в регистры то, что сохранённо там-то». восстановленный же из стека процесс продолжает работу «как ни в чём не бывало», до следующего срабатывания таймера.

Ответ 2



Регистры в процессоре. Многозадачность - фича ОС, которая сохраняет контекст процесса, включая регистры. Так и получается что один набор регистров вполне досаточен для многих процессов.

среда, 5 февраля 2020 г.

Что такое “рекурсивное программирование”?

#теория


Почитал я оглавление от книги 'Введение в рекурсивное программирование'

Но так и не понял что такое рекурсивное программирование. 

Кроме того что это чуть меньше кода 

// рекурсивная функция
int sum_first_natyrals(int n)
{
    if(n==1)
        return 1;
    else
        return sum_first_natyrals(n-1) + n;
}


И чуть больше сложности.

// не рекурсивная функция
int sum_first_natyrals(int n)
{
    int s_f_n =0; 
     if(n==1)
        return 1;
    else
        for (int i = n; i <0; i--)
             s_f_n += i;
        return  s_f_n;
}


Также помню что на собеседованиях этому методу программирования уделяют внимание. 



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


Ответы

Ответ 1



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

Ответ 2



Рекурсивное программирование — это программирование с использованием рекурсий. Рекурсия (в программировании) — это использование функций (методов), которые для выполнения заданной задачи ссылаются на самих себя. Пример. Нужно раздробить глыбу льда для прохладительных напитков на куски не более 1,5 см. Решение с помощью рекурсии: $желательный_размер_льда = 1.5см; @итоговые_куски_льда = (); функция дробить_лёд ($кусок_льда) { если ($кусок_льда <= $желательный_размер_льда) то { поместить $кусок_льда в @итоговые_куски_льда; выходим; } @куски_льда = выполнить_колотый_удар(кусок_льда); для каждого ($кусок из @куски_льда) { если ($кусок > $желательный_размер_льда) то { дробить_лёд($кусок); } иначе { поместить $кусок_льда в @итоговые_куски_льда; } } } Т.е. сначала мы применяем действие дробить_лёд к целой глыбе, потом к кускам поменьше, потом к их собственным кускам и так до тех пор, пока не получим куски размером не более 1,5 см. Эта проверка (в данном случае на размер куска) является выходом из рекурсии и является обязательной, в противном случае функция будет вызывать себя "бесконечно".

понедельник, 3 февраля 2020 г.

Глобальный фиксированный порядок блокировок

#многопоточность #теория


Как работает задание блокировкам глобального фиксированного порядка? Для чего это нужно?
    


Ответы

Ответ 1



Это способ избежать взаимоблокировок (deadlocks). Работает он просто: всем ресурсам присваиваются уникальные номера. Блокировать ресурсы каждому потоку разрешается только в порядке увеличения номера, снятие блокировки, соответственно, происходит в порядке уменьшения. Полезнее всего данный метод оказывается в ситуациях, когда все ресурсы, для которых понадобится взять блокировку, оказываются известны заранее. Так, в задаче об обедающих философах можно пронумеровать вилки и заставить философов брать вилки в порядке возрастания. Аналогичное решение применимо в задаче о банковских счетах и переводах между ними.

воскресенье, 2 февраля 2020 г.

Гибкость генетического алгоритма

#алгоритм #нейронные_сети #теория #генетический_алгоритм


Как сделать правильно гибкость генетического алгоритма (умоляю не советуйте A*),
ну вот на примитивном примере движении машины к цели, обходя препятствие:

Что у нас есть :


  
  У нас есть машина, она может двигать вперёд, влево, вправо, назад.
  Есть препятствие, если машина в него въезжает она ломается.
  Ещё есть цель, до которой наша машина должна добраться.
  




Так вот, вопрос в чём, как я понимаю наш генетический алгоритм проложит определённый
маршрут нашей машины до цели (рис. 1), но если мы изменим карту (рис. 2), то этот же
генетический алгоритм не доберётся до нашего места назначения, он просто сначала пойдёт
по тому же пути и потом опять начнёт грубо говоря подбором (скрещиванием) подбирать
маршрут, а как сделать чтобы он уже мог уверенно идти к цели основываясь на опыте (рис. 3) ?





UPD :


    


Ответы

Ответ 1



Генетический алгоритм - это оптимизационный алгоритм. В отличие от алгоритмов машинного обучения (тех же нейронных сетей) он никак не опирается на "предыдущий опыт", а просто оптимизирует (т.е. максимизирует или минимизирует, в зависимости от задачи) какую-то целевую функцию при помощи подбора значений параметров этой функции. При изменении исходных условий (изменение карты, расположение исходных и конечных точек) генетический алгоритм просто каждый раз с нуля будет строить маршрут. Конкретно для этой задачи можно просто брать за первоначальный маршрут прямую линию из начальной в конечную точку, дальше начинать "мутировать" этот маршрут: добавлять/удалять узлы, смещать их, и т.д. В простых случаях "скрещивать" маршруты между собой не обязательно, но для сложных лабиринтов это может дать какие-то бонусы (можно с этим поэкспериментировать). В общем-то, если в исходном пути по прямой нет препятствий, то этот маршрут в итоге и выиграет. Если препятствия попадутся, то за счет штрафа за пересечение препятствий будет выбран другой маршрут, где препятствий нет. Целевая функция - длина пути + штраф за пересечение препятствий (можно задать, что он будет зависеть от расстояния до края препятствия). Можно еще добавить штраф за количество узлов (чтобы они не сильно "плодились"), но он должен быть намного меньше штрафа за препятствия, иначе маршрут будет сходиться к прямой линии вне зависимости от наличия препятствий (тоже можно поэкспериментировать величиной штрафа). Для простых карт приемлемое решение будет находиться достаточно быстро (зависит от силы отклонений от исходного маршрута при "мутациях"). Использовать нейросеть для этой задачи я бы не советовал, это как раз тот случай, когда самые "простецкие" алгоритмы работают достаточно хорошо при намного меньших усилиях со стороны программиста. Нейросети побеждают в других областях: классификация, распознавание, некоторые задачи, для которых вообще проблематично найти четкий алгоритм, но которые человек относительно легко решает интуитивно.

пятница, 31 января 2020 г.

Сколько битов информации может передаваться за 1 такт

#передача_данных #теория


Частота работы устройства - это количество операций в секунду, и если каналов (шин)
много, то за один такт можно обрабатывать много бит. А вот например при передаче данных,
там один кабель, и я говорю, что за такт можно передать 1 бит информации, а ребята
говорят что можно и 2,3,..32 битов.

Скажите пожалуйста сколько битов информации может передаваться за 1 такт, и если
их больше одного, как это возможно???
    


Ответы

Ответ 1



Передать можно ровно столько, сколько позволяет алгоритм кодирования. Понятное дело, что когда мы опускаемся до физического уровня, то по проводу никто не передает 1 и 0. Там сигнал кодируют. Самое простое кодирование, которое применяют, это следующее. 0 кодируется 0-1, а 1 кодируется как 1-0 (1 - есть напряжение, ноль - нет). Почему не просто 1 и 0? а это для того, что бы избежать ситуции, когда передается много нулей или единиц. Понятно, что в этом случае на один "виртуальный такт" будет передано один бит (или даже пол бита, смотря как сделана схема). А можно передать 2 бита за "такт"? (я беру слово "такт" в кавычки, потому что низком уровне оно требует уточнения. И наверно правильнее говорить "передать бит за один раз") Оказывается можно. Для этого будет использовать не просто "есть сигнал-нет сигнала", а будем использовать амплитудную модуляцию. Грубо говоря, 00 - ноль вольт, 01 - 1 вольт, 10 - в вольта и 11 - 3 вольта. Да, эта система будет неустойчива к длинным сериям нулей или единиц, но суть передает. Понятное дело, что можно таким образом передавать и 3 бита. Главное, на приемной стороне иметь настроенный ацп, что бы он мог точно декодировать. Самое интересное, эту методику используют в современных ssd. В нем каждая ячейка - это маленький конденсатор. И различным напряжением в нем кодируются биты. MLC использует 2 бита на ячейку, TLC - 3 бита. Можно ли передать ещё больше? да, конечно. Есть различные методики кодирования. Например, QAM. Модификация QAM-16 позволяет передавать 4 бита за раз, а QAM-256 - 8 бит. И эти методы кодирования реально используются в приемо-передающей технике. Но вот объяснить, как они работают - это уже за пределами данного поста и тянет на один-два курса технического вуза по специальности "системы передачи в радио технике".

Ответ 2



Объем сигнала определяется тремя параметрами: V = FTD. Здесь F - ширина спектра сигнала, T - длительность сигнала и D - динамический диапазон (логарифм отношения сигнал/шум, упрощенно его можно считать числом различимых уровней сигнала). Сколько информации закодировано в сигнале - зависит от модуляции, но объем сигнала ограничивает количество информации сверху. Если поделить эту формулу на время - получится формула максимальной пропускной канала связи, ширина спектра умноженная на динамический диапазон. С практической стороны, эта формула обозначает следующее: За то же самое время можно передать в два раза больше бит если использовать в два раза большую полосу или в два раза больше уровней сигнала. Если подходить "в лоб", то первый способ не поможет передать два бита за такт - потому что при увеличении частоты длительность такта уменьшается. Но можно наложить друг на друга два разных сигнала, разнеся их по частотам - в таком случае длительность такта окажется прежней, а пропускная способность возрастет.

вторник, 28 января 2020 г.

P-класс задач и NP- класс задач

#теория #алгоритм #сложность


Объясните пожалуйста как можно подробнее , что такое Р задачи , NP (полные , сложные
..) задачи . А то почитав так и не понял. 
Спасибо заранее    


Ответы

Ответ 1



Смотрите, речь идёт об асимптотической сложности задач. Здесь рассматриваются только задачи, которые имеют простой однозначный ответ: «да» или «нет». Например, «есть ли подстрока "XYZ" в данной строке?». Задачи типа «найдите все перестановки данного набора чисел» как P/NP-проблемы не рассматриваются, так как ответ тут не да/нет. Алгоритмы часто параметризуются размерами входных данных. Время пробега алгоритма в общем случае тем больше, чем больше данных ему приходится обрабатывать. Обозначим n1, n2, ... — параметры, описывающие размеры входных данных, t(n1, n2, ...) — максимальное время работы алгоритма на данных такой длины. Если известно, что t(n1, n2, ...) ограничено сверху многочленом от переменных n1, n2, ..., задача называется решаемой за полиномиальное время. Класс таких задач и обозначается как P, они считаются вычислительно несложными. Теперь, что же такое NP-проблема? Представьте себе, что у вас есть алгоритм с несколькими ветвлениями (if-ами, циклами), который последовательно тестирует решения, и как только найдёт подходящее, сразу заканчивает алгоритм с криками «ура, нашёл!» Например, если мы ищем, есть ли символ 'X' в данной строке, мы можем поочерёдно в цикле проверять, совпадает ли первый символ с X, затем второй, затем третий, и как только нашли совпадение, заканчиваем работу. Так вот, представьте себе теперь такую машину, которая магическим образом сразу переходит к нужной итерации цикла: для поиска символа X в строке "ABCXYZ" она сразу проверяет в 4-ой позиции, то есть там, где надо! Такая магическая машина называется недетерминированной машиной (по историческим причинам) и, понятно, не существует в природе. Так вот, проблема называется NP-проблемой, если она решается за полиномиальное время на этой самой читерской недетерминированной машине. Понятно, что всякая P-проблема есть NP-проблема: если уж мы на нормальной машине решим её за полиномиальное время, то на читерской тем более! Возникает вопрос: а нужно ли читерство? Может быть, всякая проблема, которая решается на недетерминированной машине за полиномиальное время, может быть решена и на нормальной тоже за полиномиальное время? Это и есть знаменитая P/NP-гипотеза: предполагают, что есть проблемы, которые без недетерминированной машины за полиномиальное время не решить. Но никто пока не смог это строго математически обосновать. Проблема тут вот в чём: если мы не умеем решать какую-то задачу за полиномиальное время, значит ли это, что она в принципе за полиномиальное время не решается, или мы просто недостаточно умны и изобретательны?

Является ли курьер с документами протоколом передачи данных?

#теория #протоколы


Моего коллегу Константина начальство послало в соседний корпус с документами, которые
он должен отдать. 

Вопрос: с точки зрения теории информации и других компьютерных наук можем ли мы считать
Константина протоколом передачи данных, а окружающий его холод улицы (в процессе движения)
- средой распространения информации?

PS. Вопрос не ради хохмы, пишу методичку для чайников по информатике. 
    


Ответы

Ответ 1



Конечно же конкретный курьер Константин не является протоколом. И даже абстрактный курьер протоколом не является. Протокол - это не физическая сущность, это описание процесса, обобщенный алгоритм. Ниже я рассмотрел подробнее как могли бы выглядеть протоколы разных уровней в этом стеке. Физический уровень. Как происходит передача документов курьером? Директор вызывает курьера Директор передаёт документы курьеру Курьер идёт в соседний корпус к получателю документов Курьер передаёт документы получателю Получатель говорит курьеру "спасибо" (или "ну наконец-то") и забирает документы Попытаемся обобщить этот алгоритм, избавившись от слишком конкретных шагов. Интересно ли получателю то, как директор передавал документы курьеру? Нет, ему интересны только сами документы. Интересно ли директору, как получатель забирал документы? Нет, ему важен только чтобы получатель их получил. Остаётся от алгоритма следующее: "курьер берёт документы и идёт с ними к получателю, после чего отдаёт их получателю". Это и есть протокол физического уровня. Что же такое в таком случае курьер в этой аналогии? А курьер тут - среда. То, что переносит информацию. Теперь канальный уровень. Канальный уровень управляет доступом к среде. К протоколу канального уровня относятся алгоритмы вызова курьера, в который надо предусмотреть ситуации "что делать если курьер занят" (директор может подождать или назначить курьером кого-то ещё - во втором случае средой передачи станет множество курьеров), "что делать если курьера пытается отправить не директор, а кто-то ещё" или "как курьер узнает получателя" (да-да, в этом стеке протоколов будущего предусмотрена авторизация на канальном уровне!) Сетевой и транспортный уровни. В вашем примере эти уровни не предусмотрен, поскольку курьер принципиально один. Однако, можно придумать другой пример, в котором один курьер будет передавать документ другому или вообще пойдёт на почту. Это и будет протоколом сетевого уровня. Протокол же транспортного уровня будет отвечать за подтверждение доставки (или не будет, см. UDP) Прикладной уровень. На этом уровне описывается формат передаваемого документа.

Ответ 2



Нет, не можем. Протокол, это скорее соглашение о том, что информация передаётся таким-то способом. Соглашение о том, что документы пересылаются курьерами - это протокол. Ваш Константин его конкретная реализация (одна из возможных). Улица - среда. Холод - один из параметров среды. Как-то так...

Ответ 3



Если рассматривать модель OSI, то Физический уровень (то, где перемещается курьер) город, область, Вселенная Канальный (откуда и куда) Улица, здание или кабинет Сетевой (способ перемещения пакета данных) Курьер Транспортный (надёжность и скорость доставки) Его портфель Сеансовый (возьми это и отдай туда, мне доложи) Секретарша Представительский (секретный документ в конверт и в отправку) Директор Прикладной (я сделаю документ, а дальше отправляйте куда хотите) Главбух

Ответ 4



Протокол (любого уровня) - это способ передачи данных, в том числе способ с применением Константина. Если Константин придерживается ряда строгих правил и его участие в процессе обмена согласовано как передающей, так и принимающей стороной - его можно считать протоколом. В разрезе модели OSI курьер Константин, конечно же, выполняет свои функции на уровне транспортного протокола, а именно - обеспечивает надёжную передачу данных от отправителя к получателю. Рассмотрим всю цепочку обмена: Представим, что некая секретарша (которая, конечно же, работает на уровне представления) заботливо запечатывает данные, полученные от прикладного уровня в виде руководства (отчёты, денежные средства, договоры и пр.) в конверт, а затем передаёт их в качестве поручения Константину, с которым она предварительно познакомилась и возможно, даже планирует поддерживать длительные дружеские отношения до тех пор, пока он работает в Компании (так сказать, на сеансовом уровне). Костик совершенно не в курсе о назначении передаваемых им сообщений, но его это и не интересует. Он заворачивает их в своё пальто, чтобы пакет с доносами и кляузами на коллег не промок и не принял непристойный вид в результате попадания под проливной питерский дождь). И извлечёт Константин этот пакет не раньше, чем войдёт в сухое и теплое помещение пункта назначения, уж будьте уверены. Нет, его конечно могут принудительно заставить раздеться и даже пройти досмотр на входе в метро, но вот внутрь конверта ни у кого по пути заглянуть не получится - ведь документы надежно запечатаны, и распечатать их можно, лишь разорвав конверт. В процессе совершения доставки он пользуется подсказками о координатах конечного пункта, которые содержатся на сетевом в виде набора адресов, каждый из которых присвоен отдельному зданию или кабинету. Если Константин перед отправлением не выяснил точное месторасположение пункта назначения, ему придётся буквально уткнуться ("завернуться") в карту района и следуя по пути, постоянно сверяться с её содержимым. Константину свойственны и некоторые типичные проблемы транспортного уровня: Его надежность находится под вопросом: для подтверждения факта успешной доставки им данных в конечный пункт может потребоваться подтверждение. Но зачастую из-за высоких накладных расходов на такие подтверждения в компаниях кладут болт, ведь доля потерянных Константинов в течение рабочего дня обычно незначительна. Гарантирует ли Константин правильную последовательность получения адресатом отправленных данных? Разумеется, да. Как правило, следующее поручение Константину будет выдано лишь после возвращения его в исходный пункт. В случае внезапной пропажи Константина налаженный механизм обмена документами в Компании прервётся, но не надолго. Обворожительной секретарше придётся вновь составить поручение, но уже передать его другому курьеру. И процесс обмена будет запущен вновь. Замечу ещё, что весь городской транспорт, тротуары, коридоры, а также прочая канальная инфраструктура доступного для доставки сегмента (города, района или кампуса крупной компании), по которой возможно перемещение Константина, используются им в процессе доставки данных. В их числе, кстати могут оказаться и мосты ;) которые в модели OSI работают как раз-таки на канальном уровне. Что же является низшим, физическим протоколом в этом случае? Ни воздух, ни город, ни сама по себе Вселенная сигналы не распространяют, то есть средой они конечно являются, а вот протоколом физического уровня - нет. А протоколом я бы назвал физическое перемещение от отправителя к адресату, ведь именно этот процесс лежит в основе передачи информации. Итак, резюмирую - передача сообщений с помощью Константина - это явный пример использования курьер-подобного протокола обмена.

Java. Почему нельзя изменить ссылку на объект в методе?

#java #ссылки #объекты #теория #параметры


Мой педагог задал мне задание ответить на ряд вопросов. И два их них меня сильно
смущают. 


  
  Почему нельзя изменить ссылку на объект в методе?
  


Не могу понять смысл вопроса(((


  
  Как в Java передаются параметры в методы?
  


Я гуглил этот вопрос и понял что по всегда по значению но что точно это значит не понял.

Не могли бы вы мне помочь разобраться в этой ситуации.
    


Ответы

Ответ 1



Почему нельзя изменить ссылку на объект в методе? Потому что в метод передается не ссылка, а объект, который содержит копию ссылки. Как в Java передаются параметры в методы? Все аргументы (как примитивные типы, так и объекты) в Java передаются при вызове по значению. Тут сразу стоит оговориться, что объект по сути представляет ссылку, следовательно, при изменении объекта в методе, изменится и исходный объект. Подробнее можно почитать в «Подробное рассмотрение особенностей передачи аргументов» в полном руководстве по Java авторства Герберта Шилдта.

Ответ 2



Как намекнул Vlad from Moscow в комментарии к вопросу, вопрос довольно странный, и на мой взгляд он не вполне корректен -- либо ваш преподаватель не очень хорошо умеет выражать свои мысли, либо вы как-то слегка исказили его вопрос. Дело в том, что в методе менять ссылку вообще-то можно. Строго говоря, в Jave обычно говорят не о ссылках на объект, а о переменных (полях, аргументах) объектного типа. Но фактически значением таких переменных являются ссылки на объекты. Методы в качестве своих аргументов получают копии этих ссылок и могут делать с ними что хотят (т. е. присваивать им значения ссылок на другие объекты или null - "пустую ссылку"), что никак не отражается на значениях переменных, которые были переданы методу при его вызове. Так что вот такой код public class TestQQ { static void qq(String s) { System.out.println(s); s = "Что-то новое..."; // Это ссылка или не ссылка меняется ? System.out.println(s); } public static void main(String[] args) { String string = "Нельзя менять ссылки?"; qq(string); System.out.println(string); } } Создает новый объект класса String со значением "Нельзя менять ссылки?"; Присваивает ссылку на него переменной string; Вызывает метод qq() и передает ему копию переменной string (т. е. создает вторую ссылку на ту же строку "Нельзя менять ссылки?") Метод qq() выводит на консоль содержимое того объекта, ссылка на который содержится в его параметре - т. е. то же самое "нельзя?"; Метод qq() своему параметру s присваивает новое значение - ссылку на новую строку "Что-то новое...", -- вторая ссылка на "нельзя" исчезает, но исходная переменная string в главной программе при этом никак не меняется и по-прежнему содержит ссылку на то же самое изначальное "нельзя?"; Метод qq() печатает новую строку ("Что-то новое...") и возвращает управление в главную программу (метод main); Метод main() печатает содержимое объекта, который содержится (т. е. ссылка на который содержится) в переменной string - это по-прежнему изначальная строка "Нельзя менять ссылки?" Вывод будет такой:Нельзя менять ссылки? Что-то новое Нельзя менять ссылки? Но при этом надо отчетливо понимать, что хотя метод не может изменить значение объектной переменной, переданной ему в качестве параметра (т. е. ссылку на объект), он за милую душу может изменить сам объект! Например, в такой программе import java.util.ArrayList; public class TestQQQ { static void qqq(ArrayList list) { list.add("можно."); } public static void main(String[] args) { ArrayList strings = new ArrayList(); strings.add("А объекты менять...?"); qqq(strings); System.out.println(strings); } } метод qqq() добавляет в список, ссылку на который он получил, новую строку "можно.", и в результате мы получаем на выходе вот что: [А объекты менять...?, можно.]

Ответ 3



Почему нельзя изменить ссылку на объект в методе? При передаче объекта в метод происходит просто копирование ссылки на него (Никаких копий объекта не создаётся при передачи!). И уже с помощью неё вы общаетесь с исходным объектом. Отсюда должно быть понятно, почему при перезаписывании в эту ссылку нового объекта старый не меняется. Простой пример для разъяснения: List list1 = new ArrayList<>(); //Создаём объект и кладём в ссылку List list2 = list1; //Просто копируем ссылку list2.add(new Object); //Через копию ссылки мы меняем исходный объект в list1 list2 = new ArrayList<>(); //Хоть мы и переписали в ссылку новый объект, //исходный никуда не делся, он всё также лежит в list1. Как в Java передаются параметры в методы? Примитивы по значению, объекты - как я описал выше (не знаю как правильно называется этот способ). Update: спасибо @Roman, правильное название способа передачи объектов в метод - вызов по соиспользованию (call by sharing)

вторник, 24 декабря 2019 г.

Максимальная непрерывная сумма в двоичном дереве за N переходов

#алгоритм #дерево #теория


Дано двоичное дерево, со значениями весов перехода.
Нужно получить максимальное значение за N переходов начиная с нулевого узла. При
этом путь должен быть непрерывный,с бесплатными возвратами в родительский узел.

Мой текущий алгоритм:


Найти последний доступный узел(в котором количество ходов равно 0, либо отсутствуют
дети).  
Записать в массив текущее значение и количество доступных ходов(с учетом потомков).
Перейти в родительский узел, скопировать оба массива(если 2 потомка), либо 1 массив
(1 потомок).
Повторять п.2-3 до возврата в корневой узел.
На основании массива в корневом узле (в котором находятся все
возможные сочетания значений+ходов) найти максимальное значение.


Основные вопросы:


Существует ли лучший алгоритм?
Возможно ли оптимизировать данный алгоритм т.к. работает слишком
долго и требует слишком много памяти?

    


Ответы

Ответ 1



Решение за N*S памяти, N*S*S или N*S*log S времени. S - размер дерева. Динамика F[vert][size] - оптимальный ответ если мы в поддереве вершины vert берём size элементов. Для любого элемента F[u][0] = 0 Для листа на этом всё. Для вершины псевдокод. (r - правый потомок, l - левый). for (int i=0;i

Ответ 2



Собственно ответ,возможно пригодится кому-то: В дереве всегда добавляю сначала левую ноду , затем правую(см. if(left!=NULL & right==NULL). void getMax(Node *curr,int turns) { int i,j; if(curr->left!=NULL && turns!=0) getMax(curr->left,turns-1); if(curr->right!=NULL && turns!=0) getMax(curr->right,turns-1); curr->res=new int[turns+1](); curr->res[0]=0; if(curr->left==NULL && curr->right==NULL || turns==0) { for(i=1;ires[i]=0; return; } else { if(curr->left!=NULL && curr->right==NULL) { Node*next=curr->left; for(i=0;ires[i+1]=next->res[i]+next->value; } } else { Node *left=curr->left; Node *right=curr->right; for(i=0;ires[0]=0; } if(i==0 && j>=1) { curr->res[j]=max(curr->res[j],right->value+right->res[j-1]); } if(i>=1 && j==0) { curr->res[i]=max(curr->res[i],left->value+left->res[i-1]); } if(i>=1 && j>=1) { curr->res[i+j]=max(curr->res[i+j],left->value+right->value+left->res[i-1]+right->res[j-1]); } } } } } } и сам класс class Node { public: Node *parent; Node *left; Node *right; int id; int value; int *res;};

суббота, 14 декабря 2019 г.

Полнота по Тьюрингу

#любой_язык #теория


Как известно, большинство широко используемых языков программирования (особенно императивных)
полны по Тьюрингу. А некоторые — даже относительно времени компиляции, как, скажем,
С++ с их шаблонами.

А каким образом доказывается/опровергается полнота по Тьюрингу? Само по себе это
понятие  выглядит трудно формализуемым.
    


Ответы

Ответ 1



Формально это надо доказывать это с точки зрения теории рекурсивных функций — язык полон по Тьюрингу тогда и только тогда, когда он позволяет записать каждую вычислимую функцию. На практике для этого обычно достаточно ловко проапеллировать к [тезису Черча].(http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis) См. также «How to Prove a Programming Language is Turing Complete?».

Ответ 2



Почему-то мне кажется, что если мы можем реализовать машину Тьюринга на каком-то языке, то это означает, что он тьюринг-полный. Хотя могу ошибаться.

воскресенье, 1 декабря 2019 г.

Операторы приведения в C++

#cpp #теория


Читаю сейчас "Discovering Modern C++", и есть там одно место, где автор пишет, что
в С++ есть четыре оператора приведения (всем знакомые ..._cast) и унаследованный из
C оператор (type)expr.

В связи с этим очередной теоретический вопрос: автор забыл о приведении type(expr)
или это приведение вообще говоря не является приведением, по сути являясь созданием
объекта типа type из expr? ну, или применением оператора преобразования типа? Ведь
вроде бы тут говорится, что это тоже преобразование типа?

И еще - а есть ли вообще разница между преобразованием (conversion) и приведением
(cast) или это синонимы?

И еще о лингвистике :) - у него четко различаются casting Up (от производного к базовому)
и casting Down (понятно, наоборот)... Но что-то я в нашей литературе таких терминов
раньше не встречал?
    


Ответы

Ответ 1



В связи с этим очередной теоретический вопрос: автор забыл о приведении type(expr) Это можно считать приведением(так пишет Майерс и другие называют это приведением), но в стандарте это не входит в список операторов приведения(cast operators). Т.е. формально, данный синтаксис не является синтаксисом приведения. Он в стандарте имеет своё имя: functional notation. В сущности, это создание объекта инициализированного expr. Это вызов конструктора. И еще - а есть ли вообще разница между преобразованием (conversion) и приведением (cast) или это синонимы? Первое это существительное, второе — глагол(чаще). Нет, разницы, с точки зрения языка, — нет. Но что-то я в нашей литературе таких терминов раньше не встречал? Я нашу литературу давно не читаю, но если это перевод книги, в которой есть up-casting и down-casting, это не может быть не переведено. Из стандарта про синтаксис из вопроса: [expr.type.conv]p2 A simple-type-specifier (7.1.6.2) or typename-specifier (14.6) followed by a parenthesized expression-list constructs a value of the specified type given the expression list. If the expression list is a single expression, the type conversion expression is equivalent (in definedness, and if defined in meaning) to the corresponding cast expression (5.4) <...> Где corresponding cast expression это (T)expression

Ответ 2



Выражение type(expr) не является приведением. Это создание нового объекта на основе expr, иногда может интерпретироваться как создание новой переменной int(a); // создание переменной a unsigned b = unsigned(a); // создание нового объекта из a и инициализация b его значением Разница между преобразованием и приведением есть. Приведение не влечёт за собой выполнения никакого кода, при преобразовании будет выполненный определённый код. При использовании кастов из С++ необходимо прочитать в справке, какие конкретно действия будут выполнены.

Ответ 3



В Мэйерс. Эффективное использование C++ автор считает конструкции (T)e и T(e) не имеющими "ощутимого различия, просто скобки расставляются по-разному". Однако в "Страуструп. Язык программирования C++. Специальное издание. - М.;СПб.: Издательство БИНОМ - Невский Диалект, 2002" дается более сложное описание. T(e) - создание значения типа T из значения e с помощью конструктора. Для встроенных типов эта запись эквивалента (T)e. Однако все-таки не до конца: преобразование указателей с ее помощью невозможно - написать (char *)2 можно, а char*(2) нельзя. Поэтому, на мой взгляд, это все-таки немного разные конструкции - приведение (T)e будет компилироваться всегда, в отличие от T(e).

Ответ 4



Преобразование типов может быть как явным, так и неявным. Явное преобразование называется приведением (casting). Чтобы в этом убедиться достаточно посмотреть на раздел Index Стандарта и увидеть там такие сноски: conversion explicit type, see casting explicit type conversion, see casting type conversion, explicit, see casting Явное преобразование типов описано в двух параграфах СтандартаC++14, названия которых начинаются с фразы Explicit type conversion, но имеют разное окончание: 5.2.3 (functional notation); 5.4 (cast notation). При этом в п. 5.4/2 сказано: An explicit type conversion can be expressed using functional notation (5.2.3), a type conversion operator (dynamic_cast, static_cast, reinterpret_cast, const_cast), or the cast notation. Т.о. явное преобразование может быть выражено через: функциональную нотацию: T(e) оператор преобразования типов: dynamic_cast, static_cast и т.д. нотацию приведения: (T)e Функциональная нотация (относительно фундаментальных типов) разрешена только для простых спецификаторов типа (char, double, int и т.д.), но уже не будет работать с типами, записанными более чем одним словом (unsigned char, long double, signed int и т.д.). Для классов функциональная нотация приводит к вызову конструктора соответствующего класса. При использовании нотации приведения (Си-нотации) компилятор пытается выполнить следующие преобразования в указанном порядке: const_cast static_cast static_cast с последующим const_cast reinterpret_cast reinterpret_cast с последующим const_cast В итоге будет выбран первый вариант, который удовлетворит требованиям соответствующего оператора. По возможности следует избегать в коде на C++ использования приведения в стиле Си. И отдавать предпочтение соответствующим castам для более четкого выражения своих намерений.

Динамические свойства языка программирования как преимущество

#objective_c #теория #связывание_данных #дизайн_языка


Наверстываю упущенную теорию по парадигмам языков программирования.

В обучающих материалах по ObjC часто встречается восхищение динамичностью языка (динамическое
связывание, динамическая типизация...) с указанием на то что многое можно делать в
рантайме плюс описание соответствующих трюков. Читая документ со страницы 23 я понимаю
что это есть свойство языка, но не преимущество. Предполагаю, что сравнивая со статически
типизированными языками все те же трюки выполняются в них с тем же успехом, но не в
runtime a в compile-time. Раздел статьи Преимущества (равно как и другие статьи в сети)
свет на вопрос для меня не пролил и не дал понять в чем именно преимущество а не просто
отличие от парадигмы статической типизации. Прошу просветить и указать в чем именно
преимущество динамической типизации над статической.

UPDATE:
Если будут получены объемные ответы на вопрос о природе явления в целом, то с целью
оставить тред потомкам я добавлю метки всех языков соответствующих парадигме и уберу
акцент на objc из топика.

UPDATE 2:
Получены прекрасные всеобъемлющие ответы, в частности от @VladD. C целью аккумулирования
топиком общеобразовательной ценности хотелось бы читать мнение и других участников
форума. Заранее благодарен за передачу опыта и знаний! 
    


Ответы

Ответ 1



Если уж зашла речь о «динамичности языка» вообще, должен отметить, что отдельное понятие «динамического языка» лишено смысла. В основном, когда говорят о «динамическом языке», имеют в виду «язык с динамической системой типов», хотя существуют и другие «динамические» черты языка (первое, что приходит в голову — «динамическая область видимости»). Итак, что такое «динамическая система типов»? Определения в источниках наподобие Википедии говорят, что разница в том, присваивается ли тип переменной при объявлении (и остаётся ли таким навсегда) либо при присваивании (и меняется с каждым следующим присваиванием). Это, однако, слишком грубое описание существующего положения вещей. Куда честнее и точнее было бы говорить о богатстве системы типов, и о том, насколько полно она отображает семантику предметной области. Крайний пример — языки типа большинства ассемблеров, в которых существует лишь один тип — числовой. Это соответствует примерам «максимально динамической» системы типов: переменная может содержать число, указатель, структуру из двух байт и т. д. Примера противоположной крайности — языка, в котором каждый элемент программной семантики описывается отдельным типом — наверное не существует, но старые диалекты Паскаля довольно близки к этому. Полностью последовательным строго типизированным языком был бы язык, в котором, например, была бы невозможна ошибка при взятии квадратного корня из отрицательного числа: в языке был бы определён тип «неотрицательное действительное число», и этот тип был бы типом аргумента корня. (То же для например арксинуса.) На деле же все языки стоят где-то посередине между этими двумя крайностями. Языки, которые считаются «динамически типизированными» или «слабо типизированными» (в зависимости от того, одобряет или осуждает программист это явление), имеют меньшее количество типов, и операции между значениями с разной семантикой либо завершаются с ошибкой, либо приводят к бессмысленному результату. В качестве примера рассмотрим javascript. Его переменные, по существу, имеют лишь один тип — переменная :-) Вы можете вызвать любую операцию на переменной, вне зависимости от фактического содержимого этой переменной. Для некоторых операций (например, вызов функции) неправильное содержимое переменной вызовет исключение, для некоторых же (например, сложение) операция будет выполнена с результатом, неожиданным для программиста, который не во всех деталях проштудировал спецификацию языка. Языки наподобие C++ предоставляют более богатую систему типов: вы, например, не сможете «вызвать функцию» по переменной типа int. Таким образом, у операций в C++ гораздо меньше возможностей завершиться аварийно из-за несоответствия типов. Тем не менее, язык предоставляет вам возможность нарушить защиту: оператор приведения типов. Вы можете привести тип строки к типу числа, и попытаться выполнить числовую операцию с полученным значением. Согласно стандарту языка, вы получите неопределённое поведение, то есть, что угодно имеет право произойти. Кроме того, определённые черты слабо типизированных языков есть и в C++: операция сложения между различными арифметическими типами вызывает неявную конверсию операндов к наиболее общему типу. Язык наподобие C# мог бы казаться ещё более статически типизированным (в нём нету аналога reinterpret_cast, и тип проверяется всегда), но зато в нём есть ключевое слово dynamic, близкое по идеологии к eval. Из особенностей динамических языков, перечисленных в Википедии, C# обладает в той или иной степени всеми, за исключением, пожалуй, макросов. Где-то посередине по богатству системы типов стоит SQL: в нём есть набор примитивных типов, но нет возможности расширить систему типов, применимо к нуждам пользователя. Итак, под динамической системой типов обычно понимается система типов, в которой меньше базовых типов, и/или некоторые операции могут применяться к разным типам с возможностью получения ошибки времени выполнения либо малоосмысленного результата. Большинство языков обладают этим свойством в той или иной мере. Литература для дальнейшего чтения: [1], [2], [3], [4]. Преимущества «более динамических» языков: Лучшая выразительность в некоторых сценариях, например, там где программист хочет сказать «я уверен, что этот объект умеет выполнить эту операцию» или «объекты, не умеющие делать это, игнорируются». Для сильнее типизированных языков такая семантика достигается использованием приведения типов или другой разновидностью проверки времени выполнения. Например, в Objective C, насколько я знаю, можно отправить произвольное сообщение произвольному объекту (разновидность duck typing); в C# для этого нужно, чтобы объект поддерживал соответствующий интерфейс, или использование dynamic, то есть откладывание проверки до момента выполнения. Неявная, «плавающая» семантика объектов по сравнению с явно заданными, продуманными и жёстко прописанными типами позволяет легко менять смысл классов и операций при разработке. (Не могу придумать пример для Objective C.) Это увеличивает скорость прототипирования, хотя, возможно, и негативно скажется на качестве кода при длительной разработке проекта. Отсюда распространённое мнение о том, что «динамические» языки лучше подходят для построения proof of concept, а статические — для имплементации. Более удобное общение с популярными нетипизированными или слаботипизированными структурами, такими как XML- и JSON-документы. Ещё один часто забываемый пример динамического свойства языков: виртуальные функции. Преимуществом более динамических языков является более простая диспетчеризация вызовов функций: если у меня определены f(Base, Base), f(Base, Derived), f(Derived, Base) f(Derived, Derived), язык с развитой динамической типизацией сможет автоматически выбрать нужную перегрузку при вызове метода, в то время как другие языки вынуждены пользоваться паттерном наподобие Visitor. Частным случаем диспетчеризации по одному, нулевому аргументу является вызов виртуальной функции. Некоторые языки умеют управлять кодом во время выполнения. Например, в Javascript'е можно переопределить любой метод через прототип, в Objective C можно подменить класс, используя категории (если я не ошибаюсь), в Питоне можно модифицировать поведение методов при помощи аннотаций. Достижение подобных эффектов в не приспособленных для этого языках сопряжено со значительным объёмом кода и нередко требует от пользователей неестественного, неудобного или даже опасного синтаксиса. (Например, оборачивать каждое объявление поля в макрос.) Суммируя: для понятий, встроенных в систему типов, динамически типизированные языки проигрывают статически типизированным в выразительной силе (пример: в статическом языке легко запретить складывать длину с весом, а в динамическом — нет). Для понятий, не описываемых системой типов, динамические языки выразительнее (пример всем объектам с полем возраст увеличить этот самый возраст на 1: в статических языках требует интерфейса, одинакового имени свойства и одинакового типа свойства). Многие преимущества, которые традиционно считаются преимуществами динамических языков, на самом деле лишь следствия хорошо организованной среды выполнения (рантайма), и в частности не требуют интерпретации или виртуальной машины. Например, интроспекция/рефлексия есть не вопрос динамичности, а лишь вопрос доступности метаданных во время выполнения, и вполне статичная с точки зрения системы типов Java её реализует. Замыкания, которые в Javascript'е есть чисто динамическая особенность, реализуются статически с полным контролем типизации в Objective C (под именем блоков) и C#. Английская Википедия считает, что динамические черты ... can be emulated in nearly any language of sufficient complexity, but dynamic languages provide direct tools to make use of them. (могут быть эмулированы в любом достаточно сложном языке, но динамические языки предоставляют прямой метод ими воспользоваться) — но я позволю себе частично не согласиться. То, как динамические свойства языка реализованы, может быть сделано при подходящей реализации и в любом другом языке, так что слово «эмуляция» здесь неприменимо: если статический язык «эмулирует» рефлексию при помощи метаданных, что же делает динамический? Итак, мы видим, что граница между статическими и динамическими языками довольно сильно размыта.

Ответ 2



Преимущества Минимум дополнительных строк: переменные надо либо просто объявить без указания типа (JavaScript), либо вообще объявлять не нужно (Бейсик) или не обязательно (PHP). Соответственно, упрощается написание простых программ Повышается гибкость языка. Например, только динамический язык может иметь функцию eval(), вычисляющую значение произвольного выражения. Ускоряет работу компилятора — а значит, производственный цикл «написать-проверить». Автоматически даёт языку элементы метапрограммирования и интроспекции. Упрощается работа прикладного программиста с СУБД, которые принципиально возвращают информацию в «динамически типизированном» виде. Поэтому динамические языки ценны, например, для программирования веб-служб. Иногда требуется работать с данными переменного типа. Например, функция поиска подстроки возвращает позицию найденного символа (число) или маркер «не найдено». В PHP этот маркер — булевское false. В статических языках это особая константа (0 в Паскале, std::string::npos в C++). Динамическая типизация Википедия

понедельник, 25 ноября 2019 г.

Существуют ли реальные алгоритмы со сложностью O(1/n)?


Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу:

function test(n) {
  for (i=1; i<100000/n; i++) {
    dosomething();
  }
}

    


Ответы

Ответ 1



Их даже в теории не существует. Потому что это ограничение сверху. O(C + 1/n) = O(C) = O(1) Где C - некоторая константа, отличная от 0. А 0 она не может быть равна, поскольку у нас в любом случае есть накладные расходы хотя бы на получение самого n и какое-то его использование. Потому что если мы не используем n вообще, то сложность, очевидно, от него не зависи и не может быть O(1/n). А если используем, то мы хоть раз к нему обратимся и константа будет ненулевой. Альтернативное обоснование: представим, что такой алгоритм есть, но тогда при удвоени n время его исполнения уменьшается вдвое и при достаточно большом n должно будет стать менее одной процессорной инструкции, что невозможно. Даже в коде из вопроса for (i=1; i<100000/n; i++) { что произойдёт, когда n превысит 100000? У нас будет ровно 4 операции: присваивание, деление, сравнение и выход из функции. Это O(1) - оно уже неспособно уменьшиться с ростом n.

Ответ 2



Нет, не существует. Сначала вспомним, что такое асимптота: Пусть у нас есть некая кривая y = A(x). Тогда асимптота y = B(x) — это такая кривая, к которой A как бы «прижимается» при движении в бесконечность вдоль оси x. Графически это выглядит так: Источник: https://en.wikipedia.org/wiki/File:1-over-x-plus-x.svg В данном примере прямая y = x является асимптотой для y = 1 / x + x, так как пр достаточно больших x обе линии практически сливаются. Асимптотатическая сложность ведёт себя аналогичным образом, только вместо графиков у нас зависимость вычислительной сложности от количества элементов. Соответственно, чтобы утверждать, что алгоритм имеет сложность O(1 / N), надо, чтоб график сложности алгоритма совпадал с графиком 1 / n при очень больших n. Но в этом случае 1 / n вырождается в константу ноль. А раз у нас константа, значит и алгоритм имеет константную сложность, обозначаемую как O(1).

Ответ 3



А вообще, есть интересный случай. В большинстве случаев говоря об асимптотике м предполагаем возрастание аргумента. Но, строго говоря, это может быть не так. Например, если мы знаем, что область определения некоторой функции ограничена. Возьмём и реализуем деление int(1/x) через вычитание: function f(x) { for (var i=0, v=1; v>0; ++i, v-=x); return i; } console.log(f(1)); console.log(f(.5)); console.log(f(.25)); console.log(f(.125)); console.log(f(.0625)); console.log(f(.0000001)); В принципе можно сказать, что у этой функции асимптотика O(1/x), т. е. при маленьки значениях x она будет работать очень медленно (кстати, ещё и неточно из-за накопления погрешноти). Разумеется, в случае с целым аргументом такой вариант будет невозможен.

вторник, 7 мая 2019 г.

Аргументы методов в C# по ссылке или по значению?

Насколько я знаю в сишарпе аргументы передаются по значению. Но тогда я не понимаю вот чего. Я сейчас смотрю код, в котором присутствует такой метод:
public static string GetRequest(string Url, string UserAgent = "", CookieDictionary Cookies = null, ProxyType ProxyProto = ProxyType.None, string ProxyString = "") { ...
try { HttpResponse response = request.Get(Url); Cookies = response.Cookies; response_html = response.ToString(); }
}
То есть он получает куки, а потом добавляет в них те что получены из ответа. Если переменные передаются по значению то так по-идее работать не должно, но я проверил вот так:
CookieDictionary cookies = new CookieDictionary(); string url = "http://mail.ru"; string resp = Web.GetRequest(url, "", cookies, Web.ProxyType.HTTP, "127.0.0.1:8888"); resp = Web.GetRequest(url, "", cookies, Web.ProxyType.HTTP, "127.0.0.1:8888");
При втором запросе передаются куки, которые получены при первом. Кроме того в методе я пробовал добавлять свои куки через Cookies.Add() и они присутствовали в следующих вопросах. Почему это работает?


Ответ

В C# действительно аргументы передаются по значению. Вопрос только, что это за аргументы.
Если это аргументы — числа или похожие объекты (они называются типами-значениями), то они передаются таки как есть — передаётся их копия
А если аргументы — объекты классов (они называются ссылочными типами), то по значению передаётся ссылка (то есть как бы указатель, если вы знакомы с C) на объект, а не копия самого объекта. По копии ссылки объект доступен точно так же, как и по оригиналу, и это тот же самый объект.
Почему это сделано так? Дело в том, что не все объекты можно просто склонировать. И даже если это можно, что делать со ссылками на другие объекты, которые содержит данный объект? Клонировать все внутренние объекты? Это слишком долго и слишком сложно (например, что делать, если ссылки выстраиваются в цикл?). А если внутренние объекты не клонировать, возникает та же проблема: сам объект копируется, а внутренние подобъекты всё равно передадутся по ссылке.

четверг, 18 апреля 2019 г.

Регистры (теоретический вопрос)

Здравствуйте, извиняюсь за возможно глупый вопрос, но скажите пожалуйста где располагаются регистры eax, ebx, ecx, edx, edi, esi, в оперативной памяти или процессоре?
Сам вопрос появился после того как я подумал, что если я не чего не путаю, то регистры всегда вроде-бы располагались в процессоре (ну если верить книжкам), но я не могу понять одного, как десятки процессов используют эти регистры грубо говоря асинхронно, процессор же не может разорваться на каждый процесс. Ну и вот с этого момента мне стало очень интересно как так может быть и я решил спросить у профессионалов.


Ответ

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

в грубом приближении:
внутри процессора есть таймер, который время от времени посылает процессору сигнал («прерывание»), при получении которого процессор сохраняет текущее содержимое всех регистров в стек (находится в оперативной памяти, обычно каждый процесс имеет собственный стек; а сохраняются туда регистры не только с данными, но и со всякой контрольно-управляющей информацией, типа ip — instruction pointer — адресом следующей выполняемой команды) и передаёт управление по адресу обработчика данного прервывания (обработчик обычно реализован в ядре операционой системы).
обработчик выбирает, какой процесс следует запустить следующим (какому процессу отдать очередной «квант времени»), и даёт процессору команду «загрузить в регистры то, что сохранённо там-то».
восстановленный же из стека процесс продолжает работу «как ни в чём не бывало», до следующего срабатывания таймера.

четверг, 4 апреля 2019 г.

Гибкость генетического алгоритма

Как сделать правильно гибкость генетического алгоритма (умоляю не советуйте A*), ну вот на примитивном примере движении машины к цели, обходя препятствие:
Что у нас есть :
У нас есть машина, она может двигать вперёд, влево, вправо, назад. Есть препятствие, если машина в него въезжает она ломается. Ещё есть цель, до которой наша машина должна добраться.

Так вот, вопрос в чём, как я понимаю наш генетический алгоритм проложит определённый маршрут нашей машины до цели (рис. 1), но если мы изменим карту (рис. 2), то этот же генетический алгоритм не доберётся до нашего места назначения, он просто сначала пойдёт по тому же пути и потом опять начнёт грубо говоря подбором (скрещиванием) подбирать маршрут, а как сделать чтобы он уже мог уверенно идти к цели основываясь на опыте (рис. 3) ?


UPD :


Ответ

Генетический алгоритм - это оптимизационный алгоритм. В отличие от алгоритмов машинного обучения (тех же нейронных сетей) он никак не опирается на "предыдущий опыт", а просто оптимизирует (т.е. максимизирует или минимизирует, в зависимости от задачи) какую-то целевую функцию при помощи подбора значений параметров этой функции.
При изменении исходных условий (изменение карты, расположение исходных и конечных точек) генетический алгоритм просто каждый раз с нуля будет строить маршрут.
Конкретно для этой задачи можно просто брать за первоначальный маршрут прямую линию из начальной в конечную точку, дальше начинать "мутировать" этот маршрут: добавлять/удалять узлы, смещать их, и т.д. В простых случаях "скрещивать" маршруты между собой не обязательно, но для сложных лабиринтов это может дать какие-то бонусы (можно с этим поэкспериментировать). В общем-то, если в исходном пути по прямой нет препятствий, то этот маршрут в итоге и выиграет. Если препятствия попадутся, то за счет штрафа за пересечение препятствий будет выбран другой маршрут, где препятствий нет.
Целевая функция - длина пути + штраф за пересечение препятствий (можно задать, что он будет зависеть от расстояния до края препятствия). Можно еще добавить штраф за количество узлов (чтобы они не сильно "плодились"), но он должен быть намного меньше штрафа за препятствия, иначе маршрут будет сходиться к прямой линии вне зависимости от наличия препятствий (тоже можно поэкспериментировать величиной штрафа).
Для простых карт приемлемое решение будет находиться достаточно быстро (зависит от силы отклонений от исходного маршрута при "мутациях").
Использовать нейросеть для этой задачи я бы не советовал, это как раз тот случай, когда самые "простецкие" алгоритмы работают достаточно хорошо при намного меньших усилиях со стороны программиста. Нейросети побеждают в других областях: классификация, распознавание, некоторые задачи, для которых вообще проблематично найти четкий алгоритм, но которые человек относительно легко решает интуитивно.

четверг, 28 марта 2019 г.

P-класс задач и NP- класс задач

Объясните пожалуйста как можно подробнее , что такое Р задачи , NP (полные , сложные ..) задачи . А то почитав так и не понял. Спасибо заранее


Ответ

Смотрите, речь идёт об асимптотической сложности задач. Здесь рассматриваются только задачи, которые имеют простой однозначный ответ: «да» или «нет». Например, «есть ли подстрока "XYZ" в данной строке?». Задачи типа «найдите все перестановки данного набора чисел» как P/NP-проблемы не рассматриваются, так как ответ тут не да/нет. Алгоритмы часто параметризуются размерами входных данных. Время пробега алгоритма в общем случае тем больше, чем больше данных ему приходится обрабатывать. Обозначим n1, n2, ... — параметры, описывающие размеры входных данных, t(n1, n2, ...) — максимальное время работы алгоритма на данных такой длины. Если известно, что t(n1, n2, ...) ограничено сверху многочленом от переменных n1, n2, ..., задача называется решаемой за полиномиальное время. Класс таких задач и обозначается как P, они считаются вычислительно несложными. Теперь, что же такое NP-проблема? Представьте себе, что у вас есть алгоритм с несколькими ветвлениями (if-ами, циклами), который последовательно тестирует решения, и как только найдёт подходящее, сразу заканчивает алгоритм с криками «ура, нашёл!» Например, если мы ищем, есть ли символ 'X' в данной строке, мы можем поочерёдно в цикле проверять, совпадает ли первый символ с X, затем второй, затем третий, и как только нашли совпадение, заканчиваем работу. Так вот, представьте себе теперь такую машину, которая магическим образом сразу переходит к нужной итерации цикла: для поиска символа X в строке "ABCXYZ" она сразу проверяет в 4-ой позиции, то есть там, где надо! Такая магическая машина называется недетерминированной машиной (по историческим причинам) и, понятно, не существует в природе. Так вот, проблема называется NP-проблемой, если она решается за полиномиальное время на этой самой читерской недетерминированной машине. Понятно, что всякая P-проблема есть NP-проблема: если уж мы на нормальной машине решим её за полиномиальное время, то на читерской тем более! Возникает вопрос: а нужно ли читерство? Может быть, всякая проблема, которая решается на недетерминированной машине за полиномиальное время, может быть решена и на нормальной тоже за полиномиальное время? Это и есть знаменитая P/NP-гипотеза: предполагают, что есть проблемы, которые без недетерминированной машины за полиномиальное время не решить. Но никто пока не смог это строго математически обосновать. Проблема тут вот в чём: если мы не умеем решать какую-то задачу за полиномиальное время, значит ли это, что она в принципе за полиномиальное время не решается, или мы просто недостаточно умны и изобретательны?

вторник, 26 марта 2019 г.

Java. Почему нельзя изменить ссылку на объект в методе?

Мой педагог задал мне задание ответить на ряд вопросов. И два их них меня сильно смущают.
Почему нельзя изменить ссылку на объект в методе?
Не могу понять смысл вопроса(((
Как в Java передаются параметры в методы?
Я гуглил этот вопрос и понял что по всегда по значению но что точно это значит не понял.
Не могли бы вы мне помочь разобраться в этой ситуации.


Ответ

Почему нельзя изменить ссылку на объект в методе?
Потому что в метод передается не ссылка, а объект, который содержит копию ссылки
Как в Java передаются параметры в методы?
Все аргументы (как примитивные типы, так и объекты) в Java передаются при вызове по значению. Тут сразу стоит оговориться, что объект по сути представляет ссылку, следовательно, при изменении объекта в методе, изменится и исходный объект.

Подробнее можно почитать в «Подробное рассмотрение особенностей передачи аргументов» в полном руководстве по Java авторства Герберта Шилдта.

вторник, 27 ноября 2018 г.

Максимальная непрерывная сумма в двоичном дереве за N переходов

Дано двоичное дерево, со значениями весов перехода. Нужно получить максимальное значение за N переходов начиная с нулевого узла. При этом путь должен быть непрерывный,с бесплатными возвратами в родительский узел.
Мой текущий алгоритм:
Найти последний доступный узел(в котором количество ходов равно 0, либо отсутствуют дети). Записать в массив текущее значение и количество доступных ходов(с учетом потомков). Перейти в родительский узел, скопировать оба массива(если 2 потомка), либо 1 массив (1 потомок). Повторять п.2-3 до возврата в корневой узел. На основании массива в корневом узле (в котором находятся все возможные сочетания значений+ходов) найти максимальное значение.
Основные вопросы:
Существует ли лучший алгоритм? Возможно ли оптимизировать данный алгоритм т.к. работает слишком долго и требует слишком много памяти?


Ответ

Решение за N*S памяти, N*S*S или N*S*log S времени. S - размер дерева
Динамика F[vert][size] - оптимальный ответ если мы в поддереве вершины vert берём size элементов.
Для любого элемента F[u][0] = 0 Для листа на этом всё.
Для вершины псевдокод. (r - правый потомок, l - левый).
for (int i=0;iКак-то так. Мы либо берём только с 1 поддерева элементы. Либо берём с 2, тогда перебираем сколько берём слева и сколько справа.
Ответ - значение в F[root][N]. Для ускорения вместо двойного цикла использовать Быстрое преобразование Фурье (FFT)