Архив рубрики: Python

Немного о часовых поясах в Python 2.7

Началось всё с того, что я столкнулся с невозможностью сравнить абсолютное и относительное время в Python. PostreSQL возвращал абсолютное, а datetime.now() относительное. Про разницу очень хорошо расписано здесь:
http://asvetlov.blogspot.ru/2011/02/date-and-time.html
Проблема оказалась лишь в том, что dateutil не в курсе последнего изменения часовых поясов. Смещения он берет из time.timezone, а оно в свою очередь возвращает -11 для моего часового пояса. Откуда он его берет пока не разобрался. Поставил pytz и tzlocal по рекомендации отсюда:
http://regebro.wordpress.com/2012/09/12/presenting-tzlocal-a-simple-way-to-get-your-local-timezone-for-pytz/

>>> from tzlocal import get_localzone

>>> from datetime import datetime

>>> print(datetime.now(get_localzone()))

2014-11-27 08:31:01.458893+10:00 

Автор: Василий Иванов
Дата публикации: 2014-11-26T14:34:00.000-08:00

Оптимизация с учетом предпочтений

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

Оптимизация распределения студентов по комнатам

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

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

# Двухместные комнаты
dorms = ['Zeus','Athena','Hercules','Bacchus','Pluto']

# Люди и два пожелания у каждого (основное, второстепенное)
prefs = [('Toby', ('Bacchus', 'Hercules')),
       ('Steve', ('Zeus', 'Pluto')),
       ('Karen', ('Athena', 'Zeus')),
       ('Sarah', ('Zeus', 'Pluto')),
       ('Dave', ('Athena', 'Bacchus')), 
       ('Jeff', ('Hercules', 'Pluto')), 
       ('Fred', ('Pluto', 'Athena')), 
       ('Suzie', ('Bacchus', 'Hercules')), 
       ('Laura', ('Bacchus', 'Hercules')), 
       ('James', ('Hercules', 'Athena'))]

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

В приведенном примере общее число вариантов порядка 100 000, то можно перебрать их все и найти оптимальный. Но если комнаты будут четырехместными, то количество вариантов будет исчислять триллионами.

Представление решения

В каждой комнате должно оказаться ровно два студента. Будем считать, что в каждой комнате есть два отсека, то есть всего их в нашем случае будет десять. Каждому студенту по очереди назначается один из незанятых отсеков; первого можно поместить в любой из десяти отсеков, второго – в любой из оставшихся девяти и т. д.
Область определения для поиска (смотри предыдущую статью):
# [9, 8, 7, 6,..., 1]
domain = [i for i in xrange(9, 0, -1)]

Целевая функция

Целевая функция работает следующим образом. Создается начальный список отсеков, и уже использованные отсеки из него удаляются. Стоимость вычисляется путем сравнения комнаты, в которую студент помещен, с двумя его пожеланиями. Стоимость не изменяется, если студенту досталась та комната, в которую он больше всего хотел поселиться; увеличивается на 1, если это второе из его пожеланий; и увеличивается на 3, если он вообще не хотел жить в этой комнате.

def dorm_cost(vec):
 cost=0

 # Создаем список отсеков, т.е. первые 2 места - 0 отсек и т.д.
 slots = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]

 # Цикл по студентам, i - порядковый номер студента
 for i in xrange(len(vec)):
  x = int(vec[i])
  dorm = dorms[slots[x]]
  pref = prefs[i][1]
  print x, '->', slots[x],'->', prefs[i][0], pref, '->', dorm

  # Стоимость основного пожелания равна 0, альтернативного – 1
  # Если комната не входит в список пожеланий, стоимость увеличивается на 3
  if pref[0] == dorm: cost += 0
  elif pref[1] == dorm: cost += 1
  else: cost += 3

  # Удалить выбранны
й отсек
  # Это самое важное действие тут,
  # прошу особо обратить на него внимание и учесть, что элементы сдвигаются
  del slots[x]

 return cost

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

Оптимизация

Всем кто не изучил методы оптимизации в предыдущей статье, бегом изучать!) Хорошим мальчикам и может даже девочкам, импортировать любой из методов и запустить!) Я, для примера, попробую на генетическом алгоритме.

result, score = genetic_optimize(domain, dorm_cost)
print result, score
Например у меня, нашелся такой результат [7, 1, 2, 0, 0, 1, 2, 1, 0] 1, что соответствует следующему выводу:

7 -> 3 -> Toby (‘Bacchus’, ‘Hercules’) -> Bacchus
1 -> 0 -> Steve (‘Zeus’, ‘Pluto’) -> Zeus
2 -> 1 -> Karen (‘Athena’, ‘Zeus’) -> Athena
0 -> 0 -> Sarah (‘Zeus’, ‘Pluto’) -> Zeus
0 -> 1 -> Dave (‘Athena’, ‘Bacchus’) -> Athena
1 -> 2 -> Jeff (‘Hercules’, ‘Pluto’) -> Hercules
2 -> 4 -> Fred (‘Pluto’, ‘Athena’) -> Pluto
1 -> 3 -> Suzie (‘Bacchus’, ‘Hercules’) -> Bacchus
0 -> 2 -> Laura (‘Bacchus’, ‘Hercules’) -> Hercules

