Речь в основном будет идти...

вторник, 15 января 2008 г.

Универсальный ответ на вопрос "а зачем"

useless_faq: Зачем нужен был Кай Снежной королеве?
voidozer: Снежная королева была послана Божественной Тенью в прошлое, чтобы не дать Каю стать последним из бруннен-джи.

Убейте кто-то эту улитку...

Есть резинка длины 1 метр. По ней ползет улитка. Скорость улитки 1см в минуту. Ползет она от левого конца резинки к правому. В конце каждой минуты резинка растягивается и ее длина увеличивается на 1 метр. "Растягивание" происходит мгновенно и равномерно по всей длине.
Вопрос: доползет ли улитка до правого конца резинки?
Понятно, что улитка живет вечно и не устает.

Бурное обсуждение на хабре. Общественное мнение все больше склоняется к тому что улитка доползет.

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

концентрированный вариант рассуждений:

В первую минуту улитка проползёт 1/100 пути. Во вторую 1/200, в третью 1/300, в N-ю 1/(N*100), выносим 1/100, получаем гармонический ряд. Далее формулы.

ок, с тем что в N-ю минуту улитка проползет 1/(N*100) пути на ту минуту я согласен. Но тут неочевидные рассуждения, неочевидные поскольку все эти 1/N пути неочевидны сами по себе.

Попробуем рассуждения более понятные хотя и менее простые (не все что просто так же просто понимается).

Пусть f(x) - функция разности между длиной пути и расстоянием пройденным улиткой. Ежели улитка проползает весь путь значит эта функция где-то равна 0.
Длина пути через n шагов будет 100*n (измеряем в самнтиметрах, т.е. в "шагах" улитки).
Улитка за n шагов преодолеет U(n) = (U(n-1)+1)*(n+1)/n сантиметров. Формула у нас получилась реккурентная. И ее можно свернуть. Получится U(n) = (n+1)sum(1..n)(1/i);
(здесь sum(1..n)- сумма по i от 1 до n)
Итоговая формула -

f(n) = 100*n - (n+1)sum(1..n)(1/i);

sum(1..n)(1/i) - гармонический ряд. Заменим его по формуле приближения гармонического ряда. Получим(заменим n на х для "привычности"):

f(x) = 100*x - (x+1)ln(x) - С;

Несложно увидеть (с калькулятором в руках) что формула по началу возрастающая. Значит если улитка доползет до финиша в каком-то месте формула должна стать убывающей. Место это называется точкой перегиба. Определяется это место как место где производная этой функции равна 0. Посмотрим есть ли такие места...
f'(x) = 100 - ln(x) - (x+1)/x;

точно рассчитывать лень но видно что f'(x) == 0 где-то в районе exp(99).

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

Основная причина увольнений "по собственному" в 2008 году...начальство

Is your boss driving you to consider looking for a different job? If so, you're not alone, as 43% of workers in a recent survey said a dislike of their boss' performance would be a main reason for taking a new job in 2008.

Оригинал - What Employers want for 2008 - a new Boss

понедельник, 14 января 2008 г.

задача - перевод из одной системы счисления в другую

Программистская задача
Старая, но хорошая. Для интервью, пожалуй, сложновасто, а как головоломка сгодится.

Дан целый массив, про который известно, что его элементы имеют значения в диапазоне от 0 до 7 включительно и весь он представляет одно большое восьмеричное число (концеватость по вкусу). Написать программу, которая переводит это число в десятичный вид (с той же концеватостью), используя O(1) дополнительной памяти.

Понравилось решение автора:

Без единого гвоздя умножения, деления или вычисления остатка, прошу заметить.

// Given an integer represented as a big-endian array of base 'b' digits,
// converts it into base 'b+1'.


void stepup (int b, unsigned char digits[], int n)
{
    for (int i=n-1; i>0; i--) {
        for (int j=1; j <= i; j++) {
            if ( (char) (digits[j] -= digits[j-1]) < 0 ) {
                digits[j] += b+1;
                digits[j-1] -= 1;
            }
        }
    }
}
void octal2decimal (unsigned char digits[], int n)
{
    stepup(8, digits, n);
    stepup(9, digits, n);
}

пятница, 4 января 2008 г.

Марк Руссинович - Внутреннее устройство ядра Windows Vista

Просто ссылки для себя.
Внутреннее устройство ядра ОС Windows Vista: Часть 1.
Внутреннее устройство ядра ОС Windows Vista: Часть 2.
Внутреннее устройство ядра ОС Windows Vista: Часть 3.

2147483647 - много это или мало?

