Python-сообщество

Вообщем, судя по недавнему топику про Комбинаторику я подумал что всем будет интересно (в том числе и мне) решить одну задачку на питоне.
Эту задачку я получил когда проходил второй этап поступления в Школу программистов HH (собственно я так и не прошел). Мне удалось решить задачу частично т.к. одно из условий было

Ни одна из задач не должна считаться больше 5 секунд на валидных входных данных

№10. Пилообразные последовательности
Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n , составленных из чисел 1.. k .
Программа получает на вход два натуральных числа n и k , не превосходящих 10**6. Гарантируется, что ответ не превосходит 2**31-1.
Пример
Ввод - “3 3” Вывод - “10”

Самый быстрый код который у меня получился ( но он настолько уродский что стыдно) решал эту задачу с входными данными n = 8, k = 8 чуть больше 12 секунд ( ответ выдает 691550).
У кого получается быстрее, тот очень крут ( IMHO).
Пожалуйста, мне очень интересно как сделать ещё быстрее ( желательно без сторонних библиотек и всяких PyPy)

Решение принималось только на питоне? На скольки ядрах подразумевался запуск кода?

Я вижу, что можно распараллелить на k потоков. Каждый из потоков делает допущение, что последовательность начинается с числа 1..k и просчитывает соответствующие комбинации.

Выложите код, хуже не будет.

Отредактировано Soteric (Янв. 21, 2013 22:32:37)

Принималось и на java Но это не равный бой. Я её не знаю. )) и знать пока не хочу.
По поводу ядер нечего не писалось.
Такой вариант с потоками пробовал, но получилось медленней, возможно я не умею их готовить ( делал через класс threading.Thread) к сожалению сорцов этой попытки не осталось.
Я выложу пока более маленькое и лаконичное решение (но пи“”" медленное).

import itertools
import time
def is_pill(ch_list):
    for index, num in enumerate(ch_list[1:]):
        try:
            if not (ch_list[index] < num > ch_list[index + 2]
                 or ch_list[index] > num < ch_list[index + 2]):
                return False
        except:
            pass
    return True
def testsupper3(k, n):
    res = 0
    for args in itertools.product(*[range(1, k + 1)] * n): # обратите внимание на * перед range - удивительный оператор
        if is_pill(args):
            res += 1
    return res
n, k = 8, 8
t1 = time.time()
ans = testsupper3(k, n)
t2 = time.time()
print ans, t2 - t1

Отредактировано Frog-king (Янв. 22, 2013 07:18:02)

Условие ведь неполное.
Может быть, в правиле построения последовательности должна быть степень?

Soteric
В задании сказано, что нельзя потоки использовать ;)

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

В задании сказано потоки - можно, процессы - нельзя.

Отредактировано Soteric (Янв. 21, 2013 23:24:36)

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

Frog-king
задание написал правильно (точно)

Отредактировано Lexander (Янв. 22, 2013 00:02:14)

нет.
Ваши последовательности не пилообразные. Либо оба соседа больше элемента либо оба меньше
Вот все варианты 3 на 3:
1) 1 2 1
2) 1 3 1
3) 1 3 2
4) 2 1 2
5) 2 1 3
6) 2 3 2
7) 2 3 1
8) 3 1 2
9) 3 1 3
10)3 2 3

Вот и все
P.S 4 на 4 писать не буду))

У меня получились именно такие последовательности, к которым добавил, 123 и 321.

Frog-king
Либо оба соседа больше элемента либо оба меньше

каждый ее элемент либо строго больше, либо строго меньше своих соседей