Задачка: зеркально отразить битовое представление

Как можно зеркально отобразить битовое представление 8 битного числа ? 16 битного числа ?

Например,
M(123₁₀) = M(01111011₂) = 11011110₂ = 222₁₀.

внимание! комментарии содержат ответ.

java: Adaptive throttling, Part 1

Типичная проблема, которая возникает при обработке большого потока сообщений:

- нельзя пропихнуть большого слона через маленькую трубу, т.е. обработка сообщений не успевает «проглотить» все сообщения


При этом существуют некоторые ограничения на поток данных :

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

На диаграмме приведён пример разрешения проблемы: нагребатор™ работает на нитке T₁, а следовательно разгребатор™ на нитке T₂

• за время обработки события типа A успевают прийти новые события как типа B, так и A
• после обработки события типа B необходимо обработать наиболее актуальное событие типа A

Проблема осложняется ещё тем, что может быть несколько нагребаторов™, при этом каждый нагребатор™ может порождать только события одного типа; так и есть потребность в нескольких разгребаторах™ - при этом

Терминология. Stream есть поток данных, тогда как thread есть нитка или нить выполнения. И не стоит путать потоки с нитками.

java: nanoTime

Пока одни заливали соляру в трактор, мы продолжаем копаться в своём.

Тёма очень хорошо написал о измерении времени в java с ссылками на источники, так, что казалось бы и добавить нечего, но вставлю я свои пять копеек.

Все мы хорошо знаем метод System.nanoTime()

Задачка: развернуть односвязанный список

Задан односвязанный список, например:

A -> B -> C -> ... -> X -> Y -> Z

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

Z -> Y -> X -> ... -> C -> B -> A

Сложность: O(N), доступная память: O(1).

замечание: можно модифицировать исходный список.

внимание! комментарии содержат ответ.

java: garbage less

За время написания gflogger и борьбой за low latency в java накопился некоторый опыт о том как меньше плодить мусора и тем самым меньше нагружать сборщик мусора, и как следствие, меньше влиять на производительность самого приложения.

Такому тонкому троллиподходу придумали специальный термин garbage less design.

Впрочем, существую и некоторые другие вариации как заставить garbage collector меньше мешать нам жить.

Paragliding: U-Turn Blacklight

Добрых шесть лет верой и правдой служил мне мой крыл - триколор U-Turn Infinity II. Где мы только с ним не побывали, в каких жоусловиях не бывали, но его время пришло. Тем более, что летом на Юце имелась чудесная возможность немного попробовать U-Turn Blacklight (удлинение 5.8, качество 10.5) - и надо сказать, что его скорость просто впечатлила . Вполне очевидно, что драгдиллер сделал предложение от которого я не смог удержаться - и крыл был заказан.

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

И вот настал долгожданный момент - пришёл мой крыл в желаемой не серийной расцветке

lime/black/white

Задача №377

Задача №377:

Белка массой 0.5 кг сидит на абсолютно гладкой, обледенелой, горизонтальной, плоской крыше. Человек бросает белке камень массой 0.1 кг. Камень летит горизонтально со скоростью 6 м/с. Белка хватает камень и удерживает его.

Вычислите скорость белки, поймавшей камень.

внимание! комментарии содержат ответ.

Задачка: Объём луж

На рельеф некоторой местности падает дождь, попадая в низменности он образует лужи и озерца.

Найти объём образовавшихся луж за время O(N).

замечание №1: силами поверхностного натяжения пренебречь.

замечание №2: рельеф задан целыми числами

например:
V([0, 0, 3, 6, 6, 10, 5, 5, 5, 7, 7, 4, 9, 9, 13, 12, 14, 4, 3, 0]) = 30.

gflogger 0.0.9.x

Garbage Free Logger добрался до версии 0.0.9.x .

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

Но обо всём по порядку.

Задачки: Количество сообщений в минуту

Есть некоторый поток сообщений, идущий не равномерно.

Например, с 0 - 10 секунду может прийти 1 сообщение, в следующие 10 ещё 5, потом 10, потом 100 и т.д и опять наступит затишье.

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

Пояснение: если мы запрашиваем кол-во сообщений в 13:12:05, то должны получить кол-во сообщений с 13:11:05 по 13:12:05. Запрос в 13:12:57 отображает число сообщений с 13:11:57 по 13:12:57.

При этом не интересует сколько было получено две минуты назад, только реальные актуальные цифры. Допускается огрубление с точностью до секунды.

Ограничения: память O(1), сложность O(1), одна нитка выполнения.