Т.е. не устроило только Lauru и то, учтен был ее 2й вариант)

Вместо вывода

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

Автор: Pavel Petropavlov

Задачи оптимизации

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

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

Мы же, для примера, возьмем классическую задачу группового путешествия!)

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

Формат данных

Планирование путешествия группы людей (в данном примере семейства Сидоровых), которые, отправляясь из разных мест, должны прибыть в одно и то же место.

Члены семьи живут в разных концах страны и хотят встретиться в Урюпинске. Все они должны вылететь в один день и в один день улететь и при этом в целях экономии хотели бы уехать из аэропорта и приехать в него на одной арендованной машине. Ежедневно, в славный город Урюпинск, из мест проживания любого члена семьи отправляются десятки рейсов, все в разное время. Цена билета и время в пути для каждого рейса разные. 

Начнем со списка самих Сидоровых:

peoples = [('Seymour','BOS'),
    ('Franny','DAL'),
    ('Zooey','CAK'),
    ('Walt','MIA'),
    ('Buddy','ORD'),
    ('Les','OMA')]

# место назначения
destination = 'LGA'

# словарь рейсов
flights = {('LGA', 'CAK'): [('6:58', '9:01', 238), ('8:19', '11:16', 122), ('9:58', '12:56', 249), ('10:32', '13:16', 139), ('12:01', '13:41', 267), ('13:37', '15:33', 142), ('15:50', '18:45', 243), ('16:33', '18:15', 253), ('18:17', '21:04', 259), ('19:46', '21:45', 214)], ('DAL', 'LGA'): [('6:12', '10:22', 230), ('7:53', '11:37', 433), ('9:08', '12:12', 364), ('10:30', '14:57', 290), ('12:19', '15:25', 342), ('13:54', '18:02', 294), ('15:44', '18:55', 382), ('16:52', '20:48', 448), ('18:26', '21:29', 464), ('20:07', '23:27', 473)], ('LGA', 'BOS'): [('6:39', '8:09', 86), ('8:23', '10:28', 149), ('9:58', '11:18', 130), ('10:33', '12:03', 74), ('12:08', '14:05', 142), ('13:39', '15:30', 74), ('15:25', '16:58', 62), ('17:03', '18:03', 103), ('18:24', '20:49', 124), ('19:58', '21:23', 142)], ('LGA', 'MIA'): [('6:33', '9:14', 172), ('8:23', '11:07', 143), ('9:25', '12:46', 295), ('11:08', '14:38', 262), ('12:37', '15:05', 170), ('14:08', '16:09', 232), ('15:23', '18:49', 150), ('16:50', '19:26', 304), ('18:07', '21:30', 355), ('20:27', '23:42', 169)], ('LGA', 'OMA'): [('6:19', '8:13', 239), ('8:04', '10:59', 136), ('9:31', '11:43', 210), ('11:07', '13:24', 171), ('12:31', '14:02', 234), ('14:05', '15:47', 226), ('15:07', '17:21', 129), ('16:35', '18:56', 144), ('18:25', '20:34', 205), ('20:05', '21:44', 172)], ('OMA', 'LGA'): [('6:11', '8:31', 249), ('7:39', '10:24', 219), ('9:15', '12:03', 99), ('11:08', '13:07', 175), ('12:18', '14:56', 172), ('13:37', '15:08', 250), ('15:03', '16:42', 135), ('16:51', '19:09', 147), ('18:12', '20:17', 242), ('20:05', '22:06', 261)], ('CAK', 'LGA'): [('6:08', '8:06', 224), ('8:27', '10:45', 139), ('9:15', '12:14', 247), ('10:53', '13:36', 189), ('12:08', '14:59', 149), ('13:40', '15:38', 137), ('15:23', '17:25', 232), ('17:08', '19:08', 262), ('18:35', '20:28', 204), ('20:30', '23:11', 114)], ('LGA', 'DAL'): [('6:09', '9:49', 414), ('7:57', '11:15', 347), ('9:49', '13:51', 229), ('10:51', '14:16', 256), ('12:20', '16:34', 500), ('14:20', '17:32', 332), ('15:49', '20:10', 497), ('17:14', '20:59', 277), ('18:44', '22:42', 351), ('19:57', '23:15', 512)], ('LGA', 'ORD'): [('6:03', '8:43', 219), ('7:50', '10:08', 164), ('9:11', '10:42', 172), ('10:33', '13:11', 132), ('12:08', '14:47', 231), ('14:19', '17:09', 190), ('15:04', '17:23', 189), ('17:06', '20:00', 95), ('18:33', '20:22', 143), ('19:32', '21:25', 160)], ('ORD', 'LGA'): [('6:05', '8:32', 174), ('8:25', '10:34', 157), ('9:42', '11:32', 169), ('11:01', '12:39', 260), ('12:44', '14:17', 134), ('14:22', '16:32', 126), ('15:58', '18:40', 173), ('16:43', '19:00', 246), ('18:48', '21:45', 246), ('19:50', '22:24', 269)], ('MIA', 'LGA'): [('6:25', '9:30', 335), ('7:34', '9:40', 324), ('9:15', '12:29', 225), ('11:28', '14:40', 248), ('12:05', '15:30', 330), ('14:01', '17:24', 338), ('15:34', '18:11', 326), ('17:07', '20:04', 291), ('18:23', '21:35', 134), ('19:53', '22:21', 173)], ('BOS', 'LGA'): [('6:17', '8:26', 89), ('8:04', '10:11', 95), ('9:45', '11:50', 172), ('11:16', '13:29', 83), ('12:34', '15:02', 109), ('13:40', '15:37', 138), ('15:27', '17:18', 151), ('17:11', '18:30', 108), ('18:34', '19:36', 136), ('20:17', '22:22', 102)]}

