Сообщений в теме: 101

[asr]

Тема для интересных задач.
Обсуждение решений и реализаций на разных языках, сравнение, нахождение лучшего.

Сообщение отредактировал asr: 22.08.2012, 12:32:47

[itty]

http://ideone.com/bI4Bp

так ведь предыдущее ваше решение справляется с этим ,на сколько эффективно я не знаю пусть питонщики скажут)

в предыдущем решении формируется общий список, что при пострениие html таблицы совершенно не требуется. без него получается короче и эффективнее

[smug]

ну сначала я хотел немного абстрагировать задачу а потом подумал на*ер эти сферические задачи вакууме)

[tobber]

Подобную задачу гораздо лучше ( на питоне если ) решить так - http://ideone.com/POXo2
Не нужны ни промежуточные списки ни рекурсия.

[itty]

Подобную задачу гораздо лучше ( на питоне если ) решить так - http://ideone.com/POXo2
Не нужны ни промежуточные списки ни рекурсия.

зато начинает рождаться астрономическое кол-во туплов, которые нивелируют все теоретические плюсы предложенного решения (даже по скорости). и запаса на оптимизацию у данного решения несоизмеримо меньше чем у моего

[tobber]

Астрономическое?
Туплы там если и создаются внутри enumerate или itertools.product, то они там же и подчищаются gc.
Наружу в данном случае торчит только одна единственная тупла row.
И да, в Python туплы зачастую намного быстрее списков, т.к. они не изменяемые и это упрощает работу интерпретатору.

Мой код с itertools.product примерно в два раза быстрее вашего, при одинаковом расходе памяти.

https://gist.github....5abcf60b1dfda61

Сообщение отредактировал tobber: 24.08.2012, 23:03:42

[tobber]

Насчет "пространства для оптимизации".
Если вспомнить что вызов методов относительно дорог - заменить построение html через объединение списка на тупую конкатенацию оператором +=, а также использовать % вмест .format, то можно получить следующее.
Работает на порядок быстрее, код стал даже проще.

https://gist.github....5109139bc6fa22c

Работая с Python никогда нельзя забывать, что C код всегда быстрее.
Многие библиотеки Python написаны на C и хорошо оптимизированы, так что на чистом питоне побить в производительности тот же itertools.product - безнадежная затея ( ну разве pypy ).
Один из главных ключей к быстрым программам на Python - знать когда и где можно передать задачу C'шным библиотекам.

Сообщение отредактировал tobber: 24.08.2012, 23:10:43

[itty]

Работает на порядок быстрее, код стал даже проще.

Понятия не имею что за сферических коней меряет github, но визуально и на ideone рекурсивный метод работает заметно быстрее тупельного.
http://ideone.com/SIcZU
а я даже не начинал его оптимизировать.

Работая с Python никогда нельзя забывать, что C код всегда быстрее...

это все хорошо в теории. а на практике бывает очень по разному.

Один из главных ключей к быстрым программам на Python - знать когда и где можно передать задачу C'шным библиотекам.

вообщето задача была реализовать алгоритм, а не показать виртуозное жонглирование itertools.

Сообщение отредактировал itty: 24.08.2012, 23:32:10

[tobber]

Понятия не имею что за сферических коней меряет github, но визуально и на ideone рекурсивный метод работает заметно быстрее тупельного.
http://ideone.com/SIcZU

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

это все хорошо в теории. а на практике бывает очень по разному.

Да нет, эквивалентный С код _всегда_ быстрее питона.
Просто видимо в itertools.product внутри не тупо рекурсивный итератор как я думал, и как сделан ваш вариант.

вообщето задача была реализовать алгоритм, а не показать виртуозное жонглирование itertools.

Там из itertools используется только product, который просто вроде бы создан для того чтобы быть использованным в данной задаче.
Каюсь, есть привычка в первую очередь использовать библиотеки для любого чиха, но разве это плохо?

[itty]

Да нет, эквивалентный С код _всегда_ быстрее питона.
Просто видимо в itertools.product внутри не тупо рекурсивный итератор как я думал, и как сделан ваш вариант.

Ключевое слово "эквивалентный". Наш код совершенно разный. Создание и разрушение туплов достаточно дорогая операция по сравнению с рекурсивным вызовом.

