Gå til innhold

Effektiv minne bruk, iteratorer og primtall.


Gjest Slettet+9871234

Anbefalte innlegg

Gjest Slettet+9871234

Jeg er helt ny med Python. Dette

 

Tre poenger om iteratorer:

1. En iterator er "ikke-destruktiv", dvs. man kan ikke endre datastrukturen som den looper over via iteratoren selv. De kan derfor brukes til å gjøre data "read only". En annen måte å si dette på er: "En iterator er "enveis", data kan hentes ut, men ikke sendes inn.

 

2. En iterator har bevissthet - dvs, den vet og husker hvor i sekvensen den sist var. Du behøver ikke å holde rede på en indeks.

 

# åpne tekstfil med 4 linjer, med tall 0,1,2,3
tekstfil = open('poengsum.txt', 'r')

for line in range(2):
   print tekstfil.next()

>>> '0\n'
>>> '1\n'

# masse annen kode
for line in range(2):
   print tekstfil.next()

>>> '2\n'
>>> '3\n'

 

 

3. En iterator er ofte minne-effektiv. Et typisk eksempel her er svære filer. La oss si du har en log-fil på 1GB. Kode a la:

log_data = open('log.txt', 'r').read()

vil spise opp minnet. Ved å loope over filobjektet via den innebygde iteratoren vil du aldri bruke mer minne enn hver enkelt linje.

er meget interessant, jfr. min utheving.

 

Kilde: https://www.diskusjon.no/index.php?showtopic=592738

 

Så vidt jeg vet er grensen for en Python integer tilgjengelig minne (korriger meg om jeg tar feil). Her er koden jeg jobber med:

 

[b]# Prim3.py[/b]
#
# Kjell Bleivik 2010: www.kjellbleivik.com - www.oopschool.com - www.digitalpunkt.no, 
# 
# ---------------------------------------------------------------------------------------------------
#
# Opens the webdocument with The First 10,000 Primes, read the file and print the
# content. It functions for Python version 2.5, but not for version 3.1.2
#
# ---------------------------------------------------------------------------------------------------
#
import urllib
file = urllib.urlopen('http://primes.utm.edu/lists/small/10000.txt')
primes = file.read() 
print (primes)

 

 

#[b] Prim4.py[/b]
#
# Kjell Bleivik 2010: www.kjellbleivik.com - www.oopschool.com - www.digitalpunkt.no, 
# 
# ---------------------------------------------------------------------------------------------------
#
# Brute force prime number and prime number twin calculation. There ar no security net, exception
# handling in the code.  Note that all twin primes except (3, 5) are of the form: (nx6) +/- 1.  
# References:  http://mathworld.wolfram.com/TwinPrimeConjecture.html
# http://mathworld.wolfram.com/OftheForm.html
# 
# ---------------------------------------------------------------------------------------------------
print('This prgram is only valid for natural number between 1 and 1700')
print()
primes=[3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101] #Python inbuilt list
import math #import math module
n = int(input ('Enter a natural number between 1 and 1700 : '))
m1 = n*6 - 1
m2 = n*6 + 1
print()
limit=int(math.ceil(math.sqrt(m2))) + 1 #Ceiling of square root of number + 1
bool1=1
for prime in primes: #Loop through the list of known primes.       
       if prime <= limit:
          if m1 % prime == 0:  #Enough to test for prime factors up to the square root
              bool1=0 #No prime
              break #Break out of the loop if a prime factor is found.
if bool1 == 1:
   print (m1, ' is prime ')    
else:
   print (m1, ' is NOT prime ')
print()
bool2=1
for prime in primes: #Loop through the list of known primes.       
       if prime <= limit:
          if m2 % prime == 0:  #Enough to test for prime factors up to the square root
              bool2=0 #No prime
              break #Break out of the loop if a prime factor is found.
if bool2 == 1:
   print (m2, ' is prime ')    
else:
   print (m2, ' is NOT prime ')
print()
print()
enter=input('Hit enter ') #Prevent output window from closing.

 

