DjangoBB LoFi version

Полная версия: Вопрос по оптимизации кода

Начало » Python для новичков » Вопрос по оптимизации кода

Tucha

Окт. 6, 2015 04:57:30

Решаю очередную задачу - http://acm.timus.ru/problem.aspx?space=1&num=1209
Для решения, сперва решил генерировать строку длинна которой не превышает необходимую (исходя из полученных чисел), но код не справлялся даже с пяти/шестизначными значениями (т.е. обрабатывал ооочень долго). Потом решил отказаться от громоздкой строки и просто записывал длину числом (методом сложения длины строки каждой возведённый в степень 10ки).

def calculate_position(number):
    count = 0
    sequence = 0
    while sequence < int(number):
        x = 10 ** count
        sequence += int(len(str(x)))
        count += 1
    answer = str(x)[sequence - int(number) + 1]
    return answer

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

doza_and

Окт. 6, 2015 05:09:54

>>> int(len(str(10**1)))
2
>>> int(len(str(10**2)))
3
>>> int(len(str(10**3)))
4
>>> int(len(str(10**4)))
5
>>> int(len(str(10**5)))
6

https://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F
Что вы решаете непонятно. Ссылка не показывает задачу.

Оптимизация это всегда поиск подходящего алгоритма :). Конечно рецепты типа не вычисляйте постоянно int(number) тоже чтото дадут, но ….

Tucha

Окт. 6, 2015 05:29:29

doza_and
Что вы решаете непонятно. Ссылка не показывает задачу.

Там точка в конце просто стояла.

doza_and
Оптимизация это всегда поиск подходящего алгоритма

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

doza_and
Конечно рецепты типа не вычисляйте постоянно int(number)

Я вот и хочу узнать, как вычислить длину этого списка не запуская процесс уничтожения ЦП

py.user.next

Окт. 6, 2015 07:01:18

Вот тебе самый короткий O(n) алгоритм

def f(n):
    i = 1
    while n > i:
        n -= i
        i += 1
    return (1, 0)[n > 1]

но он не проходит, потому что они, видимо, подают большое число какое-то, которое приводит к полному перебору.

Хотя так, он быстрый и, главное, понятный.

[guest@localhost ~]$ python3 -mtimeit -s '
> def f(n):
>     i = 1
>     while n > i:
>         n -= i
>         i += 1
>     return (1, 0)[n > 1]
> ' 'f(2147483647)'
100 loops, best of 3: 16.2 msec per loop
[guest@localhost ~]$

Tucha

Окт. 6, 2015 07:29:24

py.user.next
Хотя так, он быстрый и, главное, понятный.

Для меня тут много не понятно

Во первых, что означает этот возврат “return (1, 0) |n > 1]”
Во вторых, какая функция у множества ковычек в строке ‘ ’f(2147483647)'
И вот -mtimeit -s ' тоже в первый раз вижу
Буду благодарен за пояснения.

py.user.next

Окт. 6, 2015 07:41:21

Tucha
Во первых, что означает этот возврат return ‘(1, 0)’

(1, 0)[n > 1]

(1, 0) - это простой кортеж
дальше у него берётся элемент по индексу
n > 1 равно True или False в зависимости от n
а True и False равны числам 1 и 0

Пример

>>> (10, 20)[True]
20
>>> (10, 20)[False]
10
>>>

Tucha
Во вторых, какая функция у множества ковычек

Это выполняется в консоли линукс

Вводится с кавычками, когда в одном аргументе несколько строк

[guest@localhost ~]$ echo a 'b
> c
> d
> e' f g h 'i
> j
> k
> l' m n
a b
c
d
e f g h i
j
k
l m n
[guest@localhost ~]$

Вот это место - это то, что получается в результате

a b
c
d
e f g h i
j
k
l m n

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

Tucha

Окт. 6, 2015 08:09:58

Предельно ясно. Эффективное использование логических операторов пока не моё.
А на счёт юниксовых ОСей, ещё вопрос. Есть ли какой то весомый аргумент (сопряжённый с программированием на питоне) для того, что бы пересесть с винды на на какую нибудь убунту. А то много кто пишет “кодить на питоне под виндой не комильфо”, но конкретных причин никто не называет.

py.user.next

Окт. 6, 2015 08:25:33

Да винда сама по себе хуже линукса, потому что пишется на продажу. Поэтому там главное - картинка, а качество на втором плане.

Tucha
сопряжённый с программированием на питоне

Да, и его меньше тестируют на винде, поэтому часто на винде выпадает и сам питон, и сторонние модули для него.
Вот случай описан, когда они выпустили версию, не проверив обыкновенный ввод в винде.

Tucha

Окт. 6, 2015 08:41:49

Ладно, спасибо.
Поставлю пока на виртуалку, что нибудь из юникс семейства, на тест.