Пользователь
0,3
рейтинг
3 ноября 2008 в 17:08

Разработка → Интервально-ассоциативный массив

Замечательная вещь — ассоциативный массив. Самые разные задачи решаются с его помощью легко, приятно и быстро. А как быть когда значение должно принадлежать не одному ключу, а быть «размазанным» на некоторый интервал?
Представьте, что вам нужно сделать программу для составления расписания дежурства менеджеров интернет-магазина. Работа с ним должна была максимально простой, примерно так:
# легко назначить
>>> timetable['08:00' : '12:00'] = 'Иванов'
>>> timetable['12:00' : '16:00'] = 'Петров'

# как узнать кто дежурил в 13:51 ?
>>> print timetable['13:51']
Петров

# легко просмотреть поэлементо полный список
>>> for interval, person in timetable.items(): print interval, person
('08:00', '12:00') Иванов
('12:00', '16:00') Петров

# ...или одной строкой
>>> print timetable
{['08:00', '12:00'] => 'Иванов', ['12:00', '16:00'] => 'Петров'}



# удаление как по частям
>>> del timetable['15:00' : '16:00']
>>> print timetable
{['08:00', '12:00'] => 'Иванов', ['12:00', '15:00'] => 'Петров'}

# ...так и целиком
>>> del timetable['12:00' : '16:00']
>>> print timetable
{['08:00', '12:00'] => 'Иванов'}

# перекрывание ключей должно обрабатываться корректно
>>> timetable['11:00' : '15:00'] = 'Сидоров'
>>> print timetable
{['08:00', '11:00'] => 'Иванов', ['11:00', '15:00'] => 'Сидоров'}

# соседние ключи с одинаковыми значениями должны склеиваться автоматически,
# например, если вы назначили Сидорову подежурить так же с 15 до 17,
# то наврядли это должно быть две смены подряд, скорее одна более длинная
>>> timetable['15:00' : '17:00'] = 'Сидоров'
>>> print timetable
{['08:00', '11:00'] => 'Иванов', ['11:00', '17:00'] => 'Сидоров'}

# добавим пару записей
>>> timetable['17:00' : '20:00'] = 'Петров'
>>> timetable['21:00' : '23:00'] = 'Сидоров'
>>> timetable
{['08:00', '11:00'] => 'Иванов', ['11:00', '17:00'] => 'Сидоров',
['17:00', '20:00'] => 'Петров', ['21:00', '23:00'] => 'Сидоров'}

# часто возникает задача урезать расписание, оставив из нескольких идущих подряд элементов,
# только последние. Например, нужно узнать кто закрывал рабочий день.
>>> timetable.shrink()
>>> print timetable
{['08:00', '20:00'] => 'Петров', ['21:00', '23:00'] => 'Сидоров'}


# этот же метод можно использовать для проверки
# полностью ли ваше расписание охватывает рабочий день.


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

Кому нужно — смело берите. Любые комметарии, вопросы, багрепорты приветствуются. Если есть идеи по развитию — пишите!