Словарь
рейсов имеет следующий формат: {(‘LGA’, ‘CAK’): [(‘6:58’, ‘9:01’, 238), (‘8:19′, ’11:16’, 122),….], …..} — (аэропорт вылета, прилета), как ключ и (время вылета, время прилета, стоимость), как значение. Заполните его произвольным способом, можно поискать на сайтах авиа и заполнить реальной ситуацией))

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

Например, в решении, представленном списком [1,4,3,2,7,3,6,3,2,4,5,3]
Сеймур (Seymour) летит первым рейсом из Бостона в Нью-Йорк и четвертым рейсом из Нью-Йорка в Бостон, а Фрэнни (Franny) – третьим рейсом из Далласа в Нью-Йорк и вторым обратно.

Целевая функция

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

Рассмотрим несколько параметров, которые можно измерить в примере с групповым путешествием:
  • Цена

Полная стоимость всех билетов или, возможно, среднее значение, взвешенное с учетом финансовых возможностей.

  • Время в пути

Суммарное время, проведенное всеми членами семьи в полете.

  • Время ожидания

Время, проведенное в аэропорту в ожидании прибытия остальных членов группы.

  • Время вылета

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

  • Время аренды автомобилей

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

Определившись с тем, какие переменные влияют на стоимость, нужно решить, как из них составить одно число. В нашем случае можно, например, выразить в деньгах время в пути или время ожидания в аэропорту. Скажем, каждая минута в воздухе эквивалентна $1 (иначе гово- ря, можно потратить лишние $90 на прямой рейс, экономящий полтора часа), а каждая минута ожидания в аэропорту эквивалентна $0,50. Можно было бы также приплюсовать стоимость лишнего дня аренды машины, если для всех имеет смысл вернуться в аэропорт к более поз- днему часу.

Определенная ниже, целевая функция shedule_cost принимает во внимание полную стоимость поездки и общее время ожидания в аэропорту всеми членами семьи. Кроме того, она добавляет штраф $50, если машина возвращена в более поздний час, чем арендована.

# время в минутах
def get_minutes(t):
 x=time.strptime(t,'%H:%M')
 return x[3]*60+x[4]

def schedule_cost(sol):
 totalprice = 0
 latestarrival = 0
 earliestdep = 24*60

 for d in xrange(len(sol)/2):
  # Получить список прибывающих и убывающих реисов
  origin = peoples[d][1]
  outbound = flights[(origin, destination)][int(sol[d])]
  returnf = flights[(destination, origin)][int(sol[d+1])]

  # Полная цена равна сумме цен на билет туда и обратно
  totalprice += outbound[2]
  totalprice += returnf[2]

  # Находим самыи позднии прилет и самыи раннии вылет
  if latestarrival < get_minutes(outbound[1]): latestarrival = get_minutes(outbound[1])
  if earliestdep > get_minutes(returnf[0]): earliestdep = get_minutes(returnf[0])

 # Все должны ждать в аэропорту прибытия последнего участника группы.
 # Обратно все прибывают одновременно и должны ждать свои реисы.
 totalwait = 0  
 for d in xrange(len(sol)/2):
  origin = peoples[d][1]
  outbound = flights[(origin, destination)][int(sol[d])]
  returnf = flights[(destination, origin)][int(sol[d+1])]
  totalwait += latestarrival - get_minutes(outbound[1])
  totalwait += get_minutes(returnf[0]) - earliestdep  

 # Для этого решения требуется оплачивать дополнительныи день аренды?
 # Если да, это обоидется в лишние $50!
 if latestarrival > earliestdep: totalprice += 50

 return totalprice + totalwait

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

Случайный поиск

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

Соответствующая функция принимает два параметра. Domain – это список значений, определяющих количество вариантов рейсов каждого из участников путешествия. Важно что они отсортированы в том же порядке, что и сами участники, сначала идут в Урюпинск, потом оттуда. Длина решения совпадает с длиной этого списка.