p.s. я не знаю, существует ли какое-то классическое и/или единственно верное решение или нет, уже засыпая я смог придумать вполне приемлемое для меня решение, но которое расходует больше, чем 3-5 переменных.

Задачка: <L| и |R>

Заданы два оператора:
L : L(a,b) => ( 2 * a - b , b )
R : (a,b)R => ( a, 2 * b - a )
и начальная точка (a, b) = (0, 1).

Существует последовательность операторов L и R, такая, что в результате либо a = N, либо b = N.

Например:
Число 21 может быть получено кратчайшей последовательностью L L R L R:

  (a, b):   L(a, b) | (a, b)R
  (0, 1):   (-1, 1) | (0, 2)
 (-1, 1):   (-3, 1) | (-1, 3)
 (-3, 1):   (-7, 1) | (-3, 5)
 (-3, 5):  (-11, 5) | (-3, 13)
(-11, 5):  (-27, 5) | (-11, 21)


Какова минимальная длина последовательности с помощью которой можно получить N ?

Замечание №1: число N может лежать в диапозоне -2³¹ .. 2³¹-1.
Замечание №2: сложность O(log(N)).
Замечание №3: досупная память O(1).

внимание! комментарии содержат ответ.

Bash: Let me bash that for you, Part 1

Let's get the next dan of bash with the text processing.

The 1st note is the greatest idea of the whole unix is in that everything is file - classic file, directory, devices, file systems and so on.

Many commands expects the file for its input or it could be a simple standard input also known as stdin (refers as stream #0).

As well many commands put their output to standard output aka stdout (refers as stream #1) or to standard error output aka stderr (refers as stream #2).

There are several key text processing command and several techniques like stream redirection.

And once more! the most powerful command is man means manual.

Bash: Let me bash that for you, Part 0

I was going to write about some Unix-like shell hints which I usually use like grep, sed, for loop, variables and so on. I noticed that I do usually use lots of bash kung-fu beyond the shadow of a doubt.

I'm not going to start a holly war what shell is the best one - sh, ksh or whatever. I know how to cook bash tasty - it has lots in common with sh but some nuances happen.

That isn't a bash tutorial or so - it's more like commonly used hints and tips.

Принцип Дирихле

Кажется, это было ещё в седьмом классе, когда упоминался принцип Дирихле:

Если есть M предметов, которые надо разложить по N ящиков, причём M > N, тогда хотя бы в одном ящике будет более одного предмета.

К этому прилагалась задача типа: население Москвы 10 млн человек, среднее кол-во волос у человека 1.5млн, у скольких людей в мск одинаковое кол-во волос.

Сейчас я работаю в очень высоком здании, в котором много этажей и компаний - например, едет в лифте 6 человек и лифт будет останавливаться на 3 этажах. Казалось бы всё очевидно - где-то выйдет более, чем один человек.

Можно ли сказать что-то больше ? Например, что на каждом этаже выйдет по 2 человека ?

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

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

Один из наглядных примеров - упаковка доменных объектов в пачки (batches).

Так записывая каждый объект в поток напрямую мы получаем объём данных
V ~ O(N),
в то время как зная о специфике данных, о том, что это пачка, можно достигать
V >> O(N).

задачка: синие и красные в мешках

Есть 50 синих бумажек и 50 таких же, но красных.

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

внимание! комментарии содержат ответ.

Задачка: лестница

Есть лестница с 10 ступеньками.

За один шаг можно подняться либо на одну ступеньку, либо на две, либо на три ступеньки.



Сколько существует разных способов подняться на последнюю ступеньку ?

замечание #1 Считать, что варианты 3 + 3 + 3 + 1 и 1 + 3 + 3 + 3 независимыми.

замечание #2 Последний шаг должен приводить ровно на последнюю ступеньку, н-р, недопустим вариант 3 + 3 + 3 + 2.

внимание! комментарии содержат ответ.

java: 64 vs 32 jvm

На конференции Java One 2012 Moscow я услышал интересную мысль от инженера Sun Oracle Владимира Иванова, что

64 bit jvm даст прирост производительности даже для приложений с размером кучи менее 4Gb даром.

С чего бы это вдруг ?

run script

So, for many java core applications people use self made run-scripts. Most of them are some kind of sh/bash script that run java process with required arguments, classpath and so on and so on. After process is started script usually makes a pid file to track just created java process.

Many our java applications uses spring framework that's why we use Boostraper which helps us for many cases.

run script output

java: cache padding

Думаю, что многие уже наслышаны о магии cache padding в disruptor'е.

Однако, куда более интересный факт - наличие cache padding'а уже в самом jdk 1.5