Множества и словари

Внимание: подробный рассказ про хеш-функции и хеш-таблицы см. в записях предыдущих лет.

Множества и hash()

Множества

Множества в Python реализованы как хеш-таблицы:

Элементы множества неупорядочены (в действительности, почти упорядочены по хешам, с учётом перехеширования и масштабирования):

   1 >>> s = {str(i) for i in range(10,30)}
   2 >>> s
   3 {'18', '19', '25', '29', '23', '27', '16', '11', '17', '20', '15', '28', '14', '24', '26', '13', '22', '10', '12', '21'}
   4 >>> [hash(c)%128 for c in s]
   5 [8, 10, 11, 10, 25, 32, 39, 40, 39, 64, 72, 76, 95, 100, 106, 110, 115, 122, 125, 127]
   6 

Словари

Задача: хранить произвольные объекты, каждый из которых взаимно однозначно соответствует хорошо хешируемой константе.

Использование

Словари внутри Python:

Модуль collections

Д/З

  1. Прочитать и прощёлкать
  2. EJudge: FarGalaxy 'В далёкой галактике'

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

    Input:

    35.764 -797.636 -770.320 almost
    88.213 -61.688 778.457 gene
    -322.270 -248.555 -812.730 trend
    721.262 630.355 968.287 dow
    -895.519 -970.173 97.282 non
    -561.036 -350.840 -723.149 disco
    -151.546 -900.962 -658.862 bidder
    -716.197 478.576 -695.843 hawaii
    -744.664 -173.034 -11.211 sad
    -999.968 990.467 650.551 erik
    .
    Output:

    almost erik
  3. EJudge: ThreeSquares 'Три квадрата'

    Ввести произвольную последовательность (не обязательно кортеж) натуральных чисел, не превышающих 200000. Вывести, сколько среди них различных чисел, являющихся суммой трёх квадратов натуральных чисел.

    • Пояснение. Входная последовательность должна обрабатываться так: seq = set(eval(input()))

    Input:

    3, 4, 2, 9, 1, 5, 6, 7, 8, 3, 6
    Output:

    3
  4. EJudge: DungeonMap 'Карта подземелья'

    Вводится карта проходимых в обе стороны тоннелей подземлья в виде строк, содержащих разделённые пробелом названия двух пещер, которые соединяет соответствующий тоннель. Две последние строки не содержат пробелов — это название входа в подземелье и название выхода. Вывести "YES", если из входа можно попасть в выход, и "NO" в противном случае. Пары могут повторяться или содержать одинаковые слова.

    Input:

    markers jumping
    jumping guinea
    skiing pre
    markers gauge
    skiing mpeg
    solar jackson
    skiing solar
    guinea gauge
    mpeg honor
    pre honor
    guinea gauge
    pre mpeg
    markers guinea
    markers gauge
    honor mpeg
    markers jumping
    skiing
    jumping
    Output:

    NO
  5. EJudge: AnnaTolstoy 'Анна Толстой'

    В первой строке программа вводит натуральное число N⩾3. Во всех последующих — роман Л. Н. Толстого «Анна Каренина» (именно из этого файла). Написать программу, которая составляет случайный текст длинной в N слов таким образом, чтобы любые три стоящие рядом «слова» встречались в этом же сочетании в романе.

    • «Словами» считаются:
      • любые последовательности непробельных символов (например, тире между словами)

      • Красная строка (перевод строки и четыре пробела) в начале абзаца (например, в прямой речи)
    • Все остальные непробельные символа считаются «буквами»: например слово со знаком препинания или кавычкой не равно просто слову.
    • Например, вот тут 9 слов (два тире, одна красная строка и шесть слов со знаками и без):
      • - Мы думали, с вами, - сказала она.

    • Обратите внимание на то, что текст ответа в примере не является эталонным (т. е. сравнивать с ним никто не будет), в тестах проверяется только соответствие вашего ответа условиям задачи.

    Input:

    200
    Лев Николаевич Толстой. Анна Каренина
                                                     Мне отмщение, и аз воздам
         Все счастливые семьи похожи друг на друга,  каждая  несчастливая  семья
    несчастлива по-своему.
    
    Output:

        Поняв чувства барина, Корней попросил приказчика прийти в другой она держала их наготове и, глядя в его комнате.
        - Костя будет очень рада. А то не могла иметь; и я его браню? Мне до него дело. Главные качества Степана Аркадьича, как круглый сыр, поднялся стальной бугор из-под тонкого сукна сюртука.
        - Еще слово: во всяком человеке искал отношения к земле мальчик в русском платье обгонял ее. Она катилась не совсем хорошо, - сказала Лидия Ивановна, как бы кристаллизация общества, определяющая каждому его члену определенное и предназначенное им место.
        Место это он знает народ, и часто беседовал с мужиками, что он высказал все; то, что называла той любовью. И ясность, с которою ты не уважаешь...
        - Расскажите нам что-нибудь забавное, но не смел думать об этом так легко. И она шире открыла глаза, желая этим смягчить для нее все ее слова,
        - Ах!- вскрикнул он, узнав брата, и Левин мог бы отказаться. А тебе доставляет удовольствие смотреть на небо.
        Уже пред самым отъездом приехал опоздавший Степан Аркадьич, заехав к ней, - сказал гувернер. - Я заехал еще привезть тебе денег, так как не выручить! Этот нажмет, да свое выберет. Он хрестьянина не пожалеет. А дядя Фоканыч (так