Время сопоставления a n с образцом a? na n. |
В наши дни регулярные выражения стали блестящим примером того, как игнорирование хорошей теории порождает плохие программы. Имплементации регулярных выражений, использующиеся в современных популярных инструментах, значительно медленнее, чем те, которые использовались во многих Unix-программах тридцатилетней давности.
Эта статья описывает хорошую, годную теорию: регулярные выражения, конечные автоматы, и алгоритм поиска по регулярным выражениям, изобретённый Кеном Томпсоном в середине 1960-х. Эта статья также превращает теорию в практику, описывая простую реализацию томпсоновского алгоритма. Работа именно этой имплементации, занимающей менее 400 строк на C, показана на картинках сверху. Она работает быстрее, чем более сложные настоящие имплементации, использующиеся в Perl, Python, PCRE и др. Статья завершается дискуссией о том, как теория может быть реализована на практике в промышленных применениях.
http://swtch.com/~rsc/regexp/regexp1.html
Предыдущая статья в этой серии описывает две главных стратегии по имплементированию движков регулярных выражений: в-худшем-случае-линейные стратегии, базирующиеся на NFA и DFA, которые используются в awk, egrep и в большинстве современных grep'ов, и в-худшем-случае-экспоненциальная стратегия с откатами, которая используется практически во всех остальных движках, включая ed, sed, Perl, PCRE и Python.
Эта статья представляет две стратегии как два разных способа имплементации виртуальной машины, которая выполняет регулярное выражение, представленное в виде текстораспознающих байткодов. Примерно так, как .NET и Mono — разные способы исплементации виртуальной машины, которая выполняет коды программы скомпилированной в байткоды CLI.
http://swtch.com/~rsc/regexp/regexp2.html
В предыдущих двух статьях этой серии были описаны основы того, как писать движки регулярных выражений на DFA и NFA. Обе статьи основывались на игрушечных имплементациях, оптимизированных под то, чтобы объяснить базовые идеи. Эта статья основывается на рабочей имплементации.
Я провёл лето 2006 года делая Code Search, позволяющий программистам искать исходный код по регулярным выражениям. То есть, позволяет грепать по мировому публично доступному программному коду. Для поиска с использованием регулярных выражений мы сначала хотели использовать PCRE, пока мы не поняли, что он использует алгоритм с откатами, легко позволяя делать поиск за экспоненциальное время или с использованием произвольного размера стека. Так как Code Search выполняет произвольные регулярные выражения, приходящие из сети, использование PCRE означало бы открыть сервис для DoS атак. В качестве альтернативы PCRE, я написал новый, тщательно отрецензированный парсер регулярных выражений, в который была завёрнута свободная имплементация grep от Кена Томпсона, использующая быстрый DFA.
В течение следующих трёх лет я реализовал несколько новых бэк-ендов, которые в сумме заменили grep и расширили функциональность за пределы того, что требуется от POSIX grep. Результат, RE2, обеспечивает большинство функциональности PCRE используя C++ интерфейс, очень похожий на PCRE, но гарантируя выполнение за линейное время и фиксированный размер стека. RE2 широко распространён в Google, как Code Search так и во внутренних системах типа Sawzall или Bigtable.
Over the next three years, I implemented a handful of new back ends that collectively replaced the grep code and expanded the functionality beyond what is needed for a POSIX grep. The result, RE2, provides most of the functionality of PCRE using a C++ interface very close to PCRE's, but it guarantees linear time execution and a fixed stack footprint. RE2 is now in widespread use at Google, both in Code Search and in internal systems like Sawzall and Bigtable.
По состоянию на март 2010, RE2 является проектом с открытым кодом, с открытой для общественности разработкой. Эта статья — тур по исходникам RE2, показывающий, как методы из первых двух статей применяются в промышленной имплементации.
http://swtch.com/~rsc/regexp/regexp3.html
http://swtch.com/~rsc/regexp/
.*a.{20}a.*
) эта Haskell-имплементация обгоняет Re2, описанный выше, по абсолютному времени выполнения.Две недели назад я принял участие в Workshop Programmiersprachen und Rechenkonzepte, ежегодном собрании немецких исследователей в области языков программирования. На семинаре Frank Huch и Sebastian Fischer дали замечательную лекцию по элегантному матчеру регулярных выражений, написанному на Haskell. Одной из целей дизайна матчера было линейное время выполнения в зависимости от входной строки (т. е., отсутствие возвратов) и линейная зависимость от регулярного выражения. Использование памяти тоже должно было быть линейно-зависимым от размера регулярного выражения.
Во время семинара мы с несколькими Haskell-программистами реализовали этот алгоритм на (R)Python. Участвовали Frank, Sebastian, Baltasar Trancón y Widemann, Bernd Braßel и Fabian Reck.
В этой статье я хочу описать эту имплементацию и покажу код, потому что он очень прост. В следующей статье я покажу, какие оптимизации можно задействовать в PyPy над этим матчером, и сделаю сравнения производительности.
http://morepypy.blogspot.com/2010/05/efficient-and-elegant-regular.html
В этой статье я хочу показать, как JIT генератор из проекта PyPy может быть использован для превращения элегантного, но недостаточно быстрого матчера регулярных выражений, описанного в предыдущей статье, в достаточно быструю имплементацию. В дополнении к этому, я покажу некоторые измерения производительности в сравнении с различными другими имплементациями регулярных выражений.
http://morepypy.blogspot.com/2010/06/jit-for-regular-expression-matching.html
To get a feeling for the orders of magnitude involved, the CPython re module (which is implemented in C and quite optimized) can match 2'500'000 chars/s. Google's new re2 implementation still matches 550'000 chars/s. Google's implementation is slower, but their algorithm gives complexity and space guarantees similar to our implementation in the last blog post.
[…]
The C++ version is a little bit faster than the RPython version translated to C, at 750'000 chars/s. That's not very surprising, given their similarity. The Java version is more than twice as fast, with 1'920'000 chars/s. Apparently the Java JIT compiler is a lot better at optimizing the method calls in the algorithm or does some other optimizations.
[…]
With the regular expression matcher translated to C and with a generated JIT, the regular expression performance increases significantly. Our running example can match 16'500'000 chars/s, which is more than six times faster than the re module. This is not an entirely fair comparison, because the re module can give more information than just "matches" or "doesn't match", but it's still interesting to see. A more relevant comparison is that between the program with and without a JIT: Generating a JIT speeds the matcher up by more than 20 times.
Implementation язык (ред. — lionet) chars/s speedup over pure Python Pure Python code Python 12'200 1 Python re module C 2'500'000 205 Google's re2 implementation C++ 550'000 45 RPython implementation translated to C Python 720'000 59 C++ implementation C++ 750'000 61 Java implementation Java 1'920'000 157 RPython implementation with JIT Python 16'500'000 1352
This is just in: Google seems to be taking steps to allow operator billing. If that’s true it’s huge news.
Note from the outset that the article doesn’t say in so many words that operator billing is coming, although it certainly gives that impression, and plenty of publications translate it as such.
The basic idea of operator billing is very simple: if you want to buy an app, or access to online content, the price is automatically added to your operator bill (or, I assume, deducted from your pre-paid account).
Now I’m not a mobile billing specialist by any means, but I still want to give you an idea of what we’re talking about. If I make any technical mistakes, please correct them in the comments.
Just yesterday I made my first Android Market purchase, and although the process was relatively smooth, I still had to fill in all my credit card stuff, make mistakes, being told off, etc. Besides, when I tried to do the same a few months ago, the Android Market rejected my credit card. Why? Probably because the Dutch market wasn’t active yet — but I thought of that only much later. At the moment I was pretty pissed.
Now with operator billing I wouldn’t have all this hassle. I’d just click on whatever I want to buy, give a one-time confirmation “Yes, I do want to spend € 2.39 on this” and be done. When my next operator bill comes around, the € 2.39 will be added to it.
In addition, operators can verify your identity through your SIM card, without you having to do anything. No more hassle with credit card numbers. (In fact, the only parties that have a lot to lose from operator billing are the credit card companies. Expect resistance from them; they’ll probably say it’s unsafe or something.)
Thus operator billing is by far the most user-friendly way of making mobile purchases. That’s what makes it so important. Besides, it also opens up the mobile marketplace to those that do not have a credit card.
However, Google’s rather vague announcement does leave some questions unanswered. No doubt that’s because Google is still figuring out how to answer those questions. But let’s review them anyway:
The last question is probably the most important one. If I want to make a purchase through operator billing, there are three parties involved: me, the selling party, and the operator. Somehow, the selling party has to connect to the operator to figure out exactly who I am, and to make a request to put € 2.39 on my bill for my purchase. In addition, the operator has to pay that money (maybe minus a fee) to the selling party.
The JIL 1.2 API gives us some clues as to how this system is going to work. This API, that will eventually be implemented in Vodafone 360 phones as well as, one hopes, many others, has two properties that are meant specifically for operator billing (p. 16):
Widget.Device.AccountInfo.phoneUserUniqueId Widget.Device.AccountInfo.phoneOperatorName
Thus, when purchase times comes around, the store has some grip on your identity. It will have to send off a communication to the specified operator stating that user with unique ID X wants to make a € 2.39 purchase.
The operator will have to make some effort to verify this information; after all I might be able to hack a phone to send false unique IDs. Thus the operator will probably send me an SMS “Are you sure you want to purchase product X for € 2.39?“ Once I reply to that SMS the purchase is made and downloading can commence.
Still, I hope that the process will become even more user-friendly. The same JIL specification defines a way to send an SMS from a widget. Thus, if I want to purchase something the system could automatically generate an SMS for me and send it off to the operator. Thus the operator will be able to verify my intent by comparing my unique user ID with the SIM card through which the SMS was sent. If they match the purchase is made and downloading can commence.
That’s one step less, and thus more user-friendly. Hell, if it’s implemented correctly I don’t even have to switch to my SMS application. (The operator still has to tell the store “Purchase made, proceed with download.” But a proper system will not bother me with the details.)
Unfortunately the JIL 1.2 spec does not yet contain the methods that will be used for actual payments, nor the exact workflow. Besides, it’s unclear which operators Google is talking to right now. Probably US-based ones, and of those only Verizon is part of the JIL consortium. The others might use other APIs. (Come to think of it, so might Verizon. One never knows.)
Let’s close on a positive note and assume that a system roughly similar to what I describe above will actually be in place in two years or so. Apart from the increased user-friendliness of the purchasing process, what will it bring?
The basic answer is Long Tail. Increased user-friendliness and the scrapping of the requirement to own a credit card may entice more consumers to make a mobile purchase. That would be good.
The real benefit will lie with developers, though. In theory, the system could be set up so that individual developers who offer one or two apps for download on their own site can also use it.
Thus the requirement to offer your wares through one or more app stores might also be scrapped. That could be especially important to cross-platform apps such as W3C Widgets. Whichever phone with whichever operator ends up at the developer’s site, they can all make a purchase, provided they support widgets.
One more nail in the app stores’ coffin would be the opportunity to make in-app purchases; say some articles from a news site or a few new levels for your game. Operator billing is explicitly meant for such purchases, too. And if we can use operator billing in our apps, too, the app store infrastructure is basically not necessary any more.
Picture the following:
Where’s the app store in this process? Nowhere. We don’t need it any more. Wouldn’t that be something?
(I should note that although sending widgets via Bluetooth is possible nowadays — I’ve done it — the process is not very user-friendly yet. But this functionality is definitely coming; it’s not a pipe dream.)
So I’m impatiently waiting for Google to announce more details. Exactly how will their system work? What does the user have to do? Which operators? Questions, questions.
Anyway, the future of mobile payments has come one step closer.
HTTP POST -> HTTPS = Bad Idea® « my 20% - http://paulmakowski.wordpress.com/2009...
|
Shared by arty
это круто, да
интересно, при запросе для SpeedDial опера шлёт какие-то особые заголовки?
Для пользователей Opera и любителей визуальных закладок у нас есть хорошая новость. Теперь при добавлении в SpeedDial Яндекс.Погода и Яндекс.Карты будут показывать вам актуальную информацию о погоде и пробках в вашем городе.
Выглядит это вот так:
Воспользоваться такими закладками могут пользователи браузера Opera, начиная с версии 9.2, а также пользователи Firefox с помощью плагина Speed Dial. После добавления нажмите на закладке правую кнопку мыши и настройте нужный вам интервал обновления.
Любители визуальных закладок Яндекса
Сегодня увидел в ракспейсовской рассылке крайне интересную штуку – OpenStack http://www.openstack.org который продвигают NASA и Rackspace вместе. Кроме того весь софт открытый и под Apache License 2.0
Пишут что сделано всё на Python с Tornado и Twisted и AMPQ. Обещают первую версию к середине октября, а пока можно взять код на Лаунчпаде https://launchpad.net/openstack
Выглядит весьма интересно.
Originally published at Иван Бегтин. You can comment here or there.
сейчас большинство браузеров уже поддерживают localStorage
, и можно довольно смело его использовать для хранения данных на клиенте. Но каков размер этого хранилища? Спецификация говорит про «случайно выбранное ограничение в 5 мегабайт». Но не всё так просто.
большинство приложений будет хранить не байты, а символы. Абсолютное большинство символов даже в utf-8 занимает два байта. Некоторые реализации используют utf-16, которая использует два байта даже для ascii-символов.
каждый производитель браузеров принял своё решение. Chrome ограничивает размер базы именно пятью мегабайтами. Firefox позволяет хранить около 5 миллионов символов. Explorer — чуть меньше 5 миллионов. И только Opera уже сейчас при достижении предела просто предлагает пользователю выделить побольше места для приложения — вплоть до всего диска!
скорее всего, эти ограничения будут меняться со временем. Чтобы в любой момент можно было легко проверить актуальные ограничения, я сделал тест квоты на количество данных в localStorage
.
The script constructs very long strings and tries to save them to window.localStorage. When that fails, it reports last successful length and current failing length.
Diffable: only download the deltas. JavaScript library for detecting and serving diffs to JavaScript rather than downloading large scripts every time a few lines of code are changed. “Using Diffable has reduced page load times in Google Maps by more than 1200 milliseconds (~25%). Note that this benefit only affects users that have an older version of the script in cache. For Google Maps that’s 20-25% of users.”