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

В первую очередь для всех имеющихся у нас окислительно-восстановительных реакций мы стали показывать соответствующие полуреакции.
Например, вот так:

Новый поисковик Blekko начал работу полтора месяца назад и вполне естественно привлёк к себе пристальное внимание экспертов. Не только благодаря инновационному интерфейсу и слэштегам, но и в принципе, всё-таки в наше время запуск нового поисковика общего профиля — большая редкость. Мало кто осмелится тягаться с Google. Кроме всего прочего, это требует немалых финансовых вливаний.

Давайте посмотрим, что представляет из себя инфраструктура Blekko, о которой в подробностях рассказали CEO Ричард Скрента и CTO Грег Линдал.

Дата-центр Blekko насчитывает около 800 серверов, каждый с 64 ГБ RAM и восемью SATA-дисками по терабайту. Система резервирования RAID не используется совсем, потому что RAID-контроллеры сильно снижают производительность (с 800 МБ/с для восьми дисков до 300-350 МБ/с).

Оказывается, запросы пользователей могут очень хорошо коррелировать с, например, скоростью распространения гриппа. То есть частота запросов, связанных с тем же гриппом, может совпадать с со скоростью роста количества заболеваний гриппа. Если такую корреляцию отобразить на графике, то наблюдается практически полное совпадение. Подобное было замечено где-то в конце 2008 года, когда разработчики Google запустили сервис Google Flu Trends. Данный сервис отслеживал количество запросов пользователей, связанных с гриппом, и сравнивал такие данные со скоростью распространения этой болезни. Выяснилось, что на основе всех этих данных можно прогнозировать вероятность появления начала эпидемии гриппа в определенном регионе или даже прогнозировать развитие эпидемии, причем на достаточно длительный срок.

CAPTCHA, или Completely Automated Public Turing Tests to Tell Computers and Humans Apart (Полностью автоматический публичный тест Тьюринга для различения компьютеров и людей), была создана для того, что бы убедиться, что введенные данные не были сгенерированы компьютером. Эти своеобразные тесты обычно используются в Интернете для защиты форм регистрации и комментирования от спама. Если быть честным, я испытываю смешанные чувства насчет CAPTCHA. Она в большинстве случаев раздражает меня, но не смотря на это я использовал CAPTCHA в качестве защиты на некоторых сайтах.

В этой статье я хочу углубиться в поиск идеального решения проблемы растущего количества сгенерированного людьми спама. Мы взглянем на то, как и зачем используется CAPTCHA и ее влияние на юзабилити в поисках ответа на ключевые вопросы: что представляет из себя идеальная CAPTCHA и почему в качестве защиты предпочитают именно ее?

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

Наиболее простая схема «распараллеливания» нагрузки — вынос основной нагрузки на несколько frontend. Раньше приходилось мучиться (или наслаждаться, кому как) с webdav'ами, кластерными ФС и прочими хитростями чтобы обеспечить актуальную информацию, так было до тех пор, пока не появился nginx, а точнее proxy_store и proxy_cache в нём.

Итак, сегодня мы соберём генератор миниатюрок на базе любимого народом веб-сервера — nginx-а. Что примечательно, сделаем мы это без единого гвоздя, т.е. без единой строчки кода, не считая конфигурации.

Многим разработчикам знакома ситуация когда кешировать страницы сайта, скажем, на 5-10 минут нельзя всего из-за одного небольшого блочка, актуальность которого нужно поддерживать если не в реальном времени, то с временем «старения» не больше 5-10 секунд. При этом посещаемость сайта продолжает расти, растет время генерации страниц и c этим надо что-то делать…

• Вариант решения 1: Подкрутить то, до чего не доходили руки последнее полгода. Все Вас поймут и передвинут сроки на другие задачи. Вы будете в роли «Супермена» один спасать сайт от непомерной нагрузки, решая проблему «бесплатно» (без доп. вливаний в оборудование). Вам может пригодиться статья «Тюнинг nginx».
   
