Ein np.array vorne mit 1en befüllen, hinten zuschneiden

mit matplotlib, NumPy, pandas, SciPy, SymPy und weiteren mathematischen Programmbibliotheken.
Karl-Heinz Hofmann
User
Beiträge: 11
Registriert: Dienstag 12. November 2019, 15:34

Dienstag 12. November 2019, 15:57

Es ist nicht so, daß ich das nicht hinkriege, aber die Performance ist lausig.
Es geht um ein Primzahlensieb.

1, 1, 1, 1, 1, 1, [0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
Ergebnis sollte so aussehen:
1, 1, 1, 1, 1, [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1], 1
oder so:
1, 1, 1, 1, [1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1], 1, 1

Das Sieb ist hier kurz dargestellt (Size = 4 x 7 = 28). In wirklichkeit ist es so um die 20 Mio´s lang.

Jemand ne Idee ? Gruß Kalli
__deets__
User
Beiträge: 6864
Registriert: Mittwoch 14. Oktober 2015, 14:29

Dienstag 12. November 2019, 16:01

Ich verstehe nicht, was du da erreichen willst. numpy ist nicht fuer eine solche Datenstruktur geeignet, bei der ein Element nicht eine Zahl, sondern wieder eine Liste ist. Und wozu genau soll das gut sein?
Karl-Heinz Hofmann
User
Beiträge: 11
Registriert: Dienstag 12. November 2019, 15:34

Dienstag 12. November 2019, 16:25

Oben ist das Sieb für die 7. Mein np.Array hat aber noch mehr Dimensionen (11, 13, 17 .... usw). Zum Schluß werden die Dimensionen mit fast_mul multipliziert und erzeugt so das Endsieb.
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1] (Die Dimension für die 11 zu filtern).
_______________<---------________________________________________________________ <---------
_________________n______________________________________________________________n
Concenate, stack, kopieren und append ist alles zu langsam.
Benutzeravatar
__blackjack__
User
Beiträge: 4681
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Dienstag 12. November 2019, 16:59

@Karl-Heinz Hofmann: Ich verstehe auch nicht was das werden soll.
“Give a man a fire and he's warm for a day, but set fire to him and he's warm for the rest of his life.”
— Terry Pratchett, Jingo
Sirius3
User
Beiträge: 10901
Registriert: Sonntag 21. Oktober 2012, 17:20

Mittwoch 13. November 2019, 09:51

@Karl-Heinz Hofmann: man hat nur einmal ein Sieb, das man nach und nach füllt. Sonst weiß man ja gar nicht, welche Primzahl als nächstes ausgesiebt werden soll.

Zeig doch mal Deinen Code, dann versteht man vielleicht besser, was Du machst.
Karl-Heinz Hofmann
User
Beiträge: 11
Registriert: Dienstag 12. November 2019, 15:34

Montag 18. November 2019, 20:14

for y in range (0,len(LP)):
z = 0
while XList[z] % LP[y] != 0:
z += 1
nkArray *= UrArray [y] [LP[y] - z : LP[y] - z + Sieblaenge]

Es geht eigentlich nur um zwei sehl lange (10 Mio (Sieblaenge) lange) Arrays mit 0 en und 1en die multipliziert werden. D.h. wenn eine 0 aus UrArray auf eine 1 aus nkArray trifft, so soll aus der 1 eine 0 in nkArray werden.
Eigentlich funzt der Code korrekt, nur es geht mir zu langsam.
Sirius3
User
Beiträge: 10901
Registriert: Sonntag 21. Oktober 2012, 17:20

Montag 18. November 2019, 20:50

Bei mir „funzt” da gar nichts, weil LP, XList, nkArray und UrArray oder Sieblaenge nicht definiert sind.
Ich verstehe auch immer noch nicht, wie Du daraus ein Sieb bauen willst. Nach welchem Algorithmus arbeitest Du?
Karl-Heinz Hofmann
User
Beiträge: 11
Registriert: Dienstag 12. November 2019, 15:34

Dienstag 19. November 2019, 11:05

