Одна простенькая задачка. Быстро, красиво или чисто?

    Я полагаю, что 99% Python разработчиков решали так или иначе эту задачу, поскольку она входит в стандартный набор задач, предлагаемый им для соискателей должности Python Developer'а в одной широко известной компании.

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

    Ниже любопытства ради я привел список проанализированных мной решений

    Для оценки правильности кода я набросал простенький юниттест.

    Вариант 1

    import unittest
    
    
    def dict_from_keys(keys, values):
        res = dict()
        for num, key in enumerate(keys):
            try:
                res[key] = values[num]
            except IndexError:
                res[key] = None
    
        return res
    
    
    class DictFromKeysTestCase(unittest.TestCase):
        def test_dict_from_keys_more_keys(self):
            keys = range(1000)
            values = range(900)
            for _ in range(10 ** 5):
                result = dict_from_keys(keys, values)
            self.assertEqual(keys,result.keys())
    
        def test_dict_from_keys_more_values(self):
            keys =range(900)
            values = range(1000)
            for _ in range(10 ** 5):
                result = dict_from_keys(keys, values)
            self.assertEqual(keys, result.keys())
    

    Здесь я привел первое найденное мной решение. Запускаем юниттест:

    random1st@MacBook-Pro ~/P/untitled> python -m unittest dict_from_keys
    ..
    ----------------------------------------------------------------------
    Ran 2 tests in 26.118s
    
    OK

    Какой первый момент я отметил сходу? Использование dict() — это вызов функции, в то время как использование {} — синтаксическая конструкция. Заменим инициализацию словаря:

    random1st@MacBook-Pro ~/P/untitled> python -m unittest dict_from_keys
    ..
    ----------------------------------------------------------------------
    Ran 2 tests in 25.828s
    
    OK

    Мелочь, а приятно. Хотя можно списать и на погрешность. От следующего варианта я плакал кровью, но все же приведу его здесь:

    Вариант 2

    def dict_from_keys(keys, values):
        res = {}
        it = iter(values)
        nullValue = False
        for key in keys:
            try:
                res[key] = it.next() if not nullValue else None
            except StopIteration:
                nullValue = True
                res[key] = None
        return res
    

    Результат теста:

    random1st@MacBook-Pro ~/P/untitled> python -m unittest dict_from_keys
    ..
    ----------------------------------------------------------------------
    Ran 2 tests in 33.312s
    
    OK
    

    Без комментариев.

    Вариант 3

    Следующее решение:

    def dict_from_keys(keys, values):
       return {key: None if idx>=len(values) else values[idx] for idx, key in enumerate(keys)}
    

    Результат теста:

    random1st@MacBook-Pro ~/P/untitled [1]> python -m unittest dict_from_keys
    ..
    ----------------------------------------------------------------------
    Ran 2 tests in 26.797s
    
    OK
    

    Как видим, существенного ускорения добиться не удалось. Еще вариация на тему:

    Вариант 4

    def dict_from_keys(keys, values):
        return dict((len(keys) > len(values)) and map(None, keys, values) or zip(keys, values))
    

    Результат:

    random1st@MacBook-Pro ~/P/untitled> python -m unittest dict_from_keys 
    ..
    ----------------------------------------------------------------------
    Ran 2 tests in 20.600s
    
    OK

    Вариант 5

    def dict_from_keys(keys, values):
        result = dict.fromkeys(keys, None)
        result.update(zip(keys, values))
        return result
    

    Результат:

    random1st@MacBook-Pro ~/P/untitled [1]> python -m unittest dict_from_keys
    ..
    ----------------------------------------------------------------------
    Ran 2 tests in 17.584s
    
    OK

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

    Вариант 6

    def dict_from_keys(keys, values):
        return dict(zip(keys, values + [None] * (len(keys) - len(values))))
    

    Результат:

    random1st@MacBook-Pro ~/P/untitled> python -m unittest dict_from_keys
    ..
    ----------------------------------------------------------------------
    Ran 2 tests in 14.212s
    
    OK

    Еще быстрее:

    Вариант 7

    def dict_from_keys(keys, values):
        return dict(itertools.izip_longest(keys, values[:len(keys)]))
    

    Результат:

    random1st@MacBook-Pro ~/P/untitled> python -m unittest dict_from_keys
    ..
    ----------------------------------------------------------------------
    Ran 2 tests in 10.190s
    
    OK

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

    Вариант 8

    class DataStructure(dict):
        def __init__(self, *args, **kwargs):
            super(DataStructure, self).__init__(*args, **kwargs)
            self._values = None
            self._keys = None
    
        @classmethod
        def dict_from_keys_values(cls, keys, values):
            obj = cls()
            obj._values = values[:len(keys)]
            obj._keys = keys
    
            return obj
    
        def __getitem__(self, key):
            try:
                return super(DataStructure, self).__getitem__(key)
            except KeyError:
                try:
                    idx = self._keys.index(key)
                    self._keys.pop(idx)
                    super(DataStructure, self).__setitem__(
                        key, self._values.pop(idx)
                    )
                except ValueError:
                    raise KeyError
                except IndexError:
                    super(DataStructure, self).__setitem__(key, None)
                return super(DataStructure, self).__getitem__(key)
    
        def keys(self):
            for k in self._keys:
                yield k
            for k in super(DataStructure, self).keys():
                yield k
    

    random1st@MacBook-Pro ~/P/untitled [1]> python -m unittest dict_from_keys 
    ..
    ----------------------------------------------------------------------
    Ran 2 tests in 1.219s
    
    OK

    От себя добавлю, что лично мне наиболее импонирует 6-й вариант, как в плане читабельности, так и скорости.
    P.S. Еще раз поразился количеству комментаторов абсолютно бесполезной статьи.

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

    Какой вариант Вам кажется наиболее предпочтительным:

    • 5,8%124
    • 1,9%28
    • 2,2%39
    • 0,7%43
    • 18,8%578
    • 27,7%6115
    • 32,5%7135
    • 10,4%843
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 52

      –10
      Поправьте меня если я не прав, но по одному холодному запуску нельзя оценить работу алгоритма. Ведь так? Ну и 25 секунд на 1000 ключей это просто пипец как медленно, даже 1 секунда это медленно. А еще говорят что Java тормозит.
        0
        ти видать статью так и не прочитал, там в начале видно в тестах сколько раз он запускается.
        100 000 запусков подряд это нормально для прогрева или нет?

        а 100 000 раз по 1000 ключей меньше чем за 2 сек это достаточно быстро?
          –1
          ну и раз тест запускается дважды то умнож єто все приблизительно на 2
        +9
        поправлю. Если внимательно посмотрите на тест, то увидите, что функция запускается 100 тысяч раз.
          0
          У меня за дерево из json файла со 100 тыс ключами отрисовывается в консоли за 8с. Где-то близко.
            +3
            сам процесс вывода в консоль обычно довольно тормозной
            0

            Но шестой вариант же медленнее седьмого. Как он может импонировать в плане скорости?

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

              в итоге шестой вариант является «золотой серединой»
              –8
              Вот вы мучаетесь, ребят…
              на руби решение:

              arr_keys.zip(arr_values).to_h
              
              0
              Автор, попробуйте такое решение на питоне потестировать:
              {k: v for k, v in itertools.izip_longest(keys, values)}
              
                +1
                точнее:
                {k: v for k, v in itertools.izip_longest(keys, values[:len(keys)])}
                
                  0
                  Ran 2 tests in 17.860s. Получилось медленнее, из-за того, что это dict comprehesions, а не вызов скомпилированного кода.
                +1
                Перед тем, как читать, сам быстренько набросал решение, вышел вариант 6, но из приведенных самый читаемый, по-моему, пятый. Ну а по-серьёзному, прежде чем решать такие задачи, надо раскурить доки по itertools и писать седьмой.
                  0
                  Прежде чем решать — нужно чётко понять по какому параметру оптимизируем. По читаемости или по скорости, а если по скорости, то надо чётко понять скорость чего важна.
                    +3
                    Прежде, чем упарываться в оптимизацию, нужно чётко понять, нужна ли она вообще. А тем более, когда микроскопическую задачку на собеседовании просят написать на доске. Лучше написать что-нибудь, а там уже видно будет, хотят от тебя, чтобы ты это оптимизировал, или хотят лучше следующую задачу дать.

                    Ну и если задача на хитровы2.7банные итерации-зипы-словари, то, как правило, всё это уже есть в «Симпсонах»… в смысле, в itertools. Только синтаксис хрен вспомнишь, надо доки читать.
                • НЛО прилетело и опубликовало эту надпись здесь
                    0
                    Автор из Минска. Там еще Wargaming есть.
                    +2
                    Проголосовало 63 человека. Воздержалось 47 человек.
                    Понедельник. Утро. Люди еще не проснулись чтобы решать такого рода задачи…
                      +1
                      №6 можно довести до ума, коли вам так мила идея ленивых вычислений:
                      from itertools import chain, repeat
                      
                      def dict_from_keys(keys, values):
                          return dict(zip(keys, chain(values, repeat(None))))

                      №8 просто мрак и помешательство.
                        +1
                        Ran 2 tests in 21.165s
                          0
                          А то.
                          Дёргать генераторы (т.е. лениво вычислять) медленно, слайсы весьма быстры.
                            0
                            простите, а где у Вас отложенные вычисления? У Вас все вычислится в момент вызова функции, и в результате уже будет словарь.
                              –1
                              Усы и хвост chain и repeat мои отложенные вычисления.
                              А словарь, верно, будет в результате. Со временем доступа О(1), как и положено словарю.
                        +5
                        7-й вариант и быстрый, и красивый. И чистый, так как zip_longest поддерживает keyword аргумент 'fillvalue', при помощи которого можно задавать значение по-умолчанию.

                        PS: в публикациях уже давно не стоит приводить примеры на Python2 — моветон, однако.
                          0
                          В первом списке не может быть повторяющихся значений? Или то, что в задаче указано, что это ключи, уже как бы подразумевает их уникальность?
                          Если повторяющиеся значения присутствуют, то решения будут не совсем корректные.
                            0
                            Я ночью проверил :) Для каждого повторяющегося ключа будет взято значение соответствующее последнему вхождению. А тесты, да, упадут, потому что надо проверять с с помощью

                            self.assertDictEqual(expected, actual, msg=None)
                            
                            +2
                            Вариант 4, например, не работает в третьем питоне — map работает иначе. Обозначьте где-то что это все относится ко второму питону
                              0
                              Зачем переопределен метод __getitem__ он ведь не вызывается нигде? Или это на тот случай, если данный класс кто-то решит использовать?
                                0
                                Это для того, чтобы показать, как в процессе обращения к элементам структуры данные «переезжают» из списков в словарь. Там есть еще неучтенные детали, но в целом идея такая.
                                0
                                Что-то такое в голову пришло:

                                for n, key in enumerate(keys): res[key] = (v[n:n + 1] + [None])[0]
                                  0

                                  А список в задаче на какой структуре данных основан? Там массив внутри, или реально список связанный?

                                    +1
                                      0

                                      В Питоне реализованы как массивы переменной длины. Добавляю коментарий чтобы не было необходимости лезть по ссылке.

                                    +3

                                    По-моему, совсем незаслужено упустили использование defaultdict из модуля collections:


                                    Python3:


                                    return collections.defaultdict(type(None), zip(keys, values))

                                    Python2:


                                    return collections.defaultdict(lambda: None, itertools.izip(keys, values))

                                    Да, первый тест не пройдёт в таком виде как вы его предложили, так как ключи не будут созданы, но при обращении к ним будет возвращаться None. Такая реализация у меня работает на 20% быстрее чем ваш №7.


                                    Если нужно решение, которое пройдёт и первый тест без изменений, то можно вот так записать:


                                    result = collections.defaultdict(lambda: None, itertools.izip(keys, values))
                                    result.update({key: None for key in keys[len(values):]})
                                    return result

                                    Такое решение у меня работает примерно на 1% быстрее №7.

                                      +1
                                      Да, задумывался об использовании defaultdict, но отбросил из-за момента определения длины массива, во-первых, и во-вторых, нужно оговаривать отсутствие KeyError при запросе по несуществующему ключу.
                                        0
                                        None — синглтон, и создавать его конструктором — прикольное извращение))
                                        Респект.
                                          0

                                          @longclaps, defaultdict принимает первым параметром default_factory, то есть ему нужен не объект, а тип. В Python 3 хоть type(NoneType) работает, а в Python2 вот приходится через лямбду извращаться. Если у вас есть рабочие идеи, я буду рад услышать их.

                                            +1
                                            Да, я именно и имел в виду, что в defaultdict передаётся конструктор типа, а в вашем случае — фейковый конструктор, возвращающий дефолтный синглтон.

                                            Ваш финальный вариант будет проще и быстрее с простым словарём:
                                            def dict_from_keys(keys, values):
                                                result = dict(zip(keys, values))
                                                result.update((key, None) for key in keys[len(values):])
                                                return result
                                              0

                                              Да, я тоже заметил, что в моём финальном варианте уже нет смысла в defaultdict, но так как время выполнения от этого не изменилось, я решил уже не писать об этом. Тем не менее, спасибо, что написали.

                                        0

                                        Кто-нибудь может объяснить, почему вариант, сделанный "в лоб" с минимальной вычислительной сложностью и минимальным количеством аллокаций, работает в два раза медленнее itertools?


                                        def dict_from_keys(keys, values):
                                            r = {}
                                            keysLen = len(keys)
                                            valuesLen = len(values)
                                            commonLen = min(keysLen, valuesLen)
                                            i = 0
                                        
                                            while i < commonLen:
                                                r[keys[i]] = values[i]
                                                i += 1
                                            while i < keysLen:
                                                r[keys[i]] = None
                                                i += 1
                                            return r```
                                          +1
                                          Да все просто — itertools — это скомпилированный сишный код с биндингами к Python.
                                          0
                                          Как Вариант 8 получается таким быстрым?
                                            +1
                                            Он не быстрый. Он все операции по созданию словаря оставляет на потом, переопределяя методы dict
                                            0
                                            del
                                              0

                                              У меня получились такие результаты на списках keys и values длинной 300000 и 500000 соответственно. Код модуля можно посмотреть здесь. Использовал варианты 1, 3, 4, 5, 6.


                                              Результаты
                                              Python 3.5.2 (v3.5.2:4def2a2901a5, Jun 25 2016, 22:18:55) [MSC v.1900 64 bit (AMD64)] on win32
                                              
                                              Test repetition number: 100
                                              
                                              Results for case len(keys) > len(values):
                                              Keys list size: 300000
                                              Values list size: 500000
                                              naive_dict_create        : 0.13788 sec      
                                              itertools_dict_create    : 0.10612 sec      
                                              zip_dict_create          : 0.13270 sec      
                                              from_keys_dict_create    : 0.10860 sec      
                                              for_loop_dict_create     : 0.13164 sec      
                                              
                                              Results for case len(keys) < len(values):   
                                              Keys list size: 500000
                                              Values list size: 300000
                                              naive_dict_create        : 0.21402 sec      
                                              itertools_dict_create    : 0.18627 sec      
                                              zip_dict_create          : 0.18104 sec      
                                              from_keys_dict_create    : 0.15303 sec      
                                              for_loop_dict_create     : 0.30768 sec      
                                              
                                              Total time for case len(keys) < len(values):
                                              Keys list size: 300000
                                              Values list size: 500000
                                              naive_dict_create        : 15.35587 sec     
                                              itertools_dict_create    : 14.01912 sec     
                                              zip_dict_create          : 14.33157 sec     
                                              from_keys_dict_create    : 11.88172 sec     
                                              for_loop_dict_create     : 15.96302 sec     
                                                0
                                                У Вас почему-то в коде ни разу не указанный Вами набор.
                                                0
                                                Если подгонять задачу под тест, то самое скоростное будет что-то такое
                                                class MyDict:
                                                  def __init__(self, keys, values): # работает мгновенно
                                                    self._keys = keys
                                                    self._values = values
                                                  def __getitem__(self, key): # медленно, но ведь в тесте это не проверяется
                                                    i = self._keys.index(key)  # метнёт исключение, если ключа нет
                                                    return self._values[i] if i < len(self._values) else None
                                                  def keys(self): # а вот это проверяется, поэтому пусть работает мгновенно
                                                    return self._keys
                                                
                                                  0
                                                  И еще исключение будет ValueError, а не KeyError — нетипичное поведение для словаря. Тест крайне примитивный, тут все зависит от контекста. Я хотел показать, как отложить создание словаря, а не отказаться от него вообще.
                                                  0
                                                  python2.7
                                                    return dict(izip(ks, vs) if len(vs) > len(ks) else izip_longest(ks, vs))
                                                  


                                                  Ran 2 tests in 12.800s

                                                  вариант 6 для сравнения:
                                                  Ran 2 tests in 19.312s
                                                    0
                                                    Мне тоже понравился 6 за прозрачность.
                                                    Его более рабоче-крестьянский вариант
                                                    def dict_from_keys(keys, values):
                                                        diff = len(keys) - len(values)
                                                        if diff > 0:
                                                            values.extend([None]*diff)
                                                        return dict(zip(keys, values))
                                                    
                                                    даёт устойчивый выигрыш около 1с (15.8 против 16.8) на моей машине. (Python 2.7.12)

                                                    Ещё я прогнал ваши тесты (1--7) у себя и получил следующие результаты.

                                                    №     мои, с    ваши, с   отношение
                                                    #1    33.960    26.118    1.300
                                                          33.862    25.828    1.311
                                                    #2    35.330    33.312    1.061 *
                                                    #3    33.549    26.797    1.252
                                                    #4    16.851    20.600    0.818 **
                                                    #5    20.347    17.584    1.157
                                                    #6    16.801    14.212    1.192
                                                    #7    12.622    10.190    1.239
                                                    


                                                    Нормированием не занимался, что, не поgупать ничего, но здесь явно другие результы в пункте #2 и тем более в #4. Интересно было бы найти причину.

                                                      0
                                                      У меня для этого задания были такие варианты:

                                                      from itertools import zip_longest, islice
                                                      
                                                      
                                                      def newdict(keys, values):
                                                          """ 
                                                          Returns dictionary from lists of keys and values.
                                                          Supports lists and tuples only.
                                                          """
                                                          values_  = islice(values, len(keys))
                                                          return dict(zip_longest(keys, values_))
                                                      
                                                      
                                                      def inewdict(keys, values):
                                                          """
                                                          Returns dictionary from lists of keys and values.
                                                          Supports any iterable objecs.
                                                          """
                                                          values_ = iter(values)
                                                          return {key: next(values_, None) for key in keys}
                                                      

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

                                                      Самое читаемое