?

Log in

No account? Create an account
Олег Макаренко
15 March 2014 @ 08:47 pm, reposted by miga2007


Давайте разберём несколько примеров западных софистических капканов, на которые они ловят неокрепшие души инфантильных представителей креативного класса. Начнём с патриотизма:

Дальше…Collapse )
 
 
Michael Nosov
Дисклеймер: то, что написано ниже может оказаться жутким баяном, но нагуглить что-то похожее с первого раза не удалось. Поэтому, если описанное ниже вдруг окажется новым словом в науке и технике - не забывайте при использовании материала указывать мое авторство. Sincerely yours, Михаил (Michael.Nosov@gmail.com).


Предыстория:
Вчера я слушал в интернете вот такую лекцию про хеш-таблицы: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-13-amortized-algorithms-table-doubling-potential-method
Вкратце:
- Операция вставки элемента в hash-table равна O(1)
Но когда таблица A1 заполняется (наполовину, но не суть важно) - нам надо увеличить ее размер. То есть создать новую таблицу A2 большего размера (например 2*N) и скопировать (вставить по новой) все элементы из A1 в A2. Это еще N операций, то есть сложность в такие моменты равна O(N)
Соответственно, на добавление N элементов подряд, надо операций: (1+1+1+...+1) + (1+2+4+8+...+N). Первое слагаемое - тупое добавление элемента. Второе - суммарная стоимость удвоения хеш-таблиц.
Суммарно это равно: N+2N=3N. То есть "средняя" сложность добавления одного элемента равна 3N/N=3=O(1).

Проблема:
И вроде бы все круто - среднее время добавления элемента - константа, не зависящая от N. Но блин...это же как "средняя температура по больнице" или "средняя зарплата между 1 олигархом и 100 учителей". То есть эта система будет "иногда (правда, достаточно редко) нещадно тормозить" при добавлении одного элемента. Что будет как минимум раздражать, как максимум может быть вообще неприемлемо.

Предлагаемое решение (простое, как колесо, но нагуглить что-то похожее сразу не удалось):
Идея: размазать это копирование, требующее N операций по времени, во время добавления элементов в табличку A1. То есть сделать так, чтобы по возможности вставка одного элемента занимала 3 операции (вместо обычно 1, но иногда N).
То есть (полное описание алгоритма):
1. У нас есть табличка A1 размером N. Изначально она заполнена будет наполовину от рекомендуемого объема, т.е. (N/2)/2 = N/4
2. Создаем сразу (а не когда припрет, как раньше) табличку A2, размером 2N. Операция Alloc(2N) - константа. Эту табличку мы будем потихоньку заполнять пока вставляются элементы A1
3. При добавлении элемента в A1 (1 операция), мы будем еще сразу: 3a) копировать 4 элемента из A1 в A2 (еще 2 операции). 3б) сразу скопировать этот новый элемент в A2 (1 операция). То есть вставка одного элемента займет у нас уже максимум 6 операций (в 6 раз больше чем 1, но все равно константа)
4. При добавлении следующего элемента в A1 - копируем еще 4 из A1 в A2
5. Эффект: когда табличка A1 заполнится до упора (до N/2 - макс. объем в таблице - добавится еще N/4 элементов), то табличка A2 уже будет полностью сформирована - все элементы будут уже скопированы из A1). В этом случае нам надо будет просто сделать alloc новой таблички A3, размером 4N и продолжить работу с табличками A2 и A3 (прямо с шага 1).

Улучшение: легко заметить, что нет смысла копировать пустые элементы из A1 в A2 (пункт 3a). То есть добавление одного элемента может потребовать от двух (оба элемента пустые, тогда нам нужно будет вставить только новый элемент в A1 и A2) до шести (оба элемента непустые, тогда надо копировать их плюс новый элемент в обе таблицы). И тогда суммарное среднее время вставки N/4 элементов подряд будет не 6N/4, а уже 3N/4 (поскольку за все время у нас скопируются все непустые элементы из A1 в A2 - то N/2, плюс добавится N/4 элементов в A1, т.е. N/2+N/4=3N/4 - так же как и в случае в оригинальной хеш-таблицей )