Второй параметр, costf, – это целевая функция; в нашем примере в этом качестве используется schedule_cost. Она передается в виде параметра, чтобы алгоритм можно было использовать повторно и для других задач оптимизации. Алгоритм случайным образом генерирует 1000 гипотез и для каждой вызывает функцию costf. Возвращается наилучшая гипотеза (с минимальной стоимостью).

domain = []
for people in peoples:
 domain.append(len(flights[(people[1], destination)]) - 1)
 domain.append(len(flights[(destination, people[1])]) - 1)
print domain

def random_optimize(domain, costf):
 best=999999999
 bestr=None

 for i in xrange(0, 1000):
  # Выбрать случаиное решение
  r = [random.randint(0, domain[i]) for i in xrange(len(domain))]

  # Get the cost
  cost = costf(r)

  # Сравнить со стоимостью наилучшего наиденного к этому моменту решения
  if cost < best:
   best = cost
   bestr = r
 return r, best

result, score = random_optimize(domain, schedule_cost)
print result, score
Позапускав, я получил макс хороший вариант (из 10 запусков по 1000 вариантов) 3208$, будем с ним и сравнивать)

Алгоритм спуска с горы 

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

Альтернативный метод случайного поиска называется алгоритмом спуска с горы (hill climbing). Он начинает со случайного решения и ищет лучшие решения (с меньшим значением целевой функции) по соседству. Можно провести аналогию со спуском с горы.

Представьте, что человечек на рисунке – это вы и оказались в этом месте по воле случая. Вы хотите добраться до самой низкой точки, чтобы найти воду. Для этого вы, наверное, осмотритесь и направитесь туда, где склон самый крутой. И будете двигаться в направлении наибольшей крутизны, пока не дойдете до точки, где местность становится ровной или начинается подъем.

Применим этот подход. Начнем со случайно выбранного расписания и просмотрим все расписания в его окрестности. В данном случае это означает просмотр таких расписаний, для которых один человек выбирает рейс, вылетающий чуть раньше или чуть позже. Для каждого из соседних расписаний вычисляется стоимость, и расписание с наименьшей стоимостью становится новым решением. Этот процесс повторяется и завершается, когда ни одно из соседних расписаний не дает улучшения стоимости.
def hill_climb(domain, costf):

 # Выбрать случаиное решение
 sol = [random.randint(0, domain[i]) for i in xrange(len(domain))]
 best = costf(sol)

 # Главныи цикл
 is_stop = False
 while not is_stop:
  # Создать список соседних решении
  neighbors = []
  for j in xrange(len(domain)):

   # Отходим на один шаг в каждом направлении
   if 0 < sol[j] < 9:
    neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])
    neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])

   if 0 == sol[j]:
    neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])

   if sol[j] == domain[j]:
    neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])

  # Ищем наилучшее из соседних решении

  is_stop = True
  for j in xrange(len(neighbors)):
   cost = costf(neighbors[j])
   if cost < best:
    is_stop = False
    best = cost
    sol = neighbors[j]

 return sol, best

result, score = hill_climb(domain, schedule_cost)
print result, score

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

На самом деле, в данном случае
этот мест даст так себе результаты. Хотя, в большинстве случаев, лучше чем 1000 случайных вариантов. Однако у алгоритма спуска с горы, есть один существенный недостаток.

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

Алгоритм имитации отжига

Алгоритм имитации отжига навеян физическими аналогиями. Отжигом называется процесс нагрева образца с последующим медленным охлаждением. Поскольку сначала атомы заставляют попрыгать, а затем постепенно «отпускают вожжи», то они переходят в новую низко-энергетичную конфигурацию.

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

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

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

Поскольку температура (готовность принять худшее решение) вначале очень высока, то показатель степени близок к 0, поэтому вероятность равна почти 1. По мере уменьшения температуры разность между высокой стоимостью и низкой стоимостью становится более значимой, а чем больше разность, тем ниже вероятность, поэтому алгоритм из всех худших решений будет выбирать те, что лишь немногим хуже текущего.

def annealing_optimize(domain, costf, T=10000.0, cool=0.99, step=1):
 
 # Выбрать случаиное решение
 vec = [random.randint(0, domain[i]) for i in xrange(len(domain))]

 while T > 0.1:
  # Выбрать один из индексов
  i = random.randint(0, len(domain)-1)

  # Выбрать направление изменения
  dir = random.randint(-step, step)

  # Создать новыи список, в котором одно значение изменено
  vecb = vec[:]
  vecb[i] += dir
  if vecb[i] < 0: vecb[i] = 0
  elif vecb[i] > domain[i]: vecb[i] = domain[i]

  # Вычислить текущую и новую стоимость
  ea = costf(vec)
  eb = costf(vecb)
  p = pow(math.e, (-eb-ea)/T)

  # Новое решение лучше? Если нет, метнем кости
  if (eb < ea or random.random() < p):
   vec = vecb      

  # Уменьшить температуру
  T = T * cool
 return vec, eb

result, score = annealing_optimize(domain, schedule_cost)
print result, score

