• Введение в анализ сложности алгоритмов (часть 4)

    • Перевод
    • Tutorial
    От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
    Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
    Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


    Опубликовано ранее:
    Часть 1
    Часть 2
    Часть 3

    Оптимальная сортировка


    Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n2 ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

    Этот финальный раздел — опциональный. Он несколько сложнее, так что можете не стесняясь пропустить его, если хотите.От вас потребуется сфокусироваться и потратить некоторое время на решение упражнений. Однако, так же здесь будет продемонстрирован очень полезный и мощный способ анализа сложности алгоритмов, что, безусловно, стоит внимания.
    Читать дальше →
    • +50
    • 74k
    • 6
  • Как в Украине принимать платежи на PayPal в целом (и при продажах на eBay в частности)

    Предисловие


    Не вижу смысла описывать условия, побудившие меня к поиску возможностей получения средств на счёт PayPal с других счетов PayPal. Вместо этого почти сразу перейду к сути найденной возможности. Почти — потому что предварительно хотел бы заявить о том, что возможность найдена путём теоретических измышлений и в реальность не претворялась. Я богобоязненный и законопослушный гражданин, потому мне омерзительна мысль иметь полноценный PayPal аккаунт (и продавать на eBay с использованием дефолтного способа оплаты, которого не боятся покупатели) если для этого придётся пойти на предоставление неправдивых данных с околонулевой вероятностью обнаружения обмана. В общем,

    вот как принимать платёж на PayPal
  • Опенсорс телефон «Gongkai» за 12$

      imageПо цене пары-другой чашек кофе вы получаете полноценный телефон с двухцветным OLED-экраном, Bluetooth и возможностью воспроизведения MP3-музыки. Все это — в прозрачном зеленом корпусе.

      Как пишут блогеры, предположительная себестоимость телефона Gongkai — около 10 долларов, то есть он еще и продается с неплохой маржой в 20%. В комплект поставки входят зарядное устройство, USB-кабель и защитный силиконовый чехол.

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

      Интересным также выглядит сравнение с Arduino Uno 3го поколения:
      Читать дальше →
    • Flight — новый js-фреймворк от Twitter

        Сегодня команда Twitter представила общественности собственный фреймворк. Flight — это легкий компонентный javascript фреймворк, каждый компонент которого описывает поведение элементов на странице. На самом деле, вы скорее всего уже видели Flight в действии, потому что Twitter использует его для своих приложений. Вы можете посмотреть демонстрацию возможностей фреймворка в виде простейшего почтового клиента (код на github).

        Новый фреймворк использует ES5-Shim для поддержки ES5 в старых браузерах и jQuery для манипуляции DOM. Также потребуется одна из реализаций AMD, например require.js или loadrunner.
        Зачем нам еще один фреймворк?!
      • И снова о… LAMP и базово защищённый мини-хостинг своими руками

          Увидев в очередной раз презренный посыл в Google в ответ на вопрос о том, как развернуть собственную LAMP'у, решил написать данный пост. Чтобы хоть как-то разбавить тонны радостных отчётов об успешной установке из блогов, суть которых сводится к одной команде aptitude install blah-blah.

          Нет, ну конечно понятно, PHP самый надёжный язык, а все движки сайтов, на нём написанные, являются живым воплощением непробиваемой защиты от взлома. Тогда да — aptitude install apache2 — и будет вам счастье. Не забудьте оставить phpmyadmin по дефолтному адресу, да поставьте какое-нибудь дырявое FTP решето.

          Вообще, как оказалось, многие даже не в курсе, что взломав сайт и получив возможность исполнять свой PHP код, злоумышленник на системе с дефотными настройками сможет как минимум прочитать в вашей системе почти что угодно. Оно и понятно — работая с Linux привыкаешь как-то, что по дефолту безопасность находится на вполне достаточном уровне. А тут такая дыра…

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

          Те, кому тема веб-серверов надоела, возможно смогут найти в статье интересные приёмы многопользовательского ограниченного доступа к серверу по SFTP.

          И нет, это не ещё одна статья с описанием установки Linux и выполнением aptitude install apache2. Скорее наоборот: в этой статье я хотел показать фатальную недостаточность данных манипуляций и мягко говоря некомпетентность тех, кто их тиражирует в интернете.
          Итак - снова LAMP
        • Архитектура highload проекта на примере веб-консультанта

            Наша команда занимается удаленным администрированием серверов и не так давно к нам обратились представители сервиса WebConsult с задачей построить легко масштабируемую серверную архитектуру, которая будет выдерживать серьезные нагрузки. Мы решили, что возможно это будет интересно пользователям Хабрахабра, которые так или иначе связаны с администрированием Highload проектов. Проект оказался быстрорастущим и имеющаяся на тот момент структура уже работала на пределе, поэтому нам пришлось в ускоренном режиме запускать новую.

            image

            Читать дальше →
          • EC2 — анализ цен для стартапа

            В данный момент я занимаюсь поиском подходящих серверов для инфрастуктуры моего проекта. Я остановился на EC2 и решил проанализировать, какое решение будет наиболее экономически выгодным для меня. Эта статья по сути является продолжением AWS Insight: Резервации в EC2 — как это работает, но приводит анализ для молодого веб-стартапа (24x7).

            Проблема


            Сервер должен работать 24 часа в сутки напротяжении X месяцев (количество не определено). Какой вариант (On Demand / Light Utilization Reserved / Medium Utilization Reserved / Heavy Utilization Reserved) выбрать для Micro/Small/Medium/Large серверов?

            Читать дальше →
          • Организация видео трансляции

              Предлагаю сообществу поделиться своим опытом в области видео трансляций.
              Может получится создать что-то на подобии мини пособия.
              Схема простая: кто-то задает вопрос, а знающий ответ – делиться информацией. И всё это попадает в топик.
              Попробую начать из того, что узнал по советам и ответам на форумах.

              Если у меня нету сервера, как я могу транслировать видео с моей веб камеры?
              – проще всего воспользоваться сервисами smotri.com, rutube.ru или yatv.ru
              – с помощью Moonware webcamXP Pro
              – с помощью VLC: Камера → FireWire → VLC → Lan → VLC ©amcdm

              Как организовать полноценную трансляцию через мой сервер?
              – На базе Adobe: WEB-камера → Adobe Flash Media EncoderAdobe FMS → Adobe Flash приложение. ©Min0r
              – На базе Microsoft: WEB-камера → Windows Media EncoderWindows Media Services → ASF(WMV) для Microsoft Silverlight или Windows Media Player ©TMC
              – На базе Microsoft: WebCamera/Video file → Expression Encoder → IIS media services / WMS → Flash / Silverlight / Windows Media ©gaploid
              – На основе Open Source: WEB-камера → Adobe Flash приложение → Red5 → Adobe Flash приложение. ©khromoff
              Wowza Media Server ©mykir и xternal
              Цена: $995 за сервер, либо подписка 65$ в месяц. До 10 одновременных подключений (для разработки) — бесплатно.
              ffserver, camserv, webcam-server ©JohnMcClane

              Какой из вышеперечисленных серверов менее нагружает систему?
              – Flash Media Server 2/3 и Wowza Media Server без особых отличий ©mykir

              Как работает видео трансляция где качество картинки определяется скорость канала пользователя?
              – Видео параллельно кодируется с разными битрейтами. В протоколе, насколько помню, присутствуют команды для переключения битрейтов налету. Соответственно, этим управляют одновременно плеер и вмс. ©TMC

              Как быть если несколько камер?
              – На базе Red5. ©khromoff

              С помощью какого ПО можно организовать видеоконференцию?
              Adobe Connect
              Windows Live meeting ©tikondrus

              Какие требования к каналу при ведении видеоконференций?
              –?

              А что делать, если я хочу вещать видео, которое уже хранится на компьютере, с конвертированием на лету?
              VLC, Live555 Media Server либо Darwin Streaming Server от Apple. ©ilya_smelykh
              – Плейлисты в Windows Media Services. Требуют переконвертирования всех файлов в WMV. Позволяют очень гибко настраивать плейлисты во времени. ©TMC

              Как организовать VoIP телефонию для техподдержки с сайта?
              –?

              Какие аппаратные решения видео трансляции?
              Tandberg, Polycom, Cisco ©unconnected

              Какую из веб камер посоветуете при работе со слабом освещением?
              axis p1311 – светочувствительность 0.7 lux

              Несколько презентаций на данную тематику. ©itjobby

              Задавайте свои вопросы или можете поделиться информацией как вы организовывали трансляцию.

              UPD: обновил топик новыми ответами и ценами на решения для серверов 10.08.2009
            • Создание телеканала в интернете при помощи домашнего компьютера

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

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

              Итак если вы хотите организовать собственный тв канал в интернете нам понадобится список необходимых для этого программ:

              1 вариант (бюджетный и с самой низкой нагрузкой на машину) — VLC media player, acestream (torrentstream). Все будет работать и под Windows и под Linux.

              2 вариант (только под Windows) — VLC media player, acestream (torrentstream), XSplit Broadcaster и/или VH Screen Capture driver, а также по желанию Virtual Audio Cable.
              Читать дальше →
            • Как подружить Django и Sphinx?

              Предыстория


              Понадобилось мне добавить на сайт функцию поиска. Первой мыслью было — воспользоваться возможностями SQL-сервера, — но искать надо сразу по нескольким таблицам, слова и фразы, да ещё и со стеммингом. Понял, что изобретать свой велосипед будет накладно.

              Решил поискать, а что же всё-таки есть из готовых решений? Оказалось, прямо скажем, не густо: django-haystack и django-sphinx. Ранее достоинства и недостатки обоих уже перечисляли, поэтому не буду повторяться.

              Потратив какое-то время на чтение блогов и форумов, решил всё-таки попробовать django-sphinx, т. к. в django-haystack, насколько мне известно, с поддержкой Sphinx до сих пор не очень.

              Автор же django-sphinx давно забросил свой проект, но есть множество форков, и, говорят, что пользоваться им вполне возможно. Я выбрал тот, что был, хм, посвежее и попытался подключить его к своему проекту.
              Но не тут-то было
            • Шпаргалки по MongoDB

              • Tutorial
              Хотя шпаргалки по MongoDB доступны на официальном сайте, многие до них не добираются, составляя свои собственные. Упростим задачу пользователям MongoDB.

              Шпаргалки в формате .pdf:


              Всё одним архивом.
              • +40
              • 20k
              • 5
            • Использование MongoDB в Django

                — документо-ориентированная система управления базами данных (СУБД) с открытым исходным кодом, не требующая описания схемы таблиц. Написана на языке C++ и распространяется в рамках лицензии Creative Commons.

                В последнее время становится довольно популярной и восстребованой. И вот возникла идея использовать ее в связке с фреймворком Django. Собственно о чем далее и пойдет речь.

                Читать дальше →
              • Petcube — гаджет для домашних животных

                  Всем привет, меня зовут Александр Нескин. Я живу в Киеве, работаю в сфере IT и увлекаюсь робототехникой. В этом посте я расскажу, как довольно невинное развлечение с Arduino превратилось в перспективный проект. Ах, да, все это называется Petcube – робот, который позволит вашим домашним любимцам забыть об одиночестве и депрессии в те моменты, пока вас нет дома.

                  image

                  Читать дальше →
                • Git up и все все все

                  • Tutorial
                  Комманда git up (аналог svn up) добавляется так:
                  git config --global alias.up '!(git add . && git stash && git pull --rebase >&2) | grep -v "No local changes to save" && git stash pop'
                  

                  git up при надобности ныкает все ещё незакоммиченные изменения в stash, обновляет локальную ветку до свежайшей и восстанавливает локальные изменения назад. В том числе переносит ещё неотправленные локальные коммиты в самый конец, делая историю линейной как в Subversion, т.е. избегая лишних веток и merge-коммитов.
                  Читать дальше →
                • Видеозапись доклада «Вся соль одностраничных приложений» с 404fest

                    Федя Шумов и Арсений Заречнев, фронт-енд разработчики из команды Островка, рассказали о
                    «Всей соли одностраничных приложений» на 404fest в Самаре.

                    Содержание доклада:


                    Читать дальше →
                  • Suggest.io: на пути к идеальному поиску

                      Живой поиск для вашего сайта


                      Поиск по сайту — проблема для большинства Интернет-ресурсов. Создание собственного поиска занимает время и требует навыков тонкой настройки поисковой системы. Если владелец сайта заинтересован, чтобы его поиск оставался актуальным, ему нужно иметь «под рукой» специалиста, который постоянно занимается совершенствованием алгоритма релевантности, индексом, базой запросов и т.д. Всё это хлопотно, поддержка собственного поиска требует серьезных затрат.

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

                      image

                      Читать дальше →
                    • Модульный подход к разработке web-приложений с использованием JavaScript: AMD и RequireJS

                        RequireJSПри разработке приложений с модульной структурой на JavaScript возникает две проблемы:
                        • описание и удовлетворение зависимостей различных частей приложения, необходимость организации подключения зависимостей на серверной стороне;
                        • экспорт переменных в глобальную область видимости и их коллизия.

                        Обе эти задачи решаются при использовании подхода Asynchronous Module Definition. Он сводится к описанию модулей функцией define и подключению их с помощью require. На данный момент есть несколько инструментов, реализующих AMD. Я начал своё знакомство с ними с RequireJS и был удивлён, насколько удобно и просто можно описывать зависимости модулей. Расскажу, как это работает, на простом примере.
                        Читать дальше →
                      • Amazon Glacier: клиент на Perl с многопоточной/multipart закачкой

                        image

                        Amazon Glacier


                        Вкратце — Amazon Glacier — это сервис с очень привлекательной ценой сторейджа, созданный для хранения архивов/бэкапов. Но процесс восстановления архивов довольно сложный и/или дорогой. Впрочем, сервис вполне пригоден для secondary backup.
                        Подробнее про Glacier уже писали на хабре.

                        О чём пост


                        Хочу поделиться Open Source клиентом на Perl для синхронизации локальной директории с сервисом Glacier, также расказать о некоторых ньюансах работы с glacier и описать workflow его работы.
                        Читать дальше →
                      • Встречаем Veracity — новую распределенную систему контроля версий


                          Здравствуй, мой любознательный %username%!

                          Несколько месяцев назад я случайно наткнулся на еще одну перспективную систему управления версий — Veracity, о которой и хотел бы сегодня рассказать, чтобы тебе было что поковырять на выходных. Несмотря на то, что разработка Veracity идет уже больше года, на Хабре ее имя было лишь пару раз вскользь упомянуто в комментариях. Под катом тебя ждет краткое описание Veracity и ссылки, где можно получить более подробную информацию о ней.
                          Хочу!