Nutze ich ein Array und wie?

[KlausP]

Hi liebes Team,
früher hatte ich mal ein wenig mit Basic und Pascal programmiert. Jetzige Aufgaben sind "just for fun"
Ich würde ein 2 dim Array erstellen wollen.
Aber meine Windows Python Installation (3.8.3) kann „np as numpy“ nicht finden / importieren.
Wie ich das lösen?

Ich beschreib nachstehend mal kurz mein Prpjekt, falls die Struktur von Belang sein sollte:

Vorgegeben sind z.B. 3 ... 7 Buchstaben: A1, A2 ... A7 ( z.B. "A", "E" , "G", "H", "T", "I", "D")
Ich möchte Kombinationen aus zunächst 3-stelligen, und zuletzt 7 stelligen Wörtern bilden.
Ich würde anfangen mit A1, A2, A3 an der Spalte x = 0.
Und Kombinationen bilden:
A1 A2 A3
A1 A3 A2
...
A3 A2 A1
und in einer Matrix ( = Array?) in Spalten [0,1,2] speichern.

Dann die Kombinationen nun mit A2, A3, A4 bei x = [1,2,3] hinterlegen; u.s.w bis A5, A6, A7.
Desweiteren kämen die 4-stelligen Kombinationen (A1 , A2, A3, A4), startend bei x= 0, 1, 2, 3
Entsprechend zuletzt die Kombinationen mit 5, 6 und 7 Stellen.

Auf weiterer Ebene soll die Matrix indiziert sein, ob sie nämlich aus 3, 4, 5, 6 oder 7 - stelligen Wörtern besteht.

Nun wird die Matrix mit einer Wortliste verglichen.
Hat die Matrix an einer Stelle einen Treffer mit der Wortliste, dann wird die Matrix noch mi einem "L = true" wie Lösung indiziert.

Am Ende können wählweise, bzw nacheinander 3 oder bis zu 7 stellige Lösungen ausgeben werden.

Vom programmteschnischen Ansatz stelle sich mir eine Matrix vor:
A1 .. A7, L, T …. für die Zeilen m von 1 bis n
In L sehe ich, ob ein 3, 4, 5, 6 oder 7stelliges Wort gebildet wurde.
T zeigt einen Treffer mit der Wortliste an.

Nun würde ich ein Array in dieser Form füllen wollen:
matrix : [T (true/false), länge(3 ...7), spalte(1 ... 5)] [zeile (m = 1 ....n)]

Habt ihr evtl. weitere bzw. andere Hinweise?

[__blackjack__]

@KlausP: Den Import zu lösen sind zwei Schritte: 1. Numpy installieren, 2. dann auch richtig importieren, also `numpy`, so heisst das nämlich, und nicht `np`. Man kann das beim Importieren dann zu `np` umbenennen wenn man möchte, also ``import numpy as np``.

Dann stellt sich aber die Frage ob Arrays hier die richtige Datenstruktur sind, oder ob verschachtelte Listen es nicht auch tun. Numpy nutzt man wenn man Numpy dann auch tatsächlich nutzt, also die vektorisierten *Rechen*operationen mit den Arrays nutzt. Und da haben dann in aller Regel alle Elemente in einem Array den gleichen Datentyp. Es gibt auch „record arrays“, aber dann ist man meistens schon bei Aufgaben für die man die Pandas-Bibliothek verwendet.

Aus der Beschreibung wird mir nicht klar *was* Du da eigentlich machen willst. Du solltest auch eher das Problem beschreiben und nicht die Lösung mit Arrays, denn es ist ja gar nicht gesagt das Arrays hier das richtige Mittel sind.

Was ich beispielsweise komisch finde ist, dass es sich so anhört als wären die Einträge sehr regelmässig/generiert. Da stellt sich dann auch gleich die Frage ob man die überhaupt generieren muss, oder ob man nicht auch ”rechnerisch” bestimmen kann ob und wo ein Wort in so einer Matrix stehen würde, wenn man sie denn tatsächlich generieren würde. Und statt etwas als Lösung zu markieren, könnte man auch eine Menge mit Lösungen haben. Oder falls es erforderlich ist effizient auf alle Lösungen einer bestimmten Länge zugreifen zu können ein Wörterbuch das die Länge auf eine Menge mit Lösungen abbildet.