На каждой итерации в качестве i случайно выбирается одна из переменных решения, а dir случайно выбирается межд

Почему я не люблю Flask

Есть такой популярный microframework: Flask.

Многим нравится: легкий и простой для изучения, то да сё.

А мне — категорически нет.

Нелюбовь началась с элементарного: request — это thread local variable:

import flask
from myapp import app

@app.route('/')
def handler():
    req = flask.request
    if 'arg' in req.args:
        process_arg(req.args['arg'])
    ###

Т.е. для для того чтобы узнать с какими GET или POST параметрами вызвали мой код — я должен обращаться к глобальной переменной!

Я знаю разницу между global variable и thread local variable если что — но это не избавляет от неприятного послевкусия.

Ага, есть еще и flask.g!

Если уж мне потребуются context local variables — я их буду использовать по моему выбору, морщась от осознания собственного несовершенства. Зачем flask их мне навязывает?

Дальше — больше.

Смотрим еще раз:

from myapp import app

@app.route('/')
def handler():
    ###

Имеем наполовину сконфигурированный импортированный откуда-то app, к которому добавляем обработчик.

Мне это не нравится. Я хочу сделать app и добавить в него route table.

Flask это позволяет, но документация провоцирует делать ровно наоборот.

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

Идем дальше.

Параметры в route:

@app.route('/user/')
def handler(username):
    pass

Весной это казалось мне удачным. Даже сделал что-то похожее в aiorest.

Потом понял, что штука абсолютно бесполезная: нам всегдатребовалось что-то из HTTP HEADERS, COOKIES и GET/POST parameres в обработчике запроста.

Чтобы проверить — авторизирован ли пользователь, например.

Выпилил.

С другой стороны проблема правильных параметров для обработчика не имеет красивого решения.

route args, GET, POST, COOKIES — каждый dict может иметь перекрывающиеся имена-названия.

Паша Коломиец в zorro попытался решить проблему через аннотации:

def handler(self, request: Request):
    pass

Т.е. handler имеет параметр с аннотацией Request — он получит в него request object.

В zorro можно регистрировать свои аннотации для получения дополнительной информации.

Симпатично и элегантно — но слишком сложно для библиотеки для чайников.

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

Заключение

Я не призываю не использовать flask, у меня нет такой цели. Хотите граблей — получайте.

Просто сейчас я занялся добавлением в aiohttp WEB-сервера, пригодного для использования простым программистом.

И я точно знаю, чего не будет в aiohttp — контекстных переменныхи зависимостей на этапе импорта.

aiohttp.web должен быть прост насколько это возможно, но не проще.

Желающие выстрелить себе в ногу пусть делают это в библиотеках, построенных на основе aiohttp.web — мы дадим им такую возможность.

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

Автор: Andrew Svetlov

Поиск и ранжирование

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

Что такое поисковая машина

Итак, давайте же создадим здоровую конкуренцию мировым поисковикам!) Статья так же будет полезна начинающим SEO специалистам, т.к. покажет некоторые величины, которые могут влиять на позиции вашего сайта в поиске.

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

Далее собранные документы необходимо проиндексировать. Обычно для этого строится большая таблица, содержащая список документов и вхождений различных слов. В зависимости от конкретного приложения сами документы могут и не храниться в базе данных; в индексе находится лишь ссылка (путь в файловой системе или URL) на их местонахождение

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

Итак, для данной задачи нам потребуется DB (PostgreSQL) и Python (библиотека Grab). А за источник индексирования, новостную ленту rambler’а.
Все функции, описаные ниже, у меня являются методами классов, с такой инициализацией:

class Indexer:

 def __init__(self):
   
  self.conn = psycopg2.connect("dbname='postgres' user='postgres' password='120789' host='localhost'")

  self.cur = self.conn.cursor()
  self.cur.execute("set search_path to 'rambler_search'")

  self.grab = Grab()

 def __del__(self):
  self.conn.close()

 def dbcommit(self):
  self.conn.commit()

Код паука

Для начала, рассмотрим код функции, которая будет забирать страницу статьи, разбивать ее на текст, вычленяя ссылки и передавать их индексирующим функциям. На вход подается список ссылок, являющихся вхождением для паука.

Эта функция в цикле обходит список страниц, вызывая для каждой функцию addtoindex. Далее она получает все ссылки на данной странице и добавляет их URL в список newpages. В конце цикла newpages присваивается pages, и процесс повторяется.

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

  
  # Начинаем со списка страниц для индексации
  # опускаемся в глубину на 2 уровня
 def crawl(self, pages, depth=2):

  rambler_news_href_pattern = re.compile(r'(^http://news.rambler.ru/[d]+)')

  for i in range(depth):
   newpages={}

   for page in pages:

    try:
      self.grab.go(page)

    except:
      print "Could not open %s" % page
      continue

    try:
      article_text = '' # текст статьи
      for paragraph in self.grab.tree.xpath("//p[contains(@class, 'b-article__paragraph')]"):
      article_text += paragraph.text_content()

      self.addtoindex(page, article_text) # записываем в базу текст статьи с индексацией

      links = self.grab.tree.xpath("//a")
      for link in links:

     if ('href' in link.attrib):
       url = urljoin(page, link.attrib['href']).split('#')[0]# делаем полную ссылку и удаляем часть за # если она есть

       match = rambler_news_href_pattern.findall(url)
       if match:
        url = match[0]

      if url[0:4] == 'http' and not self.isindexed(url):
       newpages[url] = 1

      linkText = link.text_content() # текст ссылки
      self.addlinkref(page, url, linkText) # записываем в базу текст ссылки с индексацией

      self.dbcommit()

    except Exception, e:
      print "Could not parse page %s" % page, e


   pages = newpages

