Laden...

Highspeed Algorithmus zur Namenserstellung aus 2 Listen

Erstellt von UltraEdit vor 9 Jahren Letzter Beitrag vor 9 Jahren 3.645 Views
U
UltraEdit Themenstarter:in
57 Beiträge seit 2013
vor 9 Jahren
Highspeed Algorithmus zur Namenserstellung aus 2 Listen

Hallo Zusammen...

z.Z. bastel ich an einem Algorithmus zur Erzeugung von "MenschenNamen" 😁

Es ist gegeben:


 string[] NachName;  // 3422 übliche Nachnamen(keine Doubletten)..aus Datei geladen...
 string[] VorName;  // 522 übliche Vornamen(keine Doubletten)..aus Datei geladen...

Das sind (3422*522) == ca. 1,9 mio. Namen(ohne Doubletten)...
Ich erzeuge bis zu 10.000 Namen in "zumutbarer Zeit" mit:


 do {
  vName = tmpVN.Name[globals.rnd.Next(0, tmpVN.Name.GetLength(0))];
  nName = tmpNN.Name[globals.rnd.Next(0, tmpNN.Name.GetLength(0))];
  }
  while (Züchter.Exists(x => x.GetFullName() == vName + " " + nName));
  Züchter.Add(new Züchter(vereinsNr, vName, nName));

klar, das "randomReingreifen" in die Arrays wird immer schlechter, je mehr Namen es werden...
Ich will aber auch nicht die Listen von "oben" nach "unten" "abklappern"
(Nachname 1 bis n + Vorname 1 bis n) (das geht schnell, aber ist mir nicht "zufällig" genug)...

Hat jemand ne Idee wie das (besser) schnell und zufällig geht?

Der Wettbewerb ist ausgerufen 😁
Vielen Dank im Voraus für die Anregungen... 8)

1.346 Beiträge seit 2008
vor 9 Jahren

Hallo UltraEdit,
Bring beide arrays in eine zufällige Reihenfolge (in O(n) möglich). dann kannst du 1 zu 1 zuordnen. kannst das also in O(n) machen.

Ist es das was du meinst?

LG pdelvo

4.931 Beiträge seit 2008
vor 9 Jahren

@pdelvo: dann würden aber keine mehrfachen Vor- bzw Nachnamen mehr generiert (und das wären dann ja keine zufälligen Namen mehr).

@UltraEdit: solange die jeweiligen Vor- bzw. Nachnamen mit gleicher Wahrscheinlichkeit benutzt werden sollen, ist das Auswählen so in Ordnung.
Inperformant ist aber deine Bedingung, da du unnötige temp. Strings erzeugst. Prüfe daher auf


while (Züchter.Exists(x => x.Vorname == vName && x.Nachname == nName));

Was für ein Datentyp ist denn "Züchter" (bei "Züchter.Add()")? [du hast zweimal "Züchter" angegeben, als Variable und als Datentyp]
Eine Liste? Noch schneller wird es sein, wenn du die erzeugten Namen (Züchter) in ein Dictionary oder HashSet packst.

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo pdelvo,

auf die Art bekommt man aber jeden Nachnamen und jeden Vornamen der überhaupt gewählt wird, nur ein mal. Außerdem ist so nach 522 oder spätestens 3422 Namen Schluss. Anscheinend will UltraEdit aber mehr Namen erzeugen.

Hallo UltraEdit,

mach die Duplikatprüfung bzw. -elmimierung der zusammengesetzten Namen mit einem HashSet, indem du sie mit Add hinzufügst. Das wird vermutlich gut funktionieren bis grob geschätzte [EDIT]50 bis 80(*)[/EDIT] Prozent der möglichen Namen erzeugt sind. Vielleicht geht es auch noch etwas länger gut. Aber nah an 100% wird man so nicht kommen und schon gar nicht bis genau 100%.

