Wie zeichne effizient genau N Punkte auf dem Bildschirm?

Das hört sich nach einer einfachen Frage an, aber ich finde es überraschend schwierig, mit guter Leistung recht zu kommen.Wie zeichne effizient genau N Punkte auf dem Bildschirm?

Der erste Algorithmus, den ich mir ausgedacht habe, ist das zufällige Zeichnen von Punkten, das Überprüfen, ob es bereits gezeichnet wurde, und das anderweitige Zeichnen. Dies funktioniert gut, wenn wir nur wenige Punkte ziehen, aber katastrophaler werden, wenn wir uns dem Bildschirm nähern.

Die beste, die ich kam, ist die Liste der Pixel zu konstruieren, mischen Sie es und wählen Sie die erste n (ich habe python's random.sample dafür verwendet). Es funktioniert besser, ist aber immer noch ein bisschen langsam, weil die ganze Liste von Pixeln im Speicher erstellt werden muss, was beim Zeichnen von 5 Punkten furchtbar übertrieben ist. Hier ist mein Python-Code:

#!/usr/bin/env python 
""" drawn n random points on the screen """ 
import pygame 
from pygame.locals import * 
import sys 
import random 
from itertools import product 

n = int(sys.argv[1]) 
s = pygame.display.set_mode() 
sx, sy = s.get_size() 

points = random.sample(list(product(range(sx), range(sy))), n) 

for p in points: 
    s.fill((255, 255, 255), pygame.Rect(*p, 1, 1)) 
pygame.display.flip() 
while True: 
    for event in pygame.event.get(): 
     if event.type == QUIT or event.type == KEYDOWN: 
      sys.exit()

Irgendwelche Vorschläge für einen besseren Algorithmus?

Bearbeiten: Gerade herausgefunden, dieses Problem wird "Reservoir Sampling" genannt. Wikipedia hat eine Reihe von guten Algorithmen: https://en.wikipedia.org/wiki/Reservoir_sampling

Quelle

2016-04-02 static_rtti

Auf den ersten Blick '(x, y) für (x, y) in' scheint nicht notwendig –

@ cricket_007: guter Punkt, das war ein Rest von einer ersten Version . Ich habe den Code in meiner Frage bearbeitet. –

Probe aus einer faulen Sequenz:

points = [(i // sy, i % sy) for i in random.sample(xrange(sx*sy), n)]

random.sample wird entscheiden, ob die Sequenz materialisieren und eine partielle Shuffle ausführen oder zufällige Elemente auswählen und ausgewählte Indizes bilden, basierend auf die relativen Größen der Sequenz und Probe.

Beachten Sie, dass es eine tatsächliche Sequenz statt eines Iterators sein muss, damit dies funktioniert. Entgegen der allgemeinen Meinung ist xrange (oder Python 3 range) eine tatsächliche Sequenz. Ein Generator würde hier nicht funktionieren.

Quelle

2016-04-02 21:59:52 user2357112

Wunderbar! Ich habe es mit einem Generator versucht, aber ich habe mich davon überzeugt, dass ein partielles Shuffle für einen Generator nicht sinnvoll ist. Ich wusste nicht, dass es einen Mittelweg zwischen einer Liste und einem Generator gab. Ihre Art, einen 2D-Bereich für einen eindimensionalen Bereich zu erstellen, ist auch sehr schön. –

Wenn Sie so viele Punkte zeichnen, dass Sie den Bildschirm ausfüllen, dann möchten Sie wahrscheinlich keine Liste von ihnen erstellen oder sich an alle die Sie gezeichnet haben erinnern.

Was Sie tun möchten, ist eine pseudozufällige, invertierbare Zuordnung zwischen Punkten zu erstellen. Rufen Sie das Mapping E(x,y) auf. Dann können Sie alle Punkte (x,y) in Scan-Zeile oder einer anderen Reihenfolge generieren, und dann für jeden Punkt (x,y), zeichnen Sie E(x,y) auf dem Bildschirm. Wenn Sie sicherstellen, dass das Mapping invertierbar ist, stellen Sie sicher, dass jedes eindeutige (x,y) auf ein eindeutiges E(x,y) mappt, so dass jeder Punkt, den Sie zeichnen, eindeutig ist.

Eine gängige Methode, eine Funktion wie E(x,y) zu machen, ist eine Feistel-Struktur zu verwenden: https://en.wikipedia.org/wiki/Feistel_cipher

Dies verwendet wird viele Verschlüsselungschiffren wie DIE machen.

In Ihrem Fall können Sie mit einem guten integer Hash-Funktion dieses Ausgangs tun H(x), dann W = die Bildschirmbreite und H = die Bildschirmhöhe gegeben, und N = die Anzahl der Runden zu verwenden (5ish tun wird),

function E(x,y) 
    for (i = 1 to N) 
     x = (x+(H(y)%W)) % W; 
     y = (y+(H(x)%H)) % H 
    return (x,y)

Beachten Sie, dass jeder Schritt ist leicht umkehrbar: Sie können Ihre Funktion wie folgt (Pseudo-Code, nicht python, sorry) machen. Wenn Sie y = (y+(H(x)%H)) % H rückgängig machen möchten, können Sie einfach y = (y-(H(x)%H)) % H tun (das ist Pseudocode, also kann ich so tun, als ob der Modulo-Operator mit negativen Zahlen richtig arbeitet).

Auch wenn die Funktion offensichtlich umkehrbar ist, weil jeder Schritt umkehrbar ist, stellt die Feistel-Struktur eine gute Durchmischung und Ihre Punkte werden in einem schönen Pseudo-Zufalls-Reihenfolge kommen, wenn Sie eine gute Hash H. verwenden

Quelle

2016-04-02 22:27:55

Danke, das sieht nach einem interessanten Ansatz aus. Ist es wirklich schneller als die angenommene Antwort? Die iterative Mapping-Funktion sieht teuer aus. –

Der Hauptvorteil ist, dass es viel weniger Speicher verwendet. Es wäre schneller als die angenommene Antwort, wenn es ausgewählte Indizes verfolgt, aber vielleicht ein bisschen langsamer, wenn es ein Array mischt ... bis Sie über einige Millionen Pixel erreichen und es dann wieder schneller wird, aufgrund von Cache-Effekten –

mir scheint, als würdest du mit dieser Antwort jedes Mal die selbe Stichprobe bekommen. Es gibt keinen offensichtlichen Ort, an dem du einen Samen oder einen Schlüssel oder irgendetwas einstecken würdest. – user2357112

Nun, Sie Vielleicht möchten Sie Stichprobenpunkte mit einem minimalen Abstand zwischen ihnen in Betracht ziehen, sodass sie sich nicht überschneiden. Es fällt mir die Poisson-Disk-Sampling ein. Beschreibung und Python-Code finden Sie hier: http://devmag.org.za/2009/05/03/poisson-disk-sampling/

Quelle

2016-04-02 22:48:41

Wie zeichne effizient genau N Punkte auf dem Bildschirm?

Antwort

Verwandte Themen