Построение индекса

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

Создание схемы

Подождите запускать программу – нужно сначала подготовить базу данных. Схема простого индекса состоит из пяти таблиц. Первая (url_list) – это список проиндексированных URL. Вторая (word_list) – список слов, а третья (word_location) – список мест вхождения слов в документы. В оставшихся двух таблицах хранятся ссылки между документами. В таблице link хранятся идентификаторы двух URL, связанных ссылкой, а в таблице link_words есть два столбца – word_id и link_id – для хранения слов, составляющих ссылку. Вся схема изображена на рисунке ниже. Код запросов приводить не буду, должны ведь и вы поработать)))

Выделение слов на странице

Для решения данной задачи, воспользуемся простейшей функцией. Мы не будем вводить стоп слова, которые не нужно индексировать, а просто введем ограничение на длину слова в 3 символа, тем самым убрав предлоги и другой мусор (хоть и пострадают всякие мелкие слова, типа «мир», «тир», «пир»).
def getwords(html):
    words = []
    for split_str in html.split():
        t = re.split("[s;:-_*".,?!()'&#«»]", split_str)
        words += [a.lower() for a in t if a != '' and len(a) > 3]
    return words

Добавление в индекс

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

  
        def addtoindex(self, url, text):

  if self.isindexed(url): return # если уже индексирована - пропускаем
  print 'Indexing %s' % url

  # Получаем слова из текста
  words = getwords(text)

  # Получаем id url'а
  url_id = self.getentryid('url_list', 'url', url)

  # Связываем слова с этим урлом
  for i, word in enumerate(words): # пронумеруем слова
    word_id = self.getentryid('word_list', 'word', word)
    self.cur.execute("insert into word_location(url_id, word_id, location) values (%d, %d, %d)" % (url_id, word_id, i))
    self.dbcommit()
Хорошо, теперь нужно описать функцию getentryid — возвращающую id записи из бд и isindexed — проверяющую, не индексировали ли мы эту страницу раньше.

  
        # Узнаем id записи в БД, если нет
        # иначе записываем и возвращаем новый
 def getentryid(self, table, field, value, createnew=True):

  self.cur.execute("select id from %s where %s = '%s'" % (table, field, value))
  cur = self.cur.fetchone()

  if not cur:
   # print (table, field, value)
   self.cur.execute("insert into %s (%s) values ('%s') returning %s.id" % (table, field, value, table))
   cur = self.cur.fetchone()
   self.dbcommit()

   return cur[0]

  else:
    return cur[0]

       # Возвращаем True, если посещали страницу
 def isindexed(self, url):
  self.cur.execute("select id from url_list where url = '%s'" % url)
  u = self.cur.fetchone()

  if u:
   # Проверяем, что паук посещал страницу
   self.cur.execute("select count(1) from word_location where url_id = %d" % u[0])
   v = self.cur.fetchone()

   if v[0]:
    return True

  return False

Последняя функция, необходимая нам для начала индексирования — это addlinkref. Как следует из ее названия, она заносит ссылки и слова из которых они состоят к нам в БД.

 def addlinkref(self, urlFrom, urlTo, linkText):

  words = getwords(linkText)
  from_id = self.getentryid('url_list', 'url', urlFrom)
  to_id = self.getentryid('url_list', 'url', urlTo)

  if from_id == to_id: return

  self.cur.execute("insert into link(from_id, to_id) values (%d, %d) returning link.id" % (from_id, to_id))
  link_id = self.cur.fetchone()[0]

  for word in words:

    word_id = self.getentryid('word_list', 'word', word)
    self.cur.execute("insert into link_words(link_id, word_id) values (%d, %d)" % (link_id, word_id))

Ну что же, на этом этапе мы можем запустить паука и создать базу данных)

Запросы

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

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

 def get_match_rows(self, query):

  select_query_add = []
  join_query_add = []
  where_query_add = []

  main_search_query = """ 
     SELECT wl0.url_id, %s
     FROM word_location wl0
     %s 
     WHERE %s
    """

  query_words = getwords(query)

  query_word_ids = []
  for query_word in query_words:

   self.cur.execute("select id from word_list where word = '%s'" % query_word)
   query_word_id = self.cur.fetchone()

   if query_word_id:
    query_word_ids.append(query_word_id[0])

  if query_word_ids:
   for position, query_word_id in enumerate(query_word_ids):

    if position:
     join_query_add.append('JOIN word_location wl%d ON wl%d.url_id = wl%d.url_id' % (position, position-1, position))

    select_query_add.append('wl%d.location' % position)
    where_query_add.append('wl%d.word_id = %d' % (position, query_word_id))

   main_search_query = main_search_query % (', '.join(select_query_add), ' '.join(join_query_add), ' and '.join(where_query_add))

   self.cur.execute(main_search_query)
   search_results = self.cur.fetchall()
   
   return search_results, query_word_ids