Wenn du (fast) alle Namen erzeugen willst, aber in zufälliger Reihenfolge, dann erzeuge sie erst systematisch mit zwei geschachtelten Schleifen und bring die Liste erst danach in eine zufällige Reihenfolge, am besten mit der Shuffle-Methode aus [Snippet] Zufallszahlen, die sich nicht wiederholen.

herbivore

PS: (*) Bei 50 Prozent sind am Ende pro Namen im Schnitt zwei Versuche nötig, bis ein noch nicht vorhandener Name gewürfelt wurde. Bei 80 Prozent sind es schon fünf Versuche, bei 90 Prozent zehn, bei 95 Prozent 20, bei 99 Prozent 100. Bei 10 Prozent führt dagegen nur jeder zehnte Versuch zu einem Duplikat. Bis dahin besteht also so gut wie keine Bremswirkung. Ab 50% ist die Bremswirkung mehr als Theorie, selbst wenn sie praktisch gesehen vielleicht noch nicht spürbar ist. Trotzdem sehe ich ungefähr bei 50% die Grenze, wo ich auf die Shuffle-Variante umsteigen würde.

C
2.121 Beiträge seit 2010
vor 9 Jahren

Was ist tempVN? Nimm hier die Länge des Arrays VorName (analog Nachname), dann sparst du dir schon einen Funktionsaufruf.
Ob ein Name bereits verwendet ist könntest du durch einen Hash prüfen. Dazu am besten nicht den Namen verwenden denn dazu wird wieder aufwendig der gane String durchlaufen, sondern nimm die verwendeten Indizes.
Beispiel: du verwendest Vorname 5 und Nachname 7. Jetzt bilde eine Zahl z.B. 1000000 * 5 + 7 und merke die in einer Hashliste. Da kannst du dann schnell prüfen ob das bereits vergeben ist.
Ist noch nicht optimal aber auf jeden Fall schneller als bisher.
Noch schneller wäre ein festes Array bool[] für alle Kombinationen anzulegen, in deinem Fall mit den genannten 1,9 Mio. Feldern.

Die (zumidest fast) perfekte Lösung wäre wenn du erst mal alle Paare aus allen Vorname und Nachname Indizes bildest und dir merkst. Daraus suchst du dann zufällig einmalige Einträge, die du anschließend nicht mehr verwendest.

Den Titel von herbivores Link wollte ich gerade noch versuchen zu finden, dürfte sich damit erledigt haben 😃

U
UltraEdit Themenstarter:in
57 Beiträge seit 2013
vor 9 Jahren

Hallo Zusammen...

...und vielen Dank für Eure Anregungen!

Habe nun folgendes gebaut:


string[] NachName;	// 3422 übliche Nachnamen(keine Doubletten)..aus Datei geladen...
string[] VorName;		// 522 übliche Vornamen(keine Doubletten)..aus Datei geladen...

// ein 2D Prüffeld (Vorname(x) * Nachname(y))
Boolean[,] bCheckFeld = new Boolean[VorName.Length, NachName.Length];

// Dummys für die Pos im bCheckFeld[x,y]
int x = 0; int y = 0;

// Hier gehts los...Loop über die 10.000 Züchter...
	
	// Suche eine freie Pos im Feld...
	do
	{
			x = rnd.Next(0, VorName.Length);
			y = rnd.Next(0, NachName.Length);
	}
	while (bCheckFeld[x, y]);
	
	// Wenn Treffer, dann Feld belegen...
	// und einfach in die 2 Listen greifen mit den x,y Werten...
	bCheckFeld[x, y] = true;
	Züchter.Add(new Züchter(vereinsNr, VorName[x], NachName[y]));
	
// ENDE Loop über die 10.000 Züchter...

Läuft rasend schnell, besonders wegen der gesparten LingQ Function, denk ich...

Nochmal Vielen Dank und bis zum nächsten Problem 😁
Lieben Gruß...
UltraEdit

PS: Nachtrag:
Wie herbivore schon richtig geschätzt hat... Ab 1 Mio. Züchter, also so ca. 50% Füllstand, wird's übel(Laufzeit ca. 3 min.).