Оказывается число фотографий во Flickr перевалило за 2147483647 (в этом месте многие думаю все уже поняли, но я продолжу).
Оказывается, каждая фотография во Flickr имеет свой ID.
Оказывается, ID фотографий определяется просто - если на Flickr было 1000 фотографий то следующая залитая фотография будет иметь ID 1001.
Некоторые сторонние библиотеки (Phlickr) обрабатывали этот ID как число. Как целое число. Я бы даже сказал как целое знаковое число. Вообщем int...
В результате - переполнение для новых фотографий.

Вывод - я все чаще замечаю что при выборе типа для представления числа я предпочитаю использовать LONGLONG. Причем соображения простые - в int поместится "всего лишь" 2147483647. Когда-то это число - 2 миллиарда с "копейками" - казалось мне заоблачным. Теперь - нет. Внутреннее ощущение того что есть много а что нет изменилось. 2 Миллиарда записей а БД? А что, вполне может быть... Выделить 2 Миллиарда байт памяти - ну да, запросто, это же всего лишь 2Г. 2 Миллиарда файлов...с кем не бывает.

"wwwdot - google = dotcom" - LINQy way

static void Main(string[] args)

{

//"wwwdot - google = dotcom"

var result = from w in Enumerable.Range(0,9)

from d in Enumerable.Range(0,9)

from o in Enumerable.Range(0,9)

from t in Enumerable.Range(0,9)

from g in Enumerable.Range(0,9)

from l in Enumerable.Range(0,9)

from e in Enumerable.Range(0,9)

from c in Enumerable.Range(0,9)

from m in Enumerable.Range(0,9)

where (w*100000+w*10000+w*1000+d*100+o*10+t-g*100000-o*10000-o*1000-g*100-l*10-e == d*100000+o*10000+t*1000+c*100+o*10+m)

select new {w,d,o,t,g,l,e,c,m};

result.ToList().ForEach((x) => Console.WriteLine(x));

}

четверг, 3 января 2008 г.

Вдогонку - 101 пример использования Linq

Вдогонку - 101 пример использования Linq от MicroSoft

Забавы с Linq

Навеяно дискуссией в RSDN MIT переходи со схемы на...

Разговор каким-то образом перекинулся на краткость которая сестра таланта и bash.
самопроизвольно возникла задача переписать вот такую команду

grep -h USER *.log | gawk "{ print $2 }" | sort | uniq

на Немерле.

В результате получилось вот что:

using Nemerle.List;

using System.IO.Directory;

using System.IO.File;

def search = "USER";

def files = GetFiles(folder).ToList().Filter(_.EndsWith(".log"));

def lines = Flatten(files.Map(ReadAllLines(_).ToList().Filter(_.Contains(search)));

def lines = lines.Map(line => line.Substring(line.IndexOf(search) + search.Length));

def lines = lines.Sort().RemoveDuplicates();

Интереса ради решил переписать этот пример с использованием Linq.
Вот что получилось (отбрасывая всякие using и прочее):

var x = (from n in Directory.GetFiles(@"D:\temp\!!!") where n.EndsWith(".log")

from line in n.LinesFromFile() where line.Contains("USER")

orderby line select line).Distinct();

Результат не совсем "чистый" поскольку стандартной функции LinesFromFile нет. Пришлось написать свою. Поэтому для полноты картины стоит наверно также добавить код этой функции. Вообщем в целом код (включая заголовок) выглядит следующим образом:

using System;

using System.Collections.Generic;

using System.Linq;

using System.IO;

namespace test_bash

{

public static class StreamReaderSequence

{

public static IEnumerable<string> LinesFromFile(this string path) {

using (StreamReader source = new StreamReader(path)){

String line;

while ((line = source.ReadLine()) != null)

yield return line;

}

class Program

{

static void Main(string[] args) {

var x = (from n in Directory.GetFiles(@"D:\temp\!!!") where n.EndsWith(".log")

from line in n.LinesFromFile() where line.Contains("USER")

orderby line select line).Distinct();

foreach (var i in x)

Console.WriteLine(i);

}

среда, 2 января 2008 г.

Разница между константной и неконстантной ссылкой.

using namespace std;

string f() { return "abc"; }

void g() {

const string& s = f();

do_something_with_string(s);//is s valid at this point? yes!

}

///////////////////////////////////

using namespace std;

string f() { return "abc"; }

void g() {

string& s = f();

do_something_with_string(s);//is s valid at this point? No!

}

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

вторник, 15 января 2008 г.

понедельник, 14 января 2008 г.

пятница, 4 января 2008 г.

четверг, 3 января 2008 г.

среда, 2 января 2008 г.

вторник, 15 января 2008 г.

понедельник, 14 января 2008 г.

пятница, 4 января 2008 г.

четверг, 3 января 2008 г.

среда, 2 января 2008 г.