Tuesday, February 26, 2008

Django urlpatterns для hostname

Я не буду сейчас детально рассказывать, что такое urlpatterns в django, понадеясь на осведомлённость возможных читателей. Однако для тех, кому это внове, дам краткий пример. В Django для сопоставления url`ов коду используются конфигурационные файлы urls.py (Urlconf). Основной смысл этих файлов в подобных строчках:

(r'login/$', 'someapp.views.login')
Данная строка означает, что когда пользователь зайдёт на страницу www.example.com/login/ , то для генерации страницы вызовется функция someapp.views.login . В простейшем случаем первым параметром такой строки является регулярка, вторым - нужная функция. Заметьте, что регулярка сопоставляется только с путём, а хостнейм отбрасывается. Сами urlconf весьма удобны, но такое игнорирование хостнейма не даёт использовать стандартные джанговские подходы для реализации подобных вещей:
  • Вызов различных функций в зависимости от части хостнейма, например, pda.example.com - PDA версия сайта, blog.example.com - блог на сайте. Конечно, это можно реализовать и другими средствами, однако создание разветвлённой структуры всё же затруднено.

  • Передача параметров в функции в зависимости от хостнейма. Например, tilarids.blogspot.com - на самом деле, все такие страницы могут генерироваться одной функцией в зависимости от имени пользователя
Т.о., возникает желание получить механизм, который бы работал аналогично urlconf, но вместо пути работал бы с хостнеймом. После небольшого исследования на эту тему у меня создалось впечатление, что это так нигде и не реализовано. Отсюда и родился подобный код:
class HostnameDispatcher(object):
def __init__(self, view, myregex):
self.regex = re.compile(myregex, re.UNICODE)
self.view_func = view
def __call__(self, request, *args, **kwargs):
current_site = RequestSite(request)
match = self.regex.search(current_site.domain)
print "Current args:",args, kwargs
if match:
new_kwargs = match.groupdict()
if new_kwargs:
new_args = args
else:
new_args = match.groups() + args
new_kwargs.update(kwargs);
return self.view_func(request,*new_args,**new_kwargs)

class HostnameRegexPattern(RegexURLPattern):
def __init__(self, regex, callback, hostname_re,proto=u'http://',default_args=None, name=None):
RegexURLPattern.__init__(self,regex,callback,default_args, name)
self.hostname_regex = hostname_re
self.dispatcher = HostnameDispatcher(self.callback, self.hostname_regex)
self.old_regex = self.regex
self.regex = re.compile(u'\b'+proto+hostname_re+u'/'+regex,re.UNICODE)

def resolve(self, path):
match = self.old_regex.search(path)
if match:
kwargs = match.groupdict()
if kwargs:
args = ()
else:
args = match.groups()
kwargs.update(self.default_args)
return self.dispatcher, args, kwargs

Хочется заметить, что основными требованиями к коду были:
  • Полная совместимость со стандартными способами resolve и reverse (получения функции по адресу и адреса по функции соответственно)
  • Безболезненное встраивание в рабочую систему Django
Возможно, код несколько сумбурный - несмотря на недолгую жизнь, он успел почувствовать на себе процесс развития и переделывания. Постараюсь объяснить, что здесь зачем. Итак:
  • HostnameDispatcher - класс, который позволяет resolv`ить функцию по хостнейму, являсь некой надстройкой над этими самими функциями(вернёмся к терминологии django и будем называть их view). Например,
    disp = HostnameDispatcher(my_view,r'^(.*)$')
    создаёт на основе существующего view новый объект, который при резолве добавляет параметры из хостнейма. Удобно, быстро, но никак не поможет при reverse. А вот reverse - это как раз самая сложная, но и не менее нужная часть
  • HostnameRegexPattern - это замена стандартным урлпаттернам. resolve здесь реализуется через уже упомянутый HostnameDispatcher. А вот с reverse пришлось извратиться. В django нет хорошей возможности изменять стандартное поведение reverse. Т.о., я просто изменил существующую регулярку, и в итоге получил почти правильный результат. Единственное, выскакивает '/' в начале. Для его устранения я не придумал ничего лучше, чем сделать небольшой патч для django(в django.core.urlresolvers):
    def backspace_process(func):
    def reverse_new(viewname, urlconf=None, args=None, kwargs=None):
    ret_val = func(viewname, urlconf, args, kwargs)
    if ret_val[:4]=='/%08':
    return ret_val[4:]
    return ret_val
    return reverse_new

    def reverse(viewname, urlconf=None, args=None, kwargs=None):
    args = args or []
    kwargs = kwargs or {}
    return iri_to_uri(u'/' + get_resolver(urlconf).reverse(viewname, *args, **kwargs))

    reverse = backspace_process(reverse)
    Т.е., добавляется в начале отдельный символ(\b), который потом удаляется при надобности. Такое удаление не должно никак повлиять на другие urlpatterns
Ну и наконец: как это использовать. Нет ничего проще- записываем в urls.py в паттерны такую строчку:
HostnameRegexPattern('test/(\d+)/$', 'blog.views.test',r'^(.*)$'),
, где первый параметр - регулярка для пути, второй - функция, третий - регулярка для хостнейма. Всё! :)