Also wenn man ans MAX ran will müsste man wohl doch Richtung 2 geschachtelte Schleifen die ALLE Kombinationen erzeugen, die Liste mischen und dann von Oben nach Unten reingreifen.

1.361 Beiträge seit 2007
vor 9 Jahren

Hey UltraEdit,

eine wunderschöne Aufgabe wie ich finde 😃.

Du suchst ja eine zufällige Permutation des Kreuzprodukts aus Vornahmen und Nachnamen. Ich würde zunächst jedem möglichen Voll-Namen eine eineindeutige Nummer zuordnen.

Bei K Vornahmen und L Nachnahmen sind das K*L Zahlen. Wenn du nun eine solche Zahl "index" hast, kannst du daraus leicht den Namen ableiten:


vorname = vornahmen[index % K];
nachname = nachnamen[index / K];

Jetzt sind wir also nur noch an einer Permutation der ersten N:=K*L natürlichen Zahlen interessiert.

1) Random Picking mit Lookup
So wie du es bereits umgesetzt hast, generierst du eine zufällige Zahl aus [0,N] und holst dir den passenden Namen dazu. Damit du nicht mehrfach den selben Namen erwischst, speicherst du dir die bereits gezogenen in einer Tabelle und wählst bei einer Kollision einfach neu.
Entweder speicherst du diese Tabelle "sparse" als HashTable<int> oder "dense" als bool[N].
(Auch hier zahlt sich die Verwendung der Nummer-Indizes statt der Vollnamen aus, da das Hashen der Strings auch wieder Zeit kostet.)
Allerdings benötigst du entsprechend viel Speicherplatz, mindestens so viel wie du Elemente generieren möchtest.

Die Wahrscheinlichkeit für eine Namenskollision ergibt sich aus dem Geburtstags-Paradoxon und ist in der Größenordnung von sqrt(N) generierten Namen gehäuft zu erwarten.

Je mehr Namen du generieren möchtest, desto häufiger sind Kollisionen und desto öfter musst du nach einer neuen Zahl suchen. Die Laufzeit ist also insbesondere nicht linear.

2) Complete Permutation
Aufbauend auf herbivores Vorschlag kannst du einfach ein Array aller Namen (oder besser: NamenIndizes) vorher aufbauen, dann einmal permutieren und dann einfach von vorne weg die Namen nehmen.
Für das Permutieren bietet sich der Fisher-Yates Algorithmus an. Dort kannst du sogar rechtzeitig aufhören, wenn du genügend Namen hast. Das gesamte Array must du aber dennoch aufbauen, was relativ viel Speicherplatz benötigt. (bei dir jedoch nur 7MB)

Bei angemessenen Mengen an Namen würde ich persönlich diesen Weg gehen.

3) Iterative Permutation
Aber nun zum "theoretisch" wie ich finde schönsten Ansatz 😃
Du hast das Problem, dass du nur einen PseudoRandomNumberGenerator (PNRG) zur Verfügung hast, aber an einer PseudoRandomPermutation (PRP) interessiert bist.

Nun gibt es glücklicherweise das Luby-Rackoff-Theorem, dass besagt, dass ein Feistel-Netzwerk mit mindestens 4 Ebenen dazu genutzt werden kann, um aus einer beliebigen Klasse an PseudoRandomFunctions (PRF) eine PseudoRandomPermutation (PRP) zu generieren.

Anders ausgedrückt: Die Grundlage für die Konstruktion von Block-Verschlüsselungen.

Eine Block-Verschlüsselung ist nichts anderes als eine pseudo-zufällige Permutation von Bit-Blöcken.
Betrachten wir einfach mal die 128-Bit AES Verschlüsselung mit einem festen Schlüssel. Wenn ich damit einen 128-Bit Block "verschlüssle", wird im Grunde nur der Block auf einen anderen Block abgebildet (permutiert). Hierbei dürfen natürlich keine Kollisionen auftreten, sonst kann ich ja nicht mehr eindeutig entschlüsseln. Daher handelt es sich um eine Permutation aller denkbaren 128-Bit Blöcke. Zudem ist sie pseudozufällig, da sie für einen Angreifer zufällig aussieht, er also ohne den Schlüssel nicht einfach zurückrechnen kann.