[KlausP]

@ blackjack : schön wieder von dir zu lesen

zu verschachtelten listen:
habe ich vorhin versuchen wollen ...
nun muss ich doch ins Detail gehen:

nehmen wir z.B. gegebene Buchstaben aus dem Hut:
E I N T E
Wenn man alle Kombinationen aus diesen Buchstaben durchspielt, bekommt man u.A. EIN, NIE, NIET, ENTE, TEN.

Mein erstes Problem z.Z.
Wie mische ich die Buchstaben EINTE, sodass alle Kombinationen gebildet werden
zunächst die 3-stelligen (EIN, ENI, IEN, INE, NEI, NIE / INT, ITN, NIT, NTI, TIN, TNI / NTE, NET, TNE, TEN, ENT, ETN)

Vorher / hinterher lese ich ein Wörterbuch ein mit z.B. 8000 3 bis 7 stelligen Wörtern.
Per Vergleich mit dem Wörterbuch soll "er" dann z.B. finden
3-stellige wie EIN, NIE, TEN
4-stellige wie NIET, ENTE, EINE

Dann per Abfrage:
zeig mir alle Lösungen mit "I" an zweiter Stelle
oder 4-stellige mit z.B. "E" an letzter Stelle (oder eine Maske)

soweit erstmal.
Möchte das ja gerne selbst bewerkstelligen; aber ohne Hilfe müsste ich jetzt wohl erstmal 2 Semester studieren .... aber was?
(Mathematik oder Python oder beides)

[__blackjack__]

@KlausP: Aber dafür braucht man doch die ganzen Kombinationen aus den Wörtern gar nicht generieren. Man würde einfach ein Histogramm von EINTE erstellen und dann von jedem Wort und abgleichen ob mindestens so viele Buchstaben in dem Histogramm des Wortes vorkommen wie in dem von EINTE. `collections.Counter` ist da hilfreich.

[KlausP]

@ blackjack
1) Histogramm von z.B. EINTE verstehe ich nicht; will ja nicht wissen, wie oft "E" vorkommt

2) habe bei collections.counter hilfreiches gefunden; z.B. Berechnung von Permutationen.
danke.
z.B. output = [' '.join(permutation) for permutation in itertools.permutations(word_list)]

3) Meine word_list muss ich aber konstruieren: ABC, ABD, ABF ... ABCD, ABCE, ABDE .... dann 5-stellig, etc.
Da stelle ich mit vor, ich hätte z.B. die word_list ['A', 'B', 'C', 'D', 'E', 'F', 'G']
Wenn ich diese mit 1 1 1 , 1 1 1 0 , 1 1 1 1 , 1 1 1 0 0 1, 1 1 1 0 1 0, 1 1 1 0 1 1 bis zu 1 1 1 1 1 1 1 maskieren könnte, hatte ich alle Kombinationen zur Berechnung
der Permutationen

Habe aber keinen Ansatz gefunden, wie die word_list quasi maskieren könnte, um die 120 Teilworte zu erhalten

[__blackjack__]

@KlausP: Doch Du willst wissen wie oft E vorkommt. Denn wenn Du weisst wie oft jeder Buchstabe in EINTE vorkommt und wie oft jeder Buchstabe in einem Wort aus der Datei vorkommt, kannst Du mit der Information einfach testen ob das Wort aus den Buchstaben von EINTE gebildet werden kann. Ohne alle Worte bilden zu müssen die man aus EINTE bilden könnte.

[__blackjack__]

Da Du BASIC erwähntest, habe ich da mal was in BASIC programmiert. Als Vorbereitung habe ich ein kleines Lua-Programm geschrieben das von der Standardeingabe Zeilen liest, die in Grossbuchstaben wandelt, und dann prüft ob das Ergebnis 3 bis 7 ASCII-only-Buchstaben lang ist. Dabei werden Doubletten raus gefiltert. Dann werden die Worte sortiert und ausgegeben:

Code: Alles auswählen

#!/usr/bin/env lua5.3

local function main()
  seen = {}
  lines = {}
  for line in io.lines() do
    line = string.upper(line)
    if not seen[line]
       and #line >= 3
       and #line <= 7
       and string.match(line, "^[A-Z]+$")
    then
      seen[line] = true
      table.insert(lines, line)
    end
  end
  
  table.sort(lines)
  
  for _, line in ipairs(lines) do
    print(line)
  end