Problemer:

  1. Prim3.py virker med Python 2.5, men ikke med Python 3.*. Kan hende mangler jeg noen eksterne biblioteker siden Python 2.5 ble installert fra en tredje parts side med mange utvildelser og eksterne bibilioteker.
  2. Beytte den mest minneeffktive metoden og iterere over filobjektet som antydet i innledningen.
  3. Hvordan kombinere Prim3.py og Prim4.py slik at kjente primtall leses inn fra den angitte eller egen nettside. Filtrere bort tekst i innledningen til filen på nettsiden.
  4. Beregne enda større primtall som lagres til text / html file.

Endret av Slettet+9871234
Lenke til kommentar
Videoannonse
Annonse
log_data = open('log.txt', 'r').read()

vil spise opp minnet. Ved å loope over filobjektet via den innebygde iteratoren vil du aldri bruke mer minne enn hver enkelt linje.

Ja read() leser log.txt inn til minnet.

Python bruker alt minne som er tilgjengelig.

 

for line in range(2):

print tekstfil.next()

En bedre måte og mer vanelig.

Leser kun line for line inn til minnet.

for i in open('poengsum.txt'): # r is default mode
   #Do something with i
   print i,

 

Med python 2.5 kom "with" statement

"with" gjør feilbehandling(try,except) og lukker filobjektet i en operasjon.

with open('poengsum.txt') as my_file:
   for line in my_file:
       print line,

 

Så vidt jeg vet er grensen for en Python integer tilgjengelig minne (korriger meg om jeg tar feil)

Ja stemmer.

 

#Python 2.x
import urllib

#Leser hele filen inn til minnet
file = urllib.urlopen('http://primes.utm.edu/lists/small/10000.txt').read()
print primes

# Leser 1 og 1 line in til minnet
file = urllib.urlopen('http://primes.utm.edu/lists/small/10000.txt')
for i in file:
   print i,

 

Prim3.py virker med Python 2.5, men ikke med Python 3.*. Kan hende mangler jeg noen eksterne biblioteker siden Python 2.5 ble installert fra en tredje parts side med mange utvildelser og eksterne bibilioteker.

urllib.urlopen() har blitt fjernet i python 3.x

Erstattet med urllib.request.urlopen

http://diveintopython3.org/porting-code-to-python-3-with-2to3.html

 

De fleste bruker python 2.x ennå og sånn vil det være noen år,til mange av de store 3 parts bibliotekene er skrevet om.

 

#python 3.x
import urllib.request

file = urllib.request.urlopen('http://primes.utm.edu/lists/small/10000.txt')
primes = file.read().decode("utf8")
print (primes)

 

Hvordan kombinere Prim3.py og Prim4.py slik at kjente primtall leses inn fra den angitte eller egen nettside. Filtrere bort tekst i innledningen til filen på nettsiden.

 

import urllib.request

file = urllib.request.urlopen('http://primes.utm.edu/lists/small/10000.txt')
primes = file.read().decode("utf8")

my_primes = []
for i,line in enumerate(primes.split('\n')):
   if i > 3 and i < 1004:
       temp = ((int(item) for item in line.split()))
       for i in temp:           
           my_primes.append(i)

print (my_primes)
#You can take out number you want.
#10 first prime number
print (my_primes[0:10]) 

Endret av SNIPPSAT
Lenke til kommentar

Takk for raskt svar. Er helt ny til Python.

 

Apropos primtall spesifikt.

 

Jeg vet ikke hvilke behov du har, men det finnes en måte å bytte lagringsplass mot tid i tilfellet med primtall. Miller-Rabin er en veldig kjent probabilistisk algoritme for å avgjøre om et gitt tall sannsynligvis er et primtall. For tall < 2^32 finnes det en spesialutgave av Miller-Rabin som alltid gir riktig svar og kun med 3 testkandidater. Mao. man har en rask algoritme som er enkel å implementere og bruker konstant plass (var ganske nyttig i projecteuler-sammenheng).

 

edit: trykkfeil

Endret av zotbar1234
Lenke til kommentar

my_primes = []
for i,line in enumerate(primes.split('\n')):
   if i > 3 and i < 1004:
       temp = ((int(item) for item in line.split()))
       for i in temp:           
           my_primes.append(i)

 

Jeg synes det virkelig litt forvirrende å bruke i som teller for begge løkkene. Men det til side, hvorfor ikke:

 

my_primes.extend(int(item) for item in line.split()
                if 3 < i < 1004)

 