Und die Technik hierfür liefern Feistel-Netzwerke. Diese ermöglichen die Konstruktion solcher Block-Chiffren (beispielsweise für DES).

Wenn wir nun eine Block-Chiffre für den Zahlenbereich [0, N] konstruieren können, können wir einfach einen Zähler (0, 1, 2, 3, ...) Stück für Stück verschlüsseln und erhalten eine zufällige - garantiert kollisionsfreie - Zahlenfolge aus [0,N].

Allerdings arbeiten Feistel-Chiffren bit-basiert, also nur auf "ganzen" Bit-Blöcken.
Wir können also nicht direkt den Bereich [0, N] verschlüsseln, sondern nur den nächst größeren ganzen Bitblock [0, 2^n].

Konkrete Idee:
Bei deinen N = (3422*522) ist die nächst größere Zweierpotenz (2^21). Also konstruieren wir uns eine 21-Bit-Verschlüsselung. Dann generieren wir einen zufälligen "Schlüssel" (der Seed für deine zufällige Permutation). Und anschließend verschlüsseln wir nacheinander die Zahlen 0, 1, 2, 3, 4, ...

Falls wir dabei auf eine Zahl größer als N stoßen, verwerfen wir diese einfach und machen mit der nächsten weiter. Da wir aber die Blockgröße möglichst passend gewählt haben, gibt es kein überflüssiges Bit und es ist garantiert, dass du höchstens doppelt so viele Zahlen generieren musst. Also immer noch eine garantiert lineare Laufzeit.

Der Feistel-Cypher braucht intern nun aber etwas mehr als einen Zufallszahlengenerator. Er braucht eine Zufallszahlenfunktion. Das ist aber im Grunde einfach eine Hash-Funktion, deren Ausgabe ja auch als "zufällig" angesehen wird. Ich habe dafür einfach mal MD5 verwendet.
Du kannst aber auch einen normalen Verschlüsselungsalgorithmus hier einbetten. Halt irgendetwas, was eine Zahl X zufällig auf eine andere Zahl Y abbildet.

Gerade wegen dem eingebauten MD5 ist das ganze jedoch etwas langsam.
Man kann es aber bedenkenlos durch eine "effizientere" Hash-Methode ersetzen.

Vorteil ist die garantiert lineare Laufzeit und der konstante Speicheraufwand.

using System;
using System.IO;
using System.Security.Cryptography;
using System.Linq;
using System.Collections.Generic;

class Mainy
{
    public static void Main(string[] args)
    {
        string[] forenames = {"Adam", "Bernd", "Charlie", "David"};
        string[] surnames = {"Repke", "Schubert", "Trem"};

        // Calculate 5 random combinations
        var names = CombineNames(forenames, surnames).Take(5);

        foreach(string name in names)
            Console.WriteLine("Hello {0}", name);

    }   

    public static IEnumerable<string> CombineNames(string[] first, string[] second)
    {
        int total = first.Length * second.Length;

        var permutator = new Permutator(total);
        for (int i=0; i<total; i++)
        {
            // Generate random index for First-Second-Pair
            int code = permutator.Next();
            int firstIndex = code / second.Length;
            int secondIndex = code % second.Length;

            // Return compound name
            yield return String.Format("{0} {1}", first[firstIndex], second[secondIndex]);
        }
    }

}

class Permutator
{
    private int N;
    private int HalfBits;
    private int Counter;
    private int BitMask;
    private Func<int, int>[] PseudoRandomFunctions;
    private Random Seeder;

    public Permutator(int n) : this(n, (int)DateTime.Now.Ticks) { }

