Гм… Прошу прощения, не дописал строку с гипотетическим заполнением массива. Да, я имелл ввиду что после объявления массив заполняется включительно до N-1 го элемента. И уже потом вызывается add()
Я сам когда-то так считал :) ArrayList и ему подобные контейнеры захватывает кучу памяти наперёд, оттуда и скорость добавления в конец. Кстати, вот неплохой синтетический случай: в цикле создаётся большой ArrayList, к которому добавляют один элемент. Что-то вроде:
for (...) {
N = 1024*1024*1024;
ArrayList<int> arr = new ArrayList<int>(N);
arr.add(0);
}
Я поставил минус статье и вот почему: Вы сравниваете слона с китом. Априори известна О-сложность операций для контейнеров типа «Элементы размещены в памяти последовательно» и «Связной список». Поэтому и нет никакого смысла сравнивать скорость их работы.
Господа, а вот многие Линуксоиды только-только дождались новой Оперы! Я до последнего момента на 12й сидел. Вы говорите: «Закладки?». Народ с каждой новой версией требовал «Сделайте под Linux!». И дождались же! Зачем сразу гнать бочку на новые закладки? Это же МЫ просили Оперу вернуть закладки. И вот их вернули! И тут начинается «Опера мертва», «Не нужно» и т.д. И не стыдно вам?
Я думал об этом, когда писал предыдущий ответ и решил, что я в данном случае я остановился бы на 4-х функциях. Спросите себя, неужто так много усилий стоит поддерживать конкретно эти функции? Скорее всего Вы напишете их и забудете надолго, до тех пор, пока не надо будет внести кардинальные изменения. Опять таки, это не должно занять так много времени, ведь функции по-сути одинаковые.
При всём, я согласен, что в других случаях такой подход совершенно неприемлим и логичнее использовать пострение через шаблон.
Такой код было бы гораздо легче читать. Т.е. представьте себя на месте человека, который не особенно знаком с комбинаторикой и разбирает Ваш код. Он начинает с permutation_norep(). Тут же он сталкивается с тем, что далее идёт вызов template() да ещё с двумя аргументами-функциями. Хорошо, идём дальше в глубину template()… Опа, assertion(). Так, а что там за assertion() был? Ага, n и k дожны быть положительными, либо равны нулю, причём n >= k. Далее — reducer(). А что там этот reducer делает?.. Думаю, Вы поняли мысль.
Вот как например будет выглядеть целостная permutation_norep:
def permutation_norep(s, k):
len_s = len(s)
is_valid_input = len_s > 0 and len_s >= k and k >= 0
if not is_valid_input:
raise ValueError('Invalid input: s={}, k={}'.format(s, k))
if k == 0:
yield ""
return
k <= 1:
yield from s
return
new_k = k - 1
for i in range(len_s):
new_s = s[:i] + s[i + 1:]
for res in permutation_norep(new_s, new_k):
yield s[i] + res
Нет, к содержанию тоже есть претензии. Я бы изначально написал каждую функцию по-отдельности, не используя общие template, с передачей в него пары лямбда-выражений.
Но в общем, переменные с ничего не говорящими именами s, k, c, new_s — это уровень первого курса. Если Вы сейчас закроете эту страницу и откроете её через пару месяцев, то может и Вам код покажется нечитаемым и непонятным. Очень рекомендую «Code complete» («Совершенный код» в русском переводе) для улучшения навыков написания красивого кода.
assert в данном случае используется неправильно, по очень простой причине: он производит валидацию значений входных данных, чем должна заниматься бизнес-логика. assert нужен в качестве инструмента для поиска ошибок программиста, например:
assert isinstance(k, int), 'Invalid input "k" argument type in template(), should be int, received %s' % type(k)
Камрад, не умаляя значения проделанной работы, хочу напомнить о наличии в стандартной библиотеке itertools, в том числе функций product(), permutations(), combinations(), combinations_with_permutations().
А я вообще себя старым почуствовал. В 2002м свой первый клиент->сервер чат на VB6 с сетью через winsocks ActiveX-контрол. При этом сдувая код с различных ресурсов, не особенно стесняясь. И потом вставляя свой «копирайт» :) Эх время!
Если некоторые люди взглянут на некоторые строчки некоторых языков, с которыми они никогда не имели дела, то они могут показаться им совершенно непонятными. И это относится к любому языку программирования, всегда найдутся конструкции, в которых без детального изучения не разобраться.
kmeaw, как вариант — оставить всё как есть, в статье, в разделе о quote, написать о недостаточно правильной реализации. А вот по-поводу, как реализовать quote правильно, я бы немного поспорил: можно например внести в интерпретатор следующие изменения:
# ...
fn = eval(list_or_atom[0])
if fn == quote
# no need to eval the rest of the list
else
# eval the rest of the list
И вот после этой операции, размер
arrв памяти увеличиться в полтора раза! LinkedList был бы чуточку экономнее.См.
grow()в hg.openjdk.java.net/jdk7/jdk7/jdk/file/00cd9dc3c2b5/src/share/classes/java/util/ArrayList.javaЯ поставил минус статье и вот почему: Вы сравниваете слона с китом. Априори известна О-сложность операций для контейнеров типа «Элементы размещены в памяти последовательно» и «Связной список». Поэтому и нет никакого смысла сравнивать скорость их работы.
Вот кстати отличный пост на эту тему: habrahabr.ru/post/188010/
При всём, я согласен, что в других случаях такой подход совершенно неприемлим и логичнее использовать пострение через шаблон.
elifпотерял (там, гдеk == 1).permutation_norep(). Тут же он сталкивается с тем, что далее идёт вызовtemplate()да ещё с двумя аргументами-функциями. Хорошо, идём дальше в глубинуtemplate()… Опа,assertion(). Так, а что там заassertion()был? Ага,nиkдожны быть положительными, либо равны нулю, причёмn >= k. Далее —reducer(). А что там этотreducerделает?.. Думаю, Вы поняли мысль.Вот как например будет выглядеть целостная
permutation_norep:s,k,c,new_s— это уровень первого курса. Если Вы сейчас закроете эту страницу и откроете её через пару месяцев, то может и Вам код покажется нечитаемым и непонятным. Очень рекомендую «Code complete» («Совершенный код» в русском переводе) для улучшения навыков написания красивого кода.assertв данном случае используется неправильно, по очень простой причине: он производит валидацию значений входных данных, чем должна заниматься бизнес-логика.assertнужен в качестве инструмента для поиска ошибок программиста, например:__debug__ == Falseпри загрузке кода из *.pyo файла. https://docs.python.org/3/reference/simple_stmts.html#the-assert-statement.assertв теле функции, который работает лишь при заданном__debug__.product(),permutations(),combinations(),combinations_with_permutations().