?

Lenke til kommentar
Gjest Slettet+9871234

Takk for nyttige innspill. Jeg gjør dette:

  1. Først og fremst for å lære Python.
  2. Og samtidig lære mer om temaet. Jeg kjenner noen av disse algoritmene. Nå er det ikke på dette stadiet viktigt å bruke den mest effektive algoritmen om ikke nye programmeringsutfordringer oppstår.
  3. Men for all del, kom gjerne med innspill om bedre algoritmer. Alle lærer av det.
  4. Lære Python og Django for et alternativt verktøy til webutvikling med PHP.
  5. Kunne kombinere Python og C / C++. Det er slik jeg har forstått det en god kombinasjon.
  6. etc.

Har så vidt skummet innholdet i noen bøker og ettersom jeg nå kan løse enkle oppgaver i Python, ser jeg også at det er et meget godt valg som første språk å lære seg og pedagogisk til å lære barn programmering. Python ligger kort sagt, slik jeg ser det, nært et pseudo språk.

 

Enda et problem som jeg nok kan finne ut av selv, men dere kan tydligvis mer enn jeg kan lære på noen timer og dager.

 

Har lest noe om "Generator expressions" som er nytt for meg. Har forstått at det kan gjøre programmer mer effektive, så hva er det og kan det brukes i det primtallsproblemet som nevnes her?

 

Og er det lett å integrere PyGames og NumPy i Python 3.*? Har begge for versjon 2.5, så er der kompatibilitetsproblemer med den siste versjonen av Python som jeg akter å bruke i eventuelle prosjekter.

 

Til slutt, siden han som lagde Python nå jobber for Google, antagelig med deres eget Go språk, lurer jeg på hvor brukervennlig det er i forhold til Python.

 

Her er Go kode for "a concurrent prime sieve":

// A concurrent prime sieve
// See "Prime Numbers" section of the tutorial:
// http://golang.org/doc/go_tutorial.html
package main
// Send the sequence 2, 3, 4, ... to channel 'ch'.
func Generate(ch chan<- int) {
for i := 2; ; i++ {
 ch <- i // Send 'i' to channel 'ch'.
}
}
// Copy the values from channel 'in' to channel 'out',
// removing those divisible by 'prime'.
func Filter(in <-chan int, out chan<- int, prime int) {
for {
 i := <-in // Receive value from 'in'.
 if i%prime != 0 {
  out <- i // Send 'i' to 'out'.
 }
}
}
// The prime sieve: Daisy-chain Filter processes.
func main() {
ch := make(chan int) // Create a new channel.
go Generate(ch)      // Launch Generate goroutine.
for i := 0; i < 10; i++ {
 prime := <-ch
 print(prime, "\n")
 ch1 := make(chan int)
 go Filter(ch, ch1, prime)
 ch = ch1
}
}

Kilde: http://golang.org/ Se nede til venstre.

 

Relatert:

 

http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html

 

Which is the fastest algorithm to find prime numbers?:

http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers

 

Uansett, takk for glimrende innspill så langt.

Endret av Slettet+9871234
Lenke til kommentar
Men for all del, kom gjerne med innspill om bedre algoritmer. Alle lærer av det.

Dette er den raskte prime tall generatoren jeg kom frem til når jeg testet dette for en stund siden.

Bruker psyco og sieveOfErat.

Dette er en bra tid på 100000000 prime nummere ned mot C/C++ fart.

 

import math
import time
import psyco
psyco.full()

start = time.clock()
def sieveOfErat(end):
       if end < 2: return []   
       lng = ((end/2)-1+end%2) 
       sieve = [True]*(lng+1)  
       for i in range(int(math.sqrt(end)) >> 1):               
               if not sieve[i]: continue               
               for j in range( (i*(i + 3) << 1) + 3, lng, (i << 1) + 3):
                       sieve[j] = False        
       primes = [2]     
       primes.extend([(i << 1) + 3 for i in range(lng) if sieve[i]])   
       pri = primes[-1]
       return pri

if __name__ == '__main__':    
   prime_nr = 100000
   print sieveOfErat(prime_nr)
   end = time.clock()
   print '%s prime number in %.3f seconds' % (prime_nr, end - start)