Code: Alles auswählen

# -*- coding: utf-8 -*-
"""
Created on Wed May  8 18:33:37 2019

@author: Kalli Hofmann
"""

from timeit import default_timer as timer
import numpy

def array_attributes(a):
   for attr in ('ndim', 'size', 'itemsize', 'dtype', 'shape', 'strides'):
        print('{:8s}: {}'.format(attr, getattr(a, attr)))


def printArray(aArray):
  print(str(aArray[0,0:15])[0:-1] + "  ...  " + str(aArray[0,-15:])[1:] + " Size: " + str(aArray.size))
 

a = numpy.full((1, 100000000), 1, numpy.float)
for x in range (0,a.size):
    if x % 3 == 0 :
        a[0,x] = 0
        
b = numpy.full((1, 100000000), 1, numpy.float)
for x in range (0,b.size):
    if x % 5 == 0 :
        b[0,x] = 0

c = numpy.full((1, 100000000), 1, numpy.float)


print("vor der Multiplikation:")
printArray(a)
printArray(b)
printArray(c)
print()

start = timer()
c = a * b
duration = timer() - start

print("nach der Multiplikation:")
printArray(a)
printArray(b)
printArray(c)
print()
array_attributes(c)
print()
print("Sekunden gebraucht: " + str(duration))
Zuletzt geändert von Karl-Heinz Hofmann am Dienstag 19. November 2019, 11:21, insgesamt 1-mal geändert.
Karl-Heinz Hofmann
User
Beiträge: 11
Registriert: Dienstag 12. November 2019, 15:34

Dienstag 19. November 2019, 11:10

Hallo
Ich habs mal stark vereinfacht und sofort lauffähig gemacht. Jetzt zu meinem Problem: Das " c = a * b " geht mir zu langsam.
0,45 sek. zeigt er mir an. Für das Herstellen von a und b braucht er sehr viel länger. Ist aber unherheblich, da a und b nur einmal am Anfang
hergestellt werden und für den weiteren Gebrauch unverändert zur Verfügung stehen und immer wieder verwendet werden.
Gruß Kalli
Benutzeravatar
sparrow
User
Beiträge: 1487
Registriert: Freitag 17. April 2009, 10:28

Dienstag 19. November 2019, 11:33

Ohne zu verstehen warum du das tust (es erscheint mir wenig sinnvoll im Bezug auf deinen ersten Post) und ohne auch nur die geringste Ahnung von numpy zu haben:

Warum baust du Arrays aus Fließkommazahlen, wenn du dort nur Ganzzahlen hinein steckst? Der Unterschied ist dir bekannt?
Benutzeravatar
__blackjack__
User
Beiträge: 4681
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Dienstag 19. November 2019, 11:56

@Karl-Heinz Hofmann: Pro Multiplikation also nur etwas weniger als 4½ Nanosekunden. Warum/wofür ist das zu langsam?

Warum `float` für Werte die nur 1 oder 0 sein können? Mit `bool` braucht das bei mir nur 0.048534920962993056 Sekunden.

Warum ein `shape` das zwei Indizes für den Zugriff nötig macht, wo die Daten eigentlich nur eindimensional sind?

`c` wird unnötigerweise definiert weil der zuerst zugewiesene Wert nie verwendet wird.

Im Gegensatz zur Geschwindigkeit bei der Multiplikation kann man bei der Erstellung von `a` und `b` tatsächlich etwas machen, denn das ist massiv ineffizient.

Das zusammengestückel in der `print_array()`-Funktion (so sollte der Name nach Konvention geschrieben werden) ist unschön. Das ist eher BASIC als Python. Zudem ist es nicht schön/robust an der Zeichenkettenrepräsentation von Objekten rumzuschnibbeln.

Zwischenstand:

Code: Alles auswählen

#!/usr/bin/env python3
"""
Created on Wed May  8 18:33:37 2019

@author: Kalli Hofmann
"""
from timeit import default_timer as timer

import numpy