Данная функция всего лишь создает строгий JOIN, типа такого:

 
 SELECT wl0.url_id, wl0.location, wl1.location
 FROM word_location wl0
 JOIN word_location wl1 ON wl0.url_id = wl1.url_id 
 WHERE wl0.word_id = 2734 and wl1.word_id = 2698
В результате, получаем список кортежей и список с id слов. Каждый кортеж — это сто список вида (id новости, позиция 1го слова, позиция 2го слова…)
Ранжирование по содержимому
Итак, худо-бедно, но мы научились искать по индексу. Однако возвращаем мы их в том порядке, в котором они посещались пауком. Чтобы решить эту проблему, необходимо как-то присвоить страницам ранг относительно данного запроса и уметь возвращать их в порядке убывания рангов.
В этом разделе мы рассмотрим несколько способов вычисления ранга 
на основе самого запроса и содержимого страницы, а именно:
  • Частота слов 
Количество вхождений в документ слова, указанного в запросе, помогает определить степень релевантности документа.
  • Расположение в документе 
Основная тема документа, скорее всего, раскрывается ближе к его началу.
  • Расстояние между словами 
Если в запросе несколько слов, то они должны встречаться в документе рядом.
Самые первые поисковые машины (кстати rambler.ru) часто работали только с подобными метриками и тем не менее давали пристойные результаты. Давайте добавим следующие методы:
 # Функция, которая взвешивает результаты
 def get_scored_list(self, rows, word_ids):

  total_scores = {row[0]: 0 for row in rows}

  if rows:
   # Список весовых функций
   weight_functions = [
      ]

   for (weight, scores) in weight_functions:
     for url in total_scores:
    total_scores[url] += weight * scores[url]

  return total_scores

 # Возвращает полный урл по id
 def get_url_name(self, url_id):

  self.cur.execute("select url from url_list where id = %d" % url_id)

  return self.cur.fetchone()[0]

 # Основная функция поиска
 def search(self, search_sentence):

  search_results, word_ids = self.get_match_rows(search_sentence)
  scores = self.get_scored_list(search_results, word_ids)

  ranked_scores = [(score, url) for (url, score) in scores.items()]
  ranked_scores.sort()
  ranked_scores.reverse()

  for (score, url_id) in ranked_scores[0:10]:
    print '%ft%s' % (score, self.get_url_name(url_id))

  return word_ids, [r[1] for r in ranked_scores[0:10]]
Наиболее важна здесь функция get_scored_list, код которой мы будем постепенно уточнять. По мере добавления функций ранжирования мы будем вводить их в список weight_functions  и начнем взвешивать полученные результаты.
Функция нормализации
Все рассматриваемые ниже функции ранжирования возвращают словарь, в котором ключом является идентификатор URL, а значением – числовой ранг. Иногда лучшим считается больший ранг, иногда – меньший. Чтобы сравнивать результаты, получаемые разными методами, необход

имо как-то нормализовать их, то есть привести к одному и тому же диапазону и направлению.
          Функция нормализации принимает на входе словарь идентификаторов и рангов и возвращает новый словарь, в котором идентификаторы те же самые, а ранг находится в диапазоне от 0 до 1. Ранги масштабируются по близости к наилучшему результату, которому всегда припи- сывается ранг 1. От вас требуется лишь передать функции список рангов и указать, какой ранг лучше – меньший или больший:
 def normalize_scores(self, scores, smallIsBetter=0):

  vsmall = 0.00001 # Avoid division by zero errors

  if smallIsBetter:
   minscore = min(scores.values())
   return {u: float(minscore)/max(vsmall, l) for (u,l) in scores.items()}

  else:
   maxscore = max(scores.values())
   if maxscore == 0: maxscore = vsmall
   return {u: float(c)/maxscore for (u,c) in scores.items()}

  return scores
Отлично! Пора заняться весовыми функциями, для которых мы и придумали эту нормализацию.
Весовые функции
Частота слов
Метрика, основанная на частоте слов, ранжирует страницу исходя из того, сколько раз в ней встречаются слова, упомянутые в запросе. Если я выполняю поиск по слову python, то в начале списка скорее получу страницу, где это слово встречается много раз, а не страницу о музыканте, который где-то в конце упомянул, что у него дома живет питон.
def frequency_score(self, rows):

  counts = {row[0]:0 for row in rows}
  for row in rows: 
   counts[row[0]] += 1

  return self.normalize_scores(counts)
