🚀 go-pugleaf

tom996@orange.pl powiada :
> Witam,
> Proszę o pomoc z optymalizacją poniższego programu ponieważ wykonuje
> się za długo i spoj nie chce  go zaakceptować z powodu błędu "limit
> czasu został przekroczony".

Twój program jest na tyle prosty, że nie pomoże zwykła optymalizacja 
- musisz wymyśleć inny sposób rozwiązania problemu. Poniżej kilka 
uwag o czytelności, bez praktyczengo wpływu na prędkość programu.

> list=[]
> while 1:
>     try:
>         wejscie=input()
>     except EOFError: break

Dlaczego nie korzystasz z warunku pętli?

>     s=0
>     list.append(wejscie)
>     dl=len(list)
>     for i in range(dl):
>       if list[i]<wejscie:

To jest kalka z jakiegoś innego języka - w pythonie pętla
idzie po liście (iteratorze), nie trzeba jej samemu liczyć.
Wystarczyłoby for item in list: if item<wejscie:

> treść zadania:
> Napisz program, który wczytuje z wejścia liczby i oblicza, ile z
> wcześniej wczytanych liczb było od nich mniejszych.

Zapamiętujesz te liczby w kolejności wczytania, więc trzeba
przejrzeć wszystkie żeby sprawdzić ile było mniejszych 
(za każdą następną wszystkie poprzednie). Można sprytniej,
i na tym właśnie polega zadanie - najwięcej z niego wyniesiesz,
jeśli sam wpadniesz na sposób zaoszczędzenia liczby porównań.

Piotr Sawicki

Piotr Sawicki pisze:
> tom996@orange.pl powiada :
>> [...]
>> treść zadania:
>> Napisz program, który wczytuje z wejścia liczby i oblicza, ile z
>> wcześniej wczytanych liczb było od nich mniejszych.
> 
> Zapamiętujesz te liczby w kolejności wczytania, więc trzeba
> przejrzeć wszystkie żeby sprawdzić ile było mniejszych 
> (za każdą następną wszystkie poprzednie). Można sprytniej,
> i na tym właśnie polega zadanie - najwięcej z niego wyniesiesz,
> jeśli sam wpadniesz na sposób zaoszczędzenia liczby porównań.

A później poznasz nazwę tego sposobu i stwierdzisz, że jego 
implementacja jest już w bibliotece standardowej Pythona :)

-- 
Tomasz "Eluś" Elendt :: http://geekspace.pl

Widzę, że ktoś spoja męczy ;)

import bisect as b
t = []
while True:
        try:
                x = int(raw_input())
        except EOFError:
                break

        b.insort_right(t, x)
        print b.bisect_left(t, x)


On 1 Maj, 16:16, tom...@orange.pl wrote:
> Witam,
> Proszę o pomoc z optymalizacją poniższego programu ponieważ wykonuje
> się za długo i spoj nie chce  go zaakceptować z powodu błędu "limit
> czasu został przekroczony".
>
> list=[]
> while 1:
>     try:
>         wejscie=input()
>     except EOFError: break
>     s=0
>     list.append(wejscie)
>     dl=len(list)
>     for i in range(dl):
>       if list[i]<wejscie:
>         s+=1
>     print s
>
> treść zadania:
> Napisz program, który wczytuje z wejścia liczby i oblicza, ile z
> wcześniej wczytanych liczb było od nich mniejszych.
>
> Wejście
> Na wejście programu podana zostanie pewna ilość (co najwyżej 25.000)
> rozdzielonych znakiem nowej linii liczb całkowitych (nie mniejszych
> niż -1.000.000.000 i nie większych niż 1.000.000.000).
>
> Wyjście
> Na wyjściu ma się pojawić ciąg liczb rozdzielonych znakiem nowej
> linii. i-ty element tego ciągu ma być równy ilości liczb, które
> zostały wczytane przed i-tą wczytaną z wejścia liczbą i są od niej
> mniejsze.
>
> Przykład
> Wejście:
>
>   1
>   2
>   3
>   4
>   5
>   6
>   3
>   4
>
> Wyjście:
>
>   0
>   1
>   2
>   3
>   4
>   5
>   2
>   4

Właśnie - co do SPOJa, mam takie pytanie - jak najlepiej wczytywać
wejście? Jestem całkiem świeży w Pythonie (ale już się zakochałem :))
i robię to w ten sposób:

s = sys.stdin.readline()
while s:
    s = sys.stdin.readline()

Widzę jednak, że badboy używa raw_input(), a tom input()
Chodzi mi konkretnie o te zadania, gdzie w pierwszej linii nie jest
podana ilość linii na wejściu i trzeba czytać aż do końca


On 5 Maj, 23:16, badboy <dev.c...@gmail.com> wrote:
> Widzę, że ktoś spoja męczy ;)
>
> import bisect as b
> t = []
> while True:
>         try:
>                 x = int(raw_input())
>         except EOFError:
>                 break
>
>         b.insort_right(t, x)
>         print b.bisect_left(t, x)
>
> On 1 Maj, 16:16, tom...@orange.pl wrote:
>
> > list=[]
> > while 1:
> >     try:
> >         wejscie=input()
> >     except EOFError: break
> >     s=0
> >     list.append(wejscie)
> >     dl=len(list)
> >     for i in range(dl):
> >       if list[i]<wejscie:
> >         s+=1
> >     print s

Dnia wtorek, 19 maja 2009 10:29, paffnucy@gmail.com napisał(a):
> Właśnie - co do SPOJa, mam takie pytanie - jak najlepiej wczytywać
> wejście? Jestem całkiem świeży w Pythonie (ale już się zakochałem :))
> i robię to w ten sposób:
> 
> s = sys.stdin.readline()
> while s:
>     s = sys.stdin.readline()
> 
> Widzę jednak, że badboy używa raw_input(), a tom input()
> Chodzi mi konkretnie o te zadania, gdzie w pierwszej linii nie jest
> podana ilość linii na wejściu i trzeba czytać aż do końca
> 
Pewnie w SPOJu najlepiej wczytać całe wejście na listę od razu (bo jest 
relatywnie małe, a potem łatwiej stosować list comprehension, operacje 
na całych listach jak sum() a nie pojedynczych elementach, ...)

Coś w stylu:
wejscie = map(int, sys.stdin.read().split())

| >>> map(int, "1 2\n3 \n  4  55\n".split())
| [1, 2, 3, 4, 55]

Ponadto imho warto poczytać o wyłączeniu gc i optymilizacji przez psyco, 
kiedy i na jakich warunkach da się zastosować.

-- 
Arkadiusz Kindziuk