def array_attributes(array):
    for attr in ["ndim", "size", "itemsize", "dtype", "shape", "strides"]:
        print("{:8s}: {}".format(attr, getattr(array, attr)))


def print_array(array):
    with numpy.printoptions(edgeitems=15):
        print(f"{array} Size: {array.size}")


def main():
    size = 100_000_000
    a = numpy.full(size, True, numpy.bool)
    a[0::3] = False

    b = numpy.full(size, True, numpy.bool)
    b[0::5] = False

    print("vor der ”Multiplikation”:")
    print_array(a)
    print_array(b)
    print()

    start = timer()
    c = a & b
    duration = timer() - start

    print("nach der ”Multiplikation”:")
    print_array(a)
    print_array(b)
    print_array(c)
    print()
    array_attributes(c)
    print()
    print("Sekunden gebraucht: " + str(duration))


if __name__ == "__main__":
    main()
Und jetzt stelle ich mir natürlich die Frage ob/warum man hier überhaupt die Multiplikation oder die Und-Verknüpfung von zwei Arrays braucht die ein drittes Array erstellt‽ Wenn ich mit Numpy das Sieb des Erathostenes implementieren wollte, bräuchte ich genau *ein* Array, eine Schleife und die Zuweisung mit „slice“-Notation wie beim setzen der Werte mit durch 3 oder 5 teilbaren Indizes auf `False` im Beispiel oben.
“Give a man a fire and he's warm for a day, but set fire to him and he's warm for the rest of his life.”
— Terry Pratchett, Jingo
Sirius3
User
Beiträge: 10901
Registriert: Sonntag 21. Oktober 2012, 17:20

Dienstag 19. November 2019, 12:00

Für was brauchst Du denn bei einem "Sieb" a und b mehrfach?
`c` wird in Zeile 30 definiert aber nie benutzt, kann also weg.
Statt mit for-Schleifen solltest Du die Fähigkeiten von numpy zur Vektorrechnung nutzen:

Code: Alles auswählen

a = (numpy.arange(100000000) % 3) == 0
Wenn Du statt mit Floats mit Bools rechnest, geht die Multiplikation auch deutlich schneller.

Trotzdem hast Du immer noch kein Sieb. Beim Sieb braucht man nämlich KEINE Division oder Multiplikation. Deshalb ist es so schnell.
Mal als Ansatz:

Code: Alles auswählen

a = numpy.ones(100000000, dtype='u1')
a[2*2::2] = 0
Benutzeravatar
__blackjack__
User
Beiträge: 4681
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Dienstag 19. November 2019, 13:06

@Karl-Heinz Hofmann: Nur mal um zu zeigen das Python/Numpy da gar nicht so schlecht ist, hier mal die Multiplikation der 100 Millionen 64-Bit-Gleitkommazahlen in C:

Code: Alles auswählen

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 	100000000
#define timespec_to_seconds(ts)	(ts.tv_sec + ts.tv_nsec / 1e9)

void print_array(double *a, uint32_t size) {
	uint32_t i;
	
	putchar('[');
	for (i = 0; i < 15; ++i) printf("%.0f ", a[i]);
	printf("... ");
	for (i = 0; i < 15; ++i) printf("%.0f ", a[size - i - 1]);
	printf("] Size: %"PRIu32"\n", size);
}

int main(void)
{
	double *a, *b, *c;
	uint32_t i;
	struct timespec start, end;
	
	a = malloc(SIZE * sizeof(*a));
	b = malloc(SIZE * sizeof(*b));
	c = malloc(SIZE * sizeof(*c));
	
	for (i=0; i < SIZE; ++i) a[i] = b[i] = 1;
	for (i=0; i < SIZE; i += 3) a[i] = 0;
	for (i=0; i < SIZE; i += 5) b[i] = 0;
	
	clock_gettime(CLOCK_MONOTONIC, &start);
	for (i=0; i < SIZE; ++i) c[i] = a[i] * b[i];
	clock_gettime(CLOCK_MONOTONIC, &end);
	
	print_array(c, SIZE);
	printf("Sekunden für die Multiplikation: %f\n",
		timespec_to_seconds(end) - timespec_to_seconds(start));
	
	free(c);
	free(b);
	free(a);
	return 0;
}
Braucht 0.321240 Sekunden bei mir, gegenüber den 0.418104 Sekunden von Deinem Python-Code.
“Give a man a fire and he's warm for a day, but set fire to him and he's warm for the rest of his life.”
— Terry Pratchett, Jingo
Karl-Heinz Hofmann
User
Beiträge: 11
Registriert: Dienstag 12. November 2019, 15:34

