# Есть два списка разной длины. В первом содержатся ключи, а во втором значения.
# Напишите функцию, которая создаёт из этих ключей и значений словарь.
# Если ключу не хватило значения, в словаре должно быть значение 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. Еще раз поразился количеству комментаторов абсолютно бесполезной статьи.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Комментарии (51)
random1st
14.11.2016 00:46+9поправлю. Если внимательно посмотрите на тест, то увидите, что функция запускается 100 тысяч раз.
poxu
14.11.2016 01:37Но шестой вариант же медленнее седьмого. Как он может импонировать в плане скорости?
Undiabler
14.11.2016 07:34+21. в седьмом один есть лишний модуль который надо импортировать
2. питон интерпретируемый язык, на нем редко разрабатывают высоконагруженные приложения, так что наравне со скоростью тут так же крайне ценна читабельность
в итоге шестой вариант является «золотой серединой»
youlose
14.11.2016 03:35Автор, попробуйте такое решение на питоне потестировать:
{k: v for k, v in itertools.izip_longest(keys, values)}
3aicheg
14.11.2016 03:48+1Перед тем, как читать, сам быстренько набросал решение, вышел вариант 6, но из приведенных самый читаемый, по-моему, пятый. Ну а по-серьёзному, прежде чем решать такие задачи, надо раскурить доки по itertools и писать седьмой.
Zibx
14.11.2016 05:15Прежде чем решать — нужно чётко понять по какому параметру оптимизируем. По читаемости или по скорости, а если по скорости, то надо чётко понять скорость чего важна.
3aicheg
14.11.2016 06:00+3Прежде, чем упарываться в оптимизацию, нужно чётко понять, нужна ли она вообще. А тем более, когда микроскопическую задачку на собеседовании просят написать на доске. Лучше написать что-нибудь, а там уже видно будет, хотят от тебя, чтобы ты это оптимизировал, или хотят лучше следующую задачу дать.
Ну и если задача на хитровы2.7банные итерации-зипы-словари, то, как правило, всё это уже есть в «Симпсонах»… в смысле, в itertools. Только синтаксис хрен вспомнишь, надо доки читать.
Pr0per
14.11.2016 07:32+2Проголосовало 63 человека. Воздержалось 47 человек.
Понедельник. Утро. Люди еще не проснулись чтобы решать такого рода задачи…
longclaps
14.11.2016 07:33+1№6 можно довести до ума, коли вам так мила идея ленивых вычислений:
from itertools import chain, repeat def dict_from_keys(keys, values): return dict(zip(keys, chain(values, repeat(None))))
№8 просто мрак и помешательство.random1st
14.11.2016 07:33+1Ran 2 tests in 21.165s
longclaps
14.11.2016 10:09А то.
Дёргать генераторы (т.е. лениво вычислять) медленно, слайсы весьма быстры.random1st
14.11.2016 10:39простите, а где у Вас отложенные вычисления? У Вас все вычислится в момент вызова функции, и в результате уже будет словарь.
longclaps
14.11.2016 11:01-1Усы и хвостchain и repeat мои отложенные вычисления.
А словарь, верно, будет в результате. Со временем доступа О(1), как и положено словарю.
renskiy
14.11.2016 08:45+57-й вариант и быстрый, и красивый. И чистый, так как zip_longest поддерживает keyword аргумент 'fillvalue', при помощи которого можно задавать значение по-умолчанию.
PS: в публикациях уже давно не стоит приводить примеры на Python2 — моветон, однако.
i_one
14.11.2016 11:08В первом списке не может быть повторяющихся значений? Или то, что в задаче указано, что это ключи, уже как бы подразумевает их уникальность?
Если повторяющиеся значения присутствуют, то решения будут не совсем корректные.Andy_U
14.11.2016 13:32Я ночью проверил :) Для каждого повторяющегося ключа будет взято значение соответствующее последнему вхождению. А тесты, да, упадут, потому что надо проверять с с помощью
self.assertDictEqual(expected, actual, msg=None)
Mutineer
14.11.2016 11:51+2Вариант 4, например, не работает в третьем питоне — map работает иначе. Обозначьте где-то что это все относится ко второму питону
ANtlord
14.11.2016 11:56Зачем переопределен метод __getitem__ он ведь не вызывается нигде? Или это на тот случай, если данный класс кто-то решит использовать?
random1st
14.11.2016 11:59Это для того, чтобы показать, как в процессе обращения к элементам структуры данные «переезжают» из списков в словарь. Там есть еще неучтенные детали, но в целом идея такая.
tumikosha
14.11.2016 11:57Что-то такое в голову пришло:
for n, key in enumerate(keys): res[key] = (v[n:n + 1] + [None])[0]
poxu
14.11.2016 13:48А список в задаче на какой структуре данных основан? Там массив внутри, или реально список связанный?
frol
14.11.2016 14:23+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.
random1st
14.11.2016 14:27+1Да, задумывался об использовании defaultdict, но отбросил из-за момента определения длины массива, во-первых, и во-вторых, нужно оговаривать отсутствие KeyError при запросе по несуществующему ключу.
longclaps
14.11.2016 14:41None — синглтон, и создавать его конструктором — прикольное извращение))
Респект.frol
14.11.2016 14:48@longclaps,
defaultdictпринимает первым параметромdefault_factory, то есть ему нужен не объект, а тип. В Python 3 хоть type(NoneType) работает, а в Python2 вот приходится через лямбду извращаться. Если у вас есть рабочие идеи, я буду рад услышать их.longclaps
14.11.2016 15:34+1Да, я именно и имел в виду, что в defaultdict передаётся конструктор типа, а в вашем случае — фейковый конструктор, возвращающий дефолтный синглтон.
Ваш финальный вариант будет проще и быстрее с простым словарём:
def dict_from_keys(keys, values): result = dict(zip(keys, values)) result.update((key, None) for key in keys[len(values):]) return resultfrol
14.11.2016 15:39Да, я тоже заметил, что в моём финальном варианте уже нет смысла в
defaultdict, но так как время выполнения от этого не изменилось, я решил уже не писать об этом. Тем не менее, спасибо, что написали.
Scf
14.11.2016 15:03Кто-нибудь может объяснить, почему вариант, сделанный "в лоб" с минимальной вычислительной сложностью и минимальным количеством аллокаций, работает в два раза медленнее 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```random1st
14.11.2016 15:04+1Да все просто — itertools — это скомпилированный сишный код с биндингами к Python.
vpetrigo
14.11.2016 17:16У меня получились такие результаты на списках 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
nickolaym
15.11.2016 01:03Если подгонять задачу под тест, то самое скоростное будет что-то такое
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._keysrandom1st
15.11.2016 09:10И еще исключение будет ValueError, а не KeyError — нетипичное поведение для словаря. Тест крайне примитивный, тут все зависит от контекста. Я хотел показать, как отложить создание словаря, а не отказаться от него вообще.
errx
15.11.2016 09:07python2.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
artemisia_borealis
15.11.2016 14:57Мне тоже понравился 6 за прозрачность.
Его более рабоче-крестьянский вариант
даёт устойчивый выигрыш около 1с (15.8 против 16.8) на моей машине. (Python 2.7.12)def dict_from_keys(keys, values): diff = len(keys) - len(values) if diff > 0: values.extend([None]*diff) return dict(zip(keys, values))
Ещё я прогнал ваши тесты (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. Интересно было бы найти причину.
UbuRus
Поправьте меня если я не прав, но по одному холодному запуску нельзя оценить работу алгоритма. Ведь так? Ну и 25 секунд на 1000 ключей это просто пипец как медленно, даже 1 секунда это медленно. А еще говорят что Java тормозит.
site6893
ти видать статью так и не прочитал, там в начале видно в тестах сколько раз он запускается.
100 000 запусков подряд это нормально для прогрева или нет?
а 100 000 раз по 1000 ключей меньше чем за 2 сек это достаточно быстро?
site6893
ну и раз тест запускается дважды то умнож єто все приблизительно на 2