end

if arg and arg[-1] then main() end

Da habe ich dann zwei grosse Dateien die in ``/usr/share/dict/`` rumlagen mit englischen und deutschen Worten reingefüttert, und eine Datei mit 154.010 Worten heraus bekommen.

Und die Daten haben ich dann mit folgendem GW-BASIC-Programm verarbeitet:

Code: Alles auswählen

10 DIM H%(25),HW%(25)
20 W$="EINTE":WL%=LEN(W$):GOSUB 80:FOR I=0 TO 25:HW%(I)=H%(I):NEXT
30 OPEN "test.txt" FOR INPUT AS #1
40 WHILE NOT EOF(1):LINE INPUT #1,W$:IF LEN(W$)>WL% THEN 70
50 GOSUB 80:FOR I=0 TO 25:IF H%(I)>HW%(I) THEN 70
60 NEXT:PRINT W$,
70 WEND:CLOSE #1:PRINT:END
80 REM Calculate histogram of w$ in h%().
90 FOR I=0 TO 25:H%(I)=0:NEXT
100 FOR I=1 TO LEN(W$):J=ASC(MID$(W$,I,1))-ASC("A")
110 H%(J)=H%(J)+1:NEXT:RETURN

Das bildet für alle Worte das Histogramm und vergleicht dann ob das Histogramm jedes eingelesenen Wortes in das Histogramm von "EINTE" ”passt”. Falls ja, wird das eingelesene Wort ausgegeben.

Die Ausgabe sieht wie folgt aus:

Code: Alles auswählen

EEN           EIN           EINE          EINT          EINTE
EITEN         ENE           ENTE          ETEN          IENE
INT           ITEN          NEE           NEET          NEI
NET           NETE          NETI          NIE           NIET
NIETE         NIT           TEE           TEEN          TEN
TENE          TIE           TIEN          TIN           TINE

Ich wollte das erst für den C64 schreiben, aber da ist die Datei mit den Worten schon etwas gross für. Die passt nicht auf eine Diskette für das 1581-Laufwerk. Da müsste man schon ein etwas exotischeres Laufwerk wie das CMD FD2000 oder etwas moderneres wie SD-Karte oder Festplatte nehmen. Da das mit GW-BASIC aber schon eine kleine Ewigkeit gebraucht hat, so 10 bis 15 Minuten, wollte ich da den C64 nicht mit beauftragen.

[DasIch]

Da es noch nicht gesagt wurde und vielleicht nicht ganz klar ist: Listen in Python sind, trotz des Names, eigentlich Arrays oder was manche Sprachen als Vector bezeichnen würden. Es sind keine (Double) Linked Lists auch wenn der Name dies vielleicht suggeriert.

Numpy arrays machen eigentlich nur dann Sinn wenn, wie von BlackJack schon erwähnt, man numerische Daten hat und Rechenoperationen ausführen möchte. Das ist wofür die optimiert sind. Die sind nicht als generische Array Implementation gedacht.

[__blackjack__]

Wobei man da dann aber vielleicht doch noch mal sagen sollte das Listen keine Arrays sind, auch wenn die sehr wahrscheinlich (und bei CPython ganz sicher) als ”dynamische” Arrays implementiert sind.

Weil sonst Leute die von BASIC oder Pascal kommen gerne anfangen Listen mit Dummywerten zu erstellen und dann mit Schleifen und Indexwerten darauf operieren als wären es Arrays in BASIC oder Pascal. Und das macht man in der Regel in Python nicht, sondern nutzt den Umstand, dass Listen eine `append()`-Operation haben um die elementweise aufzubauen. Oder auch „list comprehensions“ falls sich das anbietet.

[KlausP]

@ blackjack
Danke; dein Hinweis auf die Histogramm-Funktion war schon cool und clever.
Mit dem Collections.Counter konnte ich die Buchstaben "verdichten":
Der Vergleich wurde dann aber tricky. Schließlich habe ich die Funktion isSublist (sub, main) gefunden.
Warum dort sets ins Spiel kommen, habe ich noch nicht verstanden:
Jedenfalls konnte ich mit der Funktion mein Problem lösen und effektiv effektiv vergleichen.
Die Basic-Version schaue ich mir mal gelegentlich an.
Zunächst will ich dem ganzen Zwischenmüll aufräumen und die Doku sauber halten.
Mal sehen, vllt. gehe ich in der nä. Woche die grafische Implementierung an.