    public Permutator(int n, int seed)
    {

        this.N = n;
        int bits = (int)Math.Ceiling(Math.Log(n, 2));

        // round up to an even number of bits
        if (bits % 2 != 0)
            bits += 1;

        this.HalfBits = (bits / 2);
        this.BitMask = (1 << this.HalfBits) - 1;

        // init Random Generator for round keys   
        this.Seeder = new Random(seed);

        // initialize Pseudo Random Function for all rounds
        this.InitPseudoRandomFunctions(4);

        // reset Counter
        this.Counter = 0;
    }

    // Creates a PseudoRandomFunction (PRF).
    // PRFs should be injective into {2^HalfBits}
    // (Can be truncated hashes like MD5, SHA1 or symmetric encryptions like DES or AES)
    private Func<int, int> createPseudoRandomFunction(int roundKey)
    {
        MD5 md5Hash = MD5.Create();
        byte[] keyBytes = BitConverter.GetBytes(roundKey);
        byte[] md5Input = new byte[sizeof(int) * 2];
        System.Buffer.BlockCopy(keyBytes, 0, md5Input, 0, sizeof(int));

        return (int x) => {
            byte[] inputBytes = BitConverter.GetBytes(x);
            System.Buffer.BlockCopy(inputBytes, 0, md5Input, sizeof(int), sizeof(int));
            byte[] hash = md5Hash.ComputeHash(md5Input);
            return BitConverter.ToInt32(hash, 0) & this.BitMask;
        };
    }

    // Create a set of PRFs, one for each round with distinct, random round keys 
    private void InitPseudoRandomFunctions(int rounds)
    {

        this.PseudoRandomFunctions = Enumerable.Range(0, 4)
                                        .Select(i => this.Seeder.Next())
                                        .Select(this.createPseudoRandomFunction)
                                        .ToArray();
    }

    // Encrypts a given Number using a Feistel Cipher and the PFRs for each round.
    // (Bijectively maps {N} -> {N})
    private int Encrypt(int x)
    {
        int right = x & this.BitMask;
        int left = (x >> this.HalfBits) & this.BitMask;

        foreach(var pfr in this.PseudoRandomFunctions)
        {
            int temp = left;
            left = right ^ pfr(left);
            right = temp;
        }

        return (left << this.HalfBits) | right;
    }

    // Returns the encrypted Counter
    public int Next()
    {
        // We can only encrypt Domains of power 2.
        // Thus we reject all values bigger than N and move on with the next Counter.
        int result;
        do
        {
            result = this.Encrypt(this.Counter++);
        }
        while(result >= this.N);

        return result;
    }
}

Eine andere Minimal-Implementierung findet man als Gist: Feistel Hash

beste Grüße
zommi

PS: Die selben Techniken finden beim Format-preserving encryption statt. Beispielsweise gibt es auch einen standardisierten 'FFX-mode' für AES, ein standardisiertes Feistel-Netzwerk, welches intern AES nutzt und im Grunde wie obiger Code arbeitet. Warum ist das eigentlich noch nicht im .NET Framework?

U
UltraEdit Themenstarter:in
57 Beiträge seit 2013
vor 9 Jahren

Hallo zommi..

bis:

Hey UltraEdit,

konnte ich folgen 😁

Nein, Spaß beiseite... 8)

Vielen Dank für son umfassenden Post.
Da sind Unmengen an super Interessanten Begriffen drin, die ich alle noch erforschen/"erGooglen" werde(n will).

*Lesen geht*
...danke und Gruß 👍

1.361 Beiträge seit 2007
vor 9 Jahren

Hey,

ich habe mal an der Geschwindigkeit etwas geschraubt. MD5 ist nun rausgeflogen und stattdessen eine eigene, ziemlich obskure 32-Bit Hashfunktion reingekommen. Da diese sicherlich nicht so gute Eigenschaften wie MD5 aufweist, habe ich im Gegenzug die Rundenzahl auf 10 erhöht.

Nachfolgend das Snippet. Sie fühlt sich ein Bisschen an wie die Random Klasse (mit der Next()-Methode), bietet aber überdies noch eine komfortable Shuffle-Methode, die einem eine Abfolge von kollisionsfreien Pseudozufallszahlen im Intervall [0,N) zurückgibt.

