Два слова...

"перетурбации"
"претубирации"

Написал в письме слово "претубирации". Задумался - правильно ли написал. Коллега не знал, предложил заменить словом "перетурбации". Ну в принципе подходит...но.
Тут я задумался - а что это за слова такие..., что они означают, откуда я их знаю...
На слово "претубирации" гугль выдает всего 32 упоминания.
На "перетурбации" гугль выдает 3 тысячи.
slovari.yandex.ru таких слов не знает.
Не знает и gramota.ru.
Зато gramota.ru знает слово ПЕРТУРБАЦИЯ. По смыслу то же самое. А гугль на это слово выдает "аж" 40 тыс. ссылок. И slovari.yandex.ru об этом слове молчать не стал...
Вывод - слов "перетурбации" и "претубирации" нет. Есть слово "ПЕРТУРБАЦИЯ".

какое же это было бессмысленное занятие писать это бессмысленное сообщение...

Новый консольный шрифт для Windows

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

иногда я совсем не понимаю микрософтофобов

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

Вывод: ха-ха-ха, 7й оффис не поддерживает нормальную реализацию ooxml формата. А будет ли поддерживать? Ну мы же знаем этот M$...Никогда они нормальную поддержку не сделают. Ну неужели сложно было реализовать в 7м оффисе полную поддержку ooxml формата? Своего же формата? Причем в том виде как он принят в стандарте, а не как его видет M$. Ну мы же знаем что M$ вечно меняет стандарты под себя, данный случай не исключение. Нужно ждать нормальной реализации от OpenOffice - вот это Продукт.

Еще интересных задачек. С решениями.

Оригинал.

Есть лошади, которые бегают с разной скоростью и никогда не устают. Лошади могут учавствовать в забегах, в одном забеге может участвовать не более N лошадей. Результатом забега является очередность, в которой лошади дошли до финиша, то есть на выходе - список, на каком месте была какая лошадь в забеге.
Всего лошадей N^2.
Спрашивается - за какое минимальное количество забегов можно найти M лучших их них?

Разбиваем на N групп. В каждой проводим забег. Итого N забегов. Берем из каждой группы победителя. Проводим среди них забег. Победитель есть абсолютный победитель. Запоминаем, победителя удаляем, добавляем второго из его группы. Проводим еще один забег...короче M+N

Есть односвязный список, у которого в каждом элементе есть еще один указатель на некоторый элемент этого списка. То есть, кроме next в ноде есть еще один мембер, который указывает на любой элемент списка. Может сам на себя, могут несколько таких указателей указывать на один элемент, как угодно. Хочется создать копию этого списка, разумеется, со скопированными ссылками в элементах. За линейное время и без дополнительной памяти, кроме как на саму копию.

Код (всякие мелкие очевидные фукнции я убрал, rlist->n - следующий элемент, rlist->r - случайный элемент, предполагается что в исходном списки r!=0 никогда)

rlist* rrcopy(rlist* base_head)

{

    rlist* copy_head = clone_rlist(base_head);

    rlist* b,*c,*t;

 

    for(b=base_head,c=copy_head;b;b=b->n){

        t=c->n;

        c->r=b->r;

        c->n=b->r;

        b->r=c;

        c=t;

    }

 

    for(b=base_head;b;b=b->n){

        c=b->r;

        c->r=c->n->r;

    }

 

    for(b=base_head;b;b=b->n){

        c=b->r;

        t=c->n;

        c->n=b->n?b->n->r:0;

        b->r=t;

    }

    return copy_head;

}

Даны три массива целых положительных чисел длиной N.
Нужно выбрать из каждого из них по одному числу так, чтобы сумма равнялась некоторому данному C.
С константными затратами памяти и сложностью O(N^2).

Хинт - если два массива отсортировать то для двух таких массивов задачу можно решить за O(N). Соответственно вместе с третьим получается O(N^2)
Если массивы сортировать нельзя - не знаю :)

Видео-пираты, аудио-пираты

Мои 5 копеек.
Когда-то давно, когда деревья были ну просто намного выше а трава такая ярко-зеленая что глаза резало зародилось программирование. Появились программисты и начали писать программы. Потом кому-то пришло в голову что программу можно не только писать и раздавать но и продавать. И появилась индустрия программного обеспечения.

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

И разработчик задумался - как бы сделать так чтобы друго пользователя не смог пользоваться программой не заплатив за нее. Так появилась защита програмного обеспечения от "несанкционированного" использования. Появилась. Защита. А не движения за искоренение пиратства и суды над друзьями которые записали себе нужную программу. Защита програмного обеспечиния очень и очень непростой процесс.

Защита постоянно эволюционирует. Способов защиты много и они разные. Есть правильные, удобные, есть и раздражающие. Но главное - они существуют. И совершенствуются.

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

Тем же самым должна заниматься и медиа-индустрия. Есть такое понятие - DRM. Находится оно конечно в зачаточном состоянии, его существующие реализации в разной степени ужасны. Но именно этим и стоит заниматься. А не бороться с bittorrent и прочими напстерами. И уж конечно не бороться с конечными пользователсями.

Новая статья Пола Грахэма (Pol Graham)

Называется "Почему нет других "Гуглов" (Why there aren't more Googles). Отвечает на многие вопросы. Освещает многие проблемы венчурного финансирования. Можно узнать много интересного про его компанию.
После прочтения открытым остается только один вопрос - so....why there aren't more Googles?