Там из itertools используется только product, который просто вроде бы создан для того чтобы быть использованным в данной задаче.
Каюсь, есть привычка в первую очередь использовать библиотеки для любого чиха, но разве это плохо?

Это не плохо и даже весьма правильно, если стоит не образовательная (к чему данный топик ближе) задача .
Плохо безосновательно утверждать "Подобную задачу гораздо лучше ( на питоне если ) решить так", особенно когда это не так

[tobber]

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

In [11]: def void(): pass
In [12]: %timeit void()
10000000 loops, best of 3: 121 ns per loop
In [13]: %timeit (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
10000000 loops, best of 3: 27.6 ns per loop

^ создание тупла из 10-ти элементов и его удаление намного быстрее простого вызова функции.

Проблема в том, что Itertools.product создает по полноценному ряду для всех комбинаций, хотя нам надо всего лишь небольшую часть, т.к. первые элементы выводятся только каждые N раз.
Рекурсивный итератор как у вас эту проблему решает, а мне приходится дополнительно проверять надо ли на этой строке выводить этот столбец.

Впрочем сейчас, на свежую голову, я понял что допустил в самом коде грубую ошибку - использовал %d вместо %s в сборке строки, а это дорогая операция.
Если банально заменить %d -> %s в строке, где собирается <td>, то получается совсем другой результат - http://ideone.com/WmSk1

Хотя product все равно лажает, особенно с ростом входных данных, но это практически не имеет значения в данном случае. Время, которое тратится в .product() - ничтожно, как и время на рекурсию и итерацию.

In [5]: %timeit for i in itertools.product(range(10), range(10), range(10)): pass
10000 loops, best of 3: 59.3 us per loop



In [6]: def product(head, *tail):
   ...:     for item in head:
   ...:         yield item
   ...:     if tail:
   ...:         for item in product(*tail):
   ...:             yield item
   ...:        

In [7]: %timeit for i in product(range(10), range(10), range(10)): pass
100000 loops, best of 3: 6.51 us per loop

Даже сотня-другая us накладных расходов - это абсолютно не важно в общем ходе выполнения данного алгоритма.
Так что выигрыш пусть и в 10 раз по скорости обхода у рекурсивного варианта - не имеет значения.

Мое основное замечание - что если нет разницы, то лучше использовать itertools, т.к. это дает более "чистый" и простой код, без рекурсий и монад.

Мне кажется, что данная задача хоть и образовательная, не является в то же время слишком академической ( как числодробилки на codeforces к примеру ), поэтому я и утверждал что "Подобную задачу гораздо лучше ( на питоне если ) решить так".
Признаю, может это было немного резко.

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

[itty]

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

Потому как законы природы нарушить сложно, даже в питоне

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

In [11]: def void(): pass
In [12]: %timeit void()
10000000 loops, best of 3: 121 ns per loop
In [13]: %timeit (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
10000000 loops, best of 3: 27.6 ns per loop

^ создание тупла из 10-ти элементов и его удаление намного быстрее простого вызова функции.

(*) Это конечно хорошо. Просто замечательно. Но опять в теории. А на практике
http://ideone.com/uBa2W
[0] создание константы это одно
[1] создание тупла из констант это другое
[2] создание тупла из переменных значений, что проиходит на самомо деле, в отличие от (*) совершенно уже третье
[3] а в реальной жизни кроме создания и уничтожения тупла нужна его декомпозиция. и уже 6-ти кратное проседание от (*)
[4] а не ровен час декомпозиция ведется через `enumerate` (что тоже вызов функции)
вот и набежало обещанное ранее нивелирование выйгрыша.
но и это не все было еще. тупельная версия использует использует примерно в 2 раза больше декомпозиций через `enumerate`, чем рекурсивная своих рекурсивных вызовов функций.

итого вместо 10-ти кратного ускорения от использования туплов в теории, в реальности имеем 40...400% проседание производительности

[tobber]

итого вместо 10-ти кратного ускорения от использования туплов в теории, в реальности имеем 40...400% проседание производительности

Я не говорил, что мой код быстрее в 10 раз из-за туплов. Я неверно интерпретировал показания профайлера, мы с этим вроде уже разобрались.

Да, enumerate не шустр, скорее наоборот. Да, itertools.product тоже тормозит. Деструктуризация туплов в enumerate - не самая летающая операция.
Однако же, мое "тупельное" решение работает немного быстрее вашего и потребляет меньше памяти. ( я про последний вариант http://ideone.com/WmSk1 )

Более того - вы сильно переоцениваете общий вес "туплов" в программе.
Например - http://ideone.com/od632 - здесь, в table_manual_counter, я заменил enumerate на ручной счетчик, получив всего ~10% скорости, избавившись от "дорогого" enumerate и сопутствующей декомпозиции туплов.
На мой взгляд оно того просто не стоит.

Сообщение отредактировал tobber: 28.08.2012, 19:10:14

[tobber]

Еще хочу заметить, что если вести речь именно о максимальной оптимизации функции, то оба наши варианта вообще никуда не годятся и не имеют будущего.

Для достижения максимальной скорости в данном типе алгоритмов вариант вообще только один - кодогенерация.
Итак, смотрим на метод "оптимальнее некуда", через генерацию вложенного for-loop - http://ideone.com/MmoUd
Действительно быстро и все такое... Но стоп 0.42 это примерно 30% от 1.25, которые были в "тупельном".
Т.е. ценой втрое более массивного кода, который еще и немного сложнее для понимания из-за кодогенерации, мы получили трехкратный прирост в скорости.

Мне сложно сказать стоит ли оно того.

Поэтому я еще раз повторюсь - если производительность не совсем уж критична, то вариант с .product лучше, т.к. он проще ( и немного быстрее, да ).
Если требуется максимальная скорость - то делаем генератор кода, который разворачивает рекурсивный алгоритм во вложенную итерацию.
В любом случае вариант с рекурсией на голом Python - лишний. На небольших объемах данных ( до 10^6 строк в итоговой таблице ) он проигрывает в скорости даже у .product().

Сообщение отредактировал tobber: 28.08.2012, 19:21:27

[smug]

задача отсортировать вот такой список List<String[]>
String[] в купе со всеми элемантами этого массива такая запись уникальна по отдельности нет .

ордер как сиквеле надо сделать на этом списке.

Сообщение отредактировал smug: 25.10.2012, 12:20:27

[caken]

задача наверное на transact sql? или pl sql?

[caken]

Еще одна часто встречающаяся реальная задача по sql.
Есть одна таблица курсов валют, с двумя полями, kurs, data. Как получить актуальный курс на заданный день (Y). Причем таблица курсов заполняется не ежедневно, те будут не все даты. Напр есть курс на 01.01.2012, и следующий курс только на 10.01.2012. А заданная дата может быть напр на 07.01.2012.
(считаем что по полю data есть индекс, соответственно запрос должен быть оптимизированным по скорости, или лаконичным и "красивым")

[darkfire]

не знаю насколько это красиво, но можно взять top 1 от таких что data меньше равна параметру при этом сортировать чтоб последняя дата была первой. Если доподлинно известно что в этом месяце или в этом году есть хоть один курс можно поставить ещё ограничение.

[vladimir55]

Как-то на одном собеседовании давали такую задачку, а потом показали решение:

SELECT kurs
FROM kurs_table
WHERE date in (
  SELECT max(date)
  FROM kurs_table
  WHERE date <= Y)

[smug]

задача отсортировать вот такой список List<String[]>
String[] в купе со всеми элемантами этого массива такая запись уникальна по отдельности нет .

ордер как сиквеле надо сделать на этом списке.

вот в нете на жаве такое решения нашел

class MyClassComparator implements Comparator<String[]> {

private String fillUpLeftWithZeros(String val, int digit) {
if (digit == val.length()) {
return val;
}
String res = "";
for (int i = 1; i < digit; i++) {
res += "0";
}
return res + val;
}

@Override
public int compare(String[] t1, String[] t2) {
String char1 = "";
String char2 = "";
int l = 0;
for (int i = 0; i < t1.length; i++) {
l = Math.max(t1[i].length(), t2[i].length());
char1 += fillUpLeftWithZeros(t1[i], l);
char2 += fillUpLeftWithZeros(t2[i], l);

}
return char1.compareTo(char2);
}
}

Сообщение отредактировал smug: 29.10.2012, 14:51:49

[liroman]

pomogite rewit' v turbo pascal

Прикрепленные файлы

•  problems-10-11.pdf   259,78К   Количество загрузок: 139

Сообщение отредактировал liroman: 07.01.2013, 19:54:25