• Вариант решения 2: Улучшить техническую базу (докупить мозгов на сервер, улучшить дисковую систему, поставить под БД отдельный сервер). В принципе проблема не решена, а скорее отложена. Теперь у Вас есть время «окопаться» и подготовиться ко второй волне наплыва нагрузки, она будет больше и накроет сильнее.
   
• Вариант решения 3: Ваш вариант, о котором я, вероятно, узнаю из комментариев.
   

Позвольте предложить и мне проверенное и относительно простое решение на базе одной из старейших технологий в Web-разработке.

Одна простая клавиша Ctrl может значительно упростить работу в Visual Studio. Помимо типичных комбинаций, которые нам очень хорошо знакомы, существует также и большое количество других, менее известных, но от этого и более ценных.

Далее список того, что можно делать с клавишей Ctrl.

  Начиная с версии 0.8.50 в модуле Nginx secure_link появилось значительное улучшение по защите ссылок от подделывания. Как ни странно, новые возможности до сих пор не отражены в официальной документации [1]. Описание на английском можно найти на сайте Nginx Community [2], а также пояснения Сысоева по данным изменениям [3]. Код на PHP для генерации защищённых ссылок можно найти в форуме по nginx [4].
 В общем, новшество выглядит так:

Категорически приветствую! В прошлый раз я писал о вероятностном алгоритме определения принадлежности элемента множеству, в этот раз будет про вероятностную оценку похожести. Не надо большого ума, чтобы додуматься до следующего показателя схожести двух множеств А и Б:



То есть, количество элементов в пересечении делённое на количество элементов в объединении. Эта оценка называется коэффициентом Жаккара (Jaccard, поэтому «J»), коэффициент равен нулю, когда множества не имеют общих элементов, и единице, когда множества равны, в остальных случаях значение где-то посередине.

И снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».

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

Пишу эту статью, и представляю себе тебя, читателя Хабра, которой в обеденный перерыв залез почитать что-нибудь для развития. А этот читатель, т.е. ты (да, не отворачивай глаза от букв, именно ты) давно наслышан, что своё дело – это круто. И, может быть, как раз не хватало лёгкого пинка, чтобы выйти из зоны будничного комфорта и что-нибудь, да предпринять.

Эта статья адресована тем, кто уже «на грани». Она почти лишена философии и туманных ссылок, просто тупо туду-лист. Бери и делай. Намеренно избавляю тебя от объяснений, зачем молодому проекту нужна госрегистрация, такая ли уж это свобода – быть собственником и от куда взять деньги на госпошлину. Статья адресована московским стартаперам, гео-патчи от других городов приветствуются в комментариях.
Будем считать, что с формой собственности определились — это ООО и упрощенка 6%. Если кому нужно ИП – там проще, справишься и без этой статьи.

Для создания фирмы необходимо:

Здравствуй, Хабр! Мы с тобой уже побаловались фильтрами Блума и MinHash. Сегодня разговор пойдёт о ещё одном вероятностном-рандомизированном алгоритме, который позволяет с минимальными затратами памяти определить примерное число уникальных элементов в больших объёмах данных.

Для начала, поставим себе задачу: предположим, что у нас имеется большой объём текстовых данных — скажем, плоды литературного творчества небезызвестного Шекспира, и нам необходимо подсчитать количество различных слов встречающихся в этом объёме. Типичное решение — счётчик с урезанной хеш-таблицей, где ключами будут слова без ассоциированных с ними значений.

Способ всем хорош, но требует относительно большой объём памяти для своей работы, ну а мы с вами, как известно, неугомонные гении эффективности. Зачем много, если можно мало — примерный размер словарного запаса упомянутого выше Шекспира, можно вычислить используя всего 128 байт памяти.

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

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

Несколько лет назад ко мне пришел мой босс и сказал: «У нас есть новый проект для тебя. Это перенос сайта, который уже имеет 1 миллион посетителей в месяц. Тебенеобходимо его перенести и убедиться, что посещаемость может вырасти в будущем без всяких проблем.» Я уже был опытным программистом, но не имел никакого опыта в области масштабируемости. И мне пришлось познавать масштабируемость трудным путем.

Введение