Google BigTable против RDBMS

Оригинальная статья (основной посыл - Relational Databases are Dead).
Обсуждение на reddit

От себя - в этом как и в большенстве подобных случаев мало кто задумывается о сущности проблемы. Мнение первых сводится в основном к "Гугль это круто потому что Гугль это круто". Мнение вторых - "а как же без join и нормализации делать сложные запросы? Раз нельзя, значит BigTable в пролете".
Попробую собрать свои мысли на эту тему .

Пусть у нас "стандартная" база данных - products,customers,orders. Данные у нас скорее всего будут огранизованны следующим образом - таблица products, таблица customers, таблица orders, и всячиские таблица productid->orderid и т.д. Интерес представляют последнии. Зачем они собственно нужны? Ответ - время выборки. Допустим нам нужно посмотреть все заказы по данному продукту. Без таблиц типа productid->orderid это будет примерно так - берем productid, идем по всем записам в таблице orders, выбираем такие у которых совпадает productid. Время поиска O(n). При наличии productid->orderid найти все orderid у которых соответствующий productid можно гораздо быстрее. Соответственно скорость работы запроса намного больше. Как это сделать на BigTable без join запросов и первоначальной нормализаци базы? Да никак. Если все делать "в лоб" скорость выполнения запросов в BigTable гораздо ниже. Итого - BigTable в пролете?

Не совсем...давайте посмотрим на задачу повнимательнее. В первых мы говорили только о поиске и выборке. Что если количество операции "вставка" сопостовимо с количеством операций выборка? Причим количество таких операций в секунду достаточно велико? Случится неприятность...
Добавим "если". Что если обьем данных очень велик? Что если частота различных запросов различна? Что если их частота сильно различна?
Далее - что если нам не обязательно получить "точную" выборку. Приблизительная очень даже подойдет. А что если у нас нет таблицы products а есть только customers и orders/pictures/comments/...

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

Здесь важно следующее - задачи, возникающие перед современными веб-приложениями, работающими под польшой нагрузкой "классической" RDBMS решаются со скрипом. Это прежде всего потому что RDBMS не подходит для этих задач. Описать эти задачи можно так - огромный обьем данных, частые операции вставки/удаления, отсутствие необходимости в точном результате выборки (подойдет достоверный).

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

Выводы.:)

Cможет ли BigTable решать эти вопросы более быстро и качественно чем RDBMS? А не знаю я. Возможно и сможет. Даже скорее всего сможет. А если и не сможет - тогда возникнет что-то что cможет. Потому что необходимость есть...
Составляют ли подобные веб-приложения большенство? Скорее всего нет.
Найдет ли BigTable свое применение? Найдет.
Означает ли BigTable конец RDBMS? Тут однозначно нет.
Сузится ли круг задач решаемых с помощью RDBMS? Тут однозначное да. Причем не обязательно под влиянием BigTable. Есть еще in cloud computing. Или OODBMS. Или еще чего нибудь...

Отличная задача на "подумать"

Есть некоторое количество вагонов (конечное), которые сцеплены между собой и образуют неразрывное кольцо. Требуется посчитать вагоны. Вознестись и считать с неба возможности нет. Можно только ходить вдоль состава туда и обратно. В рамках повышения эффективности и человеколюбия счетоводу выдано ведро с краской, которому прилагается кисть. Однако предыдущие счетоводы не справились с задачей, хотя и пытались её решать, поэтому на вагонах могут быть нанесены абсолютно любые знаки – числа, буквы, девичья фамилия вашего дедушки, секретный пароль от вашего журнала, номер вашей зачётки и так далее. Вдобавок, вдоль вагона разбросаны вёдра с краской, аналогичные вашему, и аналогичные кисти. Разбросаны по всякому. Как бы вы ни бросили ведро, какой бы знак ни нарисовали, где бы вы его не поставили, как бы вы его не поставили - всё одно, такое уже могло быть. И вы об этом никак не сможете узнать. А сосчитать вагоны надо.

Linux Kernel Development - кто что когда и зачем.

Linux Kernel Development

OOXML - мнения.

1. Миф об одном месяце для просмотра 6000 страниц спецификации OOXML.
2. Трезвый взгляд на принятие OOXML из лагеря Linux.
Мне было очень интересно узнать о возможных причинах отказа от SVG.

Then there is the charge about not using SVG in OOXML. There are a few things to point out about SVG.

Referencing SVG would pull virtually every spec that the W3C has produced (Javascript, check; CSS, check; DOM, check).

This can be deceptive in terms of the "size" of the specification, but also makes it incredibly complex to support. To this date am not aware of a complete open source SVG implementation (and Gnome has been at the forefront of trying out SVG, going back to 1999).
But to make things worse, OpenOffice does not support SVG today, and interop in the SVG land leaves a lot to be desired.
Some of my friends that have had to work with SVG have complained extensively to me in the past about it. One friend said "Adobe has completely hijacked it" referring to the bloatedness of SVG and how hard it is to implement it today.
At the time of this comment, Adobe had not yet purchased Macromedia, and it seemed like Adobe was using the standards group and SVG to compete against Flash, making SVG unnecessarily complicated.
Which is why open source applications only support a subset of SVG, a sensible subset.

3. Много-много критики OOXML. В основном здоровой критики. Со многим можно не соглашаться, но по крайней мере не сплошная истерика.

Набор данных для тестирования различных алгоритмов

Запись