UPD: К сожалению, после Visual Code Highlighter-a и Хабрапарсера, форматирование кода основательно испортилось, поэтому я его убираю отсюда и выкладываю на гугль: code.google.com/p/intervalmap/source/browse/trunk/intervalmap.py
Евгений Лисицкий @el777
карма
230,5
рейтинг 0,3
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (80)

  • НЛО прилетело и опубликовало эту надпись здесь
    • +7
      Всегда пожалуйста. На следующей неделе хочу еще одну мелкую заметку про питон опубликовать.
      • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    хорошая статья
  • 0
    не имею дело непосредственно с Python, но идея отличная :) плюс
  • +1
    • 0
      Полезная ссылка :)
      Да уж код вышел весьма некрасивый после Source Code Highlighter-а. Жаль, что он не поддерживает питон корректно. Все остальные подсвечивалки, которые я нашел, используют CSS, который, как понимаю, хабрапарсер не пропустит по соображениям безопасности. Можете порекомендовать хороший онлайн-хайлайтер с поддержкой python на чистом html?
      • 0
        Именно онлайн?
        Хотя и их есть :) — тот же pygments, который используется на приведённой ссылке с сорцами. Где-то у них на сайте есть ссылка на онлайн-демо с возможностью получить html или rtf.
        • 0
          Пигменты смотрел, но там опять на стилях.
          • 0
            а если так:
            pygmentize.py -O style=native,encoding=utf-8,full=true,outencoding=cp1251,noclasses=true -o manage.py.html manage.py


            … попробовал. стили и из тэгов вырезаются…

            тогда — после этого простенький regexp натравить для замены стиля из span на <font folor="">, <i>, <b>?
            • 0
              Ну конечно все это можно, но точно так же можно раскрасить в ворде :)
              Поэтому хочется какой-то максимально простой инструмент. Чтобы закинул и получил результат.
      • +1
        нихрена се «полезная»…

        «пеп-восемь» наизусть вообще каждый разработчик должен знать =).
        • 0
          :)
          Оформлено-то оно нормально, проблема в другом — взрывоопасная сместь Source Code Highliter + HabraParser взорвали код, особенно 8-ю строку.
          Поэтому я убираю отсюда код и переношу все на гугл:
          code.google.com/p/intervalmap/source/browse/trunk/intervalmap.py
          • 0
            не…

            там строки есть по 100+ символов. в тесте так вообще больше 200 =). Название всего класса спорное. Assert лучше не использовать — ведь при -OO у вас все перестанет работать =) Там где пользовательские каяки проверяются — эксепшн простой нужен. Докстринги не по пеп-8. Pylint вообще переплевался весь)

            До кучи — на 2.4 не работает, а об этом ни слова нет. Ко всему прочему — это изза «else» в try — только и всего.

            Паблик вещи надо ж очень хорошо прилизывать…

            • 0
              А какое название предложили бы вы? Если будет лучше, интуитивнее, то давайте переимунуем.
              Мне assert-ы в тексте тоже не очень понравились, надо будет отрефакторить.

              На 2.4 не тестировал, работаю с 2.5, но даже странно, что не работает — т.к. основная часть кода была написана 2 года назад.
              • 0
                название? класс же — ТакойДолженБыть =).
                • 0
                  Если бы вы смогли подключиться, то было бы просто замечательно! :)
                  • 0
                    кууда?
                    • 0
                      К разработке.
                      МОжно непосредственно — сделаем svn-доступ на гуглокод, либо идейно.
  • –1
    Интересно, большое спасибо!
    • 0
      Дожились… дорогой минусующий, ты бы хоть не позорился :)
      • 0
        пардон?
        не очень вас понял
  • +1
    Спасибо, только что за взрыв на 8-й строке?
    • 0
      Visual Code Highligher + HabraParser :)
      Можно посмотреть в нормальном виде здесь: paste.pocoo.org/show/90012/
  • –1
    неплохо бы комменты выравнять, а то проблемы при выполнении тестов
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Как вы заметили, я не претендую на открытие Америки :)
      Я описал принцип использования интервального хеша. Пример добавлен для большей наглядности — на самом деле я решал совсем другую задачу :)
      Здесь реализованы базовые вещи, и само собой, всегда есть, что можно добавить.

      Реализовать поиск по фамилии не сложно: нужно сделать поиск по массиву _items и взять соответствующее значение из _bounds. С русскими буквами работало бы без проблем:
      >>> ['аб', 'вг'].index('вг')
      1

      Поиск без учета регистра: самое простое — последовательное сравнение с .upper(). Конечно, для больших списков это неэффективно, но это уже другая задача.
      • НЛО прилетело и опубликовало эту надпись здесь
        • +2
          А в чем проблема? Если с самого начала использовать юникод, тогда все обработается корректно:
          >>> print u'Вася Пупкин'.upper()
          ВАСЯ ПУПКИН
          
          $ python -V
          Python 2.5.2
          

        • +1
          А что там не так с русскими буквами?

          Python 2.5.2
          >>> print u«час».upper()
          ЧАС
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              print unicode(a).upper()

              Так что, все таки работает «upper с русскими буквами и utf-8»? :)
              • НЛО прилетело и опубликовало эту надпись здесь
                • 0
                  Потерпи еще немножко :)

                  P.S. Кстати, расскажи, что еще ты ждешь от 3-го питона, кроме кодировок?
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • 0
                      питон должен быть горд, что в арсенале его разработчиков присутсвуют дети +))
                  • 0
                    Что-то из него я уже использую :)
                    Например, модуль processing для управления процессами как потоками. С 3-ей версии он будет числе базовых.
            • 0
              Вопрос: что возвращает raw_input в такой ситуации?
              >>> a=raw_input()
              абв
              >>> a
              '\xd0\xb0\xd0\xb1\xd0\xb2'

              a — это не строка, это какое-то фуфло напоминающее utf-8. Вернее, по последовательности байтов это и есть «абв» в utf-8, но питон-то об этом не знает. Еще больше с толку сбивает, что на печати вы видите то, что ожидаете:
              >>> print a
              абв

              Но только питон не знает, что это строка в utf-8. Поэтому он ее обрабатывает некорректно. Это то же самое, что пытаться вывести int как последовательность байтов — выйдет не совсем то, что ожидалось.
              Поэтому эту строку нужно сконвертировать в unicode:
              >>> a8 = unicode(a, 'utf-8')
              >>> a8
              u'\u0430\u0431\u0432'

              Можете проверить: с точки зрения байтов это одно и тоже, только теперь питон правильно воспринимает эту строку.
              >>> print a8.upper()
              АБВ
              >>> print a.upper()
              абв


              • НЛО прилетело и опубликовало эту надпись здесь
                • 0
                  Я ждал этот вопрос :)
                  На самом деле в консоли, просто чтобы не грузить и не отвлекать людей на несущественные детали, я подправил вывод.

                  Если нужно чтобы в консоли строки не экранировались, можно переопределить представление строки:
                  >>> class Str(str):
                  ...   def __repr__(self):
                  ...     return "'" + self +  "'" 
                  ...
                  >>>
                  >>> s=Str("фбв")
                  >>> s
                  'фбв'

                  Впрочем это довольно коряво и кроме как «пощупать» в консоли лучше нигде не использовать.

                  • НЛО прилетело и опубликовало эту надпись здесь
                    • 0
                      Здесь самое главное — внимательно проследить путь объектов, с которыми вы имеете дело. Нужно убедиться, что везде используются unicode-объекты, а не строки с псевдо-unicode содержимым, про которые я писал чуть выше. Если их просто печатать, но их легко спутать по содержимому. Используйте проверку типа вместе с содержимым:

                      >>> type(u'абв')
                      <type 'unicode'>
                      >>> type('абв')
                      <type 'str'>


                      Давайте рассмотрим «чистый» пример.
                      >>> import re
                      >>> reg = re.compile(u'АБВ')

                      >>> print reg.match(u'АБВ')
                      <_sre.SRE_Match object at 0xb7df0218>

                      >>> print reg.match(u'абв')
                      None
                      # вроде бы работает, но на самом деле - нет.
                      # получается примерно та же проблема как с цепочкой байт

                      >>> reg = re.compile(u'АБВ', re.IGNORECASE)
                      >>> print reg.match(u'АБВ')
                      <_sre.SRE_Match object at 0xb7df01e0>

                      >>> print reg.match(u'абв')
                      None

                      # Дело в том, что нужно везде указать, что вы используете unicode-объекты:
                      >>> reg = re.compile(u'АБВ', re.UNICODE | re.IGNORECASE)

                      >>> print reg.match(u'абв')
                      <_sre.SRE_Match object at 0xb7df0250>

                      >>> print reg.match(u'АБВ')
                      <_sre.SRE_Match object at 0xb7df0250>

                      * This source code was highlighted with Source Code Highlighter.
                      • НЛО прилетело и опубликовало эту надпись здесь
                        • 0
                          :)
                      • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              А откуда python узнает, что в переменной a — юникод строка? Или, может, в культуре запускающего программу нет понятия букв в верхнем регистре — он использует только нижний регистр, или, наоборот только ВЕРХНИЙ? разве в питоне нет возможности обрабатывать вводимые строки в соответствии с явно прописанной локалью пользователя или программиста (что-то типа setlocale)?

              К примеру, несмотря на юникод, в какой-то из культур (то ли шведской, то ли норвежской) принятый порядок лексикографического сравнения латинских букв с диакритическими знаками отличается от общепринятого в остальных странах Европы и попытка лексикографической сортировки «по умолчанию» у таких пользователей пройдёт не так, как они хотят.

              Интернационализация — слишком сложная вещь, что бы её можно было решить заменой литералов вида u'юникод' на 'юникод'…
              • 0
                > А откуда python узнает, что в переменной a — юникод строка?
                Вы ему об этом сообщите, создав именно unicode объект, а не обычную строку str.
                > Интернационализация — слишком сложная вещь, что бы её можно было решить заменой литералов вида u'юникод' на 'юникод'…
                Никто не спорит. Только в комментариях я говорил не про локали, а про корректную работу с юникодом.
                А поддержка локалей, это отдельная тема: www.python.org/doc/2.5.2/lib/module-locale.html
                • 0
                  Собственно, я и сообщал автору исходника, что комп не знает, что в raw_input вводится юникод. Пример, как надо работать с вводом (хотя там сложнее немного):

                  x@y:~$ echo $LANG
                  ru_RU.UTF-8
                  x@y:~$ python
                  Python 2.5.2 (r252:60911, May 7 2008, 15:19:09)
                  >>> print raw_input( 'превед ' ).upper()
                  превед медвед
                  медвед
                  # ^-- python не телепат
                  >>> import locale
                  >>> print raw_input( 'превед ' ).decode(locale.getdefaultlocale()[1]).upper()
                  превед медвед
                  МЕДВЕД
                  # ^-- как надо было
                  • 0
                    Ну да, строку байт надо превратить в юникодную строчку, тогда все заработает.
                    С другой стороны, хорошо бы чтобы это делалось автоматом после ввода. Тем более все данные есть.
                    Пусть будет метод advanced_raw_input, который все и обработает. Я так понимаю, примерно этого хочет товарищ.
                    • 0
                      А если на системе кривая локаль, а приложение должно работать?.. Я, если честно, вышеприведённый мной пример сначала попробовал на cygwin — там ничего не заработало, т.к. там криво реализованы POSIX-локали. В Перле автоматический ввод/вывод в юникоде реализуется с помощью переменной окружения PERL_UNICODE, но это тоже не универсально, т.к. там много пограничных случаев. В частности, только автор может решить в какой кодировке ему работать с нестандартными потоками ввода/вывода (они ведь могут вообще быть бинарными).
                      • 0
                        > В частности, только автор может решить в какой кодировке ему работать с нестандартными потоками ввода/вывода (они ведь могут вообще быть бинарными).
                        Я считаю, что это в большей степени зависит от самих потоков, чем от автора программы.
                        А вот ввод и вывод через стандартные потоки (которые даже называются stdin, stdout, stderr) должен быть максимально стандартным на всех платформах. Собственно ради этого и придуман POSIX.
                        Если в системе локаль кривая, то надо брать админа за гопy и заставлять настраивать. Увы, пока такое встречается, но, надеюсь, что скоро уйдет в прошлое.
                        • 0
                          Через потоки POSIX передаются не только текстовые, но и бинарные данные. Так что я согласен с доводом максимальной стандартности, но при этом надо чётко отрецензировать большое количество библиотек, многие из которых, особенно на win32 уже не поддерживаются и даже не имеют исходников. Это — малореально…

                          Ибо тогда, к примеру, возникает вопрос: а что делать по умолчанию с потоками, где встречаются utf-суррогаты и отсутствующие символы (например, дуализм unicode 0x0 и java 0x0). Это нетривиально, поэтому в Перле в конце концов (5.8.x) остановились на варианте максимальной совместимости со старым кодом (не придумывать ничего за программиста). Вставить же в начале программы прагмы (слои) потоков (PerlIO layers) — способен программист любого уровня (но с этим постоянные проблемы, т.к. люди просто не понимают разницу между семантикой данных и сериализацией этих данных).

                          P.S. Прежде чем делать стандартизованный ввод/вывод, надо хотя бы от последнего американского программиста добиться замены char * на unsigned char*, а ещё лучше — на безопасные unicode-контейнеры.

                          P.P.S. проверил на Asus wl700ge (optware) — там raw_input вообще не запрашивает ввод. ;-) А вы говорите, админа… Понятно, что в linux, freebsd (и macosx) всё нормально с локалями, но этими системами хосты не ограничиваются. Поэтому о стандартизации ввода/вывода можно будет говорить не ранее, как отрапортуют об успешном решении «проблемы 2038K» :)
                          • 0
                            Да, есть такая проблема: очень много старого кода написано из рассчета на ascii, latin-1 или даже на 7-bit кодировку.
                            Поэтому пока не произойдет перенос всего на юникод, будут проблемы «переходного возраста». Поэтому в питоне сейчас есть два типа строк — 8-битные и юникодные. Так же есть два типа классов: старые и новые. Представляю, сколько проблем совместимости пришлось решить ребятам, чтобы хотя бы это работало нормально.
                            Что делать с конкретными потоками — трудно сказать, видимо придется каждый раз делать что-то привязанное к задаче.

                            Какая система на асустике? И какой питон? Может он вообще встроенный?
                            • 0
                              Верно. Я в связи с этим избегаю вообще использовать понятия строк таких-то, строк сяких-то. Есть два типа объекта: вектор/массив байтов и вектор символов (собственно, строка). Они просто имеют похожий интерфейс.

                              Кстати, проблем не так много, если рассматривать данные сущности, как полиморфные классы с похожим интерфейсом.

                              Asus — Asus 1.0.7.8-kc + optware oleg/cross
                              • 0
                                Я стараюсь все делать в юникоде. Хотя с выводом этого добра на консоль в свое время намучался.

                                Интерфейс общий, а внутри различия могут быть очень серьезные.

                                На базе чего эта сделана эта система — linux?
                                • 0
                                  Главное не ставить обработку юникода в библиотеки (кроме application-specific модулей).

                                  Различия непринципиальны, если помнить всегда, что на выходе любых методов получается всегда такой же объект. А вот в случае операторов (во всяком случае, в перле), это не так. В перле обычно, в результате оператора, с одной из сторон которого стоит символьные строки, получаются символьные строки с неявным преобразованием байтовых в символьные.

                                  $ uname -a
                                  Linux WL700gE 2.4.20 #44 Sat Jan 26 20:07:26 EST 2008 mips unknown

                                  Плюс в стандартной прошивке: uClibc, busybox. Плюс optware-порты под эту платформу. В общем, кривизна на кривизне, если говорить про архитектуру — содержимое / менять очень геморройно.
                                  • 0
                                    Либо везде проверять тип, либо ждать выхода 3000.
                                    на мой взгляд работать с последовательностью байт без вникания что это такое, не есть гуд. Если результат и получится правильный, то только случайно. Вот примерно как с регулярными выражениями выше.
        • 0
          ну и для кучи:
          Python 2.6
          >>> print u«час».upper()
          ЧАС
    • 0
      У меня самый большой вопрос сейчас вызывает копирование объектов.
      Как быть уверенным, что при любом содержании хеша, объект будет скопирован корректно?
      Использовать deepcopy? Это вроде как из пушки по воробьям. Можете что-нибудь порекомендовать?
  • +1
    Это очень круто. Всё больше и больше скатываюсь в Питон…
    • +4
      Да, Питон это уникальное сочетание мощи, красоты и удобства работы.
      Так что не согласен насчет «скатываюсь» — скорее «поднимаюсь» :~)
      • 0
        Ну, это как скатываюсь в Темную Сторону Силы :)
  • +1
    Интересно и красиво выглядит, решая на PHP подобную задачу заставил бы базу делать эти операции.
    • 0
      Можно и с базой. Мое текущее решение задачи активно использует базу, но в моей ситуации это не эффективно: объем хранимых данных небольшой, а запросов получается много. Эта разработка как раз для снижения нагрузки.

      Кроме того, думаю будет не так просто обрабатывать пересечения интервалов. Ведь здесь возможны самые разные случаи:
      — нет пересечения — все просто, оставляем как есть
      — полное пересечение — стираем перекрытый ключ
      — частичное перекрытие — нужно сократить старый ключ, или же наборот удлинить при равенстве значений
      — фрагментация — из одного старого ключа получается два
      — комбинация выше перечисленных случаев.
      Если это все обрабатывать, то в базе придется держать довольно сложную логику.
      • 0
        Недавно сталкивался с пересечениями временных отрезков, запрос конечно получается большой, с BETWEEN'ами и IF'ами, но рабочий. Конечно зависит от задачи и необходимой скорости.
        • 0
          Само собой, что все выходит из постановки задачи.
          Я описал случай непересекающихся отрезков, причем задача поддержания этого ограничения возложена на сам класс.
  • +2
    Сделал field для Django с такой функциональностью. Авось пригодится.
    • 0
      Класс!
      А в каком виде оно будет записываться в базу?
      • 0
        {[1:2] => 3, [2:4] => ...}, текстом. Не лучший вариант — при чтении оно вообще через eval гоняется, но это надо еще подумать, как хорошо сделать.
        • 0
          Eval? Но пока нормальный конструктор не написан. Чтобы можно было вызывать примерно так:

          tt = intervalmap( slice('08:00', '12:00'), 'Иванов')
          

          Надо будет придумать наиболее удобный синтаксис создания.
          • 0
            Вот сегодня и займусь :)
            • 0
              :)
              Да синтаксис-то ладно, это полировка.
              Я вот над работоспособностью самой штуки думаю.
              Я выложил ее на гугль — code.google.com/p/intervalmap/source/browse/trunk/intervalmap.py
              Предлагаю ядро этой штуки разрабатывать отдельно, а прикладные вещи тоже отдельно. Тогда мы получил гораздо большую гибкость.
              • 0
                code.google.com/p/django-interval-field/source/browse/trunk/interval.py
                Возьмите тогда отсюда еще __eq__ — строка 148 :)
                • 0
                  Отлично. Спасибо! :)
                  Меня смущает такой момент: как сделать качественное копирование объектов — чтобы независимо от того, что у нас в массиве и верхнем элементе, они честно и полностью скопировались. У вас есть какие-нибудь идеи на этот счет?
                  • 0
                    пока нет :(
  • 0
    • 0
      Интересная вещь.
      Но у нас есть одно серьезное упрощение: интервалы не пересекаются. Иначе сама идея хеша как однозначного сопоставления значения ключу перестает работать.
      Что касается производительности, то ожидается, что bisect работает со скоростью порядка O(log2(N)).
      Правда, другие операции существенно медленнее — порядка O(N).
  • 0
    А кто-нибудь знает, есть ли что-нибудь на подобие топика в Ruby?(только не бейте)
    ассоциативные массивы — это волшебно)
    • 0
      Не встречал. Пока мне только в питоне попалась такая вещь.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.