Плюсы: АБСОЛЮТНО полностью детерминированное время вставки элемента (константа: от 2 до 6 вставок в хэш таблицу с O(1)). Никаких редких тормозов не будет

Минусы:
- Надо сразу создавать таблицу размером 2N, то есть жрать памяти будет в 3 раза больше, чем в случае с обычной хеш-таблицей. Если учесть, что сама хэш-таблица заполнена менее чем наполовину (чтоб коллизии не возникали слишком часто) - получится в 6 раз больше памяти, чем реально необходимо для хранения данных

Имхо, для очень существенного класса задач (начиная от простого user-experience заканчивая потенциально огромными базами данных) гарантированное отсутствие тормозов - куда существеннее какого-то большего расхода памяти. Памяти в 3 раза больше купить вообще не проблема.

Ваше мнение? Велосипед или не велосипед? Какие есть подводные камни?

PS: Неясные моменты:
1. Реально, вставка одного элемента в непереполненную таблицу - тоже не факт что константа. Т.к. при вставке существует вероятность коллизий, и в самом худшем случае коллизии (плохая хеш-функция и пр.) будут встречаться постоянно, и вставка одного элемента может быть N. Но опять же в среднем - это константа. Если мне не изменяет память, где-то даже высчитывалась вероятность того, что встретится не больше 2,3 коллизий - и эта вероятность достаточно высокая (при незабитой таблице). И один хрен, предлагаемый метод намного улучшит жизнь. В моем методе тормоза могут случиться с очень небольшой вероятностью, если хеш-функция будет отстойная. А в оригинальном случае - тормоза будут всегда (!) при добавлении достаточно большого числа элементов (больше чем размер таблицы)
2. Другой подход: В случае, когда нам действительно важно не иметь таких жутких тормозов - самый простой путь - запустить что-то типа "lazy copy" в бэкграунде когда размер таблицы близок к пределу. И это копирование будет работать, пока в таблицу ничего не добавляется и она простаивает. Так что может быть идея выше будет просто небольшим теоретическим дополнением

UPD1: Исправил с учетом того, что реально таблица не заполняется больше чем наполовину
 
 
Michael Nosov
18 August 2012 @ 08:38 pm
На выбор (возможны несколько вариантов):

1. Катаемся на водных велосипедах. Цена: 230 крон за лодку на 4х человек

2. Идем на карусели


2а) Совсем рядом от работы:

Read more...Collapse )


3. Смотрим финал скейтбордистов. В субботу была квалификация, в воскресенье финал:


4. Идем на пляж, там тоже что-то намечается в воскресенье:
12080493

5. Идем на площади и слушаем всякую херню, типа этой:


или этой



или этой


6. Что бы кто ни выбрал, всегда есть вот такой вариант:
12080461
 
 
Michael Nosov
22 June 2012 @ 12:27 pm
Новое мое приложение:
screens_all
 
 
Michael Nosov
18 May 2012 @ 04:16 pm
Скриншоты с версии Symbian:


 
 
 
Michael Nosov
Nokia выложила в Nokia Store приложение Random Ringtone для Nokia N9








 
 
Michael Nosov
13 April 2012 @ 01:02 pm
Eprst

Posted via LiveJournal app for Nokia N9

 
 
Michael Nosov
Оригинал взят у dmitry_noskoff в Сотни детей-инвалидов голодают, а директор интерната живет как олигарх (ФОТО)
UPD. Интересный нюанс: в 2008 году депутаты Госдумы от КПРФ сорвали проверку скандального дома-интерната

Почитайте документы и решите - нужно ли помочь детям-инвалидам? Или пусть все останется как сейчас? Как помочь? Для того, чтобы организовать независимую проверку - нужно привлечь внимание властей и СМИ. Прочитайте пост и, если хотите помочь - оставьте комментарий, сделайте перепост, лайки в соцсетях.