С момента написания мной предыдущей статьи по оптимизации этой связки прошло довольно много времени. Тот многострадальный Pentium 4 c 512Мб памяти, обслуживающий одновременно до тысячи человек на форуме и до 150,000 пиров на трекере уже давно покоится на какой-нить немецкой, свалке, а клуб сменил уже не один сервер. Всё сказанное в ней всё ещё остаётся актуальным, однако есть вещи которые стоит добавить.
Статья большая, так что будет поделена на логические блоки:

0. Зачем вообще что-то оптимизировать?
  
1. Оптимизация ОС (FreeBSD)
  1.1 Переход на 7.х 
  1.2 Переход на 7.2
  1.3 Переход на amd64
  1.4 Разгрузка сетевой подсистемы
  1.5 FreeBSD и большое кол-во файлов
  1.6 Softupdates, gjournal и mount options
  
2. Оптимизация фронтенда (nginx)
  2.1 Accept Filters
  2.2 Кеширование
  2.3 AIO
  
3. Оптимизация бэкенда
  3.1 APC
  3.1.1 APC locking
  3.1.2 APC hints
  3.1.3 APC fragmentation
  3.2 PHP 5.3
  
4. Оптимизация базы данных
  4.1 MySQL 
  4.1.1 Переход на 5.1
  4.1.2 Переход на InnoDB
  4.1.3 Встроеный кеш MySQL - Query Cache
  4.1.4 Индексы
  
4.2 PostgreSQL
  4.2.1 Индексы
  4.2.2 pgBouncer и другие.
  4.2.3 pgFouine
  
4.3 Разгрузка базы данных
  4.3.1 SphinxQL
  4.3.2 Не-RDBMS хранилище
  4.4 Кодировки
  4.5 Асинхронность
  
Приложение. Мелочи.
  1. SSHGuard или альтернатива.
  2. xtrabackup
  3. Перенос почты на другой хост
  4. Интеграция со сторонним ПО
  5. Мониторинг
  
 6. Минусы оптимизации

Введение

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

Основные операции в деревьях выполняются за время пропорциональное его высоте. Сбалансированные деревья минимизируют свою высоту (к примеру, высота бинарного сбалансированного дерева с n узлами равна log n). Большинство знакомо с такими сбалансированными деревьями, как «красно-черное дерево», «AVL-дерево», «Декартово дерево», поэтому не будем углубляться.

В чем же проблема этих стандартных деревьев поиска? Рассмотрим огромную базу данных, представленную в виде одного из упомянутых деревьев. Очевидно, что мы не можем хранить всё это дерево в оперативной памяти => в ней храним лишь часть информации, остальное же хранится на стороннем носителе (допустим, на жестком диске, скорость доступа к которому гораздо медленнее). Такие деревья как красно-черное или Декартово будут требовать от нас log n обращений к стороннему носителю. При больших n это очень много. Как раз эту проблему и призваны решить B-деревья!

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

Здравствуйте, уважаемое сообщество! Думаю, многим знакома такая структура данных как суффиксное дерево. На Хабре уже было описание как его построить и зачем. Если вкратце, то оно нужно тогда, когда надо много раз искать какие-то произвольные образцы X_i в заранее заданном тексте A, а строится такое дерево мучительно с помощью алгоритма Укконена (есть и другие варианты, но они предполагают еще большее количество страданий). Общее наблюдение при работе с алгоритмами таково, что деревья — это, конечно, хорошо, но на практике их лучше избегать из за серьезных оверхэдов по памяти и не очень оптимального (с точки зрения эффективности оперирования данными компьютером) расположения. Кроме того, именно в таком дереве есть еще более существенная неприятность, а именно алфавитнозависимость структуры. Для решения этих проблем был придуман суффиксный массив. О том как его строить и как использовать и пойдет в этой статье.

Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто.

Судоку — популярная головоломка, основной задачей которой является размещение цифр в правильном порядке.

Игровое поле представляет собой квадрат 9х9 клеток. Клетки сгруппированы в девять сегментов 3х3. В каждой клетке может быть записана цифра от одного до девяти. Основным правилом судоку является то, что цифра не может повторяться в строке, столбце и сегменте.

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

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

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

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