Dienstag 19. November 2019, 16:10

Hallo Leute
Vielen, vielen Dank. Da sind ein Haufen guter Ideen drin. Das mit "Bool" bin ich heute Nachmittag selbst draufgekommen. Zuerst auf "int8" und dann mit "Bool" probiert. :-) Ihr fragt euch warum ich das Sieb nicht von vornherein konstruiere?
Also es geht um Mersenne Primzahlen, speziell um kleine Faktoren zu suchen. Dabei untersuche ich viele M´s hintereinander. Wenn ich z.B https://www.mersenne.ca/exponent/2917107953 = 2^2917107953 - 1 untersuche, kommen nur
folgende Faktoren in Frage: 2k * Exponent + 1 Für 2^2917107953 - 1 ist das so mit 5834215907. Der nächste mögliche 11668431813 . Diese Folge kann man auch sieben und folgt einer gewissen Regelmäßigkeit. Dennoch muß ich das Sieb bei jedem neuen Exponenten neu ausrichten. Ich hab unten nochmal das Ergebnis von heute Nachmittag gepostet und das ganze um zwei "Faktor Arrays" erweitert. Entschuldigt meinen schlechten Programmierstil. Python bringe ich mir erst seit einem halben Jahr selbst bei. Eigentlich bin ich Pascal-/Delphianer.
Karl-Heinz Hofmann
User
Beiträge: 11
Registriert: Dienstag 12. November 2019, 15:34

Dienstag 19. November 2019, 16:13

Code: Alles auswählen

# -*- coding: utf-8 -*-
"""
Created on Wed May  8 18:33:37 2019

@author: Kalli Hofmann
"""

from timeit import default_timer as timer
import numpy


def array_attributes(a):
   for attr in ('ndim', 'size', 'itemsize', 'dtype', 'shape', 'strides'):
        print('{:8s}: {}'.format(attr, getattr(a, attr)))


def printArray(aArray):
    Vorne = str(aArray[0:20])[0:-1]
    Hinten = str(aArray[-20:])[1:]
    Vorne = Vorne.replace(" True","1").replace("False","0").replace("\n","")
    Hinten = Hinten.replace(" True","1").replace("False","0").replace("\n","")
    print(Vorne + "  ...  " + Hinten + " Size: " + str(aArray.size))
 

Sieblaenge = 20000000

my_array = numpy.full((4, Sieblaenge), 1, numpy.bool)
for x in range (0,Sieblaenge):
    if x %  3 == 0:  my_array[0,x] = 0
    if x %  5 == 0:  my_array[1,x] = 0
    if x %  7 == 0:  my_array[2,x] = 0 
    if x % 11 == 0:  my_array[3,x] = 0   
res = numpy.full(( Sieblaenge), 1, numpy.bool)


print("vor der Multiplikation:")
printArray(my_array[0,:])
printArray(my_array[1,:])
printArray(my_array[2,:])
printArray(my_array[3,:])
printArray(res)
print()

start = timer()
res = my_array[0,:] * my_array[1,:] * my_array[2,:] * my_array[3,:]
duration = timer() - start

print("nach der Multiplikation:")
printArray(my_array[0,:])
printArray(my_array[1,:])
printArray(my_array[2,:])
printArray(my_array[3,:])
printArray(res)
print()
array_attributes(res)
print()
print("Sekunden gebraucht: " + str(duration))

Zuletzt geändert von Karl-Heinz Hofmann am Dienstag 19. November 2019, 16:28, insgesamt 1-mal geändert.
Antworten