Python

[Python-Nichtskönner]

Ich will ich in einem zweiten Programm nur einen bestimmten Code speichern, bei dem mindestens einmal drei gleiche Kombinationen nebeneinander stehen. Also ...,ACCA, ACCA, ACCA, ...

Das Programm zum erstellen und speichern aller Kombination lautet:


import random
Bausteine = 4
Kombinationen = 100000
buchstaben = ["A", "C", "G", "T"]
hinzu = ""
for i in range(Kombinationen):
for j in range(Bausteine):
buchstabe = random.choice(buchstaben)
hinzu += buchstabe
hinzu += " "
with open("Frankensteinspeichern.txt", "w") as f:
f.write(hinzu)

Jetzt will ich allerdings dieses Programm so umschreiben, dass nur drei gleiche Kombinationen gespeichert werden

[__blackjack__]

@Python-Nichtskönner: Das ist extrem ineffizient und Du hast Glück, dass CPython eine Optimierung beim addieren von Zeichenketten eingebaut hat, auf die man sich aber nicht verlassen kann/darf. Insgesamt wird da eine halbe Million mal *ein* Zeichen mit einer immer grösser werdenden Zeichenkette addiert. Da Zeichenketten nicht veränderbar sind, heisst das es wird jedes mal eine neue Zeichenkette erstellt in die beide Zeichenketten kopiert werden, und dann werden die beiden alten Zeichenketten freigegeben. Die immer grösser werdenden Daten werden also immer wieder im Speicher umherkopiert. Die Datenmenge die da im Speicher bewegt werden muss ist also 500.000! also 1·2·3·4·…·500.000. Das ist eine Zahl mit 2.632.336 Stellen. Das Programm würde also ohne den Kniff den CPython anwendet, *seeeehr* lange laufen. Man sammelt deswegen Teilzeichenketten in einer Liste (oder lässt sie durch einen Generator/Iterator ”lazy” erzeugen) und verwendet die `join()`-Methode auf Zeichenketten um sie effizient zusammenzusetzen. (Was ich in den JavaScript- und Io-Lösungen zu dieser Aufgabe auch so gemacht habe.)

Die Abwandlung der Aufgabe ist mir nicht klar. Sollen da 100.000 vierstellige Zufallszeichenketten erzeugt werden und das solange bis mindestens drei gleiche aufeinanderfolgen? Oder soll das irgendwie forciert werden? Sind dabei irgendwelche Wahrscheinlichkeiten wichtig?

[__blackjack__]

Falls die Interpretation mit mindestens drei gleiche aufeinanderfolgende vierstellige Zufallszeichenketten richtig sein sollte, man ein anderer Ansatz die zu generieren. Diesmal im Scheme-Dialekt Racket.

Eine Zeichenkette mit vier zufälligen Werten aus vier möglichen Zeichen zu bilden hat 256 mögliche Ergebnisse. Also ein Bytewert. Man könnte also auch 100.000 zufällige Bytes generieren, da dann mit einem regulären Ausdruck prüfen ob mindestens drei aufeinander folgende Werte vorhanden sind, und wenn man so eine Variante gefunden hat, kann man die Bytes in die vierstelligen Zeichenketten wandeln. Hier wie gesagt in Scheme, aber das Prinzip lässt sich auch leicht in Python umsetzen:

Code: Alles auswählen

#!/usr/bin/env racket
#lang racket
(require racket/random)

(define *alphabet* "AGCT")

(define (byte->string b)
  (build-string 4
                (lambda [i]
                  (let ([j (* i 2)])
                    (string-ref *alphabet* (bitwise-bit-field b j (+ j 2)))))))

(define (data->string data)
  (string-join (for/list ([b data]) (byte->string b)) " "))

(define (check-repetition data)
  (regexp-match? #px"(.)\\1{2}" data))

(displayln
 (for/last ([data (in-producer (lambda [] (crypto-random-bytes 100000)))]
            #:break (check-repetition data))
   (data->string data)))