Кто может предложить что-нибудь более интересное, или улучшить уже существующий код - буду весьма благодарен.

Tuesday, February 12, 2008

Как посчитать очень большой факториал?

Не так давно обратил внимание на то, как быстро Maple считает факториалы(встроенный функционал). 500000! - огромное число - он посчитал за пару секунд. Стало интересно - как же это реализовано? В итоге было написано несколько тестовых кусочков кода на ЯП, которые поддерживают большие числа. Первым таким языком был Erlang. Код весьма прост:
[UPD]
fact3(X)->fact3(X,1).

fact3(0,Acc)->Acc;
fact3(X,Acc)->fact3(X-1,Acc*X).
[/UPD]
Erlang соптимизирует рекурсию в цикл и в итоге этот код будет достаточно оптимальным. [UPD]На сравнительно небольших числах он работает отменно. Например, 50000! он посчитал за 6 секунд(особой точности здесь не требуется, поэтому я не старался получить максимально точные данные или тестировать в абсолютно чистой среде). Но 100000! у меня он вообще считать отказался - упал по нехватке памяти.[/UPD]
Вторым языком, который был опробован, стал PHP. Наивный код на PHP на больших числах не стесняясь выдавал INF, но тов. Josser(не знаю, куда поставить ссылку) довёл код до ума:

$targ = 50000;
$res = 1;

$startime = time();
for ($i=1; $i<=$targ; $i++) {
echo $i."\r\n";
$res = bcmul($res, $i);
}
$endtime = time();

echo $res."\r\n";

echo $endtime-$startime."\r\n";

Также Josser и протестировал его:
30000! - 99 секунды
50000! - 242 секунды

Как видим, работает оно медленней, чем вариант на Erlang, но хотя бы работает на 50000!.
Следующим языком стал Python. Код также прост, как и в предыдущих случаях:


def fact(x):
s=1
for i in range(2,x+1):
s*=i
return s

Протестировав, получаем:
30000! - 1.64100003242
50000! - 7.54700016975
100000! - 40.75

Как видим, Python смотрится просто героем на фоне Erlang и PHP. Однако, с увеличением чисел понимаем, что подобраться к заветному 500000! таким образом не получится.
Следующим протестированным языком стал Haskell. Я не особо знаком с этим языком, поэтому не могу похвастать и абсолютно правильным кодом. Главное - работает:

import Text.Printf
import Control.Exception
import System.CPUTime

time :: IO t -> IO t
time a = do
start <- getCPUTime
v <- a
end <- getCPUTime
let diff = (fromIntegral (end - start)) / (10^12)
printf "Computation time: %0.3f sec\n" (diff :: Double)
return v

fac n = if n == 0 then 1 else n * fac (n-1)

main = do
putStrLn "Starting..."
time $ fac 100000 `seq` return ()
putStrLn "Done."

Результаты тестирования:
30000! - 4.828 sec
50000! - 14.531 sec
100000! - 70.625 sec
Получше, чем Erlang и PHP, но хуже, чем Python. Также я вспомнил свои познания из области математики и попробовал организовать вычисление факториала через гамма-функцию. Код для вычисления логарифма гамма-функции:

cof :: [Double]
cof = [76.18009172947146,-86.50532032941677,24.01409824083091,-1.231739572450155,0.001208650973866179,-0.000005395239384953]

ser :: Double
ser = 1.000000000190015

gammaln :: Double -> Double
gammaln xx = let tmp' = (xx+5.5) - (xx+0.5)*log(xx+5.5)
ser' = foldl (+) ser $ map (\(y,c) -> c/(xx+y)) $ zip [1..] cof
in -tmp' + log(2.5066282746310005 * ser' / xx) where

Используется потом так:
exp (gammaln 20001)
Так считается 20000! Но, к сожалению, здесь Haskell прямо ответил - Infinity.

В итоге, после того, как мы опробовали кучу языков программирования, можно сделать вывод, что ни один из них изначально не подходит для решения заветной задачи - нахождения 500000!. Но раз стандартные средства не работают, время поискать нестандартное решение. И оно сразу находится - библиотека GNU MP или GMP. Кому хочется посмотреть, на что способна эта библиотека - попробуйте здесь. Также можно попробовать скачать и установить - даже без тонкой настройки всё равно получаем очень неплохие результаты.
Ну, и финальный аккорд - нахождение искомого 500000! при помощи GNU MP:

The result of executing 500000! is:

computation took 1418 ms
result is about 2632341 digits, not printing it


Итоговый результат: хотите посчитать очень большой факториал? Используйте GNU MP![UPD](который и используется в Хаскеле(?) )[/UPD]

[UPD]
Спасибо lionet, который заметил чушь, которую я назвал хвостовой рекурсией раньше, чем я ее исправил. Также спасибо yorool-gui за развитие Хаскелевского варианта. Я не буду исправлять текущий код - вы можете посмотреть на более оптимальные варианты решения задачи здесь.
[/UPD][UPD]
Кстати, в GMP используется функция mpz_fac_ui для того, чтобы подсчитать факториал. Т.е., это отдельная функция. И именно она даёт такие хорошие результаты. Тогда становится понятным, почему Haskell c GMP не даёт таких результатов, как просто использование данной функции.[/UPD]