Чтобы активировать ранжирование документов по частоте слов, измените строку функции get_scored_list, где определяется список weight_functions, следующим образом:
weight_functions = [(1.0,self.frequency_score(rows))]
Запустите поиск снова и радуйтесь!)
Расположение в документе
Еще одна простая метрика для определения релевантности страницы запросу – расположение поисковых слов на странице. Обычно, если страница релевантна поисковому слову, то это слово расположено близко к началу страницы, быть может, даже находится в заголовке.
def location_score(self, rows):

  locations = {}
  for row in rows:
   loc = sum(row[1:])
   if locations.has_key(row[0]):
    if loc < locations[row[0]]:
     locations[row[0]] = loc
   else:
    locations[row[0]] = loc

  return self.normalizescores(locations, smallIsBetter=1)
Расстояние между словами
Если запрос содержит несколько слов, то часто бывает полезно ранжировать результаты в зависимости от того, насколько близко друг к другу встречаются поисковые слова. Как правило, вводя запрос из нескольких слов, человек хочет найти документы, в которых эти слова концептуально связаны. Рассматриваемая метрика допускает изменение порядка и наличие дополнительных слов между поисковыми.
 def distance_score(self, rows):

  mindistance = {}

  # Если только 1 слово, любой документ выигрывает
  if len(rows[0]) <= 2:
   return {row[0]: 1.0 for row in rows}

  mindistance = {}

  for row in rows:
   dist = sum([abs(row[i]-row[i-1]) for i in xrange(2, len(row))])

   if mindistance.has_key(row[0]):
    if dist < mindistance[row[0]]:
     mindistance[row[0]] = dist
   else:
    mindistance[row[0]] = dist

  return self.normalize_scores(mindistance, smallIsBetter=1)
Использование внешних ссылок на сайт
Все обсуждавшиеся до сих пор метрики ранжирования были основаны на содержимом страницы. Часто результаты можно улучшить, приняв во внимание, что говорят об этой странице другие, а точнее те сайты, на которых размещена ссылка на нее. Особенно это полезно при индексировании страниц сомнительного содержания или таких, которые могли быть созданы спамерами, поскольку маловероятно, что на такие страницы есть ссылки с настоящих сайтов. 
Простой подсчет ссылок
Простейший способ работы с внешними ссылками заключается в том, чтобы подсчитать, сколько их ведет на каждую страницу, и использовать результат в качестве метрики. Так обычно оцениваются научные работы; считается, что их значимость тем выше, чем чаще их цитируют.
def inbound_link_score(self, rows):

  unique_urls = {row[0]: 1 for row in rows}
  inbound_count = {}
  
  for url_id in unique_urls:
   self.cur.execute('select count(*) from link where to_id = %d' % url_id)
   inbound_count[url_id] = self.cur.fetchone()[0]

  return self.normalize_scores(inbound_count)
Описанный алгоритм трактует все внешние ссылки одинаково, но такой уравнительный подход открывает возможность для манипулирования, поскольку кто угодно может создать несколько сайтов, указывающих на страницу, ранг которой он хочет поднять. Также возможно, что людям более интерес

pep8 и 80 символов в строке
На самом деле 79 если внимательно читать pep 8, если что…
Посетил на днях Python Party, организованной компанией Yandex. 
Мероприятие понравилось, а самый интерес был потом, на «поболталках» в кабаке.
Был на party доклад от Кирилла Борисова «Контроль за стилем кода». Интересный и толковый.
Только я возражаю против с высказывания вроде: 
  — pep8 рекомендует ограничивать длину строк в 79 символов максимум. Мы с этим несогласны — сейчас мониторы большие, можно писать 120 символов и это великолепно помещается на экране.
Я везде строго пишу с ограничением на 79 символов.
Попробую объяснить почему.
1. Во первых сам код Python так написан и patch вылезающий за границы просто не будет принят. OK, я committer — значит тем более обязан следовать соглашениям.
2. Во вторых мой редактор (emacs если что) настроен на то чтобы подсвечивать длинные строки. И когда я открываю код библиотеки, наплевавшей на ограничение по длине строки — у меня половина экрана «красная». Это огорчает.
3. В третьих и главное: если у вас широкий монитор — это прекрасная возможность разбить его по вертикали и видеть одновременно несколько редактируемых файлов. У меня даже на 14'' ноутбуке Full HD — это значит что при размере шрифта в 13pt у меня помещается два буфера. Коллега на 24'' привык работать в vim с шестью буферами: 3х2. Это очень удобно — гораздо лучше видеть сразу несколько файлов чем один, но с длинными строками.
Что до «невозможности» уместить код в 79 символов — это распространенное заблуждение.
При некотором навыке всё легко получается.
К тому же такой подход провоцирует сохранение промежуточных вычислений в локальные переменные — что хорошо само по себе, так как улучшает читабельность кода (вы же даете переменным не слишком длинные, но «говорящие» имена, верно?)
Коротко говоря, 79 символов заставляют лучше писать код и помогают его читать. Что вам всем и рекомендую.
Автор: Andrew Svetlov