Auch danke an den Kommentar @ DasIch bezgl. Listen und Arrays.
Ja, ich denke, Listen sind eher sequentiell; und dennoch teils indiziert ansprechbar. Das muss ich noch richtig verinnerlichen.

[__blackjack__]

@KlausP: In wiefern wurde der Vergleich bei den `Counter`-Objekten tricky? Die sind von `dict` abgeleitet. Man kann also einfach über die Buchstabe/Anzahl-Paare von einem iterieren und dann beim Anderen nachschauen ob die Anzahlen passen.

Zu den `set`\s in der unbekannten `isSublist()` kann ich nichts sagen, ausser das die ja nicht *zählen*. Da solltest Du also prüfen ob das tatsächlich das macht was Du willst, also tatsächlich die Anzahl(en) gleicher Buchstaben berücksichtigt, und nicht nur testet ob die Buchstaben an sich vorkommen, egal wie oft. Also beispielsweise ob "IMPS" laut dieser Funktion "MISSISSIPPI" ergeben können, auch wenn die vier Buchstaben "IMPS" natürlich nicht ausreichen und man mindestens "IIIIMPPSSSS" bräuchte. Es sei denn ich habe die Aufgabenstellung falsch verstanden‽

Das GW-BASIC-Programm läuft übrigens doch deutlich schneller. Ich hatte das nur so nebenher laufen lassen ohne die Zeit zu messen. Das habe ich mal nachgeholt, und es sind nur ca. 3½ Minuten. Das hat dann doch meinen Ehrgeiz angespornt das mal auf den C64 zu portieren.

Dazu muss die Wortliste-Datei kleiner werden, damit sie auf eine 3½"-Diskette passt (max. 800 KB). Und das Kompressionsschema muss möglichst einfach sein, damit man das effizient und ”on the fly” in BASIC dekodieren kann. Für sortierte Wortlisten bietet sich ein Verfahren an, bei dem nur der Suffix gespeichert wird, der sich vom vorhergehenden Wort unterscheidet. Für jeden Eintrag wird ein Byte gespeichert das die Länge (L) und den Versatz (V) des Suffix speichert, gefolgt von L Bytes für den Suffix. Länge und Versatz werden in einem Byte in den oberen und unteren vier Bits gespeichert. Damit kann beides die Werte 0 bis 15 annehmen, was bei Worten mit maximal 7 Zeichen locker ausreicht.

Hier ist das QBasic-Programm, das in ca. 2½ Minuten die Liste mit den 154.010 Worten komprimiert und auch gleich die Buchstabenwerte von den ASCII-Werten von "A" bis "Z" auf die Zahlwerte 0 bis 25 verschiebt, damit das nicht mehr im Suchprogramm passieren muss:

Code: Alles auswählen

' Simple compressing and preprocessing of the sorted word.txt file.

DIM inFile AS INTEGER, outFile AS INTEGER
DIM oldWord AS STRING, word AS STRING
DIM i AS INTEGER, j AS INTEGER

inFile = FREEFILE
OPEN "words.txt" FOR INPUT AS #inFile
outFile = FREEFILE
OPEN "words.dat" FOR OUTPUT AS #outFile

start = TIMER
oldWord = ""
DO WHILE NOT EOF(inFile)
  LINE INPUT #inFile, word
  i = 0
  DO WHILE i < LEN(oldWord) AND i < LEN(word) AND MID$(oldWord, i + 1, 1) = MID$(word, i + 1, 1)
    i = i + 1
  LOOP
  IF i = 0 THEN PRINT word,
  PRINT #outFile, CHR$((LEN(word) - i) * 16 + i);
  FOR j = i + 1 TO LEN(word)
    PRINT #outFile, CHR$(ASC(MID$(word, j, 1)) - ASC("A"));
  NEXT
  oldWord = word
LOOP
PRINT
PRINT TIMER - start; "s"

CLOSE #outFile
CLOSE #inFile

Schauen wir uns mal die ersten vier Einträge in der Textdatei und in der komprimierten Datei an. Textdatei:

Code: Alles auswählen

AAA
AABERG
AACHEN
AACHENS

Das sind für jeden Buchstaben ein Byte + zwei Bytes pro Wort für das Zeilenende = 30 Bytes.

Und so sieht das in der komprimierten Datei aus:

Code: Alles auswählen

    Bytes: 30 00 00 00  42 01 04 11 06  42 02 07 04 0D  16 12
Bedeutung: LV  A  A  A  LV  B  E  R  G  LV  C  H  E  N  LV  S
     Wort: AAA          AABERG          AACHEN          AACHENS

Der erste Eintrag hat die Länge L=3 und den Versatz V=0 gefolgt von drei 0en, die für die drei "A" stehen. Der zweite Eintrag hat die Länge 4 für "BERG" und den Versatz 2 weil die beiden führenden "A" von "AAA" gleich bleiben. Dann wird auf die gleiche Weise "BERG" durch "CHEN" ersetzt um "AACHEN" zu bekommen. Beim letzten Eintrag im Beispiel können die ersten 6 Zeiche ("AACHEN") so bleiben und es wird nur 1 Zeichen, das "S" gespeichert. So sind von den ursprünglichen 30 Bytes nur noch 16 Bytes übrig geblieben.

Insgesamt wird so die 1.245.097 Bytes grosse Textdatei auf 413.758 Bytes, also auf etwas mehr als 33% geschrumpft. Und passt jetzt auf die Diskette.

Zur Gegenprobe als Test ob man daraus wieder die Originaldatei erstellen kann, dient dieses kleine Pascal-Programm, das die komprimierte Datei liest und die unkomprimierten Worte ausgibt:

Code: Alles auswählen

program Unpack;

var
  F: File of Byte;
  b, length, offset, i: Byte;
  S: String[7];

begin
  Assign(F, 'words.dat');
  Reset(F);
  while not Eof(F) do
  begin
    Read(F, b);
    length := b shr 4;
    offset := b and 15;
    S[0] := Chr(length + offset);
    for i := 1 to length do
    begin
      Read(F, b);
      S[i + offset] := Chr(b + Ord('A'));
    end;
    WriteLn(S);
  end;
end.

In eine Datei umgeleitet und mit der Originaldatei verglichen:

Code: Alles auswählen

D:\FORUM\WORDS>unpack > check.txt
D:\FORUM\WORDS>comp words.txt check.txt
Files compare OK.

Und jetzt endlich das Suchprogramm von GW-BASIC auf CBM BASIC V2 portiert und an das komprimierte Dateiformat angepasst:

Code: Alles auswählen

    1 REM@ £PROTOCOL:£FASTFOR:£SHORTIF:£FASTARRAY
    2 REM@ £BYTE H(,HW(,W(,IL,WL=FAST,I=FAST,J,B,O=FAST,L=FAST
   10 TI$="000000":DIM H(25),HW(25),W(7):W$="EINTE":IL=LEN(W$):WL=IL
   20 FOR I=1 TO WL:W(I)=ASC(MID$(W$,I,1))-ASC("A"):NEXT
   30 GOSUB 500:FOR I=0 TO 25:HW(I)=H(I):NEXT
   40 OPEN 2,9,2,"WORDS.DAT,S,R"
   50 GET #2,C$:IF ST<>0 THEN 400
   60 B=ASC(C$):L=INT(B/16):O=B AND 15:WL=L+O
   70 FOR I=1 TO L:GET #2,C$:IF LEN(C$)=0 THEN C$=CHR$(0)
   80 W(I+O)=ASC(C$):NEXT
   90 IF WL>IL THEN 50
  100 GOSUB 500:FOR I=0 TO 25:IF H(I)>HW(I) THEN 50
  110 NEXT:FOR I=1 TO WL:PRINT CHR$(W(I)+ASC("A"));:NEXT:PRINT " ";:GOTO 50
  400 CLOSE 2:PRINT:PRINT TI$:END
  500 REM CALCULATE HISTOGRAM OF WL & W IN H().
  510 FOR I=0 TO 25:H(I)=0:NEXT:FOR I=1 TO WL:J=W(I):H(J)=H(J)+1:NEXT:RETURN

Mit dem Basic-Boss-Compiler übersetzt, läuft das Programm in nur 19¼ Minuten durch.