'''
My output-->
99999989
100000000 prime_numbers with python in 7.923 seconds
'''

Har lest noe om "Generator expressions" som er nytt for meg.

Generator expressions ligner på list comprehensions.

 

Grei info.

Basically, use a generator expression if all you're doing is iterating once. If you want to store and use the generated results, then you're probably better off with a list comprehension.

 

Since performance is the most common reason to choose one over the other, my advice is to not worry about it and just pick one; if you find that your program is running too slowly, then and only then should you go back and worry about tuning your code.

 

Iterating over the generator expression or the list comprehension will do the same thing. However, the list comp will create the entire list in memory first while the generator expression will create the items on the fly, so you are able to use it for very large (and also infinite!) sequences.

 

Litt kode jeg satte sammen som viser litt om Generator expressions.

>>> #list comprehensions
>>> even = [x for x in range(10) if x % 2 == 0]
>>> even
[0, 2, 4, 6, 8]
>>> #Generator expressions
>>> even = (x for x in range(10) if x % 2 == 0)
>>> even
<generator object <genexpr> at 0x04B3BCD8>
>>> even.next()
0
>>> even.next()
2
>>> #Generator expressions make a generator object that we have to iterating over
>>> for i in even:
...     i
...     
4
6
8
>>> #Just to break upp the list comprehensions if you havnet look to much at it
>>> even_list = []
>>> for x in range(10):
...      if x % 2 == 0:
...          even_list.append(x)
...          
>>> even_list
[0, 2, 4, 6, 8]
>>> 

Og er det lett å integrere PyGames og NumPy i Python 3.

Numpy og pygame virker begge for python 3.

The release version 1.5 of NumPy is compatible with Python versions 2.4--2.7 and Python 3

Til slutt, siden han som lagde Python nå jobber for Google, antagelig med deres eget Go språk, lurer jeg på hvor brukervennlig det er i forhold til Python.

Guido har nok ikke så mye med go og gjøre,han holder seg nok til python.

Har ikke fått sett så mye på go ennå.

Jeg synes det virkelig litt forvirrende å bruke i som teller for begge løkkene. Men det til side, hvorfor ikke:

Er enig med dine konklusjoner her.

Bruke "i" i begge for loopene er en litt gammel vane,og jeg skulle ha brukt forskjellige navn.

Endret av SNIPPSAT
Lenke til kommentar
Gjest Slettet+9871234

Dette er en bra tid på 100000000 prime nummere ned mot C/C++ fart.

Har du C / C++ versjoner av programmet?

 

Er enig med dine konklusjoner her.

Bruke "i" i begge for loopene er en litt gammel vane,og jeg skulle ha brukt forskjellige navn.

:-)

 

Nok et spørsmål. Kjenner dere http://curl.haxx.se/ som finnes for PHP, C, C++ Python etc?

 

Glimrende til å skrive sine egne boter til kvalitetssikring av egne sider samt mye mer.

 

urllib.urlopen() har blitt fjernet i python 3.x

Erstattet med urllib.request.urlopen

 

Kan urllib erstatte Python versjonen av cURL?

 

Igjen takk for inspill.

Endret av Slettet+9871234
Lenke til kommentar

Nei ikke noe lagret.

http://code.activestate.com/recipes/576559-fast-prime-generator/

Har søkt en del på dette før,og tiden i python står seg bra.

Pysco hjelper klart til en god del.

 

Kan urllib erstatte Python versjonen av cURL?

Gjør nok mye av det samme oppgavene,hva som er rett til hvilken jobb kan nok variere.

 

Python har mye bra verktøy når det gjelder og jobbe mot nettet.

urllib,urllib2, og 3 parts urllib3

urllib + urllib2 er slått sammen til kun urllib i python 3.

 

mechanize kan også nevnes.

Scrapy et web crawling framework

BeautifulSoup er en av mine favoritter når det gjelder og ta ut info fra websider.

Skrev litt om dette i denne posten.

https://www.diskusjon.no/index.php?showtopic=1263992

 

* urllib2 is found in every Python install everywhere, so is a good base upon which to start.

 

* PycURL is useful for people already used to using libcurl, exposes more of the low-level details of HTTP, plus it gains any fixes or improvements applied to libcurl.

 