class Shuffler
{
    uint N;
    int HalfBits;
    uint Counter;
    uint BitMask;
    uint[] Keys;
    const int ROUNDS = 10;

    public Shuffler(uint n) : this(n, (int)DateTime.Now.Ticks) { }

    public Shuffler(uint n, int seed)
    {
        N = n;
        Counter = 0;

        int bits = (int) Math.Ceiling(Math.Log(n, 2));
        HalfBits = (bits + 1) / 2;
        Console.WriteLine("HalfBits: {0}", HalfBits);
        BitMask = (1u << HalfBits) - 1u;

        var seeder = new Random(seed);
        Keys = Enumerable.Range(0, ROUNDS)
                        .Select(i => (uint)seeder.Next())
                        .ToArray();
    }

    uint Encrypt(uint x)
    {
        uint right = (x & BitMask);
        uint left = ((x >> HalfBits) & BitMask);
        for(int i=0; i<ROUNDS; i++)
        {
            uint temp = right;
            uint hash = ((right * 13u + Keys[i]) * 63845467u + 2345u) % 38444179u; 
            hash &= BitMask;
            right = left ^ hash;
            left = temp;
        }
        return (left << HalfBits) | right;
    }

    public uint Next()
    {
        if (Counter >= N)
            throw new InvalidOperationException("Cannot provide more than N distinct values");
        uint x = Counter++;
        do
        {
            x = Encrypt(x);
        } while (x >= N);
        return x;
    }

    public static IEnumerable<uint> Shuffle(uint n)
    {
        return Shuffle(n, (int)DateTime.Now.Ticks);
    }

    public static IEnumerable<uint> Shuffle(uint n, int seed)
    {
        var p = new Shuffler(n, seed);
        for(uint i=0; i<n; i++)
            yield return p.Next();
    }
}

Ich habe die Laufzeit mal gegen einen Fisher-Yates-Shuffle getestet um komme auf vergleichbare Laufzeiten - bei einem Speicherbedarf von O(1).

beste Grüße
zommi

PS: Obiges Snippet liefert auch wie ich finde ausgesprochen gut gleichverteilte Permutationen. Man muss auch bedenken, dass es schon ab 13 Elementen mehr Permutationen als Zufallszahlgeneratoren gibt, da 13! bereits die Zahl möglicher 32-Bit Seeds übersteigt.

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo zommi,

wie immer ein sehr fundierter Beitrag. Daher auch nur zwei kleine Anmeldungen:

  1. Complete Permutation. Aufbauend auf herbivores Vorschlag kannst du einfach ein Array aller Namen (oder besser: NamenIndizes) vorher aufbauen, dann einmal permutieren und dann einfach von vorne weg die Namen nehmen.
    Für das Permutieren bietet sich der Fisher-Yates Algorithmus an.

Bis auf die Verwendung von Indizes statt der Namen ist das genau mein Vorschlag. Auch die von mir verlinkte Shuffe-Methode ist eine (effizientere) Variante des (originalen) Fisher-Yates Algorithmus (Fisher–Yates shuffle). Man kann die also direkt verwenden und muss nicht selbst den Fisher-Yates Algorithmus implementieren.

  1. Iterative Permutation [...] Vorteil ist die garantiert lineare Laufzeit und der konstante Speicheraufwand.

Interessant, jedoch alles andere als KISS. Auch finde ich dass sich die guten Klassen für Laufzeit und Speicherplatz von 3) etwas relativieren, wenn man bedenkt, dass auch 2) eine lineare Laufzeit hat und, zumindest wenn man viele oder alle zusammengesetzten Namen haben möchte, der Aufwand für die Speicherung der Ergebnisse auch bei 3) linear (und nicht konstant) und damit auch nicht niedriger als bei 2) ist. Da 2) zudem KISS ist, würde ich, wenn ich mich zwischen 2) und 3) entscheiden müsste, immer 2) wählen. Auch wenn 3) theoretisch sehr interessant ist. Ich denke, so war es auch von dir gemeint.

herbivore