Back-und-Forth Linespace Generator

Ich bin auf der Suche nach einer Generatorfunktion, die Punkte entlang einer Linie gibt, mit einem Mindestabstand von k. Das ist einfach genug, und kann mit numpy erfolgen wie folgt:Back-und-Forth Linespace Generator

points = np.linspace(start, end, k)

Allerdings mag ich die Punkte als eine Art „zunehmende Auflösung“ zu erzeugen, das so auf einer Linie von 0 bis 1, die Generator ergäbe:

1/2, 1/4, 3/4, 1/8, 3/8, 5/8, ...

Auch dies leicht genug ist, rekursiv zu tun (nur die Endpunkte akzeptieren und auf jeder Hälfte selbst nennen), aber ich würde einen Generator wie für die gleiche Sache, ohne erzielen zu füllen ein Array mit allem von Anfang an und ohne doppelte Punkte.

Was wäre der beste Weg, dies zu tun?

Quelle

2017-12-27 Teknophilia

Hat 5/8 auf 3/8 folgen? Es gibt einen bekannten Algorithmus, um eine Sequenz mit 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16 usw. zu erzeugen. Dies wird als gut angesehen Weg zur Pseudo-Monte-Carlo-Integration. –

@ WillemVanOnsem, ja, ich glaube, das ist etwas, das "Lost Cow Algorithm" genannt wird? Die Generierung der Punkte 3/8, 4/8, 5/8 wäre einfacher, hätte aber redundante Punkte. Dies könnte leicht gelöst werden, indem man gegen eine Menge prüft, aber wenn es eine Möglichkeit gibt, keine redundanten Punkte an erster Stelle zu erzeugen - vorausgesetzt, dass dies schneller ist als die Verwendung einer Menge -, wäre das am besten. – Teknophilia

nein, der obige Satz enthält keine Duplikate. Nur wenn sich der Nenner ändert, wird die * Reihenfolge * der Werte nicht erhöht. Aber es erzeugt die gleichen Punkte ohne Duplikate. –

Ein Weg, dies zu erreichen, ist durch die Verwendung:

def infinite_linspace(): 
    den = 2 
    while True: 
     for i in range(1,den,2): 
      yield i/den 
     den <<= 1

Hier also wir mit dem Zähler 1-den-1 (einschließlich) durchlaufen, und dann die doppelten Nenner.

Die ersten 15 Nummern sind dann:

>>> list(islice(infinite_linspace(), 15)) 
[0.5, 0.25, 0.75, 0.125, 0.375, 0.625, 0.875, 0.0625, 0.1875, 0.3125, 0.4375, 0.5625, 0.6875, 0.8125, 0.9375] 
>>> [1/2,1/4,3/4,1/8,3/8,5/8,7/8,1/16,3/16,5/16,7/16,9/16,11/16,13/16,15/16] 
[0.5, 0.25, 0.75, 0.125, 0.375, 0.625, 0.875, 0.0625, 0.1875, 0.3125, 0.4375, 0.5625, 0.6875, 0.8125, 0.9375]

wir noch mehr Intelligenz in sie setzen können die i -te Element relativ schnell auch zu erhalten:

class Linspace: 

    def __iter__(self): 
     den = 2 
     while True: 
      for i in range(1,den,2): 
       yield i/den 
      den <<= 1 

    def __getitem__(self, idx): 
     if not isinstance(idx, int): 
      raise TypeError('idx should be an integer') 
     if idx < 0: 
      raise ValueError('idx should be positive') 
     den = denn = idx+1 
     denn |= den >> 1 
     while den != denn: 
      den = denn 
      denn |= denn >> 1 
     denn += 1 
     return (2*idx+3-denn)/denn

So wir jetzt kann in logarithmischer Zeit zum Beispiel das 10-te, 15-te und 123'456-te Element zugreifen:

Quelle

2017-12-27 21:21:41

Das ist genau das, wonach ich suche. Jetzt sehe ich, dass ich vergessen habe, den Nenner innerhalb der Schleife zu verdoppeln. Danke vielmals! – Teknophilia

Hier ist eine kürzere, Pseudo-O (1) Art und Weise direkt das i-te Element der Berechnung:

def jumpy(i): 
    i = (i<<1) + 3 
    return i/(1<<i.bit_length()-1) - 1 

list(map(jumpy, range(15))) 
# [0.5, 0.25, 0.75, 0.125, 0.375, 0.625, 0.875, 0.0625, 0.1875, 0.3125, 0.4375, 0.5625, 0.6875, 0.8125, 0.9375]

Quelle

2017-12-27 22:35:37

Back-und-Forth Linespace Generator

Antwort

Verwandte Themen