or python - małe nieporozumienie

U mnie też działa szybko na kompie tak jak twój z tym, że nie na spoju

Nawet wpisanie mu na sztywno tablicy liczb pierwszych do 10000 nie pomogło, albo python za wolno przeszukuje tablice albo coś na spoju pier...ło (bo sam program ograniczał się do sprawdzania czy liczba z zestawu jest w gotowej tablicy).

Pastebin: http://4programmers.net/Pastebin/2275

To co robimy :D?

qweasda napisał(a):

To co robimy :D?

są różne możliwości, np:

1. pisz w szybszym języku, np cpp, dzisiaj dostałem tam 2.6s przy 5 sekundach limitu.
2. dorób do mojego kodu szukanie binarne, być może będzie wystarczająco szybko (a na pewno będzie dużo szybsze niż jest).

Innym w pythonie się normalnie udało... tam jest możliwośc wyświetlenia czasów najlepszych i języków i python bez problemu przechodzi, coś innego musi być prowodyrem tego.

Wiem, tyle że w "najnowszym" kodzie nic nie liczę, poza zestawami. Zresztą zauważ że czasy były malutkie, tak więc nie było czasu na sprawdzanie czy jakakolwiek liczba jest pierwszą, tylko na bardzo szybkie szukanie w gotowej tablicy podobnej do mojej. moja ma 1229 elementów, tak więc w skrajnie niekorzystnym przypadku binarne przeszukanie jej wymaga tylko 11 porównań.

Teraz to jest przecież slabo napisane... Szukanie bianarne albo lepiej hashmapa (dictionary). A z "tricków" zrób tą tablicę i cały kod wewnątrz jakiejś funkcji. W pythonie dostęp do zmiennych globalnych ma większy narzut niż dostęp do zmiennych lokalnych.

Nie mam konta na spoju, więc nie sprawdzę. Na moim komputerze program tworzy dictionary zawierający liczby pierwsze z przedziału [2,10000] w 0,02 sekundy. Potem tworzę losowo listę zawierającą 100000 liczb. Sprawdzenie, które są pierwsze zajmuje 0,15 sekundy.
Po kolejnych testach chyba wiem co jest błędem: wielokrotne wypisywanie. Winno być tak:

answer = ""
for i in test:
    if i in primes:
	answer+="TAK\n"
    else:
        answer+="NIE\n"	
print answer

(primes to słownik zawierający liczby pierwsze jako klucze).

    if i in primes:
        answer+="TAK\n"
    else:
        answer+="NIE\n"     

Sprawdzałeś czy/jak to działa?
Stringi są immutable w pythonie, więc taki algorytm ma złożoność kwadratową (o ile to nie zostanie np. zoptymalizowane, każde przypisanie w teorii tworzy nowy obiekt).
edit: Mówiąc inaczej, każde += potencjalnie kopiuje cały string do kompletnie nowego miejsca w pamięci, a poprzedni czeka na GC.

W tym przypadku można zastosować np. bytearray albo chociaż tradycyjną listę.

(Btw. IO jest prawie zawsze buforowane o ile nie idzie na konsolę, czyli tak jak na spoju)

edit: http://www.skymind.com/~ocrow/python_string/ (o szybkim łączeniu łańcuchów)

Jak by się zastanowić, to można by jeszcze przed sprawdzaniem w tablicy sprawdzić czy dzieli się bez reszty przez 2, od razu mniej szukania jakiegokolwiek.

answer=[]
for i in test:
    if i in primes:
	answer.append("TAK\n")
    else:
        answer.append("NIE\n")	
print ''.join(answer)

czas 2,5 sek.

answer = ""
for i in test:
    if i in primes:
	answer+="TAK\n"
    else:
        answer+="NIE\n"	
print answer

czas 2,4 sek.

"palnołem" tablicę z 2 wartościami czyli 0 (niepierwsza), 1 (pierwsza) a potem tylko if tab[liczba] == 1 pisz tak, else pisz nie. Dalej timeout. Na chwilę obecną skończyły mi się pomysły.

Przeczytaj mój przedostatni post. Twoje rozwiązanie jest złe, należy tylko raz wypisywać.

Triumf zbiorowego umysłu nad spojem, czyli zaliczone w Pythonie

import math

tab = [2, 3, 5]
tabwyn = [0, 0, 1, 1, 0, 1]
maxspraw = 5


def sprawdz(liczba):
    pierw = math.sqrt(liczba)
    i = 0
    while tab[i] <= pierw:
    #for i in tab:
        #if liczba % i == 0:
        if (liczba % tab[i]) == 0:
            tabwyn.append(0)
            return
        i += 1
    tab.append(liczba)
    tabwyn.append(1)
    return

ilezest = int(input())
wynik = ""
for i in range(0, ilezest):
    liczba = int(input())
    if liczba > maxspraw:
        for i in range(maxspraw + 1, liczba + 1):
            sprawdz(i)
        maxspraw = liczba
    if tabwyn[liczba] == 1:
        wynik = wynik + "TAK\n"
    else:
        wynik = wynik + "NIE\n"
wynik = wynik.rstrip("\n")
print (wynik)

 

Aczkolwiek poziom trudności "łatwy" raczej nie był, czas też marny. Z drugiej jednak strony python jest szybki w pisaniu kodu a nie jego działaniu.

Ja skonczyłem tak

from math import sqrt
def liczbapierwsza(i):            
        if (i > 5) and(i % 2 == 0 or i % 3 == 0 or i % 5 == 0):
                return("NIE\n")
        elif i == 1:
            return("NIE\n")
        else:
                for y in range(2,int(sqrt(i)) + 1):
                        if (i % y) == 0:
                                return("NIE\n")
                                break
                else:
                        return("TAK\n")
 
wynik = ""
for i in range(int(input())): 
        wynik = wynik + liczbapierwsza(int(input()))
print(wynik)