Проверку уже проводили, но безуспешно.

В 2008 году ОБЭП пытался провести проверку в доме-интернате. Взято отсюда: http://www.bloknot-volgodonsk.ru/news/42

... нагрянула проверка ОБЭП (оперативники проверяли информацию о присвоении средств, выделенных на питание детей). Воронько (депутат гордумы от КПРФ), пытаясь спастись, оперативно написала письмо в Государственную Думу. На ее защиту бросились товарищи от партии КПРФ - депутаты Госдумы Николай Коломейцев и Владимир Бессонов. Из Воронько сделали страдалицу за правду. Якобы милиционеры хотели расправиться с нею за ее заявления в МВД РФ, в котором депутат Воронько обличала злоупотребления начальника городского УВД, а заодно и сообщала о противоправных действиях мэра Волгодонска Виктора Фирсова, проложившего асфальтированную дорогу к пионерскому лагерю «Маяк», находящемуся в собственности семьи Фирсова. Именно этих людей Воронько считала виновными в проводимых в ее интернате проверках. Якобы они ей таким образом мстили за публичную критику.

200 детей-инвалидов из интерната годами недоедали, чтобы директриса купила себе платья от кутюр. Гардероб на миллионы рублей и шикарный отдых в десятках зарубежных стран – такие интересные фотографии выложила в социальных сетях Татьяна Воронько, директор дома-интерната № 14 для детей с ограниченными возможностями из города Волгодонск (Ростовская область) и по совместительству - рядовой депутат Волгодонской городской Думы (без депутатской зарплаты).

Эту историю раскопал депутат Государственной Думы Олег Пахолков. У него на руках шокирующие документы - копия протокола допроса предпринимателя Веры Симоновой и ее письменное признание после отбывания наказания в местах лишения свободы (см. ниже).

В 2008 году она была осуждена за мошенничество, проколовшись на махинациях с муниципальными поставками. Честно отсидела свой срок и вышла, что называется, с чистой совестью. Каково же было ее удивление, когда она увидела, что директор дома-интерната Татьяна Воронько, для которой она в 2007 году передала откат с детского питания в размере 1,8 миллиона рублей, продолжает шикарно жить без проблем каких-либо проблем со стороны правоохранительных органов.

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

Говорят что, посмотрев на богато накрытый стол, известный своим цинизмом и жестокостью мужчина, отказался за него садиться, якобы со словами «Это ж, получается, ты у детей взяла. Мне в глотку не полезет…»

На это Воронько, проводив гостя, якобы ответила: «Гляди, какой важный – у самого руки по локоть в крови, а он котлетки детские жрать отказывается…»

Давайте посмотрим фотографии анкеты Татьяны Воронько в социальной сети badoo.com и узнаем как живет простая директор провинциального дома-интерната.


Очень много фотоCollapse )


В протоколе допроса Вера Симонова подробно рассказала о мошеннической схеме. Она выиграла контракт на поставку продуктов питания в дом-интернат в размере 3,2 миллиона рублей. Она передавала наличными половину суммы при каждом платеже на свой расчетный счет – примерно 150 тысяч рублей в месяц или 1,8 миллиона рублей в год. По документам все было шито-крыто: завпроизводством списывала продукты путем завышения расхода на приготовление конкретного блюда. То есть, мясо для детей инвалидов ужаривалось и упаривалось в несколько раз, а овощи-фрукты подвергались значительной усушке-утруске.


Сканы протокола допроса и их расшифровкаCollapse )


А вот письменное признание предпринимателя Симоновой после отсидки.

Сканы признания и их расшифровкаCollapse )

Вот тут - интересные подробности про Татьяну Воронько: http://www.bloknot-volgodonsk.ru/news/3

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

Видео: Выпускной в интернате № 14



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



Неужели Гуськов, знающий как свои пять пальцев ситуацию в системе образования Волгодонска, ничего не знает о том, что на самом деле творится в доме-интернате № 14?

Комментирует депутат Государственной Думы Олег Пахолков:



- Судя, по материалам уголовного дела, ООО «Фирма Град» в 2007 году заключила контракт на поставку детского питания в интернат № 14 г. Волгодонска на сумму 3,2 миллиона рублей. Из этой суммы – 1,8 миллиона рублей наличными деньгами – предприниматель передавала директору интерната Татьяне Воронько.

А ведь с оставшихся 1,4 миллиона рублей нужно было не только купить продукты детям, но и заплатить налоги, зарплату сотрудникам коммерческой фирмы, производственные издержки, да еще не забыть про прибыль – цель любой коммерческой организации. Можно предположить, что из 3,2 миллиона рублей на питание детям дошла, дай Бог, хотя бы треть – 1 миллион рублей. Интересно, сиротам хотя бы макароны доставались?

Совесть у всех разная. С точки зрения одного человека, чье-то деяние кажется преступлением. А с точки зрения другого – благодеянием. Вот только платья от Дольче и Габбаны, купленные за счет сиротских котлет, пожалуй, не укладываются ни в один моральный устой.

Любой вор может найти себе оправдание. Даже украв у нищего, он подумает: «Ему еще пожертвуют». Но украсть у ребенка-инвалида, зачастую безнадежно больного, лишенного не только родителей, но и здоровья, украсть буквально изо рта – половину его еды… Это омерзительно. Бесчеловечно.

В таких случаях говорят не просто о преступлении. Это – преступление против совести, против государства, против человечества. Этому нет оправдания.

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

Я знаю, что Воронько имеет депутатский мандат, и надеется, что статус защитит ее от расследования, как это уже бывало не раз. Более того, она уже успела заявить о грядущей помощи, в случае, если дело будет иметь ход, неизвестных «высоких покровителей». Хотел бы я посмотреть в глаза людям, готовым покровительствовать в таких случаях…

Я обращаюсь к избранному президенту РФ Путину, генеральному прокурору РФ Чайке, уполномоченному по правам детей Астахову.

Воровство у детей-сирот – это преступление против государства. Государство должно защитить детей. Прошу расследовать факты предполагаемого злоупотребления Воронько Т.Л. своим служебным положением, а так же обстоятельства, воспрепятствовавшие возбуждению и расследованию уголовного дела ранее, во время проведения проверки ОБЭП г. Волгодонска дома-интерната №14.

P.S.

Люди! Давайте спасем перепостом 200 детей-инвалидов от недоедания, а директора интерната от ожирения – хватит жрать детские котлетки!


 
 
Michael Nosov
22 March 2012 @ 02:54 pm
My test post

Posted via LiveJournal app for Nokia Simulator Model

 
 
Michael Nosov
Оригинал взят у asaratov в «Я просила - дайте мне автомат и пустите меня к ним!..» ...
Трое отморозков заманили в квартиру 18-летнюю девушку, поочередно изнасиловали ее, а затем, чтобы скрыть следы преступления, придушили и попытались ее сжечь заживо на заброшенной стройке. В тяжелейшем состоянии пострадавшая 10 марта была доставлена в больницу.

Первое, что шокировало всех без исключения людей, которые следят за этой трагедией, стало известие о том, что из троих задержанных двое ОТПУЩЕНЫ НА СВОБОДУ! Сразу поползли слухи о том, что как минимум двое из троих насильниов - сынки высокопоставленных персон. Слухи оказались не беспочвенными.

Как удалось установить, один из подозреваемых - сын бывшей главы Еланецкой райгосадминистрации. Другой - и того хлеще - якобы, сын бывшего прокурора Центрального района г. Николаева. То, что дело пытаются «замять» подтверждает и полное отсутствие объективной информации из правоохранительных органов: кто отпустил подозреваемых в совершении столь тяжкого преступления? На каком основании? Кто ведет следствие? Добиться ответа на все эти вопросы оказалось не возможно - глухая стена. Видно, что какие-то влиятельные силы делают все, для того чтобы выгородить мерзавцев.


       СМОТРЕТЬCollapse )