• Списки с пропусками

      Итак, многие наверное слышали о списках с пропусками(skip lists), но далеко не все знают как они работают на самом деле. Список с пропусками — очень интересная структура данных, демонстрирующая на практике всю мощь рандомизированных алгоритмов.
      Читать дальше →
    • 10 советов по улучшению юзабилити веб-форм

      • Перевод
      image

      Веб-формы играют большую роль в ежедневном использовании интернета. Если вы разрабатываете веб-сайты, то скорее всего они в них присутствуют: будь то простая форма обратной связи или навороченное веб-приложение. Вот несколько советов, которые помогут создавать удобные в использовании формы.
      Читать дальше →
    • Построение суффиксного дерева: алгоритм Укконена

        По просьбам трудящихся выкладываю описание и доказательство алгоритма Укконена.

        Описание задачи


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

        Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N2). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

        На самом деле можно.
        Реализация и доказательство алгоритма под катом
      • Асинхронное программирование на JavaScript — Остаться в живых

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

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

        Это решает проблему, но означает, что мы теряем способность записывать последовательный алгоритм, а нетривиальный последовательный код преобразуется в граф функций обратного вызова.

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

        Сообщество JavaScript в курсе этого, особенно сообщество Node.JS, так как Node.JS ставит акцент на асинхронном коде.
        Читать дальше →
      • Кладезь полезной информации

          «Чем больше я знаю, тем больше понимаю, что ничего не знаю».

          Даже если вы уже давно не чайник и не боитесь увеличить относительный уровень своего незнания — попробуйте проделать на своей машине:
          sudo apt-get install fortunes-ubuntu-server
          а потом просто вызывайте
          /usr/bin/ubuntu-server-tip

          Многократный мысленный оргазм гарантирован.
          Вот просто некоторые примеры:
          • Для создания копии файла без дублирования пути файла используйте команду '$
            cp /long/path/to/file/name{,.orig}', которая создаст копию файла с суффиксом ".orig".
          • Если вы выполнили команду и забыли про 'sudo', вы можете набрать 'sudo !!'
            для вторичного запуска предыдущей команды с использованием 'sudo'.
          • Последующие команды обычно принимают аналогичный аргумент. 'Alt-.' вставляет
            последний аргумент предыдущей команды. Чтение документации рулит!

          Приятного чтения!
        • Капканы веб-разработки или веб- разработка в удовольствие

            Завязка


            Хочу поднять тему, актуальную для разработчиков и для заказчиков: разработка в удовольствие. Что это, миф или реальность? Существуют ли компании, в которых процесс разработки поставлен так, что приносит удовольствие обеим сторонам: разработчику и заказчику. Ведь в конечном итоге цель у обеих сторон одна — удовлетворенность конечным продуктом.
            Читать дальше →
          • Selenium: ожидание завершения всех AJAX-запросов

            В последнее время развелось очень много различных AJAX-приложений. По сути автоматизация тестирования такого приложения не отличается от автоматизации тестирования обычного WEB-приложения, но есть несколько тонкостей. Одна из тонкостей — это как раз ожидание завершения всех AJAX-запросов. Например, если отметка некого checkbox'а на странице вызывает обновление какого-нибудь select'a по AJAX-запросу, то тест, который сразу после отметки выбирает конкретный option, свалится, т.к. этого option'a там не будет. А всё потому, что сам тест выполняется намного быстрее чем AJAX-запрос на обновление списка.

            В данном случае у автоматизатора есть несколько выходов.
            Читать дальше →
            • +40
            • 25,4k
            • 8
          • Javascript и canvas в игре «Жизнь» Джона Конвея

              Напишем эту алгоритмическую игру [1] так, чтобы извлечь из неё максимальную образовательную пользу в области алгоритмов, языка Javascript, хорошего стиля программ, умения оптимизировать код. Центральным местом обсуждения будет не игра, а код, способы реализации, оптимизация.

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

              Недавно проведённый на Хабре опрос [3] показал реальную картину — 20% программистов написали когда-либо её работающую реализацию, а порядка 10% о ней не слышали. Что ж, тем интереснее будет оставшимся 80% узнать, что можно извлечь из реализации игры.
              Читать дальше →
            • Импорт Content type вместе с CCK полями


                Я как-то уже описывал процесс импорта Views, а теперь хочу расказать как импортировать Content type со всеми CCK полям.

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

                Написал, чтобы самому не забыть, и другим помочь :)
                Постарался максимально все описать, так что понятно будет даже новичкам.

                Читать дальше →
              • Всё, что надо знать о точке с запятой

                • Перевод
                Автовставка точек с запятой (";") — одна из наиболее спорных особенностей яваскрипта, вокруг которой скопилось много непонимания.

                Некоторые программисты ставят ";" в конце каждого оператора, некоторые — только там, где строго необходимо. Большинство же где-то посередине, хотя есть и такие, которые добавляют лишние ";" из стилистических соображений.

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

                Читать дальше →