* mechanize is used to persistently drive a connection much like a browser would.

 

It's not a matter of one being better than the other, it's a matter of choosing the appropriate tool for the job.

Endret av SNIPPSAT
Lenke til kommentar
Gjest Slettet+9871234

Da greier du gjerne å knekke denne:

 

Denne

 

http://www.socialnorway.com/ProAJAX/content.htm

 

siden som virket tidligere:

 

Det er filen Newsticker.php som gir feil. Samme skjer med ulike feeds. Kan det ha skjedd noe med header informasjon etc.

 

Feilmelding i Opera 10.63

 

XML-parsing mislyktes

 

XML-parsing mislyktes: syntaksfeil (Linje: 1, Tegn 0)

 

IE 6.* (en grunn til at jeg bruker den stein alder gamle browseren :roll: ) feilmelding:

 

XML-siden kan ikke vises

Kan ikke vise XML-inndata ved hjelp av -stilark. Rett opp feilen og velg deretter Oppdater eller prøv på nytt senere.

 

 

--------------------------------------------------------------------------------

 

XML-dokumentet må ha et toppnivåelement. Feil under behandling av ressursen http://www.socialnorway.com/ProAJAX/Chapter7/Ne...

 

Her er en forum post om samme problem fra boken koden ble klippet fra:

 

http://p2p.wrox.com/book-professional-ajax-isbn-978-0-471-77778-6/41354-news-ticker.html

 

Mye likt denne:

 

http://www.yaldex.com/ajax-tutorial-4/BBL0053.html

 

Dersom du ikke knekker problemet, kan jeg poste hele koden i neste innlegg.

 

Vil helst unngå å bruke denne

 

http://www.jquerynewsticker.com/

 

jQuery tickeren.

 

Ikke testet i FF eller Chrome, da jeg foretrekker Opera.

 

Det er muligens lett i Python, men om man skal publisere Python kode på nettet trenger man vel også å kunne Django.

Endret av Slettet+9871234
Lenke til kommentar
  • 2 uker senere...
Gjest Slettet+9871234
Men for all del, kom gjerne med innspill om bedre algoritmer. Alle lærer av det.

Dette er den raskte prime tall generatoren jeg kom frem til når jeg testet dette for en stund siden.

Bruker psyco og sieveOfErat.

Dette er en bra tid på 100000000 prime nummere ned mot C/C++ fart.

Kjenner ikke Python godt nok til å oversette den koden direkte til C-kode.

 

Her er en enkel C versjon av min tallknuser algoritme:

 

/*
Brute force prime number computation
*/

#include <stdio.h>
#include <math.h>

#define MAX_DIM 10000

int main(void)
{
int primes[MAX_DIM]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};//#[15]Last
int k=16;  //Next index in primes array.
int j;
int r;
for (j= 54; j < 10000; j++){
	int i, m;
	int test=0;
	m=(int) sqrt(j) +1; //Enough to check up to sqrt(j).
	for (i=0; primes[i] < m; i++) {
		if ((j % primes[i])==0){ //j is not prime.
                               test=0;
			break;
		}
		else {
			test=1;
		}
	}
	if (test==1) {
		primes[k]=j;  //j is prime.
		k++;
               }
}

printf("\n\n");
printf("Prime numbers up to 10000: ");
printf("\n\n");
for (r= 0; r < k; r++)
	printf("%6d%c", primes[r], (r%10==9 || r==k-1) ? '\n' : ' ');
printf("\n\n");
       return 0;
}

som det skulle være enkelt å generalisere til unsigned long, mer effektive formler etc.

 

Python er jo et C-bibliotek, så det kunne jo vært greit å vite hvordan int typen er definert der. Embeddes den typen i C, skulle det være raskt å beregne store primtall i c.

 

Der er en grunn til at kombinasjonen Python / C / C++ / ASM er logisk.

 

Python forenkler C. C++ utvider C. ASM kan brukes til kritisk inline tallknusing.

Endret av Slettet+9871234
Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Du må være et medlem for å kunne skrive en kommentar

Opprett konto

Det er enkelt å melde seg inn for å starte en ny konto!

Start en konto

Logg inn

Har du allerede en konto? Logg inn her.

Logg inn nå
×
×
  • Opprett ny...